research-article

Predicting interconnect delay for physical synthesis in a FPGA CAD flow

Authors:

Valavan Manohararajah,

Gordon R. Chiu,

Deshanand P. Singh,

Stephen D. BrownAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 15, Issue 8

Pages 895 - 903

https://doi.org/10.1109/TVLSI.2007.900744

Published: 01 August 2007 Publication History

Abstract

This paper studies the prediction of interconnect delay in an industrial setting. Industrial circuits and two industrial field-programmable gate-array (FPGA) architectures were used in this paper. 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. Using this simple timing model in a two-phase timing driven physical synthesis flow can both improve quality of results and decrease runtime. Next, we present a metric for predicting the accuracy of our interconnect delay model and show how this metric can be used to reduce the runtime of a timing driven physical synthesis flow. 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]

M. Sheng and J. Rose, "Mixing buffers and pass transistors in FPGA routing architectures," in Proc. ACM Symp. FPGAs, 2001, pp. 75-84.

[2]

C. Sechen, "Average interconnection length estimation for random and optimized placements," in Proc. Int. Conf. Comput.-Aided Des., 1987, pp. 190-193.

[3]

T. Hamada, C.-K. Cheng, and P. M. Chau, "A wire length estimation technique utilizing neighborhood density equations," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 15, no. 8, pp. 912-922, Aug. 1996.

Digital Library

[4]

S. Bodapati and F. N. Najm, "Pre-layout estimation of individual wire lengths," in Proc. Conf. Syst. Level Interconnect Prediction, 2000, pp. 93-98.

[5]

S. Balachandran and D. Bhatia, "A-priori wirelength and interconnect estimation based on circuit characteristics," in Proc. Conf. Syst. Level Interconnect Prediction, 2003, pp. 77-84.

[6]

Altera, San Jose, CA, "Stratix device handbook (complete two-volume set). v3.1," 2004.

[7]

Altera, San Jose, CA, "Stratix II device handbook (complete two-volume set). vl.2," 2004.

[8]

Altera, San Jose, CA, "Quartus II development software handbook v5.0 (complete four-volume set). v5.0," 2005.

[9]

R. Hitchcock, G. Smith, and D. Cheng, "Timing analysis of computer-hardware," IBM J. Res. Develop., vol. 26, no. 1, pp. 100-105, Jan. 1983.

Digital Library

[10]

V. Betz, J. Rose, and A. Marquardt, Architecture and CAD for Deep-Submicron FPGAs. Norwell, MA: Kluwer, 1999.

Digital Library

[11]

D. P. Singh and S. D. Brown, "Incremental placement for layout-driven optimizations on FPGAs," in Proc. Int. Conf. Comput.-Aided Des., 2002, pp. 752-759.

[12]

D. P. Singh, V. Manohararajah, and S. D. Brown, "Incremental retiming for FPGA physical synthesis," in Proc. Des. Autom. Conf., 2005, pp. 433-438.

[13]

V. Manohararajah, D. P. Singh, and S. D. Brown, "Timing driven functional decomposition for FPGAs," in Proc. Int. Workshop Logic Synth., 2005, pp. 415-422.

[14]

V. Manohararajah, D. P. Singh, S. D. Brown, and Z. G. Vranesic, "Post-placement functional decomposition for FPGAs," in Proc. Int. Workshop Logic Synth., 2005, pp. 114-118.

[15]

D. P. Singh, V. Manohararajah, and S. D. Brown, "Two-stage physical synthesis for FPGAs," in Proc. Custom Integr. Circuits Conf., 2005, pp. 171-178.

Cited By

Lewis DChiu GChromczak JGalloway DGamsa BManohararajah VMilton IVanderhoek TVan Dyken JChen DGreene J(2016)The Stratix™ 10 Highly Pipelined FPGA ArchitectureProceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847267(159-168)Online publication date: 21-Feb-2016
https://dl.acm.org/doi/10.1145/2847263.2847267
Zheng HGurumani SRupnow KChen DBetz VConstantinides G(2014)Fast and effective placement and routing directed high-level synthesis for FPGAsProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554775(1-10)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554775
Liu HRajavel SAkoglu A(2013)Integration of Net-Length Factor with Timing- and Routability-Driven Clustering AlgorithmsACM Transactions on Reconfigurable Technology and Systems10.1145/25173246:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2517324
Show More Cited By

Index Terms

Predicting interconnect delay for physical synthesis in a FPGA CAD flow
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware

Recommendations

Optimality Study of Logic Synthesis for LUT-Based FPGAs

Field-programmable gate-array (FPGA) logic synthesis and technology mapping have been studied extensively over the past 15 years. However, progress within the last few years has slowed considerably (with some notable exceptions). It seems natural to ...
Sequential delay budgeting with interconnect prediction

Delay budgeting is a process of determining upper bounds for net delays to guide timing-driven placement. The existing approaches deal de facto only with combinational circuits. However, incorporating retiming into delay budgeting introduces more ...
Product-term-based synthesizable embedded programmable logic cores

As integrated circuits become increasingly complex, the ability to make post-fabrication changes will become more important and attractive. This capability can be realized by using programmable logic cores. Currently, such cores are available from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 15, Issue 8

August 2007

130 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 August 2007

Revised: 29 January 2007

Received: 28 June 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lewis DChiu GChromczak JGalloway DGamsa BManohararajah VMilton IVanderhoek TVan Dyken JChen DGreene J(2016)The Stratix™ 10 Highly Pipelined FPGA ArchitectureProceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847267(159-168)Online publication date: 21-Feb-2016
https://dl.acm.org/doi/10.1145/2847263.2847267
Zheng HGurumani SRupnow KChen DBetz VConstantinides G(2014)Fast and effective placement and routing directed high-level synthesis for FPGAsProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554775(1-10)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554775
Liu HRajavel SAkoglu A(2013)Integration of Net-Length Factor with Timing- and Routability-Driven Clustering AlgorithmsACM Transactions on Reconfigurable Technology and Systems10.1145/25173246:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2517324
Shum WAnderson JCompton KHutchings B(2012)Analyzing and predicting the impact of CAD algorithm noise on FPGA speed performance and powerProceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays10.1145/2145694.2145711(107-110)Online publication date: 22-Feb-2012
https://dl.acm.org/doi/10.1145/2145694.2145711

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents