А.М. Сергієнко, д-р техн. наук,
В.О. Романкевич, д-р техн. наук, А.А. Сергієнко
Національний технічний університет України
«Київський політехнічний інститут ім. Ігоря Сікорського»
(Україна, 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
АНОТАЦІЯ
Запропоновано метод синтезу спеціалізованих конвеєрних пристроїв, який ґрунтується на генетичному програмуванні. Метод полягає у відтворенні алгоритму просторовим графом синхронних потоків даних, кодуванні його матриці вершин-операторів хромосомою та використанні алгоритму генетичної оптимізації. Високу ефективність методу показано на прикладі синтезу процесора для дискретного косинусного перетворення, конфігурованого у програмованій логічній інтегральній схемі.
КЛЮЧОВІ СЛОВА:
програмовані логічні інтегральні схеми, граф потоків даних, генетичне програмування.
СПИСОК ЛІТЕРАТУРИ
- 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.
- 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.
- 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
- Kruse R., Borgelt C., Braune C. et al. Computational Intelligence. A Methodological Introduction. 2-nd Ed. Springer, 2016. 564 p.
- Miller F. Cartesian Genetic Programming. Berlin: Springer, 2011. 342 p.
- Сергиенко А. М., Симоненко В. П. Отображение периодических алгоритмов в программируемые логические интегральные схемы // Электрон. моделирование, 2007, 29, № 2, с. 49—61
- Сергієнко А. М., Сімоненко В. П. Складання розкладу для графів синхронних потоків даних // Системні дослідження та інформаційні технології, 2016, № 1, с. 51—62. DOI: 10.20535/SRIT.2308-8893.2016.1.06
- Affenzeller , Winkler S., Wagner S., Beham A. Genetic Algorithms and Genetic Programming. Modern Concepts and Practical Applications. Chapman & Hall, CRC Press, 2009, 358 p.
- 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.
- Grajcar M. Conditional Scheduling for Embedded Systems using Genetic List Scheduling // 13th International Symposium on System Synthesis (ISSS). Madrid, Spain, 2000, p. 123—128.
- Parsa S., Lotfi S. A New Genetic Algorithm for Loop Tiling// The Journal of Supercomputing, 2006, Vol. 37, № 3, p.249—269
- 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
- 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
- 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
- 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
- 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
- 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.
- 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
- 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
- Pilato C., Tumeo A., Palermo G. et al. Improving evolutionary exploration to area-time optimization of FPGA designs // Journal of Systems Architecture. 2008, Vol. 54, p. 1046—1057
- Poli R. Evolution of Graph-like Programs with Parallel Distributed Genetic Programming // Genetic Algorithms: Proc. 7-th International Conference, 1997, p. 346—353
- 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
- Parhi K. K. VLSI Digital Signal Processing Systems. Design and Implementation. Wiley. 1999, 784 p.
- 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
- 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.
- 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
- Holland J. H. Adaptation in Natural and Artificial Systems. MIT Press, USA, 1992, 228 p.
- Petrowski A., Ben-Hamida S. Evolutionary Algorithms. Wiley & Sons, Inc., Hoboken, New Jersey, USA, 2017.
- 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
- 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—
- Chao L., LaPaugh A., Sha E. Rotation scheduling: A loop pipelining algorithm // Proc 30-th Design Automation Conf. (DAC’93), June 1993, 566—572.
- Jin Y. A comprehensive survey of fitness approximation in evolutionary computation // Soft Computing, 2005, Vol. 9, №1, p. 3—12
- Норенков И. П. Основы автоматизированного проектирования. М.: Изд-во МГТУ им. Баумана, 2009, 430 с.
- 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
- 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.
СЕРГІЄНКО Анатолій Михайлович, д-р техн. наук, ст. наук. співроб., професор кафедри обчислювальної техніки Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського». В 1975 р. закінчив Київський політехнічний ін-т. Область наукових досліджень — архітектура ком’ютерів, високорівневий синтез обчислювальних пристроїв, програмування ПЛІС, цифрова обробка сигналів, штучний інтелект.
РОМАНКЕВИЧ Віталій Олексійович, д-р техн. наук, професор, зав. кафедрою системного програмування і спеціалізованих комп'ютерних систем Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського». В 1996 р. закінчив Київський політехнічний ін-т. Область наукових досліджень — синтез відмовостійких багатопроцесорних систем, штучний інтелект.
СЕРГІЄНКО Анастасія Анатоліївна, асистентка кафедри обчислювальної техніки Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського», який закінчила у 2016 р. Область наукових досліджень — високорівневий синтез обчислювальних пристроїв, цифрова обробка сигналів, штучний інтелект.
Повний текст: PDF