RPack: routability-driven packing for cluster-based FPGAs

ABSTRACT

Routing tools consume a significant portion of the total design time. Considering routability at earlier steps of the CAD flow would both yield better quality and faster design process. In this paper we are presenting a routability-driven clustering method for cluster-based FPGAs. Our method packs LUTs into logic clusters while incorporating routability metrics into a cost function. The objective is to minimize this routability cost function . Our cost function is consistently able to indicate improved routability. Our method yields up to 50 % improvement over existing clustering methods in terms of the number of routing tracks required. The average improvement obtained is 16.5 %. Reduction in number of tracks yields reduced routing area.

REFERENCES

• 1: Elias Ahmed , Jonathan Rose, The effect of LUT and cluster size on deep-submicron FPGA performance and density, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.3-12, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329171]
• 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: 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]
• 4: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 5: N. Bhat, D. Hill, "Routable Technology Mapping for FPGAs," First International Workshop on FPGAs, pp. 143-148, Feb. 1992.
• 6: M. Schlag, J. Kong, P. K. Chan, "Routability-Driven Technology Mapping for Lookup Table-Based FPGAs," IEEE Transactions on CAD, Vol. 13, pp.13-26, Jan 1994.
• 7: Andrew E. Caldwell , Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Alex Zelikovsky, On wirelength estimations for row-based placement, Proceedings of the 1998 international symposium on Physical design, p.4-11, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274536]
• 8: J. Cong, Y. Ding, " FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Design," IEEE Trans. on Computer-Aided Design, Vol.13, No.1, pp. 1-12,Jan. 1994.
• 9: E. M. Sentovich, et al, "SIS: A System for Sequential Analysis," Tech. Report No. UCD/ERL M92/41 , University of California, Berkeley, 1992.
• 10: S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0," Tech. Report, Microelectronics Center of North Carolina, 1991.

INDEX TERMS

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

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

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Design, Measurement, Performance, Theory