2. Home
  3. ARCHIVE
  4. 2020
  5. VOL 42, NO 2 (2020)
  6. pp. 25-40

GENETIC PROGRAMMING OF APPLICATION-SPECIFIC PIPELINED DATAPATHS

A.М. Sergiyenko, V.A. Romankevich, A.A. Serhienko

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

ABSTRACT

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.

KEYWORDS

FPGA, VHDL, SDF, data flow graph, genetic programming.

REFERENCES

  1. 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.
    https://doi.org/10.1201/b19569-3
  2. Wang, G., Gong, W. and Kastner, R. (2008), Operation Scheduling: Algorithms and Applications. High-level synthesis: from algorithm to digital circuit,
  3. Hwang, C.T., Lee, T.H. and Hsu, Y.C. (1991), “A formal approach to the scheduling prob­lem in high level synthesis”, IEEE Trans. Comput. Aided Design, 10, no. 4, pp. 464-475.
    https://doi.org/10.1109/43.75629
  4. Kruse, R., Borgelt, C., Braune, C., Mostaghim, S. and Steinbrecher, M. (2016), Computational Intelligence. A Methodological Introduction. 2-nd Ed, Springer.
    https://doi.org/10.1007/978-1-4471-7296-3
  5. Miller, F. (2011), Cartesian Genetic Programming, Springer, Berlin, Germany.
    https://doi.org/10.1007/978-3-642-17310-3
  6. Sergiyenko, A. M. and Simonenko, V. P. (2007), “Mapping periodic algorithms to programmable logic integrated circuits”, Electronic Modeling, 29. no. 2, pp. 49-61.
  7. 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
    https://doi.org/10.20535/SRIT.2308-8893.2016.1.06
  8. Affenzeller, M., Winkler, S., Wagner, S. and Beham, A. (2009), Genetic Algorithms and Genetic Programming. Modern Concepts and Practical Applications, Chapman & Hall, CRC Press.
    https://doi.org/10.1201/9781420011326
  9. Ouaiss, I., Govindarajan, S., Srinivasan, V., Kaul, M. and Vemuri, R. (1998), “An Integrated Partitioning and Synthesis System for Dynamically Reconfigurable Multi-FPGA Architectures”, Proceeding of the Reconfigurable Architectures Workshop (RAW’98), Springer, LNCS, Vol. 1388, Berlin, Heidelberg, pp. 31-36.
    https://doi.org/10.1007/3-540-64359-1_669
  10. 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.
    https://doi.org/10.1109/ISSS.2000.874038
  11. Parsa, S. and Lotfi, S. (2006), “A New Genetic Algorithm for Loop Tiling”, The Journal of Supercomputing, Vol. 37, no. 3, pp. 249-269.
    https://doi.org/10.1007/s11227-006-6367-9
  12. Bonsma, E. and Gerez, S. (1997), “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, Netherlands, pp. 67-76.
  13. 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.
  14. 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.
    https://doi.org/10.1109/92.902270
  15. 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.
    https://doi.org/10.1109/CEC.2003.1299584
  16. Chen, D. and Cong, J. (2004), “Register binding and port assignment for multiplexer optimization”, Proceeding of the 2004 Conference on Asia South Pacific Design Automation, (ASP-DAC’04), 68-73.
    https://doi.org/10.1109/ASPDAC.2004.1337542
  17. 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.
    https://doi.org/10.1109/TEVC.2005.860764
  18. 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.
    https://doi.org/10.1109/ICSAMOS.2007.4285745
  19. 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.
    https://doi.org/10.1145/774789.774804
  20. 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.
    https://doi.org/10.1016/j.sysarc.2008.04.010
  21. Poli, R. (1997), “Evolution of Graph-like Programs with Parallel Distributed Genetic Programming”, Genetic Algorithms: Proceeding of the 7-th International Conference, pp. 346-
  22. 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.
  23. Parhi, K. K. (1999), VLSI Digital Signal Processing Systems. Design and Implementation, Wiley.
  24. 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.
    https://doi.org/10.1007/978-3-319-77553-1_13
  25. 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.
    https://doi.org/10.1007/978-3-030-16670-0_7
  26. 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.
    https://doi.org/10.1109/ICEC.1994.350037
  27. Holland, J. H. (1992), Adaptation in Natural and Artificial Systems, MIT Press, USA.
    https://doi.org/10.7551/mitpress/1090.001.0001
  28. Petrowski, A. and Ben-Hamida, S. (2017), Evolutionary Algorithms, Wiley & Sons, Inc, Hoboken, New Jersey, USA.
    https://doi.org/10.1002/9781119136378
  29. 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.
    https://doi.org/10.1007/s10489-007-0062-2
  30. Sergiyenko, A., Serhienko, A. and Simonenko, A. (2017), “A method for synchronous dataflow retiming”, IEEE First Ukraine Conference on Electrical and Computer Enginee­ring (UKRCON), Kiev, Ukraine, 2017, pp. 1015-1018.
    https://doi.org/10.1109/UKRCON.2017.8100404
  31. 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.
    https://doi.org/10.1145/157485.165042
  32. Jin, Y. (2005), “A comprehensive survey of fitness approximation in evolutionary computation”, Soft Computing,   9, no. 1, pp. 3-12.
    https://doi.org/10.1007/s00500-003-0328-5
  33. Norenkov, I.P. (2009), Osnovy Avtomatizirovannogo Proektirovaniya [Computer Aided Design Basics], Izd-vo MGTU im. Baumana, Мoskow, Russia.
  34. 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.
    https://doi.org/10.1109/ISCAS.2001.922384
  35. 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.

Full text: PDF