Article

Fast and robust quadratic placement combined with an exact linear net model

Authors:

Peter Spindler,

Frank M. JohannesAuthors Info & Claims

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

Pages 179 - 186

https://doi.org/10.1145/1233501.1233537

Published: 05 November 2006 Publication History

Abstract

This paper presents a robust quadratic placement approach, which offers both high-quality placements and excellent computational efficiency. The additional force which distributes the modules on the chip in force-directed quadratic placement is separated into two forces: hold force and move force. Both of these forces are determined without any heuristics. Based on this novel systematic force implementation, we show that our iterative placement algorithm converges to an overlapfree placement. In addition, engineering change order (ECO) is efficiently supported by our placer. To handle the important trade-off between CPU time and placement quality, a deterministic quality control is presented.

In addition, a new linear net model is proposed, which accurately models the half-perimeter wirelength (HPWL) in the quadratic cost function of quadratic placement. HPWL in general is a linear metric for netlength and represents an efficient and common estimation for routed wirelength. Compared with the classical clique net model, our linear net model reduces memory usage by 75%, CPU time by 23% and netlength by 8%, which is measured by the HPWL of all nets.

Using the ISPD-2005 benchmark suite for comparison, our placer combined with the new linear net model has just 5.9% higher netlength but is 16x faster than APlace, which offers the best netlength in this benchmark. Compared to Capo, our placer has 9.2% lower netlength and is 5.4x faster.

In the recent ISPD-2006 placement contest, in which quality is mainly determined by netlength and CPU time, our placer together with the new net model produced excellent results.

References

[1]

International symposium on physical design. http://www.ispd.cc.

[2]

International technology roadmap for semiconductors. http://public.itrs.net.

[3]

Ucla/umich physical design tools. http://vlsicad.eecs.umich.edu/BK/PDtools.

[4]

S. N. Adya, S. Chaturvedi, J. a Roy, D. A. Papa, and I. L. Markov. Unification of partitioning, placement and floorplanning. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 550--557, 2004.

Digital Library

[5]

A. R. Agnihorti, S. Ono, C. Li, M. C. Yildiz, A. Khathate, C.-K. Koh, and P. H. Madden. Mixed block placement via fractional cut recursive bisection. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(5):748--761, May 2005.

Digital Library

[6]

U. Brenner and M. Struzyna. Faster and better global placement by a new transportation algorithm. In ACM/IEEE Design Automation Conference (DAC), pages 591--596, June 2005.

Digital Library

[7]

T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 185--192, 2005.

Digital Library

[8]

T. F. Chan, J. Cong, M. Romesis, J. R. Shinnerl, K. Sze, and M. Xie. mPL6: A robust multilevel mixed-size placement engine. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 227--229, 2005.

Digital Library

[9]

T.-C. Chen, T.-C. Hsu, Z.-W. Jiang, and Y.-W. Chang. NTUplace: A ratio partitioning based placement algorithm for large-scale mixed-size designs. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 236--238, 2005.

Digital Library

[10]

C. Chu. FLUTE: Fast lookup table based wirelength estimation technique. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 696--701, 2004.

Digital Library

[11]

W. Donath. Complexity theory and design automation. In ACM/IEEE Design Automation Conference (DAC), volume 19, pages 412--419, 1980.

Digital Library

[12]

H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In ACM/IEEE Design Automation Conference (DAC), pages 269--274, June 1998.

Digital Library

[13]

K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219--229, Nov. 1970.

Digital Library

[14]

M. Hanan. On Steiner's Problem with Rectiliner Distance. SIAM Journal of Applied Mathemetics, 14(2):255--265, 1966.

[15]

B. Hu and M. Marek-Sadowska. FAR: Fixed-points addition & relaxation based placement. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 161--166, 2002.

Digital Library

[16]

B. Hu and M. Marek-Sadowska. Multilevel fixed-point-addition-based vlsi placement. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(8):1188--1203, Aug. 2005.

Digital Library

[17]

A. B. Kahng, S. Reda, and Q. Wang. Architecture and details of a high quality, large-scale analytical placer. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 890--897, 2005.

Digital Library

[18]

A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(05):734--747, May 2005.

Digital Library

[19]

J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Transactions on Computer-Aided Design of Circuits and Systems, CAD-10(3):356--365, Mar. 1991.

Digital Library

[20]

M. Kowarschik and C. Weiß. DiMEPACK -- A Cache-Optimized Multigrid Library. In H. Arabnia, editor, Proc. of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA 2001), pages 425--430. CSREA Press, June 2001.

[21]

M. C. V. Lier and R. H. J. M. Otten. Planarization by transformation. IEEE Transactions on Circuits and Systems CAS, 20(2):169--171, Mar. 1973.

[22]

K. G. Murty and F.-T. Yu. Linear complementary, linear and nonlinear programming. http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarit%y_webbook/.

[23]

G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter, and M. Yildiz. The ISPD2005 placement contest and benchmark suite. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 216--219, May 2005.

Digital Library

[24]

G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng. A fast hierarchical quadratic placement algorithm. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 25(4):678--691, Apr. 2006.

Digital Library

[25]

W. Naylor, R. Donelly, and L. Sha. Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. U.S. Patent 6301693, Oct. 2001.

[26]

B. Obermeier and F. M. Johannes. Quadratic placement using an improved timing model. In ACM/IEEE Design Automation Conference (DAC), pages 705--710, San Diego, June 2004.

Digital Library

[27]

