An architecture-driven metric for simultaneous placement and global routing for FPGAs

ABSTRACT

FPGA routing resources typically consist of segments of various lengths. Due to the segmented routing architectures, the traditional measure of wiring cost (wirelength, delay, congestion, etc) based on geometric distance and/or channel density is no longer accurate for FPGAs. Researchers have shown that the number of segments, instead of geometric (Manhattan) distance, traveled by a net is the most crucial factor in controlling the routing delay and cost in an FPGA. Further, the congestion information of a routing channel shall be measured by the available segments of specific lengths, instead of the density in a channel alone. In this paper, we propose an architecture-driven metric for simultaneous FPGA placement and global routing. The new metric considers the available segments and their lengths to optimize the wiring cost for placement and global routing. Experiments by employing a cluster growth placement and maze routing to demonstrate the new metric show respective average reductions of 8%, 20%, and 19% in the number of tracks used (area), maximum net delay, and average net delay based on the Lucent Technologies ORCA2C-like and the Xilinx XC4000EX-like architectures, compared with the traditional metric of geometric distance and channel density.

REFERENCES

• 1: Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, Performance-oriented placement and routing for field-programmable gate arrays, Proceedings of the conference on European design automation, p.80-85, September 18-22, 1995, Brighton, England
• 2: Michael J. Alexander , Gabriel Robins, New performance-driven FPGA routing algorithms, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.562-567, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217589]
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: S. Brown, G. Lemieux, and M. Khellah, "Segmented routing for speedperformance and routability in field-programmable gate arrays", Journal of VLSI Design, 4(4), pp. 275-291, 1996.
• 5: Yao-Wen Chang , Shashidhar Thakur , Kai Zhu , D. F. Wong, A new global routing algorithm for FPGAs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.356-361, November 06-10, 1994, San Jose, California, United States
• 6: Yao-Wen Chang , Kai Zhu , D. F. Wong, Timing-driven routing for symmetrical array-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.433-450, July 2000 [doi>10.1145/348019.348101]
• 7: C. -D. Chen, Y. -S. Lee, C. -H. Wu, and Y. -L. Lin, "TRACER-fpga: a router for RAM-based FPGA's," IEEE Trans. on CAD, vol. 14, no. 3, pp. 371-374, Mar. 1995.
• 8: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 9: J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
• 10: M. Khellah, S. Brown, and Z. Vranesic, "Modelling routing delays in SRAM-based FPGAs," P1vc. of Canadian Conf. on VLSI, 1993.
• 11: C.Y. Lee, "An algorithm for path connection and its application", IRE Trans. Electlvnic Comput., Vol. EC-10, pp 346-365, 1961.
• 12: Yuh-sheng Lee , Allen C.-H. Wu, A performance and routablity driven router for FPGAs considering path delays, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.557-561, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217588]
• 13: Guy G. F. Lemieux , Stephen D. Brown , Daniel Vranesic, On two-step routing for FPGAS, Proceedings of the 1997 international symposium on Physical design, p.60-66, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267682]
• 14: Lucent Technologies Inc., ORCA OR2CxxA (5.0 V) and OR2TxxA (3.3 V) Series Field-Programmable Gate Arrays, Aug. 1996.
• 15: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 16: Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for island-style FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.332-338, November 05-09, 1995, San Jose, California, United States
• 17: S.K. Nag and R. A. Rutenbar, "Pertbrmance-driven simultaneous placement and routing for FPGA's," IEEE Trans. on Computer-Aided Design, Vol. 17, No. 6, pp. 499-518, June 1998.
• 18: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
• 19: Nozomu Togawa , Masao Sato , Tatsuo Ohtsuki, A simultaneous technology mapping, placement, and global routing algorithm for field-programmable gate arrays, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.156-163, November 06-10, 1994, San Jose, California, United States
• 20: Yu-Liang Wu , Malgorzata Marek-Sadowska, Orthogonal greedy coupling: a new optimization approach to 2-D FPGA routing, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.568-573, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217591]
• 21: Xilinx Inc., The P1vgrammable Logic Data Book, 1996.
• 22: K. Zhu, Y.-W. Chang, and D. F. Wong, "Timing-driven routing for symmetricalarray-based FPGAs," P~vc. oflCCD, October 1998.
• 23: K. Zhu and D. F. Wong, "Switch bound allocation for maximizing drRoutability in timing-driven routing of FPGA's," IEEE Trans. on CAD, vol. 17, no. 4, pp.316- 323, Apr. 1998.

INDEX TERMS

Primary Classification:
  J. Computer Applications

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
  B.8 Performance and Reliability

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