Генетичне програмування спеціалізованих конвеєрних пристроїв

А.М. Сергієнко, д-р техн. наук,
В.О. Романкевич, д-р техн. наук, А.А. Сергієнко
Національний технічний університет України
«Київський політехнічний інститут ім. Ігоря Сікорського»
(Україна, 03056, пр-т Перемоги, 37,
тел. +38(068) 8123376, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.;
тел. +38(096) 1607909, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.;
тел. +38(096) 8127583, e-mail: Ця електронна адреса захищена від спам-ботів. Вам необхідно увімкнути JavaScript, щоб побачити її.)

Èlektron. model. 2019, 42(2):25-38
https://doi.org/10.15407/emodel.42.02.025

АНОТАЦІЯ

Запропоновано метод синтезу спеціалізованих конвеєрних пристроїв, який ґрунтується на генетичному програмуванні. Метод полягає у відтворенні алгоритму просторовим графом синхронних потоків даних, кодуванні його матриці вершин-операторів хромо­сомою та використанні алгоритму генетичної оптимізації. Високу ефективність методу показано на прикладі синтезу процесора для дискретного косинусного перетворення, конфігурованого у програмованій логічній інтегральній схемі.

КЛЮЧОВІ СЛОВА:

програмовані логічні інтегральні схеми, граф потоків даних, генетичне програмування.

СПИСОК ЛІТЕРАТУРИ

