Decomposition-based logic synthesis for PAL-based CPLDs

Opara, A. ; Kania, D.

International Journal of Applied Mathematics and Computer Science, Tome 20 (2010) no. 2, pp. 367-384.

Résumé

The paper presents one concept of decomposition methods dedicated to PAL-based CPLDs. The proposed approach is an alternative to the classical one, which is based on two-level minimization of separate single-output functions. The key idea of the algorithm is to search for free blocks that could be implemented in PAL-based logic blocks containing a limited number of product terms. In order to better exploit the number of product terms, two-stage decomposition and BDD-based decomposition are to be used. In BDD-based decomposition methods, functions are represented by Reduced Ordered Binary Decision Diagrams (ROBDD)). The results of experiments prove that the proposed solution is more effective, in terms of the usage of programmable device resources, compared with the classical ones.

Détail

Keywords: decomposition, technology mapping, logic optimization, BDD, CPLD
Mots-clés : rozkład, odwzorowanie technologiczne, optymalizacja logiczna, BDD, CPLD

Bibliographie

[1] Akers, S.B. (1978). Functional testing with binary decision diagrams, Proceedings of the 8-th Annual Conference on Fault-Tolerant Computing, pp. 75-82.

[2] Anderson, J.H. and Brown, S.D. (1998). Technology mapping for large complex PLDs, DAC '98: Proceedings of the 35th Annual Design Automation Conference, New York, NY, USA, pp. 698-703.

[3] Ashar, P., Devadas, S. and Newton, A.R. (1992). Sequential Logic Synthesis, Kluwer Academic Publishers, Norwell,MA.

[4] Ashenhurst, R. (1957). The decomposition of switching functions, Proceedings of an International Symposium on the Theory of Switching, pp. 74-116.

[5] Bolton, M. (1990). Digital Systems Design with Programmable Logic, Addison-Wesley Longman Publishing Co., Inc., Boston, MA.

[6] Brace, K.S., Rudell, R.L. and Bryant, R.E. (1990). Efficient implementation of a bdd package, DAC '90: Proceedings of the 27th ACM/IEEE Design Automation Conference, New York, NY, USA, pp. 40-45.

[7] Brayton, R.K., Sangiovanni-Vincentelli, A.L., McMullen, C.T. and Hachtel, G. D. (1984). Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA.

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

[9] Burns, M., Perkowski, M., Jóźwiak, L. and Grygiel, S. (1998). An efficient and effective approach to column-based input/output encoding in functional decomposition, Proceedings of the 3rd International Workshop on Boolean Problems, Freiberg, Germany, pp. 19-29.

[10] Chartrand, G. and Zhang, P. (2008). Chromatic Graph Theory, Chapman Hall/CRC, Boca Raton, FL.

[11] Chen, K. and Muroga, S. (1988). Input assignment algorithm for decoded-PLAs with multi-input decoders, IEEE International Conference on Computer-Aided Design. ICCAD-88. Digest of Technical Papers, Santa Clara, CA, USA, pp. 474-477.

[12] Chen, S., Hwang, T. and Liu, C. (2002). A technology mapping algorithm for CPLD architectures, 2002 IEEE International Conference on Field-Programmable Technology, pp. 204-210.

[13] Ciesielski, M. and Yang, S. (1992). PLADE: A two-stage PLA decomposition, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11(8): 943-954.

[14] Curtis, H. (1962). A New Approach to the Design of Switching Circuits, Van Nostrand, Princeton, NJ.

[15] De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, New York, NY.

[16] Devadas, S.,Wang, A., Newton, A. and Sangiovanni-Vincentelli, A. (1988). Boolean decomposition of programmable logic arrays, Proceedings of the IEEE Custom Integrated Circuit Conference, Rochester, NY, USA, Vol. 2, pp. 2.5.1-2.5.5.

[17] Ebendt, R., Fey, G. and Drechsler, R. (2005). Advanced BDD Optimization, Springer-Verlag, Berlin/Heidelberg.

[18] Kania, D. (2004). Logic Synthesis for PAL-based Complex Programmable Logic Devices, Zeszyty Naukowe: Elektronika, Vol. 14, pp. 5-212, (in Polish).

[19] Kania, D., Kulisz, J. and Milik, A. (2005). A novel method of two-stage decomposition dedicated for PAL-based CPLDs, Proceedings of the 8th Euromicro Conference on Digital System Design, Porto, Portugal, pp. 114-121.

[20] Kim, J., Kim, H. and Lin, C. (2001). A new technology mapping for CPLD under the time constraint, Proceedings of the Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 235-238.

[21] Kouloheris, J. and Gamal, A. (1992). PLA-based FPGA area versus cell C+ granularity, Proceedings of the Custom Integrated Circuits Conference, Boston, MA, USA, Vol. 4, pp. 4.3.1-4.3.4.

[22] Lai, Y., Pan, K. and Pedram, M. (1994). FPGA synthesis using function decomposition, ICCS '94: Proceedings of the 1994 IEEE International Conference on Computer Design: VLSI in Computer Processors, Washington, DC, USA, pp. 30-35.

[23] Lai, Y., Pan, K. 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.

[24] Minato, S. (1996). Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, Norwell, MA.

[25] Murgai, R., Brayton, R. and Sangiovanni-Vincentelli, A. (1994). Optimum functional decomposition using encoding, Proceedings of the 31st Annual Conference on Design Automation, New York, NY, USA, pp. 408-414.

[26] Muthukumar, V. (2001). An improved input-output encoding approach for functional decomposition, DSD '01: Proceedings of the Euromicro Symposium on Digital Systems Design, Washington, DC, USA, pp. 144-147.

[27] Muthukumar, V., Bignall, R. and Selvaraj, H. (2000). An input output encoding approach for serial decomposition, SBCCI' 00: Proceedings of the 13th Symposium on Integrated Circuits and Systems Design, Washington, DC, USA, pp. 61-68.

[28] Nowicka, M., Łuba, T. and Selvaraj, H. (1997). Multilevel decomposition strategies in decomposition-based algorithms and tools, International Workshop on Logic and Architecture Synthesis, Grenoble, France, pp. 129-136.

[29] Opara, A. (2009). Decompositional Synthesis Methods of Combinatorial Circuits with Binary Decision Diagrams Application, Ph.D. thesis, Silesian University of Technology, Gliwice, (in Polish).

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

[31] Rawski, M., Łuba, T. and Falkowski, B. (2008). Logic synthesis method for FPGAs with embedded memory blocks, IEEE International Symposium on Circuits and Systems, Seattle, WA, USA, pp. 2014-2017.

[32] Rudell, R. (1993). Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design, Los Alamitos, CA, USA, pp. 42-47.

[33] Saldanha, A., Villa, T., Brayton, R. and Sangiovanni-Vincentelli, A. (1994). Satisfaction of input and output encoding constraints, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 13(5): 589-602.

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

[35] Yan, K. (2001). Practical logic synthesis for CPLDs and FPGAs with PLA-style logic blocks, Proceedings of the 2001 Conference on Asia South Pacific Design Automation, ACM New York, NY, USA, pp. 231-234.

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

[37] Yang, S. and Ciesielski, M.J. (1991). Optimum and suboptimum algorithms for input encoding and its relationship to logic minimization, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 10(1): 4-12.