Post-placement interconnect entropy: how many configuration bits does a programmable logic device need?

ABSTRACT

We introduce the concept of post-placement interconnect entropy: the minimal number of bits required to describe a well-placed netlist, which has connection lengths distributed according to Rent's rule. The entropy is a function of the number N of cells in the netlist and the Rent exponent p. We derive an expression for the entropy per cell and show that it converges as N approaches infinity. The entropy provides an achievable lower bound on the number of configuration bits in a programmable logic device. Specific numerical values are computed for practical situations. For example, any scalable FPGA composed of 4-input lookup table cells would require 31 configuration bits per cell. We compare this to the actual number of configuration bits in a standard FPGA architecture. We generalize the bound to dimensions higher than two, and show that for any p there is an optimal dimension that minimizes the bound.

REFERENCES

• 1: http://www.actel.com/products/
• 2: http://www.altera.com/products/
• 3: http://www.latticesemi.com/products/
• 4: http://www.xilinx.com/products/
• 5: M. Alexander, J. Cohoon, J. Colflesh, J. Karro and G. Robins. Three-dimensional FPGAs. Proceedings of the IEEE International ASIC Conference, pp. 253--256, September, 1995.
• 6: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: J.A. Davis, V.K. De, and J.D. Meindl. A stochastic wire-length distribution for gigascale integration (GSI) -- PART I: derivation and validation. IEEE Trans. on Electron Devices, vol. 45, pp. 580--589, March, 1998.
• 9: 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]
• 10: André DeHon, Rent's rule based switching requirements, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.197-204, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368870]
• 11: W.E. Donath. Placement and average interconnection lengths of computer logic. IEEE Trans. on Circuits and Systems, vol. CAS-26, pp. 272--277, April, 1979.
• 12: W.E. Donath. Wire length distribution for placements of computer logic. IBM Journal of Research and Development, vol. 25, pp. 152--155, May, 1981.
• 13: B.S. Landman and R.L. Russo. On a pin versus block relationship for partitions of logic graphs. IEEE Trans. On Computers. vol. C-20, pp. 1469--1479, 1971.
• 14: Miriam Leeser , Waleed M. Meleis , Mankuan M. Vai , Silviu Chiricescu , Weidong Xu , Paul M. Zavracky, Rothko: A Three-Dimensional FPGA, IEEE Design & Test, v.15 n.1, p.16-23, January 1998 [doi>10.1109/54.655178]
• 15: Guy Lemieux , David Lewis, Design of Interconnection Networks for Programmable Logic, Kluwer Academic Publishers, Norwell, MA, 2004
• 16: Yohei Matsumoto , Akira Masaki, FPGAs with Multidimensional Switch Topology, IEICE - Transactions on Information and Systems, v.E88-D n.4, p.775-778, April 2005 [doi>10.1093/ietisy/e88-d.4.775]
• 17: Joachim Pistorius , Mike Hutton, Placement rent exponent calculation methods, temporal behaviour and FPGA architecture evaluation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639936]
• 18: Arifur Rahman , Shamik Das , Anantha P. Chandrakasan , Rafael Reif, Wiring requirement and three-dimensional integration technology for field programmable gate arrays, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.1, p.44-54, February 2003 [doi>10.1109/TVLSI.2003.810003]
• 19: Raphael Rubin , André DeHon, Design of FPGA interconnect for multilevel metalization, 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.611841]
• 20: H. Schmit. Extra dimensional island style FPGAs. Field Programmable Logic and Application (FPL 2003), pp. 406--415, September, 2003.
• 21: C.E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, vol. 27, pp. 379--423 and 623--656, July and October, 1948.
• 22: D. Stroobandt. A Priori Wire Length Estimates for Digital Design. Kluwer Academic Publichsers, 2001.
• 23: Dirk Stoobandt, Multi-terminal nets do change conventional wire length distribution models, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.41-48, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368679]
• 24: H. Van Marck and J. Van Campenhout. Modeling signal delay distribution in optoelectronic architectures. SPIE Proceedings: Optoelectronic Interconnects III, vol. 2400, pp. 267--276, SPIE, 1995.
• 25: P. Verplaetse , J. Dambre , D. Stroobandt , J. Van Campenhout, On partitioning vs. placement rent properties, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.33-40, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368665]

INDEX TERMS

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

General Terms:
Design, Theory

Keywords:
FPGAs, entropy, interconnect, lower bound, placement, programmable interconnect, rent's rule, switching requirement