Area–Oriented Technology Mapping for LUT–Based Logic Blocks

Kubica, Marcin; Kania, Dariusz

doi:10.1515/amcs-2017-0015

Abstract

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.

References

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 Systems12(7): 913–925.10.1109/43.238028
Search in Google Scholar Back to article
Akers, S. (1978). Binary decision diagrams, IEEE Transactions on ComputersC-27(6): 509–516.10.1109/TC.1978.1675141
Search in Google Scholar Back to article
Altera (2010). Introduction to the Quartus II software, ver. 10.0, www.altera.com/content/dam/altera–www/global/en_US/pdfs/literature/manual.
Search in Google Scholar Back to article
Altera (2012). Logic array blocks and adaptive logic modules in Stratix V devices, www2.engr.arizona.edu/~ece506/readings/project–reading/6–cad/.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Anderson, J., Wang, Q. and Ravishankar, C. (2012). Raising FPGA logic density through synthesis-inspired architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems20(3): 537–550.10.1109/TVLSI.2010.2102781
Search in Google Scholar Back to article
Ashenhurst, R. (1957). The decomposition of switching functions, Proceedings of an International Symposium on the Theory of Switching, Cambridge, MA, USA, pp. 74–116.
Search in Google Scholar Back to article
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 Sciences81(12): 2545–2553.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Bryant, R. (1986). Graph-based algorithms for Boolean function manipulation, IEEE Transactions on ComputersC-35(8): 677–691.10.1109/TC.1986.1676819
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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 Systems13(1): 1–12.10.1109/43.273754
Search in Google Scholar Back to article
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 Systems26(2): 230–239.10.1109/TCAD.2006.887922
Search in Google Scholar Back to article
Curtis, H. (1962). A New Approach to the Design of Switching Circuits, Chin Jih, Princeton, NJ.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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) Systems8(4): 392–400.10.1109/92.863618
Search in Google Scholar Back to article
Kania, D. (2004). Decomposition elements dedicated for LUT-based FPGAs, Archiwum Informatyki Teoretycznej i Stosowanej16(1): 45–62.
Search in Google Scholar Back to article
Karplus, K. (1993). Xtmap: Generate-and-test mapper for table-lookup gate arrays, Compcon Spring’93, San Francisco, CA, USA, pp. 391–399.
Search in Google Scholar Back to article
Kubica, M. (2014). Decomposition and Technology Mapping Using Binary Decision Diagrams, PhD thesis, Silesian University of Technology, Gliwice, (in Polish).
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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).10.1515/bpasts-2017-0036
Search in Google Scholar Back to article
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 Systems15(8): 977–990.10.1109/43.511577
Search in Google Scholar Back to article
Lattice (2012). Lattice ECP3 family data sheet, www.latticesemi.com/.../LatticeSemi/.../DataSheets/Lattice/LatticeECP3EAFamilyData.
Search in Google Scholar Back to article
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 Systems31(7): 1134–1139.10.1109/TCAD.2012.2187525
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Long, D. (2008). Carnegie Mellon University BDD Library, http://www.cs.cmu.edu/afs/cs/project/modck/pub/www/.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
McElvain, K. (1993). IWLS’93 benchmark set: Version 4.0, https://ddd.fit.cvut.cz/prj/Benchmarks/IWLS93.pdf.
Search in Google Scholar Back to article
Micheli, G.D. (1994). Synthesis and Optimization of Digital Circuits, 1st Edn., McGraw-Hill Higher Education, New York, NY.
Search in Google Scholar Back to article
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).
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Opara, A. (2008). Decomposition Synthesis Methods of Combinational Circuits using Binary Decision Diagrams, PhD thesis, Silesian University of Technology, Gliwice, (in Polish).
Search in Google Scholar Back to article
Opara, A. and Kania, D. (2010). Decomposition-based logic synthesis for PAL-based CPLDs, International Journal of Applied Mathematics and Computer Science20(2): 367–384, DOI: 10.2478/v10006-010-0027-1.10.2478/v10006-010-0027-1
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Rohani, A. and Zarandi, H. (2009). A new CLB architecture for tolerating SEU in SRAM-based FPGAs, International Conference on Reconfigurable Computing and FPGAs, ReConFig’09, pp. 83–88.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publishers, Norwell, MA.10.1007/978-1-4757-3393-8
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Vemuri, N., Kalla, P. and Tessier, R. (2002). BDD-based logic synthesis for LUT-based FPGAs, ACM Transactions on Design Automation of Electronic Systems7(4): 501–525, DOI: 10.1145/605440.605442.10.1145/605440.605442
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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 Science23(2): 473–483, DOI: 10.2478/amcs-2013-0036.10.2478/amcs-2013-0036
Search in Google Scholar Back to article
Xilinx (1997). XC3000 technical information, xapp024, www.xilinx.com/support/documentation/application_notes/xapp024.pdf.
Search in Google Scholar Back to article
Xilinx (2013). ISE Design Suite 14, UG631, www.xilinx.com/products/design–tools/ise–design–suite.html.
Search in Google Scholar Back to article
Yang, C. and Ciesielski, M. (2002). BDS: A BDD-based logic optimization system, IEEE Transactions on
Search in Google Scholar Back to article

Area–Oriented Technology Mapping for LUT–Based Logic Blocks

Abstract

Paradigm

My account