Dekompozycja skończonych automatów stanów

• Autorzy: Bukowiec A.
• Języki publikacji: PL

Abstrakty

PL

Celem tego artykułu było przedstawienie i omówienie algorytmu partycjonowania skonczonych automatów stanów i narzedzia CAD, które go implementuje. Algorytm został zilustrowany w pełni działajacym przykładem. W dalszych pracach należałoby się skupić nad opracowaniem algorytmów umożliwiających automatyczne uzyskanie zbioru podziału. W tym celu należy jednak przetworzyć dodatkowe informacje takie, jak wymagany czas wykonania, czy prawdopodobieństwo wystąpienia przejścia. Implementacja takiego algorytmu może być bardzo złożona i należy rozważyc zastosowanie algorytmów genetycznych lub systemu wnioskujacego do tego celu.

EN

Popular way for realization of control units are finite state machines. Up-to-date control unit circuits very often are implemented using PLDs. Microprocessors can be also considered as a solution taking costs into account. But very often microprocessors are too slow for realization control units of digital systems. The partitioning of state machines can be a solution for this problem allowing a parallel execution of state machines, keeping performance and cost at adequate levels. In this case, the time critical part of the control unit can be implemented in fast FPGA device and other parts can be realized by cheaper platforms. The problems and algorithms of partitioning of state machines are discussed in this paper. A CAD tool for partitioning implementing the proposed algorithm is also presented.

Słowa kluczowe

PL

sterowanie; automat stanu skończonego; FPGA; KISS2; partycjonowanie

EN

control unit; finite state machine; FPGA; KISS2; partitioning

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2010
• Tom: nr 2 (23)
• Strony: 5--13
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Bukowiec A.

• Uniwersytet Zielonogórski, Wydział Elektrotechniki, Informatyki i Telekomunikacji, Instytut Informatyki i Elektroniki

Bibliografia

• [1] Baranov S. I., Logic Synthesis for Control Automat. Boston: Kluwer, 1994
• [2] Barkalov A., Titarenko L., Logic Synthesis for FSM-based Control Units. Berlin: Springer-Verlag, 2009
• [3] Bukowiec A., Gomes L., DivideFSM [online] http://www.uninova.pt/gres/DivideFSM/ [dostęp: 2010]
• [4] Bukowiec A., Gomes L., Partitioning of mealy finite state machines, 4th IFAC Workshop Discrete-Event System Design DESDes'09, Gandia Beach, Hiszpania, 2009, ss. 21-26
• [5] Bukowiec A., Synthesis of Finite State Machines for FPGA Devices Based on Architecturel Decomposition. Zielona Góra: University of Zielona Góra Press, 2009
• [6] De Micheli G., Synthesis and Optimization of Digital Circuits. New York: McGraw-Hill, 1994
• [7] Gomes L., Costa A., From use cases to system implementation: Statechart based codesign, Proc. 1st ACM & IEEE Conf. Formal Methods and Programming Models for Codesign MEMOCODE'03, Mt St-Michel, Francja, 2003, s. 24-33
• [8] Jantsch A., Modeling Embedded Systems and SoC's: Concurrency and Time in Models of Computation. San Francisco: Morgan Kaufmann, 2003
• [9] Jóźwiak L., General decomposition and its use in digital circuit synthesis, VLSI Design, vol. 3, 1995, s. 225-248
• [10] Łuba T., Synteza układów logicznych. Warszawa: Oficyna Wydawnicza Politechniki Warszawskiej, 2005
• [11] Yang S., Logic Synthesis and Optimization Benchmarks User Guide. v.3.0, Raport techniczny, North Carolina: Microelectronics Center of North Carolina, 1991