Article

Getting more out of Donath's hierarchical model for interconnect prediction

Authors:

J Dambre,

P. Verplaetse,

D. Stroobandt,

J. Van CampenhoutAuthors Info & Claims

SLIP '02: Proceedings of the 2002 international workshop on System-level interconnect prediction

Pages 9 - 16

https://doi.org/10.1145/505348.505351

Published: 06 April 2002 Publication History

Get Access

Abstract

Though it has become one of the most popular techniques for a priori wirelength estimation, Donath's method is heavily constrained by the underlying circuit and architecture models. In this paper, we propose analytical and numerical extensions to this model to overcome some of these constraints. It turns out that, with our extensions, Donath's model correlates very well with experimental data. This makes it particularly well suited for, among others, the parametric exploration of placement options.

References

[1]

C.J.Alpert.The ISPD98 circuit benchmark uite.In Proc.of the 1998 Intl.Symp.on Physical Design, pages 80-85.ACM Press,April 1998.

Digital Library

Google Scholar

[2]

P.Christie.A di .erential equation for placement analy is.IEEE Trans.on VLSI Systems,Special Issue on System-Level Interconnect Prediction, 9(6):913-921,December 2001.

Digital Library

Google Scholar

[3]

J.A.Davi,V.K.De,andJ.D.Meindl.A tochatic wire-length distribution for gigascale integration (GSI) -PART I:Derivation and validation.IEEE Trans.on El ectron Devices,45(3):580-589,March 1998.

Google Scholar

[4]

J.Depreitere,H.Van Marck,and J.Van Campenhout. A quantitative analy i of the bene .ts of the use of area-I/O pad in FPGAs.Microprocessors and Microsystems,21(2):89-97,October 1997.

Crossref

Google Scholar

[5]

W.E.Donath.Wire length di tribution for placement of computer logic.IBM J.of Research and Development,25:152-155,1981.

Digital Library

Google Scholar

[6]

G.Karypis and V.Kumar.hMetis:A Hypergraph Partitioning Package,November 1998.Available at: http://www-u ers.cs.umn.edu/ ~karypis/meti /hmeti /main.html.

Google Scholar

[7]

B.S.LandmanandR.L.Ru o.On apinveru block relationship for partitions of logic graphs.IEEE Trans.on Comput.,C-20:1469-1479,1971.

Digital Library

Google Scholar

[8]

D.Stroobandt.A priori Wire Length Estimates for Digital Design .Kluwer Academic Publi hers,April 2001.

Google Scholar

[9]

D.Stroobandt,P.Verplaetse,and J.Van Campenhout.Generating ynthetic benchmark circuit for evaluating CAD tools.IEEE Trans.on Computer-Aided Design of Integrated Circuits and Systems,19(9):1011-1022,September 2000.

Digital Library

Google Scholar

[10]

H.Van Marck,D.Stroobandt,and J.Van Campenhout.Interconnection length di tributions in 3-dimensional ani otropic y tem .In M.H.Hamza,editor,Proc.13th IASTED Intl.Conf. on Applied Informatics,pages 98-101. IASTED-ACTA Press,1995.

Google Scholar

[11]

P.Verplaet e,J.Dambre,D.Stroobandt,and J.Van Campenhout.On partitioning vs.placement rent properties.In Proc.of Intl.Workshop on System-Level Interconnect Prediction,pages 33-40, March 2001.

Digital Library

Google Scholar

Cited By

View all

Won-Jin Kim Ahn BKi-Seok Chung Jong-Wha Chung Sung-Hwan Oh (2008)Timing driven force-directed floorplanning with incremental static timing analyzerAPCCAS 2008 - 2008 IEEE Asia Pacific Conference on Circuits and Systems10.1109/APCCAS.2008.4746193(1000-1003)Online publication date: Nov-2008
https://doi.org/10.1109/APCCAS.2008.4746193
Wong JDavoodi AKhandelwal VSrivastava APotkonjak M(2006)A statistical methodology for wire-length predictionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85588525:7(1327-1336)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.855885
Davoodi AKhandelwal VSrivastava A(2004)Empirical models for net-length probability distribution and applicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2004.83423512:10(1066-1075)Online publication date: 1-Oct-2004
https://dl.acm.org/doi/10.1109/TVLSI.2004.834235
Show More Cited By

Index Terms

Getting more out of Donath's hierarchical model for interconnect prediction
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies

Recommendations

Fast timing-driven partitioning-based placement for island style FPGAs
DAC '03: Proceedings of the 40th annual Design Automation Conference

In this paper we propose a partitioning-based placement algorithm for FPGAs. The method incorporates simple, but effective heuristics that target delay minimization. The placement engine incorporates delay estimations obtained from previously placed and ...
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 ...
Pre-layout prediction of interconnect manufacturability
SLIP '01: Proceedings of the 2001 international workshop on System-level interconnect prediction

Functional yield is a term used to describe the percentage of dies on a wafer that fail due to catastrophic defects. Within the interconnect these defects are usually caused by particle contamination and are divided into bridging defects, which join ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SLIP '02: Proceedings of the 2002 international workshop on System-level interconnect prediction

April 2002

116 pages

ISBN:1581134819

DOI:10.1145/505348

General Chair:
Jeff A. Davis
Georgia Institute of Technology
,
Program Chair:
Dennis Sylvester
University of Michigan

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 April 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SLIP02

Sponsor:

SIGDA

SLIP02: System Level Interconnect Prediction Workshop

April 6 - 7, 2002

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 6 of 8 submissions, 75%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
300
Total Downloads

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

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Won-Jin Kim Ahn BKi-Seok Chung Jong-Wha Chung Sung-Hwan Oh (2008)Timing driven force-directed floorplanning with incremental static timing analyzerAPCCAS 2008 - 2008 IEEE Asia Pacific Conference on Circuits and Systems10.1109/APCCAS.2008.4746193(1000-1003)Online publication date: Nov-2008
https://doi.org/10.1109/APCCAS.2008.4746193
Wong JDavoodi AKhandelwal VSrivastava APotkonjak M(2006)A statistical methodology for wire-length predictionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85588525:7(1327-1336)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.855885
Davoodi AKhandelwal VSrivastava A(2004)Empirical models for net-length probability distribution and applicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2004.83423512:10(1066-1075)Online publication date: 1-Oct-2004
https://dl.acm.org/doi/10.1109/TVLSI.2004.834235
Dambre JStroobandt DVan Campenhout J(2004)Toward the accurate prediction of placement wire length distributions in VLSI circuitsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2004.82585112:4(339-348)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1109/TVLSI.2004.825851
Dambre JStroobandt DVan Campenhout JSylvester DStroobandt DScheffer LZarkesh-Ha P(2003)Fast estimation of the partitioning rent characteristic using a recursive partitioning modelProceedings of the 2003 international workshop on System-level interconnect prediction10.1145/639929.639940(45-52)Online publication date: 5-Apr-2003
https://dl.acm.org/doi/10.1145/639929.639940
Pistorius JHutton MSylvester DStroobandt DScheffer LZarkesh-Ha P(2003)Placement rent exponent calculation methods, temporal behaviour and FPGA architecture evaluationProceedings of the 2003 international workshop on System-level interconnect prediction10.1145/639929.639936(31-38)Online publication date: 5-Apr-2003
https://dl.acm.org/doi/10.1145/639929.639936

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.

Cited By

Index Terms

Recommendations

Fast timing-driven partitioning-based placement for island style FPGAs

Sequential delay budgeting with interconnect prediction

Pre-layout prediction of interconnect manufacturability