Runtime and quality tradeoffs in FPGA placement and routing

ABSTRACT

Many applications of FPGAs, especially logic emulation and custom computing, require the quick placement and routing of circuit designs. In these applications, the advantages FPGA-based systems have over software simulation are diminished by the long run-times of current CAD software used to map the circuit onto FPGAs. To improve the run-time advantage of FPGA systems, users may be willing to trade some mapping quality for a reduction in CAD tool runtimes. In this paper, we seek to establish how much quality degradation is necessary to achieve a given runtime improvement. For this purpose, we implemented and investigated numerous placement and routing algorithms for FPGAs. We also developed new tradeoff-oriented algorithms, where a tuning parameter can be used to control this quality vs. runtime tradeoff. We show how different algorithms can achieve different points within this tradeoff spectrum, as well as how a single algorithm can be tuned to form a curve in the spectrum. We demonstrate that the algorithms vary widely in their tradeoffs, with the fastest algorithm being 8x faster than the slowest, and the highest quality algorithm being 5x better than the least quality algorithm. Compared to the commercial Xilinx CAD tools, we can achieve a 3x speed-up by allowing 1.27x degradation in quality, and a factor of 1.6x quality improvement with 2x slowdown.

REFERENCES

• 1: P. Zhong , M. Martonosi , P. Ashar , S. Malik, Accelerating Boolean Satisfiability with Configurable Hardware, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines, p.186, April 15-17, 1998
• 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: Yaska Sankar , Jonathan Rose, Trading quality for compile time: ultra-fast placement for FPGAs, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.157-166, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296449]
• 4: Pak K. Chan , Martine D. F. Schlag, New parallelization and convergence results for NC: a negotiation-based FPGA router, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.165-174, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329201]
• 5: Xilinx, The Programmable Logic Data Book, 1996, pp.4.5-4.106.
• 6: S.Yang, Logic Synthesis and Optimization Benchmarks, Version 3.0, Tech. Report, Microelectronics center of North Carolina, 1991.
• 7: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 8: A.E.Dunlop and B.W.Kernighan, A Procedure for Placement of Standard Cell VLSI Circuits, IEEE Transactions on Computer-Aided Design, Vol. 4, No. 1, 1985, pp.92-98.
• 9: K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]
• 10: Jimmy Lam , Jean-Marc Delosme, Performance of a new annealing schedule, Proceedings of the 25th ACM/IEEE conference on Design automation, p.306-311, June 12-15, 1988, Atlantic City, New Jersey, United States
• 11: 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]
• 12: 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]
• 13: K.W. Lee and C. Sechen, A New Global Router for Row-Based Layout, International Conference on Computer-Aided Design, IEEE, 1988, pp.180-183.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Simulation

General Terms:
Experimentation, Verification

Keywords:
FPGAs, computer-aided design, fast CAD for FPGAs, placement, routing