Difficulty of predicting interconnect delay in a timing driven FPGA CAD flow

ABSTRACT

This paper studies the difficulty of predicting interconnect delay in an industrial setting. Fifty industrial circuits, Altera's Quartus II CAD software, and Altera's Stratix and Stratix II FPGA architectures were used in the study. We show that there is a large amount of inherent randomness in a state-of-the-art FPGA placement algorithm. Thus, it is impossible to predict interconnect delay with a high degree of accuracy. Futhermore, we show that a simple timing model can be used to predict some aspects of interconnect timing with just as much accuracy as predictions obtained by running the placement tool itself. Finally, we examine the benefits of using the simple timing model in a timing driven physical synthesis flow, and attempt to establish an upper bound on these possible gains, given the difficulty of interconnect delay prediction.

REFERENCES

• 1: Mike Sheng , Jonathan Rose, Mixing buffers and pass transistors in FPGA routing architectures, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.75-84, February 2001, Monterey, California, United States [doi>10.1145/360276.360302]
• 2: C. Sechen. Average Interconnection Length Estimation for Random and Optimized Placements. In Proceedings of the International Conference on Computer Aided Design, November 1987, pp. 190--193.
• 3: T. Hamada, C.-K. Cheng, and P. M. Chau. A Wire Length Estimation Technique Utilizing Neighborhood Density Equations. IEEE Transactions on Computer-Aided Design, Vol. 15, No. 8, August 1996, pp. 912--922.
• 4: Srinivas Bodapati , Farid N. Najm, Pre-layout estimation of individual wire lengths, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.93-98, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333038]
• 5: Shankar Balachandran , Dinesh Bhatia, A-priori wirelength and interconnect estimation based on circuit characteristics, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639945]
• 6: Altera. Stratix Device Handbook (Complete Two-Volume Set). v3.1, Sept. 2004.
• 7: Altera. Stratix II Device Handbook (Complete Two-Volume Set). v1.2, Oct. 2004.
• 8: Altera. Quartus II Development Software Handbook v5.0 (Complete Four-Volume Set). v5.0, May 2005.
• 9: R. Hitchcock, G. Smith and D. Cheng. Timing Analysis of Computer-Hardware. IBM Journal of Research and Development, Jan. 1983, pp. 100--105.
• 10: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 11: Deshanand P. Singh , Stephen D. Brown, Incremental placement for layout driven optimizations on FPGAs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.752-759, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774683]
• 12: Deshanand P. Singh , Valavan Manohararajah , Stephen D. Brown, Incremental retiming for FPGA physical synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065694]
• 13: V. Manohararajah, D. P. Singh, and S. D. Brown. Timing Driven Functional Decomposition for FPGAs. In Proceedings of the International Workshop on Logic and Synthesis, Lake Arrowhead, CA, June 2005, pp. 415--422.
• 14: V. Manohararajah, D. P. Singh, S. D. Brown, and Z. G. Vranesic. Post-Placement Functional Decomposition for FPGAs. In Proceedings of the International Workshop on Logic and Synthesis, Temecula Creek, CA, June 2005, pp. 114--118.
• 15: D. P. Singh, V. Manohararajah, and S. D. Brown. Two-Stage Physical Synthesis for FPGAs. In Proceedings of the Custom Integrated Circuits Conference, San Jose, CA, September 2005, pp. 171--178.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization; Automatic synthesis
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization; Automatic synthesis
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Measurement, Performance