Logic synthesis dedicated for CPLD circuits

Kania, D.; Milik, A.; Kulisz, J.; Opara, A.; Czerwiński, R.

Artykuł - szczegóły

Tytuł artykułu

Logic synthesis dedicated for CPLD circuits

Autorzy

Kania D. , Milik A. , Kulisz J. , Opara A. , Czerwiński R.

Wybrane pełne teksty z tego czasopisma

http://ijet.pl/index.php/ijet

Identyfikatory

Warianty tytułu

Konferencja

Digital Control Units Design ; 6.03.2009 ; Zielona Góra, Poland

Języki publikacji

Abstrakty

The paper presents synthesis strategies for PAL-based devices. All component methods used in presented strategies are originally developed. In this paper the essentials of all methods have been presented. Exact algorithms descriptions can be found in referenced materials. The optimization of synthesis methods were aimed toward required areas minimization or propagation delay minimization (reducing number of levels). A low computation complexity of synthesis methods that use tri-state output buffers or output graphs make them useful as additional steps of complex synthesis strategies. Application of those methods can radically reduce areas or propagation delay. Without doubt the best results in terms of required surface can be obtained by methods that use decomposition components. Decomposition methods that extend classical model of functional decomposition (Curtis' decomposition - row based and column based decompositions) are computing demanding procedures. The binary decision diagram was taken into consideration in order to increase computation performance/efficiency. The experience that has been gained in implementation of column and row based decomposition allows to implement efficient partitioning procedures for the BDD. Decomposition results for the BDD methods are slightly worse as referenced to previous approaches. The synthesis process is computation efficient and allows to decompose complex logic circuits in reasonable amount of time. The exploration of BDD decomposition methods shows their undiscovered potential that still can be developed especially for decomposition of function consisting of few hundred of input and output variables. Several years' of experience in design of decomposition procedures for CPLD allows developing complex synthesis strategies that have been presented as summary of the paper. They are dedicated for different CPLD families addressing different features (e.g. three-state output buffers) and requirements (e.g. propagation time constraint).

Słowa kluczowe

logic synthesis CPLD decomposition technology mapping

Wydawca

Polish Academy of Sciences, Committee of Electronics and Telecommunication

Czasopismo

Electronics and Telecommunications Quarterly

Rocznik

2009

Tom

Vol. 55, No 2

Strony

287--315

Opis fizyczny

Bibliogr. 67 poz., wykr.

Twórcy

autor

Kania D.

autor

Milik A.

autor

Kulisz J.

autor

Opara A.

autor

Czerwiński R.

Politechnika Śląska, Instytut Elektroniki, dkania@pdsi.pl

Bibliografia

1. 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, October 1996, pp. 1226-1235
2. A. Dzikowski, E. Hrynkiewicz: Złożona dekompozycja obszarowa zespołu funkcji logicznych z wykorzystaniem diagramów ROBDD. Krajowa Konferencja Elektroniki KKE'03, Kołobrzeg (Poland), Czerwiec 2003, tom II, ss. 393 398
3. Y. Lai, K. R. Pan, M. Pedram: OBDD-Based Function Decomposition: Algorithms and Implementation. IEEE Transactions on Computer-Aided Design, Vol. 15, No. 8, August 1996, pp. 977-990
4. M. Rawski, H. Selvaraj, T. Łuba, P. Szotkowski: Application of symbolic functional decomposition concept in FSM implementation targeting FPGA devices. Sixth International Conference on Computational Intelligence and Multimedia Applications, 2005, Aug. 2005, pp. 153-158.
5. C. Scholl: Functional Decomposition with Application to FPGA Synthesis. Kluwer Academic Publishers, Boston, 2001
6. H. Selveraj, T. Łuba, M. Nowicka, B. Bignall: Multiple-valued decomposition and ils applications in data compression and technology mapping. Proceedings of ICCIMA'97, Gold Coast (Australia), 1997, pp. 42-48
7. C. Yang, M. Ciesielski: BDS: A BDD-Based Logic Optimization System. IEEE Transactions on CAD of Integrated Circuits and Systems, Vol. 21, No. 7, July 2002, pp. 866-876.
8. M. Adamski, A. Barkalov: Architectural and Sequential Synthesis of Digital Devices. University of Zielona Góra Press, 2006.
9. J. H. Anderson, S. D. Brown: Technology mapping for large complex PLDs. Proceedings of Design Automation Conference, DAC'98, January 1998, pp. 698-703.
10. A. Barkalov, L. Titarenko, S. Chmielewski: Reduction in the number of PAL macrocells in the circuit of a Moore FSM. International Journal of Applied Mathematics and Computer Science, Number 4, Volume 17, 2007.
11. 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, December 2002,pp. 204-210.
12. S. Deniziak, K. Sapiecha: An Efficient Algorithm of Perfect State Encoding for CPLD Based Systems. IEEE Workshop on Design and Diagnostic of Electronic Circuits and Systems, DDECS'1998, Szczyrk (Poland) 1998, pp. 47-53.
13. 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.
14. H-S. Kim, J-J. Kim, Ch-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.
15. J-J. Kim, H-S. Kim, Ch-H. Lin: A new technology mapping for CPLD under the time constraint. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC'01, 2001, pp. 235-238.
16. A. Kaviani, S. Brown: Technology mapping issues for an FPGA with lookup tables and PLA-like blocks. Proceedings of the 2000 ACM/SIGDA Eighth International Symposium on Field Programmable Gate Arrays, Monterey, 2000, pp. 60-66.
17. V. Salauyou, A. Klimowicz, T. Grześ, T. Dimitrova-Grekow, I. Bulatowa: Badania efektywności metod syntezy automatów skończonych zaimplementowanych w pakiecie ŻUBR. Miesięcznik Naukowo-Techniczny “Pomiary Automatyka Kontrola” nr 6 bis, 2006, ss. 44-46.
18. W. Sołowjew: Synthesis of sequential circuits on programmable logic devices based on new models of finite state machines. Proceedings of the EUROMICRO Conference on Digital Systems Design, 2001, pp. 170-173.
19. J. L. Kouloheris, A. E. Gamal: FPGA performance versus cell granularity. Proceedings of the IEEE Custom Integrated Circuits Conference, May 1991, pp. 6.2/1-6.2/4
20. J. L. Kouloheris, A. E. Gamal: PLA-based FPGA Area Versus Cell C+ Granularity. Proceedings of the IEEE Custom Integrated Circuits Conference, May 1992, pp. 4.3.1-4.3.4.
21. K. Yan: Logic synthesis for CPLDs and FPGAs with PLA-style logic blocks. Fourteenth International Conference on VLSI Design, 2001, pp. 291-297.
22. 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.
23. K. C. Chen, S. Muroga: Input assignment algorithm for decoded-PLAs with multi-input decoders. IEEE International Conference on Computer-Aided Design, ICCAD'88, Digest of Technical Papers, November 1988, pp. 474-477.
24. M. J. Ciesielski, S. Yan g: PLADE: A two-stage PLA decomposition. IEEE Trans. on Computer-Aided Design, Vol. 11, No. 8, 1992, pp. 943 954.
25. S. Devadas, A. R. Wang, A. R. Newton, A. Sangiovanni-Vincentelli: Boolean Decomposition of Programmable Logic Arrays. IEEE Custom Integrated Circuits Conference, May 1988, pp. 2.5.1-2.5.5.
26. S. Devadas, A. R. Wang, A. R. Newton, A. Sangiovanni-Vincentelli: Boolean decomposition in multi-level logic optimization. Digest of Technical Papers, IEEE International Conference on Computer-Aided Design, ICCAD-88, Nov 1988, pp. 290-293.
27. C. Yang, M. J. Ciesielski: PLA decomposition with generalized decoders. IEEE International Conference on Computer-Aided Design, ICCAD-89, Nov 1989, pp. 312-315.
28. D. Kania: Two-level logic synthesis on PALs. Electronics Letters, 1999, Vol. 35, No. 11, pp. 879-880.
29. D. Kania: Two-level logic synthesis on PAL-based CPLD and FPGA using decomposition. Proceedings of 25-th Euromicro Conference, IEEE Computer Society Press, Milan (Italy), 1999, pp. 278-281.
30. D. Kania: Multi-level logic synthesis on PAL-based devices with three state output buffers. Kwartalnik Elektroniki i Telekomunikacji, 2000, 46, z. 1, pp. 81-90.
31. D. Kania: Logic synthesis on PAL-based devices containing output buffers. Kwartalnik Elektroniki i Telekomunikacji, 2002, 48, z. 1, pp. 53-66
32. D. Kania: A p-stage Logic Synthesis for PAL-based Devices. Kwartalnik Elektroniki i Telekomunikacji, 2004, 50, z. 1, pp. 65-86.
33. D. Kania: The Logic Synthesis for the PAL-based Complex Programmable Logic Devices, Zeszyty Naukowe Politechniki Śląskiej, Nr 1619, Wydawnictwo Politechniki Śląskiej, Gliwice 2004.
34. D. Kania: A New Approach to Logic Synthesis of Multi-Output Boolean Functions on PAL-based CPLDs. Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI'07 Stressa - Lago Maggiore (Italy), March 2007, pp. 152-155.
35. D. Kania: Method for Efficient Implementation of Multiple-Output Function in PAL-based Devices. Kwartalnik Elektroniki i Telekomunikacji, 1999, 45, z. 3-4, pp. 433-444.
36. D. Kania: A technology mapping algorithm for MACH devices. Kwartalnik Elektroniki i Telekomunikacji, 2001, 47, z. 1, pp. 65-74.
37. D. Kania: Improved Technology Mapping for PAL-based Devices Using a New Approach to Multi-Output Boolean Functions. DATE 02, IEEE Computer Society, Los Alamitos, 2002, p. 1087.
38. D. Kania: Logic Synthesis of Multi-Output Functions for PAL-based CPLDs. IEEE International Conference on Field-Programmable Technology, Hong Kong, December 2002, pp. 429-432.
39. D. Kania: An Efficient Approach to Synthesis of Multi-Output Boolean Functions on PAL-based Devices. IEE Proceedings on Computer and Digital Techniques, Vol. 150, No. 3, May 2003, pp. 143-149.
40. S. Devadas, A. R. Newton: Exact Algorithms for Output Encoding, State Assignment, and Four-Level Boolean Minimization. IEEE Transactions on Computer-Aided Design, Vol. 10, No. 1, January 1991.
41. D. Kania: An Efficient Algorithm for Output Coding in PAL-based CPLDs. International Journal of Engineering, Vol. 15, No. 4, November 2002, pp. 325-328.
42. G. Micheli: Synthesis and optimization of digital circuits. McGrew-Hill, Inc., 1994.
43. Ch. J. Shi, J. A. Brzozowski: An Efficient Algorithm for Constrained Encoding and its Applications. IEEE Trans. on CAD, Vol. 12, No. 12, December 1993, pp. 1813-1826.
44. H. A. Curtis: The Design of switching Circuits. D.van Nostrand Company, Inc., Princeton, New Jersey, Toronto, New York, 1962.
45. D. Kania: Method for calculation of column multiplicity dedicated for CPLDs. Archiwum Informatyki Teoretycznej i Stosowanej, Tom 17, z. 1, 2005, pp. 65-76.
46. D. Kania: Coding capacity of programmable transcoder. Kwartalnik Elektroniki i Telekomunikacji, 1998, 44, z. 2, pp. 193-204.
47. D. Kania: Coding Capacity of PAL-based Programmable Transcoder with Uneven Number Terms per Output. Kwartalnik Elektroniki i Telekomunikacji, 1999, 45, z. 1, pp.73-84.
48. D. Kania: Coding capacity of PAL-based logic blocks included in CPLDs and FPGAs. IFAC Workshop on Programmable Devices and Systems, PDS 2000, Ostrava, February 2000, Published for the IFAC by PERGAMON, An Imprint of Elsevier Science, 2000, pp. 164-169.
49. D. Kania, A. Milik, J. Kulisz: Decomposition of Multiple-Output Functions for CPLDs. Proceedings of Euromicro Symposium on Digital System Design, IEEE Computer Society Press, Porto, September, 2005, pp. 442-449.
50. D. Kania: Logic Decomposition for CPLD Synthesis. IFAC Workshop on Programmable Devices and Systems, PDS 2000, Ostrava, February 2000, Published for the IFAC by PERGAMON, An Imprint of Elsevier Science, 2000, pp. 49-52.
51. D. Kania: Decomposition-based synthesis and its application in PAL-oriented technology mapping. Proceedings of 26th Euromicro Conference, IEEE Computer Society Press, Maastricht, 2000, pp. 138-145.
52. D. Kania, J. Kulisz: The row incompatibility and complement graph - a novel concept of graph for decomposition. Programmable Devices and Embedded Systems, PDES 2006, Brno, February 2006, pp. 169-173.
53. D. Kania, J. Kulisz, A. Milik: A novel method of two-stage decomposition dedicated for PAL-based CPLDs. Proceedings of Euromicro Symposium on Digital System Design, IEEE Computer Society Press, Porto, September, 2005, pp. 114-121.
54. D. Kania: Row decomposition in logic synthesis for CPLDs. Kwartalnik Elektroniki i Telekomunikacji, Tom 52, z. 4, 2006, pp. 825-847.
55. D. Kania, J. Kulisz: A method of logic synthesis for PAL-based CPLD-s based on two-stage decomposition. Programmable Devices and Embedded Systems, PDES 2006, Brno, February 2006, pp. 163-168.
56. T. Sasao: FPGA Design by Generalized Functional Decomposition in Logic Synthesis and Optimization. Kluwer Academic Publishers, Boston/London/Dotdrecht, 1993.
57. A. Milik, D. Kania: Application of BDD in Logic Synthesis for PAL-based Devices. Pomiary, Automatyka, Kontrola vol. 53, nr 7, 2007, pp. 118-120.
58. A. Opara: Dekompozycyjne metody syntezy układów kombinacyjnych wykorzystujące binarne diagramy decyzyjne, Rozprawa doktorska, Politechnika Śląska, 2009.
59. Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University, http://www.cbl.ncsu/edu/
60. D. Kania: A technology mapping algorithm for PAL-based devices using multi-output function graphs. Proceedings of 26-th Euromicro Conference, IEEE Computer Society Press, Maastricht, 2000, pp. 146-153.
61. D. Kania, J. Kulisz: Logic synthesis for PAL-based CPLD-s based on two-stage decomposition. The Journal of Systems and Software 80, 2007, pp. 1129-1141.
62. A. Opara, D. Kania: Decomposition of multi-output function based on pseudo-MTBDD. Pomiary, Automatyka, Kontrola vol. 54, nr 8, 2008, pp. 496-498.
63. A. Opara, D. Kania: A Novel Non-Disjunctive Method for Decomposition of CPLDs. Kwartalnik Elektroniki i Telekomunikacji, Vol. 55, No. 1, 2009, pp. 95-111.
64. G. Saucier, P. Sicard, L. Bouchet: Multi-level synthesis on PAL's. Proc. European Design Automation Conference, Glasgow, March 1990, pp. 542-546.
65. G. Saucier, P. Sicard, L. Bouchet: Multi-level synthesis on programmable devices in the ASYL system. Euro ASIC '90, 1990, pp. 136-141.
66. R. Czerwiński: The FSMs state assignment for PAL-based matrix programmable structures. PhD Thesis, Gliwice, 2006.
67. R. Czerwiński, J. Kulisz: State machine description oriented towards effective usage of vendor-independent synthesis tools. IFAC Workshop on Programmable Devices and Embedded Systems 2009, PDES'09, February 2009, pp. 27-32

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BWA0-0041-0008