Article

Partition-driven standard cell thermal placement

Authors:

Sachin SapatnekarAuthors Info & Claims

ISPD '03: Proceedings of the 2003 international symposium on Physical design

Pages 75 - 80

https://doi.org/10.1145/640000.640018

Published: 06 April 2003 Publication History

Abstract

The thermal problem has been emerged as one of the key issues for next-generation IC design. In this paper, we propose a scheme to achieve better thermal distribution for partition-driven standard cell placement. The proposed heuristic uses a multigrid-like method that simplifies the thermal equation at each level of partitioning and makes it possible to incorporate temperature considerations directly as placement constraints, thus leading to better thermal distribution. Our experimental results verify the effectiveness of our scheme. We also describe an algorithm to derive a compact thermal model with a complexity of O(mn + m²), where m is the number of the mesh nodes on the substrate surface and $n$ is the number of all internal mesh nodes.

References

[1]

K. Banerjee, A. Mehrotra, A. Sangiovanni-Vincentelli, and C. Hu, "On thermal effects in deep sub-micron VLSI interconnects," Proceedings of the ACM/IEEE Design Automation Conference, pp. 885--891, 1999.

Digital Library

[2]

C. Tsai and S. Kang, "Cell-level placement for improving subtrate thermal distribution," IEEE Transactions on Computer-Aided Design, Vol. 19, No. 2, pp. 253--266, Feb 2000.

Digital Library

[3]

C. Chu and D. F. Wong, "A matrix synthesis approach to thermal placement," IEEE Transactions on Computer-Aided Design, Vol. 17, No. 11, pp. 1166--1174, Nov 1998.

Digital Library

[4]

G. Ausiello et al., Complexity and Approximation: Combinatorial Optimization Problems and their Approximability, Berlin, Germany: Springer, 1999.

Digital Library

[5]

W. Sun and C. Sechen, "Efficient and effective placement for very large circuits," IEEE Transactions on Computer-Aided Design, Vol. 14, No. 3, pp. 349--359, March 1995.

Digital Library

[6]

J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich, "GORDIAN: VLSI Placement by quadratic programming and slicing optimization," IEEE Transactions on Computer-Aided Design, Vol. 10, No. 3, pp. 356--365, March 1991.

Digital Library

[7]

C. J. Alpert, T. Chan, A. B. Kahng, I. Markov, and P. Mulet, "Faster minimization of linear wirelength for global placement," IEEE Transactions on Computer-Aided Design, Vol. 17, No. 1, pp.3--13, Jan 1998.

Digital Library

[8]

C. Alpert, J.-H. Huang, and A. B. Kahng, "Multilevel circuit partitioning," Proceedings of the ACM/IEEE Design Automation Conference, pp. 530--533, 1997.

Digital Library

[9]

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel hypergraph partitioning: application in VLSI design," Proceedings of the ACM/IEEE Design Automation Conference, pp. 526--529, 1997.

Digital Library

[10]

K. Zhong and S. Dutt, "Effective partition-driven placement with simultaneous level processing and global net views," Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 254--259, 2000.

Digital Library

[11]

G. Golub and C. F. Van Loan, Matrix Computation, Baltimore, MD: John Hopkins University Press, 1996.

[12]

R. Horn and C. Johnson, Matrix Analysis, Cambridge, UK: Cambridge University Press, 1985

Digital Library

[13]

U. Trottenberg, C. Oosterlee and A Schuller, Multigrid, New York: Academic Press, 2001.

Digital Library

[14]

C. M. Fiduccia and R. M. Mattheyses, "A Linear Time Heuristic for Improving Network Partitions," Proceedings of the ACM/IEEE Design Automation Conference, pp. 175--181, 1982.

Digital Library

[15]

A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov, and A. Zelikovsky, "On Wirelength Estimations for Row-Based Placement," IEEE Transactions on Computer-Aided Design, Vol. 18, No. 9, pp. 1265--1278, Sep 1999.

Digital Library

[16]

http://vlsicad.cs.ucla.edu/software/PDtools/

[17]

A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning," ACM Journal of Experimental Algorithms, Vol. 5, 2000.

Digital Library

[18]

http://www.netlib.org/c/meschach/

[19]

P. Madden, "Reporting of Standard Cell Placement Results," Proceedings of the International Symposium on Physical Design, pp. 30--35, 2001.

Digital Library

[20]

Y. Cheng and S. Kang, "A Temperature-Aware Simulation Environment for Reliable ULSI Chip Design," IEEE Transactions on Computer-Aided Design, Vol. 19, No. 10, pp. 1211--1220, Oct 2000.

Digital Library

Cited By

