CR&P: an efficient co-operation between routing and placement
Authors: 
Erfan Aghaeekiasaraee, Aysa Fakheri Tabrizi, Tiago Augusto Fontana, Renan Netto, Sheiny Fabre Almeida, Upma Gandhi, José Luís Güntzel, David Westwick, Laleh BehjatAuthors Info & Claims
Pages 772 - 777
Abstract
Placement and Routing (P&R) are two main steps of the physical design flow implementation. Traditionally, because of their complexity, these two steps are performed separately. But the implementation of the physical design in advanced technology nodes shows that the performance of these two steps is tied to each other. Therefore, creating efficient co-operation between the routing and placement steps has become a hot topic in Electronic Design Automation (EDA). In this work, to achieve an efficient collaboration between the routing and placement engines, an iterative replacement and rerouting framework facilitated with an Integer Linear Programming (ILP)-based legalizer is proposed and tested on the ACM/IEEE International Symposium on Physical Design (ISPD) 2018 contest's benchmarks. Numerical results show that the proposed framework can improve detailed routing vias and wirelength by 2.06% and 0.14% on average in a reasonable runtime without adding new Design Rule Violations (DRVs). The proposed framework can be considered as an add-on to the physical design flow between global routing and detailed routing.
References
[1]
C. Alpert and et al, "Handbook of Algorithms for Physical Design Automation", 1st ed. Auerbach Publications, Nov. 2008.
[2]
A. Kahng and et al, "VLSI Physical Design: From Graph Partitioning to Timing Closure", 2011th ed. Springer Netherlands, 2011.
[3]
K. Hu and et al, "ICCAD-2020 cad contest in routing with cell movement," in ICCAD2020, 2020, pp. 1--4.
[4]
A. Kahng, "Advancing placement," in ISPD2021, March 2020, pp. 15--22.
[5]
S. Mantik and et al, "Ispd 2018 initial detailed routing contest and benchmarks," in ISPD2018, 2018, pp. 140--143.
[6]
N. K. Darav and et al, "Eh? placer: A high-performance modern technology-driven placer," ACM TODAES, vol. 21, no. 3, pp. 1--27, 2016.
[7]
T. Lin and et al, "Polar: A high performance mixed-size wirelengh-driven placer with density constraints," TCAD, vol. 34, no. 3, pp. 447--459, 2015.
[8]
X. He and et al, "Ripple 2.0: High quality routability-driven placement via global router integration," in 50th DAC, 2013, pp. 1--6.
[9]
C.-C. Huang and et al, "Ntuplace4dr: A detailed-routing-driven placer for mixed-size circuit designs with technology and region constraints," TCAD, vol. 37, no. 3, pp. 669--681, 2018.
[10]
Y. Lin and et al, "Dreamplace: Deep learning toolkit-enabled gpu acceleration for modern vlsi placement," in 56th DAC, 2019, pp. 1--6.
[11]
F. Gessler and et al, "A shared-memory parallel implementation of the replace global cell placer," in VLSID, 2020, pp. 78--83.
[12]
Y. Lin and et al, "Abcdplace: Accelerated batch-based concurrent detailed placement on multithreaded cpus and gpus," TCAD, vol. 39, no. 12, pp. 5083--5096, 2020.
[13]
L. Yibo and et al, "Mrdp: Multiple-row detailed placement of heterogeneous-sized cells for advanced nodes," TCAD, vol. 37, no. 6, pp. 1237--1250, 2018.
[14]
J. Chen and et al, "Mixed-cell-height detailed placement considering complex minimum-implant-area constraints," TCAD, pp. 1--1, 2020.
[15]
N. Viswanathan and et al, "Fastplace: efficient analytical placement using cell shifting, iterative local refinement,and a hybrid net model," TCAD, vol. 24, no. 5, pp. 722--733, 2005.
[16]
A. Kahng, L. Wang, and B. Xu, "Tritonroute: The open-source detailed router," TCAD, vol. 40, no. 3, pp. 547--559, 2021.
[17]
K. Hu and et al, "ICCAD-2021 cad contest in routing with cell movement," in ICCAD2021, 2021, pp. 1--4.
[18]
T. A. Fontana and et al, "Ilp-based global routing optimization with cell movements," in ISVLSI, 2021, pp. 25--30.
[19]
"Lef/def language reference," 2009, http://www.ispd.cc/contests/18/lefdefref.pdf.
[20]
J. Chen and et al, "Toward optimal legalization for mixed-cell-height circuit designs," in DAC, 2017, pp. 1--6.
[21]
J. Liu and et al, "CUGR: detailed-routability-driven 3d global routing with probabilistic resource model," in DAC, 2020, pp. 1--6.
[22]
Y. J. Chang and et al, "Nthu-route 2.0: A fast and stable global router," in ICCAD, 2008, pp. 338--343.
[23]
C. Sechen and et al, "The timberwolf placement and routing package," IEEE Journal of Solid-State Circuits, vol. 20, no. 2, pp. 510--522, 1985.
[24]
"The boost c++ libraries." [Online]. Available: https://www.boost.org/users/history/version1680.html
[25]
"IBM ILOG CPLEX." [Online]. Available: https://www.ibm.com/products/ilog-cplex-optimization-studio
- CR&P: an efficient co-operation between routing and placement
Recommendations
Area-I/O flip-chip routing for chip-package co-design considering signal skews
The area-input/output (I/O) flip-chip package provides a high chip-density solution to the demand of more I/Os in very large scale integration designs; it can achieve smaller package size, shorter wirelength, and better signal and power integrity. In ...
Full-Chip Routing Considering Double-Via Insertion
As the technology node advances into the nanometer era, via-open defects are one of the dominant failures due to the copper cladding process. To improve via yield and reliability, redundant-via insertion is a highly recommended technique proposed by ...
Flip-chip routing with unified area-I/O pad assignments for package-board co-design
DAC '09: Proceedings of the 46th Annual Design Automation ConferenceIn this paper, we present a novel flip-chip routing algorithm for package-board co-design. Unlike the previous works that can consider only either free- or pre-assignment routing, our router is the first work in the literature that can handle both the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2022
1637 pages
ISBN:9783981926361
- General Chairs:
- Cristiana Bolchini,
- Ian O'Connor,
- Program Chairs:
- Ingrid Verbauwhede,
- Robert Wille
Sponsors
In-Cooperation
- EDAA: European Design Automation Association
- IEEE SSCS Shanghai Chapter
- ESDA: Electronic System Design Alliance
- IEEE CEDA
- IEEE CS
- IEEE-RAS: Robotics and Automation
Publisher
European Design and Automation Association
Leuven, Belgium
Publication History
Published: 31 May 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
DATE '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 518 of 1,794 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 34Total Downloads
- Downloads (Last 12 months)14
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
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.
Sign in