Dekompozycja funkcji logicznych metodą rozwojowego programowania genetycznego

• Autorzy: Deniziak S. , Wieczorek K.

Warianty tytułu

EN

Functional decomposition of logical functions using developmental genetic programming

• Języki publikacji: PL

Abstrakty

PL

Praca przedstawia metodę wyszukiwania strategii dekompozycji funkcji logicznych za pomocą rozwojowego programowania genetycznego. Strategia dekompozycji jest reprezentowana w formie drzewa decyzyjnego, w którym węzły określają jeden krok dekompozycji. Drzewo podlega ewolucji, której celem jest uzyskanie jak najlepszego rozwiązania. Otrzymane wyniki wykonanych eksperymentów wskazują na wysoką skuteczność przedstawionej metody w porównaniu z dotychczas stosowanym podejściem deterministycznym.

EN

Functional decomposition splits logical function into two simpler functions. For complex functions the decomposition should be repeated iteratively for the result functions. It was observed that types of decomposition applied during each step have strong influence on the final result. Thus, a proper decomposition strategy should be used to find optimal FPGA implementation for a given function. This paper presents the method for searching the decomposition strategy for logical functions specified by cubes. The strategy is represented using the decision diagram, in which each node corresponds to a single decomposition step. In this way the multistage decomposition of a complex logical function can be specified. The diagram is evolved using the developmental genetic programming. In opposite to classical genetic methods, in our approach the methods producing solutions, instead of the solutions, are evolved. The goal of the evolution is to find the decomposition strategy for which the cost of FPGA implementation of a given function is minimal. The experimental results show that our approach gives significantly better solutions than other known methods.

Słowa kluczowe

PL

dekompozycja funkcji logicznych; rozwojowe programowanie genetyczne; układy FPGA

EN

functional decomposition; developmental genetic programming; FPGA devices

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 12
• Strony: 1430--1432
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wzor

Twórcy

autor

Deniziak S.

autor

Wieczorek K.

• Politechnika Świętokrzyska, atedra Informatyki, Al. 1000-lecia Państwa Polskiego 7, 25-314 Kielce,

Bibliografia

• [1] Ashenhurst R. L.: The Decomposition of Switching Functions, Proc. of Int. Symp. on Theory of Switching Functions, pp. 74-116, 1957.
• [2] Ashar P., Devadas S., Newton A. R.: Sequential Logic Synthesis, Kluwer Academic Publisher, Norwell, 1992.
• [3] Scholl C.: Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers, 2001.
• [4] Brzozowski J., Łuba T.: Decomposition of Boolean Functions Specified by Cubes, Journal of Mult. - Valued Logic & Soft Computing, vol. 9, 2003, pp. 377-417.
• [5] Nowicka M., Łuba T., Rawski M.: FPGA-Based Decomposition of Boolean Functions. Algorithms and Implementation, Proc. of the 6th International Conference on Advanced Computer Systems, 1999.
• [6] Rawski M.: Efficient Variable Partitioning Method for Functional Decomposition, Electronics and Telecommunications Quarterly, vol. 53, no 1, pp. 63-81, 2007.
• [7] Goldberg D. E.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1989.
• [8] Koza J. R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA, 1992.
• [9] Keller R. E., Banzhaf W.: The evolution of genetic code in genetic programming, Proc. of the Genetic and Evolutionary Computation Conference, 1999, pp. 1077-1082.
• [10] Koza J. R., Keane M. A., Streeter M. J., Mydlowec W., Yu J., Lanza G.: Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer, 2003.
• [11] Deniziak S., Górski A.: Hardware/Software Co-Synthesis of Distributed Embedded Systems Using Genetic Programming, Lecture Notes in Computer Science, Springer-Verlag, 2008, pp. 83-93.
• [12] http://rawski.zpt.tele.pw.edu.pl/pl/node/161
• [13] Muthukumar V., Bignall R.J., Selvaraj H.: An efficient variable partitioning approach for functional decomposition of circuits, Journal of Systems Architecture, vol. 53 (2007), pp. 53-67.