Lin JChen THsieh HShyu YChang YLu J(2021)Thermal-Aware Fixed-Outline Floorplanning Using Analytical Models With Thermal-Force ModulationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.306266929:5(985-997)Online publication date: May-2021
https://doi.org/10.1109/TVLSI.2021.3062669
Delaram HDastfan ANorouzi M(2018)Optimal Thermal Placement and Loss Estimation for Power Electronic ModulesIEEE Transactions on Components, Packaging and Manufacturing Technology10.1109/TCPMT.2017.27812828:2(236-243)Online publication date: Feb-2018
https://doi.org/10.1109/TCPMT.2017.2781282
Pangracious VMarrakchi ZMehrez HPangracious VMarrakchi ZMehrez H(2015)Three-Dimensional Thermal Modeling: Tools and MethodologiesThree-Dimensional Design Methodologies for Tree-based FPGA Architecture10.1007/978-3-319-19174-4_7(147-168)Online publication date: 26-Jun-2015
https://doi.org/10.1007/978-3-319-19174-4_7
Show More Cited By

Index Terms

Partition-driven standard cell thermal 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
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

Thermal via placement in 3D ICs
ISPD '05: Proceedings of the 2005 international symposium on Physical design

As thermal problems become more evident, new physical design paradigms and tools are needed to alleviate them. Incorporating thermal vias into integrated circuits (ICs) is a promising way of mitigating thermal issues by lowering the thermal resistance ...
Placement of thermal vias in 3-D ICs using various thermal objectives

As thermal problems become more evident, new physical design paradigms and tools are needed to alleviate them. Incorporating thermal vias into integrated circuits (ICs) is a promising way of mitigating thermal issues by lowering the effective-thermal ...
Placement of 3D ICs with thermal and interlayer via considerations
DAC '07: Proceedings of the 44th annual Design Automation Conference

Thermal problems and limitations on interlayer via densities are important design constraints on three-dimensional integrated circuits (3D ICs), and need to be considered during global and detailed placement. Analytical and partitioning-based techniques ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '03: Proceedings of the 2003 international symposium on Physical design

April 2003

218 pages

ISBN:1581136501

DOI:10.1145/640000

General Chair:
Massoud Pedram
USC
,
Program Chair:
Charles J. Alpert
IBM

Copyright © 2003 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 April 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD03

Sponsor:

ISPD03: International Symposium on Physical Design

April 6 - 9, 2003

CA, Monterey, 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

60
Total Citations
View Citations
718
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lin JChen THsieh HShyu YChang YLu J(2021)Thermal-Aware Fixed-Outline Floorplanning Using Analytical Models With Thermal-Force ModulationIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2021.306266929:5(985-997)Online publication date: May-2021
https://doi.org/10.1109/TVLSI.2021.3062669
Delaram HDastfan ANorouzi M(2018)Optimal Thermal Placement and Loss Estimation for Power Electronic ModulesIEEE Transactions on Components, Packaging and Manufacturing Technology10.1109/TCPMT.2017.27812828:2(236-243)Online publication date: Feb-2018
https://doi.org/10.1109/TCPMT.2017.2781282
Pangracious VMarrakchi ZMehrez HPangracious VMarrakchi ZMehrez H(2015)Three-Dimensional Thermal Modeling: Tools and MethodologiesThree-Dimensional Design Methodologies for Tree-based FPGA Architecture10.1007/978-3-319-19174-4_7(147-168)Online publication date: 26-Jun-2015
https://doi.org/10.1007/978-3-319-19174-4_7
Liu SLuo RAroonsantidecha SChin CChen H(2014)Fast Thermal Aware Placement With Accurate Thermal Analysis Based on Green FunctionIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2013.226858222:6(1404-1415)Online publication date: Jun-2014
https://doi.org/10.1109/TVLSI.2013.2268582
Liu SLuo RChen HMacii E(2013)A network-flow based algorithm for power density mitigation at post-placement stageProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485691(1707-1710)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485691
Cuesta DRisco-Martin JAyala JIgnacio Hidalgo J(2013)3D thermal-aware floorplanner using a MOEA approximationIntegration, the VLSI Journal10.1016/j.vlsi.2012.04.00346:1(10-21)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.vlsi.2012.04.003
Banerjee SBhattacharya BDas SKarmakar AMaheshwari ARoy S(2012)On the Construction of a Generalized Voronoi Inverse of a Rectangular TessellationProceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering10.1109/ISVD.2012.24(132-137)Online publication date: 27-Jun-2012
https://dl.acm.org/doi/10.1109/ISVD.2012.24
Gracia NRajaram SNivethitha NSudarsan A(2012)Thermal aware modern VLSI floorplanning2012 International Conference on Devices, Circuits and Systems (ICDCS)10.1109/ICDCSyst.2012.6188701(187-190)Online publication date: Mar-2012
https://doi.org/10.1109/ICDCSyst.2012.6188701
Aroonsantidecha SLiu SChing-Yu Chin Hung-Ming Chen (2012)A fast thermal aware placement with accurate thermal analysis based on Green function17th Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2012.6164986(425-430)Online publication date: Jan-2012
https://doi.org/10.1109/ASPDAC.2012.6164986
Cuesta DRisco-Martin JAyala J(2012)Full Length ArticleMicroprocessors & Microsystems10.1016/j.micpro.2012.02.01236:5(344-354)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1016/j.micpro.2012.02.012
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.

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