Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon openaccess Multi-objective optimisation algorithm for routability and timing driven circuit clustering on FPGAs

This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)
Received 10/07/2018, Accepted 30/10/2018, Published 17/12/2018

Circuit clustering algorithms fit synthesised circuits into field programmable gate array (FPGA) configurable logic blocks (CLBs) efficiently. This fundamental process in FPGA CAD flow directly impacts both effort required and performance achievable in subsequent place-and-route processes. Circuit clustering is limited by hardware constraints of specific target architectures. Hence, better circuit clustering approaches are essential for improving device utilisation whilst at the same time optimising circuit performance parameters such as, e.g. power and delay. In this study, the authors present a method based on multi-objective genetic algorithm (MOGA) to facilitate circuit clustering. They address a number of challenges including CLB input bandwidth constraints, improvement of CLB utilisation, minimisation of interconnects between CLBs. The authors’ new approach has been validated using the ‘Golden 20’ MCNC benchmark circuits that are regularly used in FPGA-related literature. The results show that the method proposed in this study achieves improvements of up to 50% in clustering, routability and timing when compared to state-of-the-art approaches including VPack, T-VPack, RPack, DPack, HDPack, MOPack and iRAC. The key contribution of this work is a flexible EDA flow that can incorporate numerous objectives required to successfully tackle real-world circuit design on FPGA, providing device utilisation at increased design performance.

Inspec keywords: genetic algorithms; timing circuits; electronic design automation; logic design; integrated circuit design; field programmable gate arrays; network routing

Other keywords: CLB input bandwidth constraints; FPGA-related literature; Golden 20 MCNC benchmark circuits; field programmable gate array; real-world circuit design; flexible EDA flow; multiobjective optimisation algorithm; interconnect minimisation; timing driven circuit clustering; CLB utilisation; configurable logic blocks; multiobjective genetic algorithm; place-and-route process; FPGA CAD flow; time optimising circuit performance parameters

Subjects: Optimisation techniques; Logic circuits; Digital circuit design, modelling and testing; Logic design methods; Optimisation techniques; Logic and switching circuits

