A fast routability-driven router for FPGAs

ABSTRACT

Three factors are driving the demand for rapid FPGA compilation. First, as FPGAs have grown in logic capacity, the compile computation has grown more quickly than the compute power of the available computers. Second, there exists a subset of users who are willing to pay for very high speed compile with a decrease in quality of result, and accordingly being required to use a larger FPGA or use more real-estate on a given FPGA than is otherwise necessary. Third, very high speed compile has been a long-standing desire of those using FPGA-based custom computing machines, as they want compile times at least closer to those of regular computers.This paper focuses on the routing phase of the compile process, and in particular on routability-driven routing (as opposed to timing-driven routing). We present a routing algorithm and routing tool that has three unique capabilities relating to very high-speed compile:For a “low stress” routing problem (which we define as the case where the track supply is at least 10% greater than the minimun number of tracks per channel actually needed to route a circuit) the routing time is very fast. For example, the routing phase (after the netlist is parsed and the routing graph is constructed) for a 20,000 LUT/FF pair circuit with 30% extra tracks is only 23 seconds on a 300 MHz Sparcstation.For low-stress routing problems the routing time is near-linear in the size of the circuit, and the linearity constant is very small: 1.1 ms per LUT/FF pair, or roughly 55,000 LUT/FF pairs per minute. For more difficult routing problems (where the track supply is close to the minimum needed) we provide a method that quickly identifies and subdivides this class into two sub-classes: (i) those circuits which are difficult (but possible) to route and will take significantly more time than low-stress problems, and (ii) those circuits which are impossible to route. In the first case the user can choose to continue or reduce the amount of logic; in the second case the user is forced to reduce the amount of logic or obtain a larger FPGA.

REFERENCES

• Alle76: James R. Allen, A topologically adaptable cellular router, Proceedings of the 13th conference on Design automation, p.161-167, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804809]
• Apti96: Apfix Corporation, Product Brief.' The System Explorer MP4, 1996. This and other documents are available on the Apfix web site: http://www, aptix.eom.
• Babb97: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• Betz97: 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
• Brow92: Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
• Brow92a: S. Brown, J. Rose, and Z. G. Vranesie, "A Detailed Router for Field-Programmable Gate Arrays" IEEE Trans. on CAD, May 1992, pp. 620-628.
• Chen94: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• Cong94: J. Cong and Y. Ding, "Flowmap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs}' IEEE Trans. on CAD, Jan. 1994, pp. 1-12.
• Corm90: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• Ebel95: 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]
• Hutt97: Michael Hutton , Jonathan Rose , Derek Corneil, Generation of synthetic sequential benchmark circuits, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.149-155, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258333]
• Korn82: R. Kom, "An Efficient Variable Cost Maze Router", Proc. 19th DAC, June 1992.
• Lee61: C. Y. Lee, '~n Algorithm for Path Connections and its Applications,' IRE Transactions on Electronic Computers, Vol. EC=10, 1961, pp. 346-365.
• Lemi93: G. Lemieux and S. Brown, "A Detailed Router for Allocating Wh:e Segments in FPGAs;' ACM/SIGDA Physical Design Workshop, 1993, pp. 215-226.
• Lewi97: David M. Lewis , David R. Galloway , Marcus van Ierssel , Jonathan Rose , Paul Chow, The Transmogrifier-2: a 1 million gate rapid prototyping system, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.53-61, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258312]
• Nair87: R. Nair, "A Simple Yet Effective Technique for Global Wiring/' IEEE Trans. on Computer-Aided Design, vol. CAD-6, no. 6, March 1987, pp. 165-172.
• Palc92: M. Palczewski, Plane parallel a maze router and its application to FPGAs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.691-697, June 08-12, 1992, Anaheim, California, United States
• Rubi74: E Rubin, "The Lee Path Connection Algorithm", IEEE Trans. Computers, vol e-23, no. 9, Sept. 1974.
• Sent92: E. M. Sentovieh et. al, "SIS: A System for Sequential Circuit Analysis;' TecE Report No. UCB/ERL 3492/ 41, University of California, Berkeley, 1992.
• Souk78: J. Soukup, Fast maze router, Proceedings of the 15th conference on Design automation, p.100-102, June 19-21, 1978, Las Vegas, Nevada, United States
• Wilt97: Steven Joseph Edward Wilton , Jonathan Rose , Zvenko Vranesic, Architectures and algorithms for field-programmable gate arrays with embedded memory, 1997
• Wu94: Y.-L. Wu and M. Marek-Sadowka, '~An Efficient Router for 2-D Field-Programmable Gate Arrays;' EDAC, 1994, pp. 412-416.
• Yang91: S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0;' Tech. Report, Mieroeleetronics Centre 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
  B.8 Performance and Reliability

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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