More Web Proxy on the site http://driver.im/

Article

A network-flow approach to timing-driven incremental placement for ASICs

Authors:

Vishal SutharAuthors Info & Claims

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

Pages 375 - 382

https://doi.org/10.1145/1233501.1233577

Published: 05 November 2006 Publication History

Abstract

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits. FlowPlace includes: a) a timing-driven (TD) analytical global placer TAN that uses accurate delay functions and minimizes a combination of linear and quadratic objective functions; b) a network flow based detailed placer TIF that has new and effective techniques for performing TD incremental placement and satisfying rowlength (white space) constraints. We have obtained results on three sets of benchmarks: i) TD versions of the ibm benchmark suite that we have constructed; ii) benchmarks used in TD-Dragon; iii) the Faraday benchmarks. Results show that starting with Dragon-placed circuits, we are able to obtain up to 34% and an average of 18% improvement in critical path delays, at an average of 17.5% of the run-time of the Dragon placer. Starting with a state-of-the-art TD placer TD-Dragon, for the TD-Dragon benchmarks we obtain up to about 10% and an average of 4.3% delay improvement with 12% of TD-Dragon's run times; this is significant as we are extracting performance improvements from a performanceoptimized layout. Wire length deterioration on the average over all benchmark suites is less than 8%.

References

[1]

S. N. Adya, I. L. Markov, "Consistent Placement of Macro-Blocks using Floorplanning and Standard-Cell Placement", Proc. ACM/IEEE Intl. Symp. on Physical Design, 12--17, April, 2002

Digital Library

[2]

S. N. Adya, et al., "Unification of Partitioning, Floorplanning and Placement", ICCAD, 2004, pp. 41--46.

Digital Library

[3]

R. Ahuja, et al., "A network simplex algorithm with O(n) consecutive degenerate pivots", Operations research letters, pp. 1417--1436, 1995.

[4]

U. Brenner, et al., "Almost optimum placement legalization by minimum cost flow and dynamic programming", ISPD, 2004.

Digital Library

[5]

K. Doll, F. Johannes, K. Antreich, "Iterative placement improvement by network flow methods", IEEE Trans. Computer-Aided Design, pp. 1189--1200, 1994.

Digital Library

[6]

C. A. Floudas and V. Visweswaran, "Quadratic Optimization", in Handbook of global optimization, Kluwer Acad. Publ., Dordrecht, pp. 217--269, 1995.

[7]

The FlowPlace page: http://www.ece.uic.edu/~dutt/benchmarksetc/FlowPlace/flow.html.

[8]

A. Kahng, S. Mantik and I. Markov, "Min-Max placement for large scale timing optimization", ISPD'02.

Digital Library

[9]

A Kahng, I. Markov, S. Reda "Boosting: min-cut placement with improved signal delay" Proc. DATE, 2004, pp. 1098--1103

Digital Library

[10]

J. Kleinhans, et al., "GORDIAN: VLSI placement by quadratic programming and slicing optimization". IEEE Trans. CAD, vol. 10, pp.356--365, Mar. 1991.

Digital Library

[11]

A. Marquardt, V. Betz and J. Rose, "Timing-Driven Placement for FPGAs", Proc. Int'l Symp. FPGAs, 2000, pp. 203--213.

Digital Library

[12]

S-L Ou, M. Pedram, "Timing-driven Placement Based on Partitioning with Dynamic Cut-net Control", Proc. Design Automation Conf. 2000, pp. 472--476

Digital Library

[13]

G. Sigl, et al., "Analytical placement: A linear or a quadratic objective function?", Proc. DAC, 1991, pp. 427--432.

Digital Library

[14]

C. Wonjoon, K. Bazargan, "Incremental placement for timing optimization", ICCAD, pp. 463--466, 2003

Digital Library

[15]

Y. Xiaojian, C. Bo-Kyung, M. Sarrafzadeh; "Timing-driven placement using design hierarchy guided constraint generation", ICCAD, pp. 177--180, 2002.

Digital Library

[16]

H. Yang and D. F. Wong, "Efficient Network Flow Based Min-cut Balanced Partitioning", IEEE Trans. CAD, pp. 1533--1540, 1996.

Digital Library

Cited By

Ren HDutt S(2013)Fast and near-optimal timing-driven cell sizing under cell area and leakage power constraints using a simplified discrete network flow algorithmVLSI Design10.1155/2013/4746012013(1-1)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1155/2013/474601
Dutt SRen HScheffer LPhillips JHu A(2010)Timing yield optimization via discrete gate sizing using globally-informed delay PDFsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133549(570-577)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133549
Ren HDutt SNassif SRoychowdhury J(2008)Algorithms for simultaneous consideration of multiple physical synthesis transforms for timing closureProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509488(93-100)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509488

Index Terms

A network-flow approach to timing-driven incremental placement for ASICs
1. Hardware
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

A Flat Timing-Driven Placement Flow for Modern FPGAs
DAC '19: Proceedings of the 56th Annual Design Automation Conference 2019

In this paper, we propose a novel, flat analytic timing-driven placer without explicit packing for Xilinx UltraScale FPGA devices. Our work uses novel methods to simultaneously optimize for timing, wirelength and congestion throughout the global and ...
Discretized Network Flow Techniques for Timing and Wire-Length Driven Incremental Placement With White-Space Satisfaction

We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits without appreciable increase in wire length (WL). FlowPlace includes: 1) a timing-driven (TD) ...
Timing-driven partitioning-based placement for island style FPGAs

In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2006 ACM.

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]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
196
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ren HDutt S(2013)Fast and near-optimal timing-driven cell sizing under cell area and leakage power constraints using a simplified discrete network flow algorithmVLSI Design10.1155/2013/4746012013(1-1)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1155/2013/474601
Dutt SRen HScheffer LPhillips JHu A(2010)Timing yield optimization via discrete gate sizing using globally-informed delay PDFsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133549(570-577)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133549
Ren HDutt SNassif SRoychowdhury J(2008)Algorithms for simultaneous consideration of multiple physical synthesis transforms for timing closureProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509488(93-100)Online publication date: 10-Nov-2008
https://dl.acm.org/doi/10.5555/1509456.1509488

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents