Area-oriented technology mapping for LUT-based logic blocks

Kubica, M. ; Kania, D.

International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 1, pp. 207-222.

Résumé

One of the main aspects of logic synthesis dedicated to FPGA is the problem of technology mapping, which is directly associated with the logic decomposition technique. This paper focuses on using configurable properties of CLBs in the process of logic decomposition and technology mapping. A novel theory and a set of efficient techniques for logic decomposition based on a BDD are proposed. The paper shows that logic optimization can be efficiently carried out by using multiple decomposition. The essence of the proposed synthesis method is multiple cutting of a BDD. A new diagram form called an SMTBDD is proposed. Moreover, techniques that allow finding the best technology mapping oriented to configurability of CLBs are presented. In the experimental section, the presented method (MultiDec) is compared with academic and commercial tools. The experimental results show that the proposed technology mapping strategy leads to good results in terms of the number of CLBs.

Détail

Keywords: SMTBDD, FPGA, synthesis method, decomposition technique
Mots-clés : SMTBDD, FPGA, metoda syntezy, technika rozkładu

Bibliographie

[1] Abouzeid, P., Babba, B., Crastes de Paulet, M. and Saucier, G. (1993). Input-driven partitioning methods and application to synthesis on table-lookup-based FPGAs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12(7): 913–925.

[2] Akers, S. (1978). Binary decision diagrams, IEEE Transactions on Computers C-27(6): 509–516.

[3] Altera (2010). Introduction to the Quartus II software, ver. 10.0, www.altera.com/content/dam/altera-www/global/en_US/pdfs/literature/manual.

[4] Altera (2012). Logic array blocks and adaptive logic modules in Stratix V devices, www2.engr.arizona.edu/˜ece506/readings/project-reading/6-cad/.

[5] Anderson, J. and Wang, Q. (2011). Area-efficient FPGA logic elements: Architecture and synthesis, 16th Asia and South Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, pp. 369–375.

[6] Anderson, J., Wang, Q. and Ravishankar, C. (2012). Raising FPGA logic density through synthesis-inspired architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 20(3): 537–550.

[7] Ashenhurst, R. (1957). The decomposition of switching functions, Proceedings of an International Symposium on the Theory of Switching, Cambridge, MA, USA, pp. 74–116.

[8] Babu, H.M.H. and Sasao, T. (1998). Shared multi-terminal binary decision diagrams for multiple-output functions, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 81(12): 2545–2553.

[9] Brayton, R. and Mishchenko, A. (2010). ABC: An academic industrial-strength verification tool, in T. Touili et al. (Eds.), Proceedings of the 22nd International Conference on Computer Aided Verification, CAV’10, Springer-Verlag, Berlin/Heidelberg, pp. 24–40, DOI: 10.1007/978-3-642-14295-6 5.

[10] Bryant, R. (1986). Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers C-35(8): 677–691.

[11] Chang, S.-C. and Marek-Sadowska, M. (1992). Technology mapping via transformations of function graphs, IEEE 1992 International Conference on Computer Design: VLSI in Computers and Processors, Washington, DC, USA, pp. 159–162.

[12] Chen, D. and Cong, J. (2004). DAOMAP: A depth-optimal area optimization mapping algorithm for FPGA designs, IEEE/ACM International Conference on Computer Aided Design, ICCAD-2004, San Jose, CA, USA, pp. 752–759.

[13] Cheng, L., Chen, D. and Wong, M. (2007). DDBDD: Delay-driven BDD synthesis for FPGAs, 44th ACM/IEEE Design Automation Conference, DAC’07, San Diego, CA, USA, pp. 910–915.

[14] Cong, J. and Ding, Y. (1994). FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13(1): 1–12.

[15] Cong, J. and Minkovich, K. (2007). Optimality study of logic synthesis for LUT-based FPGAS, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26(2): 230–239.

[16] Curtis, H. (1962). A New Approach to the Design of Switching Circuits, Chin Jih, Princeton, NJ.

[17] Fiser, P. and Schmidt, J. (2009). The case for a balanced decomposition process, 12th Euromicro Conference on Digital Systems Design (DSD), Patras, Greece, pp. 601–604.

[18] Fiser, P. and Schmidt, J. (2012). On using permutation of variables to improve the iterative power of resynthesis, 10th International Workshop on Boolean Problems (IWSBP), Freiberg, Germany, pp. 107–114.

[19] Francis, R., Rose, J. and Chung, K. (1990). CHORTLE: A technology mapping program for lookup table-based field programmable gate arrays, 27th ACM/IEEE Design Automation Conference, Orlando, FL, USA, pp. 613–619.

[20] Garg, V., Chandrasekhar, V., Sashikanth, M. and Kamakoti, V. (2005). A novel CLB architecture and circuit packing algorithm for logic-area reduction in SRAM-based FPGAs, Asia and South Pacific Design Automation Conference ASP-DAC 2005, Shanghai, China, Vol. 2, pp. 791–794.

[21] Huang, J.-D., Jou, J.-Y. and Shen, W.-Z. (2000). Alto: An iterative area/performance tradeoff algorithm for LUT-based FPGA technology mapping, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 8(4): 392–400.

[22] Kania, D. (2004). Decomposition elements dedicated for LUT-based FPGAs, Archiwum Informatyki Teoretycznej I Stosowanej 16(1): 45–62.

[23] Karplus, K. (1993). Xtmap: Generate-and-test mapper for table-lookup gate arrays, Compcon Spring’93, San Francisco, CA, USA, pp. 391–399.

[24] Kubica, M. (2014). Decomposition and Technology Mapping Using Binary Decision Diagrams, PhD thesis, Silesian University of Technology, Gliwice, (in Polish).

[25] Kubica, M. and Kania, D. (2015). New concept of graph for function decomposition, IFAC Conference on Programmable Devices and Embedded Systems, PDES 2015, Cracow, Poland, pp. 61–66.

[26] Kubica, M. and Kania, D. (2016). Decomposition of multi-output functions oriented to configurability of logic blocks, Bulletin of the Polish Academy of Sciences: Technical Sciences, (accepted).

[27] Lai, Y.-T., Pan, K.-R. and Pedram, M. (1996). OBDD-based function decomposition: Algorithms and implementation, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 15(8): 977–990.

[28] Lattice (2012). Lattice ECP3 family data sheet, www.latticesemi.com/.../LatticeSemi/.../DataSheets/Lattice/LatticeECP3EAFamilyData.

[29] Liang, Y.-Y., Kuo, T.-Y., Wang, S.-H. and Mak, W.-K. (2012). Almmap: Technology mapping for FPGAs with adaptive logic modules, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 31(7): 1134–1139.

[30] Long, D. (1998). The design of a cache-friendly BDD library, IEEE/ACM International Conference on Computer-Aided Design, 1998, San Jose, CA, USA, pp. 639–645.

[31] Long, D. (2008). Carnegie Mellon University BDD Library, http://www.cs.cmu.edu/afs/cs/project/modck/pub/www/.

[32] Mao, Z., Chen, L., Wang, Y. and Lai, J. (2011). A new configurable logic block with 4/5-input configurable LUT and fast/slow-path carry chain, IEEE 9th International Conference on ASIC (ASICON), Xiamen, China, pp. 67–70.

[33] McElvain, K. (1993). IWLS’93 benchmark set: Version 4.0, https://ddd.fit.cvut.cz/prj/Benchmarks/IWLS93.pdf.

[34] Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, 1st Edn.,McGraw-Hill Higher Education, New York, NY.

[35] Miczulski, P. (2000). Analysis of the efficiency of BDD libraries, International Scientific Symposium for Students and Young Scientists, Zielona Góra, Poland, pp. 65–71, (in Polish).

[36] Mikusek, P. (2009). Multi-terminal BDD synthesis and applications, International Conference on Field Programmable Logic and Applications, FPL 2009, Prague, Czech Republic, pp. 721–722.

[37] Mikusek, P. and Dvorak, V. (2009). Heuristic synthesis of multi-terminal BDDs based on local width/cost minimization, 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, DSD’09, Patras, Greece, pp. 605–608.

[38] Minato, S., Ishiura, N. and Yajima, S. (1990). Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, 27th ACM/IEEE Design Automation Conference, Orlando, FL, USA, pp. 52–57.

[39] Murgai, R., Shenoy, N., Brayton, R. and Sangiovanni-Vincentelli, A. (1991). Improved logic synthesis algorithms for table look up architectures, IEEE International Conference on Computer-Aided Design, ICCAD-91, Santa Clara, CA, USA, pp. 564–567.

[40] Ochi, H., Ishiura, N. and Yajima, S. (1991). Breadth-first manipulation of SBDD of Boolean functions for vector processing, 28th ACM/IEEE Design Automation Conference, San Francisco, CA, USA, pp. 413–416.

[41] Opara, A. (2008). Decomposition Synthesis Methods of Combinational Circuits using Binary Decision Diagrams, PhD thesis, Silesian University of Technology, Gliwice, (in Polish).

[42] Opara, A. and Kania, D. (2010). Decomposition-based logic synthesis for PAL-based CPLDs, International Journal of Applied Mathematics and Computer Science 20(2): 367–384, DOI: 10.2478/v10006-010-0027-1.

[43] Rawski, M., Jozwiak, L., Nowicka, M. and Luba, T. (1997). Non-disjoint decomposition of boolean functions and its application in FPGA-oriented technology mapping, 23rd EUROMICRO Conference EUROMICRO 97: New Frontiers of Information Technology, Budapest, Hungary, pp. 24–30.

[44] Ray, S., Mishchenko, A., Een, N., Brayton, R., Jang, S. and Chen, C. (2012). Mapping into LUT structures, Proceedings of the Conference on Design, Automation and Test in Europe, DATE’12, San Jose, CA, USA, pp. 1579–1584.

[45] Rohani, A. and Zarandi, H. (2009). A new CLB architecture for tolerating SEU in SRAM-based FPGAs, International Conference on Reconfigurable Computing and FPGAs, Re-ConFig’09, pp. 83–88.

[46] Sasao, T. and Butler, J. (1996). A method to represent multiple-output switching functions by using multi-valued decision diagrams, 26th International Symposium on Multiple-Valued Logic, Santiago De Compostela, Spain, pp. 248–254.

[47] Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers, Norwell, MA.

[48] Scholl, C., Becker, B. and Brogle, A. (2001). The multiple variable order problem for binary decision diagrams: Theory and practical application, Proceedings of the Design Automation Conference, Asia and South Pacific, Yokohama, Japan, pp. 85–90.

[49] Tang, W.-C., Lo, W.-H. and Wu, Y.-L. (2007). Further improve excellent graph-based FPGA technology mapping by rewiring, IEEE International Symposium on Circuits and Systems, ISCAS 2007, New Orleans, LA, USA, pp. 1049–1052.

[50] Thornton, M., Williams, J., Drechsler, R., Drechsler, R. and Wessels, D. (1999). SBDD variable reordering based on probabilistic and evolutionary algorithms, IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, Canada, pp. 381–387.

[51] 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, DOI: 10.1145/605440.605442.

[52] Wan, W. and Perkowski, M.A. (1992). A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping, Proceedings of the Conference on European Design Automation, EURO-DAC’92, Hamburg, Germany, pp. 230–235.

[53] Wyrwoł, B. and Hrynkiewicz, E. (2013). Decomposition of the fuzzy inference system for implementation in the FPGA structure, International Journal of Applied Mathematics and Computer Science 23(2): 473–483, DOI: 10.2478/amcs-2013-0036.

[54] Xilinx (1997). XC3000 technical information, xapp024, www.xilinx.com/support/documentation/application_notes/xapp024.pdf.

[55] Xilinx (2013). ISE Design Suite 14, UG631, www.xilinx.com/products/design-tools/ise-design-suite.html.

[56] Yang, C. and Ciesielski, M. (2002). BDS: A BDD-based logic optimization system, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 21(7): 866–876.