References

    1. 1)
      • 23. Bäck, T., Hammel, U., Schwefel, H.P.: ‘Evolutionary computation: comments on the history and current state’, IEEE Trans. Evol. Comput., 1997, 1, (1), pp. 3–17.
    2. 2)
      • 29. Landman, B.S., Russo, R.L.: ‘On a pin versus block relationship for partitions of logic graphs’, IEEE Trans. Comput., 1971, C-20, pp. 1469–1479.
    3. 3)
      • 14. Feng, W.: ‘K-way partitioning based packing for FPGA logic blocks without input bandwidth constraint’. 2012 Int. Conf. Field-Programmable Technology (FPT), Seoul, Republic of Korea, 2012, pp. 8–15.
    4. 4)
      • 19. Karypis, G., Kumar, V.: ‘Multilevel K-way hypergraph partitioning’. DAC ‘99 Proc. of the 36th Annual ACM/IEEE Design Automation Conf., New Orleans, LA, USA, 1999, pp. 343–348.
    5. 5)
      • 4. Deb, K., Pratap, A., Agarwal, S., et al: ‘A fast and elitist multiobjective genetic algorithm: NSGA-II’, IEEE Trans. Evol. Comput., 2002, 6, pp. 182–197.
    6. 6)
      • 6. Bozorgzadeh, E., Ogrenci-Memik, S., Sarrafzadeh, M.: ‘RPack: routability-driven packing for cluster-based FPGAs’. Proc. of the ASP-DAC 2001. Asia and South Pacific Design Automation Conf., Yokohama, Japan, 2001, pp. 629–634.
    7. 7)
      • 20. Marrakchi, Z., Mrabet, H., Mehrez, H.: ‘Hierarchical FPGA clustering based on a multilevel partitioning approach to improve routability and reduce power dissipation’, ReConFig'05, Puebla City, Mexico, 2005, p. 25.
    8. 8)
      • 2. Betz, V., Rose, J., Marquardt, A.R.: ‘CAD Tools: Packing and Placement’, in Betz, V., Rose, J., Marquardt, A. (Eds.) ‘Architecture and CAD for deep-submicron FPGAs’ (Kluwer Academic Publishers, Norwell, MA, USA, 1999), pp. 37–61.
    9. 9)
      • 15. Betz, V., Rose, J.: ‘VPR: a new packing placement and routing tool for FPGA research’. Int. Workshop on Int. Workshop on Field-Programmable Logic and Application, London, UK, 1997, pp. 213–222.
    10. 10)
      • 3. Singh, A., Marek-Sadowska, M.: ‘Efficient circuit clustering for area and power reduction in FPGAs’. FPGA ‘02 Proc. of the 2002 ACM/SIGDA Tenth Int. Symp. on Field-Programmable Gate Arrays, Monterey, CA, USA, 2002, pp. 59–66.
    11. 11)
      • 26. Horn, J., Nafploitis, N., Goldberg, D.E.: ‘A niched Pareto genetic algorithm for multiobjective optimization’. Proc. of the First IEEE Conf. on Evolutionary Computation, Orlando, FL, USA, 1994, pp. 82–87.
    12. 12)
      • 1. Betz, V., Rose, J.: ‘Cluster-based logic blocks for FPGAs: area-efficiency vs. input sharing and size’. Proc. of CICC 97 – Custom Integrated Circuits Conf., Santa Clara, CA, USA, 1997, pp. 551–554.
    13. 13)
      • 11. Feng, W., Kaptanoglu, S.: ‘Designing efficient input interconnect blocks for LUT clusters using counting and entropy’, ACM Trans. Reconfigur. Technol. Syst., 2008, 1, (1), pp. 6:1–6:28. Available at http://doi.acm.org/10.1145/1331897.1331902.
    14. 14)
      • 5. Marquardt, A.S., Betz, V., Rose, J.: ‘Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density’. FPGA ‘99 Proc. of the 1999 ACM/SIGDA Seventh Int. Symp. on Field Programmable Gate Arrays, Monterey, CA, USA, 1999, pp. 37–46.
    15. 15)
      • 10. Kuon, I., Tessier, R., Rose, J.: ‘FPGA architecture: survey and challenges’, Found. Trends Electron. Des. Autom., 2007, 2, (2), pp. 135–253.
    16. 16)
      • 7. Chen, D.T., Vorwerk, K., Kennings, A.: ‘Improving timing-driven FPGA packing with physical information’. Int. Conf. on Field Programmable Logic and Applications, FPL, Amsterdam, Netherlands, 2007, pp. 117–123.
    17. 17)
      • 13. Leventis, P., Chan, M., Chan, M., et al: ‘Cyclone: a low-cost, high-performance FPGA’. Proc. of the IEEE 2003 CICC, San Jose, CA, USA, 2003, pp. 49–52.
    18. 18)
      • 28. Wang, Y., Bale, S.J., Walker, J.A., et al: ‘Multiobjective genetic algorithm for routability-driven circuit clustering on FPGAs’. 2014 IEEE Int. Conf. on Evolvable Systems, Orlando, FL, USA, 2014, pp. 109–116.
    19. 19)
      • 18. Bozorgzadeh, E., Memik, S.O., Yang, X., et al: ‘Routability-driven packing: metrics and algorithms for cluster-based FPGAs’, J. Circuits Syst. Comput., 2004, 13, pp. 77–100.
    20. 20)
      • 9. Marquardt, A.R.: ‘Cluster-based architecture, timing-driven packing and timing-driven placement for FPGAs’ (ACM New York, NY, USA, 1999).
    21. 21)
      • 17. Fukunaga, A.S., Korf, R.E.: ‘Bin completion algorithms for multicontainer packing, knapsack, and covering problems’, J. Artif. Intell. Res., 2007, 28, pp. 393–429.
    22. 22)
      • 25. Holland, J.H.: ‘Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence’ (MIT Press, Cambridge, MA, USA, 1992).
    23. 23)
      • 22. Liu, H., Akoglu, A.: ‘T-NDPack: timing-driven non-uniform depopulation based clustering’. 5th Southern Conf. on Programmable Logic, SPL, Sao Carlos, Brazil, 2009, pp. 9–14.
    24. 24)
      • 30. Deb, K., Pratap, A., Meyarivan, T.: ‘Constrained test problems for multi-objective evolutionary optimization’. Evolutionary Multi-Criterion Optimization, Zurich, Switzerland, 2001, pp. 284–298.
    25. 25)
      • 32. Falkenauer, E.: ‘A new representation and operators for genetic algorithms applied to grouping problems’, Evol. Comput., 1994, 2, (2), pp. 123–144.
    26. 26)
      • 24. Eiben, A.E., Smith, J.E.: ‘Introduction to evolutionary computing’, Natural Computing Series (Springer Berlin Heidelberg, Berlin, Germany, 2007). Available at https://books.google.co.uk/books?id=RRKo9xVFW\_QC.
    27. 27)
      • 27. Srinivas, N., Deb, K.: ‘Multiobjective function optimization using nondominated sorting genetic algorithms’, Evol. Comput., 1995, 2, pp. 221–248.
    28. 28)
      • 16. Rose, J., Brown, S.: ‘Flexibility of interconnection structures for field-programmable gate arrays’, IEEE J. Solid-State Circuits, 1991, 26, (3), pp. 277–282.
    29. 29)
      • 8. Rajavel, S.T., Akoglu, A.: ‘MO-Pack: many-objective clustering for FPGA CAD’. Proc. of the 48th Design Automation Conf., San Diego, CA, USA, 2011, pp. 818–823.
    30. 30)
      • 21. Tom, M., Leong, D., Lemieux, G.: ‘Un/DoPack: re-clustering of large system-on-chip designs with interconnect variation for low-cost FPGAs’. IEEE/ACM Int. Conf. on Computer-Aided Design, ICCAD'06, San Jose, CA, USA, 2006, pp. 680–687.
    31. 31)
      • 31. Deb, K., Pratap, A., Moitra, S.: ‘Mechanical component design for multiple objectives using elitist non-dominated sorting GA’. Proc. of the Parallel Problem solving from Nature VI Conf., Paris, France, 2000, pp. 859–868.
    32. 32)
      • 12. Lewis, D.: ‘The stratixTM logic and routing architecture’. Proc. of the 2003 ACM/SIGDA Eleventh Int. Symp. on Field Programmable Gate Arrays, Monterey, CA, USA, 2003, pp. 12–20.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2018.5115
Loading

Related content

content/journals/10.1049/iet-cdt.2018.5115
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address