Article

Free access

An empirical model for accurate estimation of routing delay in FPGAs

Authors:

Tanay Karnik,

Sung-Mo KangAuthors Info & Claims

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

Pages 328 - 331

Published: 01 December 1995 Publication History

PDF eReader Publisher Site

Abstract

We present an empirical routing delay model for estimating interconnection delays in FPGAs. We assume that the routing delay is a function of interPLC distances, circuit size, fanout of the net and routing congestion in the channel. We performed extensive simulations of various circuits to generate a sufficiently large dataset. Our method estimates delays by reading the average value tables and interpolating the values, if necessary. We present a rigorous statistical justification of this delay model. Our results show that our method predicts the delays within 20% of actual and it far outperforms all other existing techniques.

References

[1]

S. Raman, Timing-Constrained Layout Algorithms for Symmetrical FPGAs. PhD thesis, University of Illinois at Urbana-Champaign, 1994.

Digital Library

Google Scholar

[2]

J. Cong and Y. Ding, "An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," International Conference on Computer Aided Design, pp. 48-53, 1992.

Digital Library

Google Scholar

[3]

T. Gao, C. L. Liu, and K. C. Chen, "A Performance Driven Hierarchical Partitioning Placement Algorithm," European Design Automation Conference, pp. 33-38, 1993.

Google Scholar

[4]

K. Roy and C. Sechen, "A Timing Driven N-Way Chip and Multi-Chip Partitioner," International Conference on Computer Aided Design, pp. 240-247, 1993.

Digital Library

Google Scholar

[5]

A. Mathur and C. L. Liu, "Compression-Relaxation: A New Approach to Performance Driven Placement for Regular Architectures," International Conference on Computer Aided Design, pp. 130-136, 1994.

Digital Library

Google Scholar

[6]

C.-S. Chen, Y.-W. Tsay, T. Hwang, A. C. H. Wu, and Y.-L. Lin, ~Combining Technology Mapping and Placement for Delay-Optimization in FPGA Designs," International Conference on Computer Aided Design, pp. 123- 127, 1993.

Digital Library

Google Scholar

[7]

AT&:T Microelectronics, ORCA Development System, 1993.

Google Scholar

[8]

AT&:T Microelectronics, Optimized Reconfigurable Cell Array (ORCA) Series Field-Programmable Gate Arrays, 1993.

Google Scholar

[9]

T. Karnik, Hierarchical Timing-Driven Partitioning and Placement for Symmetrical FPGAs. PhD thesis, University of Illinois at Urbana-Champaign, 1995.

Digital Library

Google Scholar

Cited By

View all

(2010)FPGA-based combined architecture for stream categorization and intrusion detectionProceedings of the Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2010.5558652(77-80)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1109/MEMCOD.2010.5558652
Gopalakrishnan PLi XPileggi LSentovich E(2006)Architecture-aware FPGA placement using metric embeddingProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147033(460-465)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147033
Anderson JNajm FImai M(2004)Interconnect capacitance estimation for FPGAsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015284(713-718)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015284
Show More Cited By

Index Terms

An empirical model for accurate estimation of routing delay in FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

A Novel Message Scheduling Framework for Delay Tolerant Networks Routing

Multicopy routing strategies have been considered the most applicable approaches to achieve message delivery in Delay Tolerant Networks (DTNs). Epidemic routing and two-hop forwarding routing are two well-reported approaches for delay tolerant networks ...
Power estimation techniques for FPGAs

The dynamic power consumed by a digital CMOS circuit is directly proportional to both switching activity and interconnect capacitance. In this paper, we consider early prediction of net activity and interconnect capacitance in field-programmable gate ...
Message delay in MANET
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

A generic stochastic model with only two input parameters is introduced to evaluate the message delay in mobile ad hoc networks (MANETs) where nodes may relay messages. The Laplace-Stieltjes transform (LST) of the message delay is obtained for two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

December 1995

748 pages

ISBN:0818672137

Chairman:
Richard Rudell
Synopsys, Inc., Mountain View, CA

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1995

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD '95

Sponsor:

SIGDA
IEEE-CS

ICCAD '95: International Conference on Computer Aided Design

November 5 - 9, 1995

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)9

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2010)FPGA-based combined architecture for stream categorization and intrusion detectionProceedings of the Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign10.1109/MEMCOD.2010.5558652(77-80)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1109/MEMCOD.2010.5558652
Gopalakrishnan PLi XPileggi LSentovich E(2006)Architecture-aware FPGA placement using metric embeddingProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1147033(460-465)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1147033
Anderson JNajm FImai M(2004)Interconnect capacitance estimation for FPGAsProceedings of the 2004 Asia and South Pacific Design Automation Conference10.5555/1015090.1015284(713-718)Online publication date: 27-Jan-2004
https://dl.acm.org/doi/10.5555/1015090.1015284
Taghavi TGhiasi SRanjan ARaje SSarrafzadeh MAlpert, CGroeneveld P(2004)Innovate or perishProceedings of the 2004 international symposium on Physical design10.1145/981066.981099(148-155)Online publication date: 18-Apr-2004
https://dl.acm.org/doi/10.1145/981066.981099
Wang MRanjan ARaje S(2003)Multi-Million Gate FPGA Physical Design ChallengesProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009992Online publication date: 9-Nov-2003
https://dl.acm.org/doi/10.5555/996070.1009992
Venkatraman RPatnaik LSarrafzadeh MBanerjee PRoy K(2000)An evolutionary approach to timing driven FPGA placementProceedings of the 10th Great Lakes symposium on VLSI10.1145/330855.330986(81-85)Online publication date: 2-Mar-2000
https://dl.acm.org/doi/10.1145/330855.330986

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

A Novel Message Scheduling Framework for Delay Tolerant Networks Routing

Power estimation techniques for FPGAs

Message delay in MANET