Designing Efficient Input Interconnect Blocks for LUT Clusters Using Counting and Entropy

ABSTRACT

In a cluster-based FPGA, the interconnect from external routing tracks and cluster feedbacks to the LUT inputs consumes significant area, and no consensus has emerged among different implementations (e.g., 1-level or 2-level). In this paper, we model this interconnect as a unified input interconnect block (IIB). We identify three types of IIBs and develop general combinatorial techniques to count the number of distinct functional configurations for them. We use entropy, defined as the logarithm of this count, to estimate an IIB's routing flexibility. This enables us to analytically evaluate different IIBs without the customary time-consuming place and route experiments. We show that both depopulated 1-level IIBs and VPR-style 2-level IIBs achieve high routing flexibility but lack area efficiency. We propose a novel class of highly efficient, yet still simple, IIBs that use substantially fewer switches with only a small degradation in routing flexibility. Experimental results verify the routability of these IIBs, and confirm that entropy is a good predictor of routability.

REFERENCES

• 1: Ahmed, E. and Rose, J. 2004. The effect of LUT and cluster size on deep-submicron FPGA performance and density. IEEE Trans. on VLSI, 12, 288--298.
• 2: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 3: Brualdi, R. A. 1998. Introductory Combinatorics. Prentice Hall, Englewood Cliffs, NJ.
• 4: Yao-Wen Chang , D. F. Wong , C. K. Wong, Universal switch modules for FPGA design, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.80-101, Jan. 1996 [doi>10.1145/225871.225886]
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: André DeHon, Entropy, counting, and programmable interconnect, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.73-79, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228381]
• 7: Wenyi Feng , Jonathan W. Greene, Post-placement interconnect entropy: how many configuration bits does a programmable logic device need?, Proceedings of the 2006 international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany [doi>10.1145/1117278.1117289]
• 8: Michael Hutton, Interconnect prediction for programmable logic devices, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.125-131, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368816]
• 9: Lemieux, G., Lee, E., Tom, M., and Yu, A. 2004. Directional and single-driver wires in FPGA interconnect. In Proceedings of the International Conference on Field-Programmable Technology (FPT 2004), 41--48.
• 10: Guy Lemieux , David Lewis, Design of Interconnection Networks for Programmable Logic, Kluwer Academic Publishers, Norwell, MA, 2004
• 11: Leventis, P., Chan, M., Lewis, D., Nouban, B., Powell, G., Vest, B., Wong, M., Xia, R., and Costello, J. 2003. Cyclone: A low-cost, high-performance FPGA. In Proceedings of the IEEE 2003 Custom Integrated Circuits Conference (CICC 2003). 49--52.
• 12: David Lewis , Vaughn Betz , David Jefferson , Andy Lee , Chris Lane , Paul Leventis , Sandy Marquardt , Cameron McClintock , Bruce Pedersen , Giles Powell , Srinivas Reddy , Chris Wysocki , Richard Cliff , Jonathan Rose, The stratixπ routing and logic architecture, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611821]
• 13: Shannon, C. E. 1950. Memory requirements in a telephone exchange. In Bell Syst. Techn. J. 29, 343--349.
• 14: Xilinx Inc. 2001. Virtex-II Field-Programmable Gate Arrays. San Jose, CA. Web site: http://www.xilinx.com.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Design, Theory

Keywords:
FPGAs, LUT, PLDs, cluster, counting, entropy, interconnect