Interconnect complexity-aware FPGA placement using Rent's rule

ABSTRACT

Field Programmable Gate Arrays (FPGAs) have gained in commercial acceptance because they offer instant manufacturing turnaround and low costs. However, FPGAs are constantly hard pressed to keep up with the requirements of the more complex and larger scale circuits which are being targeted for them. Routability of a circuit depends on the FPGA architecture, the placement, and the interconnection complexity of the circuit to be placed and routed. This paper explores the use of Rent's rule as a complexity metric for improving the placement of circuits on a target FPGA architecture, such that routing resource utilization is improved. A new simulated annealing based placement algorithm is presented and experimental results are presented to illustrate the validity of the approach for certain example circuits and the ISCAS benchmarks.

REFERENCES

• 1: Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, An architecture-independent approach to FPGA routing based on multi-weighted graphs, Proceedings of the conference on European design automation, p.259-264, September 19-23, 1994, Grenoble, France
• 2: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 3: S. Brown, J. Rose, and Z.G. Vranesic. A stochastic model to predict the routability of field-programmable gate arrays. IEEE Trans. on CAD, pages 1827-1838, Dec 1993.
• 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: 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]
• 6: S. Devadas. Optimal Layout via Boolean Satisfiability. In ICCAD, pages 294-297, Nov. 1989.
• 7: W.E. Donath. Placement and average interconnection requirements of computer logic. IEEE Trans. on Circuits and Systems, CAS-26:272-277, 1979.
• 8: A.A. El. Gamal. Two-dimensional stochastic model for interconnections in master-slice integrated circuits. IEEE Transactions on Circuits and Systems, CAS-28:127-138, Feb 1981.
• 9: L. Hagen , F. J. Kurdahi , C. Ramachandran , A. B. Kahng, On the intrinsic rent parameter and spectra-based partitioning methodologies, Proceedings of the conference on European design automation, p.202-208, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 10: S. Kirkpatrick, C.D. Gelatt, and M.P Vecchi. Optimization by Simulated Annealing. Science, 220:671-680, 1983.
• 11: B.S. Landman and R.L. Russo. On a pin versus block relationship for partitions of logic graphs. IEEE Trans. on Computers, C-20:1469-1479, 1971.
• 12: H. Van Marck, D. Stroobandt, and J. Van Campenhout. Toward an extension of rent's rule for describing local variations in interconnection complexity. InProc. of 4th Intl. Conference for Young Computer Scientists, pages 136-141, 1995.
• 13: D. Stroobandt, P. Verplaetse, and J. Van Campenhout. Generating Synthetic Benchmark circuits for evaluating CAD tools. IEEE Trans. on CAD, 19(9):1011-1022, September 2000.
• 14: R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.119-125, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258322]
• 15: Yu-Liang Wu , Douglas Chang, On the NP-completeness of regular 2-D FPGA routing architectures and a novel solution, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.362-366, November 06-10, 1994, San Jose, California, United States
• 16: Y.L. Wu, S. Tsukiyama, and M. Marek-Sadowska. Graph based analysis of 2-d fpga routing. IEEE Trans. on CAD, (1):33-44, Jan 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
      B.7.2 Design Aids
          Subjects: Placement and routing

  C. Computer Systems Organization

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

Keywords:
Rent's exponent, interconnect, placement