1. Bhattacharyya S., Wolf M. Tools and Methodologies for System-Level Design // Electronic  Design  Automation  for  IC  System Design, Verification, and Testing. Scheffer, L. Lavagno, G. Martin — Ed-s. CRC Press. 2016, p. 39—57.
2. Wang G., Gong W., Kastner R. Operation Scheduling: Algorithms and Applications // High-level synthesis: from algorithm to digital circuit. Coussy, ‎A. Morawiec — Ed-s. Springer. 2008, p. 231—255.
3. Hwang C.T., Lee T.H., Hsu Y.C. A formal approach to the scheduling problem in high level synthesis // IEEE Trans. Comput. Aided Des., 1991, Vol. 10, № 4, p. 464—475
4. Kruse R., Borgelt C., Braune C. et al. Computational Intelligence. A Methodological Introduction. 2-nd Ed. Springer, 2016. 564 p.
5. Miller F. Cartesian Genetic Programming. Berlin: Springer, 2011. 342 p.
6. Сергиенко А. М., Симоненко В. П. Отображение периодических алгоритмов в програм­мируемые логические интегральные схемы // Электрон. моделирование, 2007, 29, № 2, с. 49—61
7. Сергієнко А. М., Сімоненко В. П. Складання розкладу для графів синхронних потоків даних // Системні дослідження та інформаційні технології, 2016, № 1, с. 51—62. DOI: 10.20535/SRIT.2308-8893.2016.1.06
8. Affenzeller , Winkler S., Wagner S., Beham A. Genetic Algorithms and Genetic Prog­ramming. Modern Concepts and Practical Applications. Chapman & Hall, CRC Press, 2009, 358 p.
9. Ouaiss, I., Govindarajan, S., Srinivasan, V. et al. An Integrated Partitioning and Synthesis System for Dynamically Reconfigurable Multi-FPGA Architectures. // Proc. of the Reconfigurable Architectures Workshop (RAW’98). Springer, 1998. LNCS, V 1388. Berlin: Heidelberg, p. 31—36.
10. Grajcar M. Conditional Scheduling for Embedded Systems using Genetic List Scheduling // 13th International Symposium on System Synthesis (ISSS). Madrid, Spain, 2000, p. 123—128.
11. Parsa S., Lotfi S. A New Genetic Algorithm for Loop Tiling// The Journal of Supercomputing, 2006, Vol. 37, № 3, p.249—269
12. Bonsma E., Gerez S. A genetic approach to the overlapped scheduling of iterative data-flow graphs for target architectures with communication delays // ProRISC Workshop on Circuits, Systems and Signal Processing. November, 27—28, 1997. Mierlo, the Netherlands. 1997, p. 67—76
13. Mandal C., Chakrabarti P., Ghose S. Design space exploration for data path synthesis // Proc. of the 10-th International Conference on VLSI Design, 1996, p. 166—170
14. Mandal С., Chakrabarti P., Ghose S. GABIND: a GA approach to allocation and binding for the high-level synthesis of data paths // IEEE Trans. on VLSI Systems. 2000, Vol. 8, №6, p. 747—750
15. Grewal G., O’Cleirigh M., Wineberg M. An evolutionary approach to behavioural-level synthesis // The 2003 Congress on Evolutionary Computation, December 2003, CEC’03. 2003. Vol. 1, p. 264—272
16. Chen D., Cong J. Register binding and port assignment for multiplexer optimization // Proc. of the 2004 Conf. on Asia South Pacific Design Automation, ASP-DAC’04. 2004, p. 68—73
17. Krishnan V., Katkoori S. A genetic algorithm for the design space exploration of datapaths during high-level synthesis // IEEE Trans. Evolutionary Computation. 2006, Vol. 10, № 3, p. 213—229.
18. Ferrandi F., Lanzi P.L., Palermo G. et al. An evolutionary approach to area-time optimization of FPGA designs // Intern. Conf. on Embedded Computer Systems: Architectures, Modeling and Simulation, ICSAMOS. 2007. p. 145—152
19. Palesi M., Givargis T. Multi-objective design space exploration using genetic algorithms // Intern. Symp. on Hardware/software Codesign, CODES. ACM, NY, USA, 2002, p. 67—72
20. Pilato C., Tumeo A., Palermo G. et al. Improving evolutionary exploration to area-time op­ti­mization of FPGA designs // Journal of Systems Architecture. 2008, Vol. 54, p. 1046—1057
21. Poli R. Evolution of Graph-like Programs with Parallel Distributed Genetic Programming // Genetic Algorithms: Proc. 7-th International Conference, 1997, p. 346—353
22. Miller J. F., Walker J. A. Embedded cartesian genetic programming and the lawnmower and hierarchical-if-and-only-if problems // Genetic and Evolutionary Computation Conference, GECCO06. July, 2006, Seattle, Washington, USA,  p. 911—918
23. Parhi K. K. VLSI Digital Signal Processing Systems. Design and Implementation. Wiley. 1999, 784 p.
24. Husa J., Kalkreuth R. A Comparative Study on Crossover in Cartesian Genetic Programming // Proc. 21-st European Conference “Genetic Programming”. EuroGP, Parma, Italy, April 4—6, 2018. LNCS. 2018, Vol. 10781, p. 203—219
25. Koncal O., Sekanina L. Cartesian Genetic Programming as an Optimizer of Programs Evolved with Geometric Semantic Genetic Programming // Proc. 22-nd European Conference in Genetic Programming (EuroGP), April 24— Leipzig, Germany, 2019, p. 98—113.
26. Horn J., Nafpliotis N., Goldberg D. E. A Niched Pareto Genetic Algorithm for Multiobjective Optimization // Proc. of the 1-st IEEE Conf. on Evolutionary Computation. 1994. Vol. 1, p. 82—87
27. Holland J. H. Adaptation in Natural and Artificial Systems. MIT Press, USA, 1992, 228 p.
28. Petrowski A., Ben-Hamida S. Evolutionary Algorithms. Wiley & Sons, Inc., Hoboken, New Jersey, USA, 2017.
29. Lee S., Soak S., Kim K. et al. .Statistical properties analysis of real world tournament selection in genetic algorithms // Applied Intelligence, 2008. Vol. 28, № 2, p. 195—205
30. Sergiyenko A., Serhienko A., Simonenko A. A method for synchronous dataflow retiming // IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), Kiev, 2017, p. 1015—
31. Chao L., LaPaugh A., Sha E. Rotation scheduling: A loop pipelining algorithm // Proc 30-th Design Automation Conf. (DAC’93), June 1993, 566—572.
32. Jin Y. A comprehensive survey of fitness approximation in evolutionary computation // Soft Computing, 2005, Vol. 9, №1, p. 3—12
33. Норенков И. П. Основы автоматизированного проектирования. М.: Изд-во МГТУ им. Баумана, 2009, 430 с.
34. Nikara J., Takala J., Akopian D., Saarinen J. Pipeline Architecture for DCT/IDCT // IEEE International Symposium on Circuits and Systems. ISCAS, 2001, May 6-9, Sydney, Australia, 2001, p. 902—905
35. Hsiao S.-F., Shiue W.-R., Tseng J.-M. A cost efficient fully-pipelinable architecture for DCT/IDCT // IEEE Trans. On Communications, 1991, Vol. 39, № 5, p. 640—643.

Повний текст: PDF