Decomposition-based logic synthesis for PAL-based CPLDs

Adam Opara; Dariusz Kania

International Journal of Applied Mathematics and Computer Science (2010)

  • Volume: 20, Issue: 2, page 367-384
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Adam Opara, and Dariusz Kania. "Decomposition-based logic synthesis for PAL-based CPLDs." International Journal of Applied Mathematics and Computer Science 20.2 (2010): 367-384. <http://eudml.org/doc/207993>.

@article{AdamOpara2010,
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.},
author = {Adam Opara, Dariusz Kania},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {decomposition; technology mapping; logic optimization; BDD; CPLD},
language = {eng},
number = {2},
pages = {367-384},
title = {Decomposition-based logic synthesis for PAL-based CPLDs},
url = {http://eudml.org/doc/207993},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Adam Opara
AU - Dariusz Kania
TI - Decomposition-based logic synthesis for PAL-based CPLDs
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 2
SP - 367
EP - 384
AB - 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.
LA - eng
KW - decomposition; technology mapping; logic optimization; BDD; CPLD
UR - http://eudml.org/doc/207993
ER -

References

top
  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. Zbl0565.94020
  8. Bryant, R.E. (1986). Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers 35(8): 677-691. Zbl0593.94022
  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. Zbl1169.05001
  11. Chen, K. and Muroga, S. (1988). Input assignment algorithm for decoded-PLAs with multi-input decoders, IEEE International Conference on Computer-Aided Design. ICCAD88. 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. Zbl0846.68022
  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 inputoutput 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. Zbl0989.94003
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.