Technology mapping of multi-output functions leading to the reduction of dynamic power consumption in FPGAs

Opara, Adam ; Kubica, Marcin

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 2, pp. 267-284.

Résumé

This article presents a synthesis strategy aimed at minimizing the dynamic power consumption of combinational circuits mapped in LUT blocks of FPGAs. The implemented circuits represent the mapping of multi-output functions. Properly selected multi-output functions are described using a new form of the binary decision diagram (BDD), which is an extension of pseudomulti-terminal BDDs (PMTBDDs) in the literature. The essence of limiting power consumption is to include additional parameters during decomposition, such as the switching activity associated with the switching PMTBDD (SWPMTBDD). In addition, we highlight the key importance of circuit optimization methods via non-disjoint decomposition when minimizing power consumption. An algorithm is proposed to assess the effectiveness of decomposition, considering several parameters, such as the number of non-disjoint decompositions as well as that of shared and non-shared bound functions or the switching activity. The results of experiments that demonstrate the effectiveness of the proposed methods are also included.

Détail

Keywords: low power synthesis, FPGA, switching activity, technology mapping
Mots-clés : FPGA, czynność przełączania, mapowanie technologii

Bibliographie

[1] [1] Akers, S.B. (1978). Binary decision diagrams, IEEE Transactions on Computers 27(06): 509-516.

[2] [2] Ali, H. and Al-Hashimi, B.M. (2007). Architecture level power-performance tradeoffs for pipelined designs, IEEE International Symposium on Circuits and Systems, New Orleans, USA, pp. 1791-1794.

[3] [3] Ashenhurst, R.L. (1957). The decomposition of switching functions, Proceedings of the International Symposium on the Theory of Switching, Cambridge, USA, pp. 76-116.

[4] [4] Balasubramanian, P. and Anantha, K. (2007). Power and delay optimized graph representation for combinational logic circuits, Engineering and Technology International Journal of Structural and Construction Engineering 1(8): 2481-2487.

[5] [5] Bard, S. and Rafla, N.I. (2008). Reducing power consumption in FPGAs by pipelining, 51st Midwest Symposium on Circuits and Systems, Knoxville, USA, pp. 173-176.

[6] [6] Barkalov, A., Titarenko, L. and Chmielewski, S. (2020b). Improving characteristics of LUT-based Moore FSMSs, IEEE Access 8: 155306-155318, DOI: 10.1109/ACCESS.2020.3006732.

[7] [7] Barkalov, A., Titarenko, L. and Mazurkiewicz, M. (2022). Improving the LUT count for Mealy FSMs with transformation of output collections, International Journal of Applied Mathematics and Computer Science 32(3): 479-494, DOI: 10.34768/amcs-2022-0035.

[8] [8] Barkalov, A., Titarenko, L., Mazurkiewicz, M. and Krzywicki, K. (2021). Improving LUT count of FPGA-based sequential blocks, Bulletin of the Polish Academy of Sciences: Technical Sciences 69(2): 1-12.

[9] [9] Barkalov, A., Titarenko, L. and Mielcarek, K. (2020b). Improving characteristics of LUT-based Mealy FSMs, International Journal of Applied Mathematics and Computer Science 30(4): 745-759, DOI: 10.34768/amcs-2020-0055.

[10] [10] Benini, L. and Micheli, G.d. (2000). System-level power optimization: Techniques and tools, ACM Transactions on Design Automation of Electronic Systems 5(2): 115-192.

[11] [11] BLSG (2005). ABC: A system for sequential synthesis and verification, Berkeley Logic Synthesis and Verification Group, http://www.eecs.berkeley.edu/˜alanmi/abc.

[12] [12] Bogliolo, A., Benini, L. and De Micheli, G. (1998). Characterization-free behavioral power modeling, Design, Automation and Test in Europe, Paris, France, pp. 767-773.

[13] [13] Brooks, D., Tiwari, V. and Martonosi, M. (2000). Wattch: A framework for architectural-level power analysis and optimizations, ACM SIGARCH Computer Architecture News 28(2): 83-94.

[14] [14] Chen, C., Srivastava, A. and Sarrafzadeh, M. (2001). On gate level power optimization using dual-supply voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 9(5): 616-629.

[15] [15] Cheng, L., Chen, D. and Wong, M.D. (2008). DDBDD: Delay-driven BDD synthesis for FPGAs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27(7): 1203-1213.

[16] [16] Chung, S.J.K. and Brayton, A.M.R. (2009). A power optimization toolbox for logic synthesis and mapping, https://people.eecs.berkeley.edu/˜alanmi/publications/2009/iwls09_pwr.pdf.

[17] [17] CBEAL (2004). Collection of digital design benchmarks, https://ddd.fit.cvut.cz/www/prj/Benchmarks/.

[18] [18] Costa, J.C., Monteiro, J.C. and Devadas, S. (1997). Switching activity estimation using limited depth reconvergent path analysis, Proceedings of the 1997 International Symposium on Low Power Electronics and Design, Monterey, USA, pp. 184-189.

[19] [19] Curtis, H.A. (1962). The Design of Switching Circuits, D. van Nostrand Company, New York.

[20] [20] Dubrova, E. (2004). A polynomial time algorithm for non-disjoint decomposition of multiple-valued functions, 34th International Symposium on Multiple-Valued Logic, Toronto, Canada, pp. 309-314.

[21] [21] Dubrova, E., Teslenko, M. and Martinelli, A. (2004). On relation between non-disjoint decomposition and multiple-vertex dominators, 2004 IEEE International Symposium on Circuits and Systems, Vancouver, Canada, Vol. 4, pp. 493-496.

[22] [22] Ferreira, R., Trullemans, A.-M., Costa, J. and Monteiro, J. (2000). Probabilistic bottom-up RTL power estimation, IEEE 2000 1st International Symposium on Quality Electronic Design, San Jose, USA, pp. 439-446.

[23] [23] Hasan Babu, H.M. and Sasao, T. (1999). Representations of multiple-output functions using binary decision diagrams for characteristic functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 82(11): 2398-2406.

[24] [24] Jóźwiak, L. and Chojnacki, A. (2003). Effective and efficient FPGA synthesis through general functional decomposition, Journal of Systems Architecture 49(4): 247-265.

[25] [25] Kajstura, K. and Kania, D. (2018). Low power synthesis of finite state machines-State assignment decomposition algorithm, Journal of Circuits, Systems and Computers 27(03): 1850041.

[26] [26] Kim, S. and Kim, J. (2000). Low-power data representation, Electronics Letters 36(11): 1.

[27] [27] Kubica, M., Kajstura, K. and Kania, D. (2018). Logic synthesis of low power FSM dedicated into LUT-based FPGA, Proceedings of the International Conference of Computational Methods in Sciences and Engineering, Thessaloniki, Greece, pp. 1-4.

[28] [28] Kubica, M. and Kania, D. (2016). SMTBDD: New form of BDD for logic synthesis, International Journal of Electronics and Telecommunications 62(1): 33-41.

[29] [29] Kubica, M. and Kania, D. (2017a). Area-oriented technology mapping for LUT-based logic blocks, International Journal of Applied Mathematics and Computer Science 27(1): 207-222, DOI: 10.1515/amcs-2017-0015.

[30] [30] Kubica, M. and Kania, D. (2017b). Decomposition of multi-output functions oriented to configurability of logic blocks, Bulletin of the Polish Academy of Sciences: Technical Sciences 65(3): 317-331.

[31] [31] Kubica, M. and Kania, D. (2019). Technology mapping oriented to adaptive logic modules, Bulletin of the Polish Academy of Sciences: Technical Sciences 67(5): 947-956.

[32] [32] Kubica, M., Opara, A. and Kania, D. (2017). Logic synthesis for FPGAs based on cutting of BDD, Microprocessors and Microsystems 52: 173-187, DOI: 10.1016/j.micpro.2017.06.010.

[33] [33] Kubica, M., Opara, A. and Kania, D. (2021a). Logic synthesis strategy oriented to low power optimization, Applied Sciences 11(19): 8797.

[34] [34] Kubica, M., Opara, A. and Kania, D. (2021b). Technology Mapping for LUT-based FPGA, Springer, Cham, DOI: 10.1007/978-3-030-60488-2.

[35] [35] Kuc, M., Sułek, W. and Kania, D. (2020). Low power QC-LDPC decoder based on token ring architecture, Energies 13(23): 6310.

[36] [36] Li, X., Chen, L., Yang, F., Yuan, M., Yan, H. and Wan, Y. (2022). HIMAP: A heuristic and iterative logic synthesis approach, Proceedings of the 59th ACM/IEEE Design Automation Conference, DAC’22, San Francisco, USA, pp. 415-420, DOI: 10.1145/3489517.3530460.

[37] [37] Lin, Z., Yuan, Z., Zhao, J., Zhang, W., Wang, H. and Tian, Y. (2022). Powergear: Early-stage power estimation in FPGA HLS via heterogeneous edge-centric GNNs, Proceedings of the 2022 Conference Exhibition on Design, Automation Test in Europe, DATE’22, Antwerp, Belgium, pp. 1341-1346.

[38] [38] Lindgren, P., Kerttu, M., Thornton, M. and Drechsler, R. (2001). Low power optimization technique for BDD mapped circuits, Proceedings of the 2001 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 615-621.

