Article

FAR: fixed-points addition & relaxation based placement

Authors:

Bo Hu,

Malgorzata Marek-SadowskaAuthors Info & Claims

ISPD '02: Proceedings of the 2002 international symposium on Physical design

Pages 161 - 166

https://doi.org/10.1145/505388.505426

Published: 07 April 2002 Publication History

Get Access

Abstract

In this paper we describe the Fixed-points Addition and Relaxation (FAR) based placement technique. Fixed point is a pseudo cell connected to a movable cell. By introducing fixed points, the placement can be maintained in a force equilibrium state and further transformed into another equilibrium state. By relaxing some of the previously introduced fixed points, we can partially or completely collapse the current placement in order to reposition the cells, or incrementally perturb the existing good solution to fulfill additional requirements. We apply the FAR-based approach to global placement for total wire length minimization, and to incremental placement for Buffer Site Generation (BSG). For global placement, our experimental results show that the FAR method achieves 54.4% CPU speedup and total wire length comparable to that achieved by the constant force based approach [1]. Experimental results indicate that to accommodate buffers in specific regions, FAR is able to perturb incrementally a given solution in a well-controlled way.

References

[1]

H.Eisenmann and F.M.Johannes, "Generic Global Placement and Floorplanning", in Proc. of the 35th Design Automation Conference, pp. 269--274, 1998.

Digital Library

Google Scholar

[2]

J.M.Kleinhans, G.Sigl, F.M.Johannes and K.J.Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. CAD, vol.10, no.3, Mar1991, pp.356--365.

Digital Library

Google Scholar

[3]

H.Etawil, S.Areibi, A.Vannelli, "Attractor-repealer approach for global placement", in Proc. of International Conference on Computer-Aided Design, pp.20--24, 1999.

Digital Library

Google Scholar

[4]

J.Cong, T.Kong and D.Z.Pan, "Buffer Block Planning for Interconnect-Driven Floorplanning", Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 1999, pp.358--363.

Digital Library

Google Scholar

[5]

F.F.Dragan, A.B.Kahng, I.Mandoiu, S.Umddu, "Provably Good Global Buffering Using an Available Buffer Block Plan", IEEE/ACM ICCAD, 2000, pp. 104--109.

Digital Library

Google Scholar

[6]

C.J.Alpert, Jiang Hu, S.S.Sapatnekar, P.G.Villarrubia, "A Practical Methodology for Early Buffer and Wire Resource Allocation", Design Automation Conference, 2001, pp. 189--194.

Digital Library

Google Scholar

[7]

X.Tang and D.F.Wong, "Planning Buffer Locations by Net¿work Flows", Intl. Symp. Physical Design, 2000, pp. 180--185.

Digital Library

Google Scholar

[8]

W.-J.Sun and C. Sechen, "Efficient and effective placement for very large circuits", IEEE Trans. CAD, vol 14, no. 3, pp.349--359, 1995.

Digital Library

Google Scholar

[9]

M.Wang, X.Yang, M.Sarrafzadeh, "Dragon2000: standard-cell placement tool for large industry circuits", IEEE/ACM ICCAD, 2000, pp. 260--263.

Digital Library

Google Scholar

[10]

A.E.Caldwell, A.B.Kahng, I.L.Markov, "Can recursive bisec¿tion alone produce routable placements", Design Automation Conference, 2000, pp. 477--482.

Digital Library

Google Scholar

[11]

"http://vlsicad.cs.binghamton.edu/benchmarks.html".

Google Scholar

[12]

"http://www.tu-dresden.de/mwism/skalicky/laspack/laspack.html"

Google Scholar

Cited By

View all

Dadaliaris AKranas GOikonomou PFloros GDossis M(2022)Exploiting Net Connectivity in Legalization and Detailed Placement ScenariosInformation10.3390/info1305021213:5(212)Online publication date: 20-Apr-2022
https://doi.org/10.3390/info13050212
Kahng ALienig JBehjat LYang S(2021)Advancing PlacementProceedings of the 2021 International Symposium on Physical Design10.1145/3439706.3446884(15-22)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439706.3446884
Wang FZhang JWu LZhang WLuo G(2017)Search space reduction for the non-exact projective NPNP Boolean matching problem2017 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2017.8050970(1-4)Online publication date: May-2017
https://doi.org/10.1109/ISCAS.2017.8050970
Show More Cited By

Index Terms

FAR: fixed-points addition & relaxation based placement
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

Recommendations

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation Conference

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...
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 ...

Comments

Information & Contributors

Information

Published In

ISPD '02: Proceedings of the 2002 international symposium on Physical design

April 2002

216 pages

ISBN:1581134606

DOI:10.1145/505388

General Chair:
Sachin Sapatnekar
University of Minnesota
,
Program Chair:
Massoud Pedram
USC

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: 07 April 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISPD02

Sponsor:

SIGDA

ISPD02: International Symposium on Physical Design

April 7 - 10, 2002

CA, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
823
Total Downloads

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

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dadaliaris AKranas GOikonomou PFloros GDossis M(2022)Exploiting Net Connectivity in Legalization and Detailed Placement ScenariosInformation10.3390/info1305021213:5(212)Online publication date: 20-Apr-2022
https://doi.org/10.3390/info13050212
Kahng ALienig JBehjat LYang S(2021)Advancing PlacementProceedings of the 2021 International Symposium on Physical Design10.1145/3439706.3446884(15-22)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439706.3446884
Wang FZhang JWu LZhang WLuo G(2017)Search space reduction for the non-exact projective NPNP Boolean matching problem2017 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2017.8050970(1-4)Online publication date: May-2017
https://doi.org/10.1109/ISCAS.2017.8050970
Wang XCai YZhou Q(2017)Cell spreading optimization for force-directed global placers2017 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2017.8050572(1-4)Online publication date: May-2017
https://doi.org/10.1109/ISCAS.2017.8050572
Pawanekar STrivedi GKapoor K(2015)A Nonlinear Analytical Optimization Method for Standard Cell Placement of VLSI Circuits2015 28th International Conference on VLSI Design10.1109/VLSID.2015.77(423-428)Online publication date: Jan-2015
https://doi.org/10.1109/VLSID.2015.77
Kim MLee DMarkov I(2013)SimPLCommunications of the ACM10.1145/2461256.246127956:6(105-113)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2461256.2461279
Wang SZhou QQian XCai YGao WZhou W(2012)Accurate and fast cell spreading for force directed placement2012 4th Asia Symposium on Quality Electronic Design (ASQED)10.1109/ACQED.2012.6320470(23-28)Online publication date: Jul-2012
https://doi.org/10.1109/ACQED.2012.6320470
Kim MLee DMarkov IScheffer LPhillips JHu A(2010)SimPLProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133568(649-656)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133568
Kahng APark CSharma PWang Q(2009)Lens aberration aware placement for timing yieldACM Transactions on Design Automation of Electronic Systems10.1145/1455229.145524514:1(1-26)Online publication date: 23-Jan-2009
https://dl.acm.org/doi/10.1145/1455229.1455245
Chu C(2009)PlacementElectronic Design Automation10.1016/B978-0-12-374364-0.50018-7(635-685)Online publication date: 2009
https://doi.org/10.1016/B978-0-12-374364-0.50018-7
Show More Cited By

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

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

MP-trees: a packing-based macro placement algorithm for mixed-size designs

A robust detailed placement for mixed-size IC designs