A.М. Sergiyenko, V.A. Romankevich, A.A. Serhienko
Èlektron. model. 2020, 42(2):25-40
A method for the synthesis of application-specific pipeline data paths based on the genetic programming is proposed. The method consists in representing the algorithm with a spatial synchronous data flow graph, encoding its matrix of operator-nodes as chromosomes and using the genetic optimization algorithm. The high efficiency of the method is shown by the example of the discrete cosine transform processor synthesis, which is configured in FPGA.
FPGA, VHDL, SDF, data flow graph, genetic programming.
- Bhattacharyya, S. and Wolf, M. (2016), Tools and Methodologies for System-Level Design. Electronic Design Automation for IC System Design, Verification, and Testing, CRC Press.
- Wang, G., Gong, W. and Kastner, R. (2008), Operation Scheduling: Algorithms and Applications. High-level synthesis: from algorithm to digital circuit,
- Hwang, C.T., Lee, T.H. and Hsu, Y.C. (1991), “A formal approach to the scheduling problem in high level synthesis”, IEEE Trans. Comput. Aided Design, 10, no. 4, pp. 464-475.
- Kruse, R., Borgelt, C., Braune, C., Mostaghim, S. and Steinbrecher, M. (2016), Computational Intelligence. A Methodological Introduction. 2-nd Ed, Springer.
- Miller, F. (2011), Cartesian Genetic Programming, Springer, Berlin, Germany.
- Sergiyenko, A. M. and Simonenko, V. P. (2007), “Mapping periodic algorithms to programmable logic integrated circuits”, Electronic Modeling, 29. no. 2, pp. 49-61.
- Sergiyenko, A.M. and Simonenko, V.P. (2016), “Sheduling of Synchronous Data Flows”, System Investigations and Informational Technologies, no. 1, pp. 51-62. DOI: 10.20535/ 2308-8893.2016.1.06
- Affenzeller, M., Winkler, S., Wagner, S. and Beham, A. (2009), Genetic Algorithms and Genetic Programming. Modern Concepts and Practical Applications, Chapman & Hall, CRC Press.
- Ouaiss, I., Govindarajan, S., Srinivasan, V., Kaul, M. and Vemuri, R. (1998), “An Integrated Partitioning and Synthesis System for Dynamically Reconﬁgurable Multi-FPGA Architectures”, Proceeding of the Reconﬁgurable Architectures Workshop (RAW’98), Springer, LNCS, Vol. 1388, Berlin, Heidelberg, pp. 31-36.
- Grajcar, M. (2000), “Conditional Scheduling for Embedded Systems using Genetic List Scheduling”, Proceeding of the 13th International Symposium on System Synthesis (ISSS), Madrid, Spain, 2000, pp. 123-128.
- Parsa, S. and Lotﬁ, S. (2006), “A New Genetic Algorithm for Loop Tiling”, The Journal of Supercomputing, Vol. 37, no. 3, pp. 249-269.
- Bonsma, E. and Gerez, S. (1997), “A genetic approach to the overlapped scheduling of iterative data-ﬂow graphs for target architectures with communication delays”, ProRISC Workshop on Circuits, Systems and Signal Processing, November 27-28, 1997, Mierlo, Netherlands, pp. 67-76.
- Mandal, C., Chakrabarti, P. and Ghose, S. (1996), “Design space exploration for data path synthesis”, Proceeding of the 10-th International Conference on VLSI Design, 1996, pp. 166-170.
- Mandal, С., Chakrabarti, P. and Ghose, S.(2000), “GABIND: a GA approach to allocation and binding for the high-level synthesis of data paths”, IEEE Trans. on VLSI Systems, 8, no. 6, pp. 747-750.
- Grewal, G., O’Cleirigh, M. and Wineberg, M. (2003), “An evolutionary approach to behavioural-level synthesis”, The 2003 Congress on Evolutionary Computation, (CEC’03), 1, pp. 264-272.
- Chen, D. and Cong, J. (2004), “Register binding and port assignment for multiplexer optimization”, Proceeding of the 2004 Conference on Asia South Paciﬁc Design Automation, (ASP-DAC’04), 68-73.
- Krishnan, V. and Katkoori, S. (2006), “A genetic algorithm for the design space exploration of datapaths during high-level synthesis”, IEEE Trans. Evolutionary Computation, Vol. 10, no. 3, pp. 213-229.
- Ferrandi, F., Lanzi, P.L., Palermo, G., Pilato, C., Sciuto, D. and Tumeo, A. (2007), “An evolutionary approach to area-time optimization of FPGA designs”, International Conference on Embedded Computer Systems: Architectures, Modeling and Simulation, (ICSAMOS), pp. 145-152.
- Palesi, M. and Givargis, T. (2002), “Multi-objective design space exploration using genetic algorithms”, International Conference on Hardware/software Codesign, (CODES), ACM, New York, USA, pp. 67-72.
- Pilato, C., Tumeo, A., Palermo, G., Ferrandi, F., Lanzi, P. L. and Sciuto, D. (2008), “Improving evolutionary exploration to area-time optimization of FPGA designs”, Journal of Systems Architecture, 54, pp. 1046-1057.
- Poli, R. (1997), “Evolution of Graph-like Programs with Parallel Distributed Genetic Programming”, Genetic Algorithms: Proceeding of the 7-th International Conference, pp. 346-
- Miller, J.F., Walker, J.A. (2006), “Embedded cartesian genetic programming and the lawnmower and hierarchical-if-and-only-if problems”, Genetic and Evolutionary Computation Conference, GECCO06, Seattle, Washington, USA, July, 2006, pp. 911-918.
- Parhi, K. K. (1999), VLSI Digital Signal Processing Systems. Design and Implementation, Wiley.
- Husa, J. and Kalkreuth, R. (2018), “A Comparative Study on Crossover in Cartesian Genetic Programming”, Proceeding of the 21-st European Conference “Genetic Programming”, EuroGP, Parma, Italy, April 4-6, 2018, Vol. 10781, pp. 203-219.
- Koncal, O. and Sekanina, L. (2019), “Cartesian Genetic Programming as an Optimizer of Programs Evolved with Geometric Semantic Genetic Programming”, Proceeding of the 22-nd European Conference in Genetic Programming, EuroGP, Leipzig, Germany, April 24-26, 2019, pp. 98-113.
- Horn, J., Nafpliotis, N. and Goldberg, D.E. (1994), “A Niched Pareto Genetic Algorithm for Multiobjective Optimization”, Proceeding of the 1-st IEEE Conf. on Evolutionary Computation, Vol. 1, pp. 82-87.
- Holland, J. H. (1992), Adaptation in Natural and Artiﬁcial Systems, MIT Press, USA.
- Petrowski, A. and Ben-Hamida, S. (2017), Evolutionary Algorithms, Wiley & Sons, Inc, Hoboken, New Jersey, USA.
- Lee, S., Soak, S., Kim, K., Park, H. and Jeon, M. (2008), “Statistical properties analysis of real world tournament selection in genetic algorithms”, Applied Intelligence, 28, no. 2, pp. 195-205.
- Sergiyenko, A., Serhienko, A. and Simonenko, A. (2017), “A method for synchronous dataflow retiming”, IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON), Kiev, Ukraine, 2017, pp. 1015-1018.
- Chao, L., LaPaugh, A. and Sha, E. (1993), “Rotation scheduling: A loop pipelining algorithm” Proceeding of the 30-th Design Automation Conference. (DAC’93), June 1993, pp. 566-572.
- Jin, Y. (2005), “A comprehensive survey of ﬁtness approximation in evolutionary computation”, Soft Computing, 9, no. 1, pp. 3-12.
- Norenkov, I.P. (2009), Osnovy Avtomatizirovannogo Proektirovaniya [Computer Aided Design Basics], Izd-vo MGTU im. Baumana, Мoskow, Russia.
- Nikara, J., Takala, J., Akopian, D. and Saarinen, J. (2001), “Pipeline Architecture for DCT/IDCT”, IEEE International Symposium on Circuits and Systems, (ISCAS 2001), May 6-9, Sydney, Australia, pp. 902-905.
- Hsiao, S.-F., Shiue, W.-R. and Tseng, J.-M. (1991), “A cost efficient fully-pipelinable architecture for DCT/IDCT”, IEEE Trans. On Communications, Vol. 39, no. 5, pp. 640-643.