Wyniki 1-2 spośród 2 dla zapytania: authorDesc:"Łukasz Golly"

Generacja cykli fundamentalnych metodą dynamicznego budowania drzewa grafu

Czytaj za darmo! »

Wyszukiwanie minimalnych cykli fundamentalnych jest mocno związane z analizą układów elektronicznych i elektrycznych [8], jak również z ich testowaniem [6]. Podstawowym problemem przy wyznaczaniu takich cykli jest określenie odpowiedniego drzewa grafu. Zgodnie z zależnością Cayleya ilość możliwych drzew w grafie o k węzłach osi k k-2. Przeanalizowanie wszystkich możliwych drzew, a następnie sprawdzenie, który zbiór cykli fundamentalnych zawiera najmniejszą liczbę gałęzi przy grafach o dużej liczbie gałęzi, mogłoby trwać bardzo długo, a w niektórych przypadkach stać się nie możliwe. W literaturze znane są podejścia, w których wyszukuje się optymalne drzewo grafu poprzez zastosowanie algorytmów DFS(deep-first search) [1], BFS (breadth-first search) [3], and MS (mixed search) [2]. Interesująca modyfikacją algorytmu BFS z heurystycznym wyborem kolejnego wierzchołka została przedstawiona w [4]. Kolejne ciekawe podejście polegające na zamianie gałęzi drzewa z gałęziami łączącymi przedstawiono w [7]. Prezentowany algorytm nie opiera się na znajdowaniu optymalnego drzewa grafu a na dopasowaniu struktury drzewa do zestawu najmniejszych cykli. Proponowany algorytm Niech G = (V, E) będzie grafem nieskierowanym zawierającym n gałęzi i k węzłów. Definiujemy drzewo grafu jako podgraf T grafu G, który jest acyklicznym grafem zawierającym k-1 gałęzi zwanych gałęziami drzewa. Dołożenie dowolnej gałęzi ze zbioru G\T (gałęzie łączące) spowoduje, że pod-graf T będzie zawierał dokładnie jeden cykl. Cyklem fundamentalnym nazywamy zbiór cykli zawierających dokładnie jedną gałąź łączącą i dowolną liczbę gałęzi drzewa. Liczba cykli fundamentalnych wynosi n-k+1. Zdefiniowano także dwa dodatkowe pojęcia gałęzie charakterystyczne i gałęzie nadmiarowe. Gałęzie charakterystyczne to zbiór gałęzi unikalnych dla danego cyklu (nie występują w żadnym innym cyklu). Gałęzie nadmiarowe to zbiór gałęzi określonych jako różnica pomiędzy sumą gałęzi w wyznaczon[...]

Timing analysis of multitask systems in SystemC environment


  Hardware Description Languages (HDLs) have been developed for several years in the field of electronic design automation and tools based on them gave new abilities to designers. However today, when the complexity of design problems grows exponentially every year, these tools seem to be not sufficient. Now engineers needs tools working on higher levels of abstraction allowing modeling of the entire system i.e. without initial, manual partitioning it into the hardware and software [1]. The terms of system level design, codesign and co-simulation have been well recognized and defined for several years now [2] and new tools: SystemC [3, 4] and SystemVerilog [5, 6] have appeared since the beginning of the 21st century. The approach presented within the paper is based on SystemC language, a tool that combines HDL with programming language and supports many new techniques of communication modeling. SystemC has been proposed by OSCI group [4] as a natural extension of the object-oriented programming language C++ supporting the system level specification language demands [1]. SystemC combines two design domains: hardware and software within a single environment. It defines many communication and synchronization issues (timers, mutexes, semaphores, FIFOs) that are very useful in system level modeling. SystemC introduces also abstract term: the model of computation (MoC) [11], which means that each module can have various (different) implementations within the model. The working group of the SystemC - WG OSCI [1] unified the modeling methodology and suggested transaction level modeling technique (TLM). This modeling philosophy (TLM) has been introduced by Cai and Gajski [7] and it divides the entire design process into small tasks. The term “transaction" within the embedded electronic system is defined as: “the exchange of data or an event between two components of a modeled and simulated system". Moreover, because the detai[...]

 Strona 1