Performance-driven mapping for CPLD architectures

ABSTRACT

In this paper we present a performance-driven mapping algorithm, PLAmap, for CPLD architectures which consist of a large number of PLA-style logic cells. The primary goal of our mapping algorithm is to minimize the depth of the mapped circuit. Meanwhile, we have successfully reduced the area of the mapped circuits by applying several heuristic techniques, including threshold control of PLA fanouts and product terms, slack-time relaxation, and PLA-packing. We compare our PLAmap with a recently-published algorithm TEMPLA [1] and a commercial tool, Altera's MAX+PLUS II [16]. Experimental results on various MCNC benchmarks show that overall TEMPLA uses 8 to 11% less area at the cost of 96 to 106% more mapping depth, and MAX+PLUS II uses 12% less area but 58% more delay compared with our mapper.

REFERENCES

• 1: Jason Helge Anderson , Stephen Dean Brown, Technology mapping for large complex PLDs, Proceedings of the 35th annual conference on Design automation, p.698-703, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277220]
• 2: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 3: J. Cong and Y. Ding, FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs", IEEE Trans. on Computer-Aided Design, Jan. 1994, Vol. 13, No. 1, pp.1- 12.
• 4: J. Cong and Y. Ding, On Area/Depth Trade-off in LUT-based FPGA Technology Mapping", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.2, (no.2), June 1994. pp.137-148.
• 5: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 6: Jason Cong , Songjie Xu, Invited talk: synthesis challenges for next-generation high-performance and high-density PLDs, Proceedings of the 2000 conference on Asia South Pacific design automation, p.157-162, January 2000, Yokohama, Japan [doi>10.1145/368434.368596]
• 7: Jason Cong , Hui Huang , Xin Yuan, Technology mapping for k/m-macrocell based FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.51-59, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329179]
• 8: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 9: Zafar Hasan , David Harrison , Maciej Ciesielski, A Fast Partitioning Method for PLA-Based FPGAs, IEEE Design & Test, v.9 n.4, p.34-39, October 1992 [doi>10.1109/54.173331]
• 10: Sunil P. Khatri , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Cross-talk immune VLSI design using a network of PLAs embedded in a regular layout fabric, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 11: J.L. Kouloheris and A. El Gamal, FPGA Performance vs. Cell granularity", Proc. Custom Integrated Circuits Conference, 1991, pp.621-624.
• 12: J.L. Kouloheris, Empirical Study of the Effect of Cell Granularity on FPGA Density andPerformance", PhD thesis, Stanford University, 1993.
• 13: E.L. Lawler, K.N. Levitt, and J. Turner, Module Clustering to Minimize Delay in Digital Networks", IEEE Trans. on Computers, Vol. C18(1), Jan. 1969, pp.47-57.
• 14: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 15: Ellen Sentovich, et.al., SIS: A System for Sequential Circuit Synthesis", Electronics Research Lab., Memo. No. UCB/ERL M92/41, 1992.
• 16: MAX 7000B, Programmable Logic Device Family, the Altera Data Book, Altera Corporation, February 2000.
• 17: Understanding MAX 7000 Timing, Application Note 94, Altera Corporation, May 1999.
• 18: The Cypress Data Book, Cypress Semiconductor Corporation, Aug. 2000.
• 19: The Lattice Data Book, Lattice Semiconductor Corporation, July 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

General Terms:
Algorithms, Design, Performance

Keywords:
CPLD, FPGA, PLA-style logic cells, delay optimization, technology mapping