Placement rent exponent calculation methods, temporal behaviour and FPGA architecture evaluation

ABSTRACT

In the design of FPGA architectures, it is important to understand wiring requirements of placed circuits. Rent's Rule is an empirical metric of connectivity and congestion in a circuit that has applications in the prediction of interconnect usage.Traditional methods of calculating Rent exponents are based on recursive partitioning, with the exception of some recent work [21], [22] that defines an alternative Rent exponent of a circuit based on a placement-induced partitioning tree.In this paper we take a different look at the calculation of Rent exponents in placement, contrasting several different methods empirically and outlining the relevant biases in each. We will compare the Rent exponent observed for timing-driven vs. purely congestion-driven placement algorithms, and for different types of benchmark circuits. We also observe the temporal behaviour of Rent exponents through a simulated annealing placement and its correlation to the placement cost function and wirelength. Finally we apply the empirical results to the analysis of the Cyclone FPGA architecture and comment on the routability of the device.

REFERENCES

• 1: Altera Corp. "Cyclone Family Data-Sheet". Available at www.altera.com.
• 2: V. Betz, "Directional Bias and Non-Uniformity in FPGA Global Routing Architectures", IEEE TVLSI, pp. 445--456, Sept. 1998.
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: Pak K. Chan , Martine D. F. Schlag , Jason Y. Zien, On routability prediction for field-programmable gate arrays, Proceedings of the 30th international conference on Design automation, p.326-330, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164915]
• 5: T. Chiba, "Impact of the LSI on high-speed computer packaging," IEEE Trans. Comput., Vol C-27, pp. 319--325, 1978.
• 6: Phillip Christie, Rent exponent prediction methods, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.679-688, Dec. 2000 [doi>10.1109/92.902262]
• 7: Philip Christie , Dirk Stroobandt, The interpretation and application of Rent's rule, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.639-648, Dec. 2000 [doi>10.1109/92.902258]
• 8: J Dambre , P. Verplaetse , D. Stroobandt , J. Van Campenhout, Getting more out of Donath's hierarchical model for interconnect prediction, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505351]
• 9: J. Davis, V. De and J. Meindl, "A stochastic wire-length distribution for gigascale integration (GSI): Part II: Application to clock frequency, power dissipation and chip-size estimation," IEEE Trans. Electron Devices, Vol. 45. pp 590--597. Mar, 1998.
• 10: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 11: W.E. Donath, "Placement and Average Interconnection Lengths of Computer Logic." IEEE Trans. Circuits and Systems, Vol 26(4), pp. 272--277, 1979.
• 12: M. Feuer, "Connectivity of Random Logic", IEEE Trans. On Computers, Vol C-31, pp. 29--33, 1982.
• 13: L. Hagen, A.B. Kahng, F.J. Kurdahi and C. Ramachandran, "On the Intrinsic Rent Parameter and Spectra-Based Partitioning Methodologies." IEEE Trans. CAD. Vol 13:1, pp. 27--37, 1994.
• 14: 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]
• 15: B Landman and R. Russo, "On a Pin vs. Block Relationship for Partitions of Logic Graphs." IEEE Trans. On Computers, Vol. C-20. pp 1469--1479, 1971.
• 16: Amit Singh , Malgorzata Marek-Sadowska, FPGA interconnect planning, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505353]
• 17: D. Stroobandt, A Priori Wire Length Estimates for Digital Design, Kluwer, 2001.
• 18: Dirk Stroobandt, A priori system-level interconnect prediction: Rent's rule and wire length distribution models, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.3-21, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368645]
• 19: Dirk Stroobandt, On an Efficient Method for Estimating the Interconnection Complexity of Designs and on the Existence of Region III in Rent's Rule, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.330, March 04-06, 1999
• 20: P. Verplaetse, J. Van Campenhout and D. Stroobandt. "On Synthetic Benchmark Generation Methods." In Proc. Intl. Symp. On Circuits and Systems (ISCAS) pp. IV 213--216, May 2000.
• 21: 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]
• 22: Xiaojian Yang , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Wirelength estimation based on rent exponents of partitioning and placement, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.25-31, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368658]
• 23: Payman Zarkesh-Ha , Jeffrey A. Davis , James D. Meindl, Prediction of net-length distribution for global interconnects in a heterogeneous system-on-a-chip, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.6, p.649-659, Dec. 2000 [doi>10.1109/92.902259]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Experimentation, Measurement, Theory

Keywords:
FPGA architecture, SLIP, interconnect prediction, rent