Technology mapping issues for an FPGA with lookup tables and PLA-like blocks

ABSTRACT

In this paper we present new technology mapping algorithms for use in a programmable logic device (PLD) that contains both lookup tables (LUTs) and PLA-like blocks. The technology mapping algorithms partially collapse circuits to reduce either area or depth, and pack the circuits into a minimum number of LUTs and PLA-like blocks. Since no other technology mapping algorithm for this problem has been previously published, we cannot compare our approach to others. Instead, to illustrate the importance of this problem we use our algorithms to investigate the benefits provided by a PLD architecture with both LUTs and PLA-like blocks compared to a traditional LUT-based FPGA. The experimental results indicate that our mixed PLD architecture is more area-efficient than LUT-based FPGAs by up to 29%, or more depth-efficient by up to 75%.1

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: Frank Heile , Andrew Leaver, Hybrid product term and LUT based architectures using embedded memory blocks, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.13-16, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296415]
• 3: J. Cong and Y. Ding, "'FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," IEEE trans, on CAD of integrated circuits and systems, January 1994.
• 4: 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]
• 5: A.H. Farrahi and M. Sarrafzadeh, "Complexity of the Lookup-Table Minimization Problem for FPGA Technology Mapping," IEEE trans, on computer-aided design of integrated eirenits and systems, Nov. 1994.
• 6: A. Kaviani, "Novel Architectures and Synthesis Methods for High Capacity Field Programmable Devices," Ph.D. dissertation 1999
• 7: Alireza Kaviani , Stephen Brown, The Hybrid Field-Programmable Architecture, IEEE Design & Test, v.16 n.2, p.74-83, April 1999 [doi>10.1109/54.765206]
• 8: J. L. Kouloheris and A. E1 Gamal, "PLA-based FPGA Area vs. Cell Granularity," Proceedings of the 1992 Custom Integrated Circuits Conference, pp. 4.31-4.3.4.
• 9: E. L. Lawler, K. L. Levitt, and J. Turner, "Module CluS- tering to Minimize Delay in Digital Networks," IEEE trans, on Computers, Jan. 1969, pp. 47-57.
• 10: E. M. Sentovich et al., "SIS: A System for Sequential Circuit Synthesis," Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41.
• 11: H. Touati, H. Savoj, R. Brayton, "Delay optimization of Combinational Logic Circuits by Clustering and Partial Collapsing," IEEE Conference on Computer-Aided Design, 1991, pp. 188-191.
• 12: Xilinx data book.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Experimentation, Theory