A novel non-disjunctive method for decomposition of CPLDs

• Autorzy: Opara A. , Kania D.
• Języki publikacji: EN

Abstrakty

EN

The paper discusses the concept of a novel decomposition method dedicated for 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 exploit better the number of product terms, a non-disjunctive decomposition is to be used. In contrast to classical methods, the functions are represented by Reduced Ordered Binary Decision Diagrams (ROBDD). The results of the experiments prove that the proposed solution is more effective in terms of the usage of programmable device resources, compared to the classical ones.

Słowa kluczowe

EN

technology mapping; decomposition; CPLD; BDD

PL

odwzorowanie technologiczne; dekompozycja; CPLD; BDD

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 1
• Strony: 95--111
• Opis fizyczny: Bibliogr. 21 poz., wykr.

Twórcy

autor

Opara A.

autor

Kania D.

• Silesian University of Technology, Department of Computer Science, Department of Electronics, 44-100 Gliwice, ul. Akademicka 16,

Bibliografia

• 1. M. Bolton: Digital Systems Design with Programmable Logic. Addison-Wesley Publishing Company, 1990
• 2. R. K. Brayton, G. D. Hachtel, C. McMullen, A. L. Sangiovanni-Vincentelli: Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, Boston, 1984.
• 3. S. Chang, M. Marek-Sadowska, T. Hwang: Technology Mapping for TLU FPGA's Based on Decomposition of Binary Decision Diagrams, IEEE Transactions on Computer-Aided Design, Vol. 15, No. 10, 1996, pp. 1226-1235.
• 4. J-D. Huang, J-Y. Jo , W-Z. Shen: ALTO: An Iterative Area/Performance Tradeoff Algorithm for LUT-Based FPGA Technology Mapping, IEEE Transactions on Very Large Integration (VLSI) Systems, Vol. 8, No. 4, pp. 392-400.
• 5. Y. Lai, K. Pan, M. Pedram: FPGA synthesis using function decomposition, Proceedings of the IEEE International Conference on Computer Design, Cambridge, 1994, pp. 30-35.
• 6. M.-T. Lai, K.-R. R. Pan, M. Pedram: OBDD-Based Function Decomposition: Algorithms and Implementation, IEEE Transactions on Computer-Aided Ddesign of Integrated Circuits and Systems, 1996, Vol. 15, No. 8, pp. 977-990.
• 7. C. Yang, M. Ciesielski: BDS: A BBD-Based Logic Optimization System, IEEE Transactions on CAD of Integrated circuits and systems, Vol. 21, No. 7, 2002, pp. 866-876.
• 8. J. H. Anderson, S. D. Brown: Technology mapping for large complex PLDs, Proceedings of Design Automation Conference, DAC'98, 1998, pp. 698 -703.
• 9. S.-L. Chen, T.-T. Hwang, C. L. Liu: A technology mapping algorithm for CPLD architectures, IEEE International Conference on Field Programmable Technology, Hong Kong, 2002, pp. 204-210.
• 10. J. Kim, S. Byun, H. Kim: Development of technology mapping algorithm for CPLD under time constraint, 6th International Conference on VLSI and CAD, ICVC'99, 1999, pp. 411-414.
• 11. H.-S. Kim, J.-J. Kim, C.-H. Lin: An efficient CPLD technology mapping under the time constraint, Proceedings of the 12th International Conference on Microelectronics, ICM 2000, 2000, pp. 265 -268.
• 12. J. L. Kouloheris, A. El Gamal: PLA-based FPGA Area Versus Cell C+ Granularity, Proceedings of the IEEE Custom Integrated Circuits Conference, 1992, pp. 4.3.1-4.3.4.
• 13. K. Yan: Logic synthesis for CPLDs and FPGAs with PLA-style logic blocks, Fourteenth In-ternational Conference on VLSI Design, 2001, pp. 291-297.
• 14. K. Yan: Practical logic synthesis for CPLDs and FPGAs with PLA-style logic blocks, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC 2001, 2001, pp. 231-234.
• 15. R. E. Bryant: Graph Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, Vol. C-35, No. 8, 1986, pp. 677-691.
• 16. D. Kania, J. Kulisz, A. Milik: A novel method of two-stage decomposition dedicated for PAL-based CPLDs, Digital System Design, Proceedings. 8th Euromicro Conference, 2005, pp. 114-121.
• 17. S. B. Akers: Functional Testing with Binary Decision Diagrams, Eighth Annual Conference on Fault-Tolerant Computing, 1978, pp. 75-82.
• 18. K. S. Brace, R. L. Rudell, R. E. Bryant: Efficient implementation of a BDD package, 27th ACM/IEEE Design Automation Conference, 1990, pp. 40-45.
• 19. S. Minato: Binary Decision Diagrams and Applications for VLSI CAD. Kluwer Academic Publishers, 1996.
• 20. R. Ebend, G. Fey, R. Drechsler: Advanced BDD Optimization. Springer, Dordrecht, 2005.
• 21. R. Rudell: Dynamic variable ordering for ordered decision diagram, IEEE International Conference on Computer-Aided Design, 1993, pp. 42-47.