Decomposition-based logic synthesis for PAL-based CPLDs

Opara, Adam; Kania, Dariusz

doi:10.2478/v10006-010-0027-1

Abstract

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 (ROBDDs). 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.

References

Akers, S. B. (1978). Functional testing with binary decision diagrams, Proceedings of the 8-th Annual Conference on Fault-Tolerant Computing, pp. 75-82.
Search in Google Scholar
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.
Search in Google Scholar
Ashar, P., Devadas, S. and Newton, A. R. (1992). Sequential Logic Synthesis, Kluwer Academic Publishers, Norwell, MA.10.1007/978-1-4615-3628-4
Search in Google Scholar
Ashenhurst, R. (1957). The decomposition of switching functions, Proceedings of an International Symposium on the Theory of Switching, pp. 74-116.
Search in Google Scholar
Bolton, M. (1990). Digital Systems Design with Programmable Logic, Addison-Wesley Longman Publishing Co., Inc., Boston, MA.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1007/978-1-4613-2821-6
Search in Google Scholar
Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers 35(8): 677-691.10.1109/TC.1986.1676819
Search in Google Scholar
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.
Search in Google Scholar
Chartrand, G. and Zhang, P. (2008). Chromatic Graph Theory, Chapman & Hall/CRC, Boca Raton, FL.10.1201/9781584888017
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/43.149766
Search in Google Scholar
Curtis, H. (1962). A New Approach to the Design of Switching Circuits, Van Nostrand, Princeton, NJ.
Search in Google Scholar
De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, New York, NY.
Search in Google Scholar
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.
Search in Google Scholar
Ebendt, R., Fey, G. and Drechsler, R. (2005). Advanced BDD Optimization, Springer-Verlag, Berlin/Heidelberg.
Search in Google Scholar
Kania, D. (2004). Logic Synthesis for PAL-based Complex Programmable Logic Devices, Zeszyty Naukowe: Elektronika, Vol. 14, pp. 5-212, (in Polish).
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/43.511577
Search in Google Scholar
Minato, S. (1996). Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, Norwell, MA.10.1007/978-1-4613-1303-8
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
Muthukumar, V., Bignall, R. and Selvaraj, H. (2000). An input-output encoding approach for serial decomposition, SBC-CI'0: Proceedings of the 13th Symposium on Integrated Circuits and Systems Design, Washington, DC, USA, pp. 61-68.
Search in Google Scholar
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.
Search in Google Scholar
Opara, A. (2009). Decompositional Synthesis Methods of Combinatorial Circuits with Binary Decision Diagrams Application, Ph.D. thesis, Silesian University of Technology, Gliwice, (in Polish).
Search in Google Scholar
Opara, A. and Kania, D. (2000). A novel non-disjunctive method for decomposition of CPLDs, Electronics and Telecommunications Quarterly 55(1): 95-111.
Search in Google Scholar
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.
Search in Google Scholar
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.
Search in Google Scholar
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.10.1109/43.277632
Search in Google Scholar
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
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.
Search in Google Scholar
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.10.1109/TCAD.2002.1013899
Search in Google Scholar
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.10.1109/43.62787
Search in Google Scholar

Decomposition-based logic synthesis for PAL-based CPLDs

Abstract

Paradigm

My account