[39] [39] Ling, A., Singh, D.P. and Brown, S.D. (2005). FPGA technology mapping: A study of optimality, Proceedings of the 42nd Annual Design Automation Conference, DAC’05, New York, USA, pp. 427-432, DOI: 10.1145/1065579.1065693.

[40] [40] Manzak, A. and Chakrabarti, C. (2002). A low power scheduling scheme with resources operating at multiple voltages, IEEE Transactions on Very Large Scale Integration Systems 10(1): 6-14.

[41] [41] Marakkalage, D.S., Testa, E., Riener, H., Mishchenko, A., Soeken, M. and De Micheli, G. (2020). Three-input gates for logic synthesis, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 40(10): 2184-2188.

[42] [42] Mehrotra, R. (2013). Systematic Delay-driven Power Optimisation and Power-driven Delay Optimisation of Combinational Circuits, PhD thesis, University College Cork, Cork.

[43] [43] Minato, S.-i. (1996). Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, New York.

[44] [44] Opara, A. and Kania, D. (2009). A novel non-disjunctive method for decomposition of CPLDs, Electronics and Telecommunications Quarterly 55(1): 95-111.

[45] [45] Opara, A. and Kubica, M. (2017). Optimization of synthesis process directed at FPGA circuits with the usage of non-disjoint decomposition, AIP Conference Proceedings, 1906: 120004, DOI: 10.1063/1.5012396.

[46] [46] Opara, A. and Kubica, M. (2018). The choice of decomposition path taking non-disjoint decomposition into account, AIP Conference Proceedings 2040, Paper ID: 080010, DOI: 10.1063/1.5079144.

[47] [47] Opara, A., Kubica, M. and Kania, D. (2018). Strategy of logic synthesis using MTBDD dedicated to FPGA, Integration 62: 142-158, DOI: 10.1016/j.vlsi.2018.02.009.

[48] [48] Opara, A., Kubica, M. and Kania, D. (2019). Methods of improving time efficiency of decomposition dedicated at FPGA structures and using BDD in the process of cyber-physical synthesis, IEEE Access 7: 20619-20631, DOI: 10.1109/ACCESS.2019.2898230.

[49] [49] Patalas-Maliszewska, J., Wiśniewski, R., Topczak, M. and Wojnakowski, M. (2022). Design optimization of the Petri net-based production process supported by additive manufacturing technologies, Bulletin of the Polish Academy of Sciences: Technical Sciences 70(2): e140693.

[50] [50] Raghunathan, A., Jha, N.K. and Dey, S. (2012). High-Level Power Analysis and Optimization, Springer, New York, USA.

[51] [51] Rawski, M., Łuba, T., Jachna, Z. and Tomaszewicz, P. (2005). The influence of functional decomposition on modern digital design process, in M.A. Adamski et al. (Eds), Design of Embedded Control Systems, Springer US, Boston, pp. 193-204, DOI: 10.1007/0-387-28327-7 17.

[52] [52] Sánchez, F.M., Fungairiño, Y.T. and Alcaide, T.R. (2009). A BDD proposal for probabilistic switching activity estimation, Proceedings of the 23rd International Conference on Design of Circuits and Integrated Systems (DCIS), Grenoble, France.

[53] [53] Scholl, C. (2001). Functional Decomposition with Applications to FPGA Synthesis, Springer, New York.

[54] [54] Selvaraj, H., Sapiecha, P., Rawski, M. and Łuba, T. (2006). Functional decomposition-The value and implication for both neural networks and digital designing, International Journal of Computational Intelligence and Applications 6(01): 123-138.

[55] [55] Vemuri, N., Kalla, P. and Tessier, R. (2002). BDD-based logic synthesis for LUT-based FPGAs, ACM Transactions on Design Automation of Electronic Systems 7(4): 501-525.

[56] [56] Wisniewski, R. (2021). Design of Petri net-based cyber-physical systems oriented on the implementation in field programmable gate arrays, Energies 14(21): 7054, DOI: 10.3390/en14217054.

[57] [57] Wisniewski, R., Grobelna, I. and Karatkevich, A. (2020). Determinism in cyber-physical systems specified by interpreted Petri nets, Sensors 20(19): 5565.

[58] [58] Wojnakowski, M., Wiśniewski, R., Bazydło, G. and Popławski, M. (2021). Analysis of safeness in a Petri net-based specification of the control part of cyber-physical systems, International Journal of Applied Mathematics and Computer Science 31(4): 647-657, DOI: 10.34768/amcs-2021-0045.

[59] [59] Xilinx (2021). Vivado design suite user guide: Implementation (UG904), https://docs.xilinx.com/r/en-US/ug904-vivado-implementation.