A matrix synthesis approach to thermal placement

Chris C.N. Chu, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

42 Citations (Scopus)


In this paper, we consider the thermal placement problem for gate arrays. We introduce a new combinatorial optimization problem MSP (Matrix Synthesis Problem) to model the thermal placement problem. Given a list of mn non-negative real numbers and an integer t, MSP constructs a m × n matrix out of the given numbers such that the maximum sum among all t×t sub-matrices is minimized. We show that MSP is NP-complete and present several provably good approximation algorithms for the problem. We also demonstrate that our thermal placement strategy is flexible enough to allow simultaneous consideration of other objectives such as wiring.

Original languageEnglish
Title of host publicationISPD '97
Subtitle of host publicationProceedings of the 1997 International Symposium on Physical Design
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)9780897919272
Publication statusPublished - 14 Apr 1997
Event1997 International Symposium on Physical Design, ISPD 1997 - Napa Valley, United States
Duration: 14 Apr 199716 Apr 1997
https://dl.acm.org/doi/proceedings/10.1145/267665 (Conference proceedings )

Publication series

NameProceedings of the International Symposium on Physical Design, ISPD


Symposium1997 International Symposium on Physical Design, ISPD 1997
Country/TerritoryUnited States
CityNapa Valley
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'A matrix synthesis approach to thermal placement'. Together they form a unique fingerprint.

Cite this