B. Obermeier and F. M. Johannes. Temperature-aware global placement. In Asia and South Pacific Design Automation Conference, volume 1, pages 143--148, Yokohama, Japan, Jan. 2004.

Digital Library

[28]

J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, A. N. Ng, J. F. Lu, and I. L. Markov. Capo: Robust and scalable open-source min-cut floorplacer. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 224--226, 2005.

Digital Library

[29]

G. Sigl, K. Doll, and F. M. Johannes. Analytical placement: A linear or a quadratic objective function? In ACM/IEEE Design Automation Conference (DAC), pages 427--432, San Francisco, 1991.

Digital Library

[30]

W.-J. Sun and C. Sechen. Efficient and effective placement for very large circuits. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 170--177, 1993.

Digital Library

[31]

T. Taghavi, X. Yang, and B.-K. Choi. Dragon2005: Large-scale mixed-size placement tool. In ACM/SIGDA International Symposium on Physical Design (ISPD), pages 245--247, 2005.

Digital Library

[32]

N. Viswanathan and C. C.-N. Chu. Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. IEEE Transactions on Computer-Aided Design of Circuits and Systems, 24(5):722--733, May 2005.

Digital Library

[33]

J. Vygen. Algorithms for large-scale flat placement. In ACM/IEEE Design Automation Conference (DAC), pages 746--751, 1997.

Digital Library

[34]

X. Yang, B.-K. Choi, and M. Sarrafzadeh. A standard-cell placement tool for designs with high row utilization. In IEEE International Conference on Computer Design (ICCD), pages 45--47, Sept. 2002.

Digital Library

Cited By

Jiang QLee YZomaya A(2020)The Limit of Horizontal Scaling in Public CloudsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33733565:1(1-22)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3373356
Rattaro CAspirot LMordecki EBelzarena P(2020)QoS Provision in a Dynamic Channel Allocation Based on Admission Control DecisionsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727865:1(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372786
Yang JLi BLilja D(2020)Exploring Performance Characteristics of the Optane 3D Xpoint Storage TechnologyACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727835:1(1-28)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372783
Show More Cited By

Index Terms

Fast and robust quadratic placement combined with an exact linear net model

Recommendations

A robust detailed placement for mixed-size IC designs
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

The rapid increase in IC design complexity and wide-spread use of intellectual-property (IP) blocks have made the so-called mixed-size placement a very important topic in recent years. Although several algorithms have been proposed for mixed-sized ...
A Robust Mixed-Size Legalization and Detailed Placement Algorithm

Placement is one of the most important steps in the RTL-to-GDSII synthesis process as it directly defines the interconnects. The rapid increase in IC design complexity and the widespread use of intellectual-property blocks have made the so-called mixed-...
Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs
DAC '08: Proceedings of the 45th annual Design Automation Conference

Routability is a challenging cost metric for modern large-scale mixed-size placement. Most existing routability-driven placement algorithms apply whitespace allocation to relieve the routing congestion. Nevertheless, we observe that whitespace ...

Comments

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

37
Total Citations
View Citations
364
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang QLee YZomaya A(2020)The Limit of Horizontal Scaling in Public CloudsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33733565:1(1-22)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3373356
Rattaro CAspirot LMordecki EBelzarena P(2020)QoS Provision in a Dynamic Channel Allocation Based on Admission Control DecisionsACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727865:1(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372786
Yang JLi BLilja D(2020)Exploring Performance Characteristics of the Optane 3D Xpoint Storage TechnologyACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/33727835:1(1-28)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3372783
Miller AReges SObourn A(2017)jGRASPACM Inroads10.1145/31485628:4(53-58)Online publication date: 27-Oct-2017
https://dl.acm.org/doi/10.1145/3148562
Popyack J(2017)Scholastic excellence in 2017ACM Inroads10.1145/31417968:4(8-11)Online publication date: 27-Oct-2017
https://dl.acm.org/doi/10.1145/3141796
Wilson G(2017)Building a new mythologyACM Inroads10.1145/31327068:4(66-71)Online publication date: 27-Oct-2017
https://dl.acm.org/doi/10.1145/3132706
Nambiar MKattepur ABhaskaran GSinghal RDuttagupta S(2016)Model Driven Software Performance EngineeringACM SIGMETRICS Performance Evaluation Review10.1145/2897356.289736343:4(53-62)Online publication date: 25-Feb-2016
https://dl.acm.org/doi/10.1145/2897356.2897363
Rehmann KSeo CHwang DTruong BBoehm ALee D(2016)Performance Monitoring in SAP HANA's Continuous Integration ProcessACM SIGMETRICS Performance Evaluation Review10.1145/2897356.289736243:4(43-52)Online publication date: 25-Feb-2016
https://dl.acm.org/doi/10.1145/2897356.2897362
Grottke MAvritzer AMenasché Dde Aguiar LAltman E(2016)On the Efficiency of Sampling and Countermeasures to Critical-Infrastructure-Targeted Malware CampaignsACM SIGMETRICS Performance Evaluation Review10.1145/2897356.289736143:4(33-42)Online publication date: 25-Feb-2016
https://dl.acm.org/doi/10.1145/2897356.2897361
Li ZO'Brien LKihl M(2016)DoKnowMeACM SIGMETRICS Performance Evaluation Review10.1145/2897356.289736043:4(23-32)Online publication date: 25-Feb-2016
https://dl.acm.org/doi/10.1145/2897356.2897360
Show More Cited By

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.

Figures

Tables

Media

View Table of Conten