Decomposition of multi-output functions oriented to configurability of logic blocks

• Autorzy: Kubica M. , Kania D.

Identyfikatory

DOI

10.1515/bpasts-2017-0036

• Języki publikacji: EN

Abstrakty

EN

The main goal of the paper is to present a logic synthesis strategy dedicated to an LUT-based FPGA. New elements of the proposed synthesis strategy include: an original method of function decomposition, non-disjoint decomposition, and technology mapping dedicated to configurability of logic blocks. The aim of all of the proposed synthesis approaches is the sharing of appropriately configured logic blocks. Innovation of the methods is based on the way of searching decomposition, which relies on multiple cutting of an MTBDD diagram describing a multi-output function. The essence of the proposed algorithms rests on the method of unicoding dedicated to sharing resources, searching non-disjoint decomposition on the basis of the partition of root tables, and choosing the levels of diagram cutting that will guarantee the best mapping to complex logic blocks. The methods mentioned above were implemented in the MultiDec tool. The efficiency of the analyzed methods was experimentally confirmed by comparing the synthesis results with both academic and commercial tools.

Słowa kluczowe

EN

BDD; decomposition; logic synthesis; technology mapping

PL

BDD; rozkład; Synteza logiczna; Mapowanie technologii

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 3
• Strony: 317--331
• Opis fizyczny: Bibliogr. 49 poz., rys., wykr., tab.

Twórcy

autor

Kubica M.

• Faculty of Mechanical Engineering and Computer Science, University of Bielsko-Biała, 2 Willowa St., 43-309 Bielsko-Biała, Poland

autor

Kania D.

• Institute of Electronics, Silesian University of Technology, 2A Akademicka St., 44-100 Gliwice, Poland

Bibliografia

• [1] R.L. Ashenhurst, “The decomposition of switching functions”, Proceedings of an International Symposium on the Theory of Switching, April 1957.
• [2] H.A. Curtis, The Design of Switching Circuits, D. van Nostrand Company, Inc., Princeton, 1962.
• [3] R. Murgai, N. Shenoy, R.K. Brayton, and A. Sangiovanni-Vincentelli, “Improved logic synthesis algorithms for table look up architectures”, ICCAD-91, 564–567 (1991).
• [4] P. Abouzeid, B. Babba, M. Crastes, and G. Saucier, “Input-driven partitioning methods and application to synthesis on table-lookup-based FPGAs”, IEEE Trans on CAD 12 (7), 913–925, 1993.
• [5] S.D. Brown, R.J. Francis, J. Rose, and Z.G. Vranesic, Field Programmable Gate Arrays, pp. 45–86, Kluwer Academic Publishers, Boston, 1993.
• [6] R.K. Brayton, G.D. Hachtel, C. McMullen, and A.L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Boston, 1984.
• [7] D. Chen and J. Cong, “DAOmap: A depth-optimal area optimization mapping algorithm”, IEEE/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004, 752–759 (2004).
• [8] J-D. Huang, J-Y. Jou, and W-Z. Shen, “ALTO: An iterative area/performance tradeoff algorithm for LUT-based FPGA technology mapping”, IEEE Transactions on Very Large Integration (VLSI) Systems 8 (4), 392–400 (2000).
• [9] A. Mishchenko, S. Chatterjee, and R. Brayton, “Improvements to technology mapping for LUT-based FPGAs”, Proc. FPGA 2006, 41–49 (2006).
• [10] A. Mishchenko, S. Chatterjee, and R.K. Brayton, “Improvements to technology mapping for LUT-based FPGAs”, IEEE Trans. Comput. Aided Design Integr. Circuits Syst. 26 (2), 240–253 (2007).
• [11] Siddhartha and N. Kapre, “Fanout decomposition dataflow optimizations for FPGA-based sparse LU factorization”, International Conference on Field-Programmable Technology (FPT), 252–255 (2014).
• [12] Siddhartha and N. Kapre, “Breaking sequential dependencies in FPGA-based sparse LU factorization”, FCCM ’14: Proceedings of the 22nd IEEE Symposium on Field Programmable Custom Computing Machines, 1–4 (2014).
• [13] Y.Y. Liang, T.Y. Kuo, S.H. Wang, and W.K. Mak, “ALMmap: Technology mapping for FPGAs with adaptive logic modules”, 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 143–148 (2010).
• [14] S. Chang, M. Marek-Sadowska, and T. Hwang, “Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams”, IEEE Transactions on Computer-Aided Design 15 (10), 1226–1235 (1996).
• [15] M. Kubica and D. Kania, “Area-oriented technology mapping for LUT-based logic blocks”, International Journal of Applied Mathematics and Computer Science 27 (1), 2017, (in press).
• [16] Y. Lai, K.R. Pan, and M. Pedram, “OBDD-based function decomposition: Algorithms and implementation”, IEEE Transactions on Computer-Aided Design 15(8), 977–990 (1996).
• [17] N. Vemuri, P. Kalla, and R. Tessier, “BDD-based logic synthesis for LUT-based FPGAs”, ACM Trans. Design Autom. Electron. Syst. 7 (4), 501–525 (2002).
• [18] D. Kania, “Logic decomposition for PAL-based CPLDs”, Journal of Circuits, Systems, and Computers 24 (3), 1–27 (2015).
• [19] D. Kania and J. Kulisz, “Logic synthesis for PAL-based CPLD-s based on two-stage decomposition”, The Journal of Systems and Software 80, 1129–1141 (2007).
• [20] A. Opara and D. Kania, “Decomposition-based logic synthesis for PAL-based CPLDs”, International Journal of Applied Mathematics and Computer Science 20 (2), 367–384 (2010)
• [21] G. Borowik, T. Łuba, and P. Tomaszewicz, “On memory capacity to implement logic functions”, Computer Aided Systems Theory – EUROCAST 2011 Part II, pp. 343–350, eds. R. Moreno-Díaz, F. Pichler, and A. Quesada-Arencibia, Springer-Verlag, Berlin, 2012.
• [22] T. Sasao, Memory-Based Logic Synthesis, Springer, New York, 2011.
• [23] D. Kania, “Decomposition-based synthesis and its application in PAL-oriented technology mapping”, Proceedings of the 26th Euromicro Conference, 138–145 (2000).
• [24] T. Łuba and H. Selvaraj, “A general approach to Boolean function decomposition and its applications in FPGA-based synthesis. VLSI design”, Special Issue on Decompositions in VLSI Design 3 (3–4), 289–300 (1995).
• [25] M. Perkowski, R Malvi, S. Grygiel, M. Burns, and A. Mishchenko, “Graph coloring algorithms for fast evaluation of curtis decompositions”, 36th ACM/IEEE DAC’99, (1999).
• [26] C. Yang and M. Ciesielski, “BDS: A BDD-based logic optimization system”, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 21 (7), 866–876 (2002).
• [27] L. Cheng, D. Chen, and M.D.F. Wong, “DDBDD: Delay-driven BDD synthesis for FPGAs”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27 (7), 1203–1213 (2008).
• [28] L. Cheng, D. Chen, and M.D.F. Wong, “DDBDD: Delay-driven BDD synthesis for FPGAs”, 44th ACM/IEEE Design Automation Conference, 910–915 (2007).
• [29] P. Fiser and J. Schmidt, “The case for a balanced decomposition process”, Proc. of 12th Euromicro Conference on Digital Systems Design (DSD), 601–604 (2009).
• [30] P. Fiser and J. Schmidt, “On using permutation of variables to improve the iterative power of resynthesis”, Proc. of 10th Int. Workshop on Boolean Problems (IWSBP), 107–114 (2012).
• [31] Berkeley Logic Synthesis Group, ABC: A System for Sequential Synthesis and Verification, Dec. 2005, http://www.eecs.berkeley.edu/~alanmi/abc
• [32] V. Manohararajah, D.P. Singh, and S.D. Brown, “Post-placement BDD-based decomposition for FPGAs”, International Conference on Field Programmable Logic and Applications 2005, 31–38 (2005).
• [33] K. Muma, D. Chen, Y. Choi, D. Dodds, M.H. Lee, and S.-B. Ko, “Combining ESOP minimization with BDD-based decomposition for improved FPGA synthesis”, Canadian Journal of Electrical and Computer Engineering 33 (3/4), 177–182 (2008).
• [34] K. Muma and S.-B. Ko, “A new logic synthesis, ExorBDS”, Canadian Conference on Electrical and Computer Engineering 2005, 816–819 (2005).
• [35] A. Opara and D. Kania, “Logic synthesis strategy based on BDD decomposition and PAL-oriented optimization”, 11th International Conference of Computational Methods in Science and Engineering, ICCMSE 2015, AIP Conf. Proc. 1702 (1), 60002.1‒60002.4 (2015).
• [36] T. Sasao, FPGA Desig by Generalized Functional Decomposition in Logic Synthesis and Optimization, Kluwer Academic Publishers, Boston, 1993.
• [37] M. Kubica and D. Kania, “SMTBDD: New concept of graph for function decomposition”, 13th IFAC Conference on Programmable Devices and Embedded Systems, 49–54 (2015).
• [38] M. Kubica and D. Kania, “SMTBDD: New form of BDD for logic synthesis”, International Journal of Electronics and Telecommunications 62 (1), 33–41 (2016).
• [39] S. Minato, Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, 1996.
• [40] M. Kubica, Decomposition and Technology Mapping Based on BDD, PhD thesis, Silesian University of Technology, Gliwice, 2014, http://ssuise-keit.multimedia.edu.pl/doktoraty.php, [in Polish].
• [41] D. Kania, Programmable Logic Devices, PWN, Warszawa 2012 (in Polish)
• [42] Ch. Scholl, Functional Decomposition with Application to FPGA Synthesis, Kluwer Academic Publisher, Boston, 2001.
• [43] E. Dubrova, “A polinominal time algorithm for non-disjoint decomposition of multi-valued functions”, 34th International Symposium on Multiple-Valued Logic, 309–314 (2004).
• [44] E. Dubrova, M. Teslenko, and A. Martinelli, “On relation between non-disjoint decomposition and multiple-vertex dominators”, 2004 IEEE International Symposium on Circuits and Systems, vol. IV, 493–496 (2004).
• [45] E. Hrynkiewicz and S. Kołodziński, “An Ashenhurst disjoint and non-disjoint decomposition of logic functions in Reed-Muller spectral domain”, 17th International Conference on Mixed Design of Integrated Circuits and Systems, 293–296 (2010).
• [46] A. Opara, Decomposition Synthesis Methods of Combinational Circuits Using BDD, PhD thesis, Silesian University of Technology, Gliwice, 2008, http://ssuise-keit.multimedia.edu.pl/doktoraty.php, [in Polish].
• [47] S. Yamashita, H. Sawada, and A. Nagoya, “New methods to find optimal non–disjoint bi–decompositions”, Design Automation Conference 1998. Proceedings of the ASP-DAC ‘98, 59–68 (1998).
• [48] Altera, Logic Array Blocks and Adaptive Logic Modules in Stratix V Devices, 2012
• [49] Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University, http://www.cbl.ncsu/edu/

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).