The effect of LUT and cluster size on deep-submicron FPGA performance and density

ABSTRACT

We use a fully timing-driven experimental flow [4] [15] in which a set of benchmark circuits are synthesized into different cluster-based [2] [3] [15] logic block architectures, which contain groups of LUTs and flip-flops. We look across all architectures with LUT sizes in the range of 2 inputs to 7 inputs, and cluster size from 1 to 10 LUTs. In order to judge the quality of the architecture we do both detailed circuit level design and measure the demand of routing resources for every circuit in each architecture. These experiments have resulted in several key contributions. First, we have experimentally determined the relationship between the number of inputs required for a cluster as a function of the LUT size (K) and cluster size (N). Second, contrary to previous results, we have shown that when the cluster size is greater than four, that smaller LUTs (size 2 and 3) are almost as area efficient as 4-input LUTs, as suggested in [11]. However, our results also show that the performance of FPGAs with these small LUT sizes is significantly worse (by almost a factor of 2) than larger LUTs. Hence, as measured by area-delay product, or by performance, these would be a bad choice. Also, we have discovered that LUT sizes of 5 and 6 produce much better area results than were previously believed. Finally, our results show that a LUT size of 4 to 6 and cluster size of between 4 and 10 provides the best area-delay product for an FPGA.

REFERENCES

• 1: Om Agrawal , Herman Chang , Brad Sharpe-Geisler , Nick Schmitz , Bai Nguyen , Jack Wong , Giap Tran , Fabiano Fontana , Bill Harding, An innovative, segmented high performance FPGA family with variable-grain-architecture and wide-gating functions, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.17-26, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296422]
• 2: V. Betz and J. Rose, "Cluster-Based Logic Blocks for FPGAs: Area-Efficiency vs. Input Sharing and Size", IEEE Custom Integrated Circuits Conference, Santa Clam, CA, 1997, pp. 551- 554.
• 3: Vaughn Betz , Jonathan Rose, How Much Logic Should Go in an FPGA Logic Block?, IEEE Design & Test, v.15 n.1, p.10-15, January 1998 [doi>10.1109/54.655177]
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• 6: Stephen Brown , Jonathan Rose, FPGA and CPLD Architectures: A Tutorial, IEEE Design & Test, v.13 n.2, p.42-57, June 1996 [doi>10.1109/54.500200]
• 7: Kevin Chung, PhD Thesis: "Architecture and Synthesis of Field-Programmable Gate Arrays with Hardwired Connections", University of Toronto, 1994.
• 8: J.Cong and Y.Ding,"FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs", IEEE Trans. on CAD, Jan. 1994, pp.l-12.
• 9: Jason Cong , Yean-Yow Hwang, Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.27-34, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275116]
• 10: D. Hill and N-S Woo, "The Benefits of Flexibility in Look-up Table FPGAs', in FPGAs, W. Moore and W. Luk Eds., Abingdon 1991, edited from the Oxford 1991 International Workshop on FPGAs, pp. 127-136.
• 11: Sinan Kaptanoglu , Greg Bakker , Arun Kundu , Ivan Corneillet , Ben Ting, A new high density and very low cost reprogrammable FPGA architecture, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.3-12, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296405]
• 12: J. Kouloheris and A.EI Gamal, "FPGA Performance vs. Cell Granularity", Proc. of Custom Integrated Circuits Conference, May 1991, pp. 6.2.1 - 6.2.4.
• 13: J. Kouioheris and A.EI Gamal, "FPGA Area vs. Cell Granularity - Lookup Tables and PLA Cells", First ACM Workshop on FPGA's, FPGA '92, Berkeley, CA, February 1992.
• 14: J. Kouioheris and A.EI Gamal, "FPGA Area vs. Cell Granularity - PLA Cells", Proc. of Custom Integrated Circuits Conference, May 1992.
• 15: A. Ma~uardt, "M.A.Sc Thesis: Cluster-Based Architecture, Timing-Driven Packing, and Timing-Driven Placement for FP- GAs", University of Toronto, 1999.
• 16: Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
• 17: J. Rose, R.J. Francis, P. Chow and D. Lewis, "The Effect of Logic Block Complexity on Area of Programmable Arrays", Proc. 1989 Custom Integrated Circuits Conference, May 1989, pp. 5.3.1-5.3.5.
• 18: J. Rose, RJ. Francis, D. Lewis and P. Chow, "Architecture of Field-Programmable Gate Arrays: The Effect of Logic Functionality on Area Efficiency", IEEE Journal of Solid-State Circuils, 1990.
• 19: Adel S. Sedra , Kenneth C. Smith, Microelectronic circuits, 2nd ed., Holt, Rinehart & Winston, Austin, TX, 1987
• 20: E.M, Sentovich et al, "SIS: A System for Sequential Circuit Analysis", Tech. Report No. UCB/ERL M92/41, University of California, Berkeley, 1990.
• 21: S. Singh, "The Effect of Logic Block Architecture on FPGA Performance", M.A.Sc. Thesis, University of Toronto, 1991.
• 22: S. Singh, J. Rose, P. Chow and D. Lewis, "The Effect of Logic Block Architecture on FPGA Performance", IEEE Journal of Solid-State Circuits, 1992.
• 23: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 24: S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0", Tech. Report, Microelectronics Centre of North Carolina, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

General Terms:
Design, Experimentation, Performance