Matrix synthesis approach to thermal placement

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

Research output: Contribution to conferencePaperpeer-review


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 (US)
Number of pages6
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 1st International Symposium on Physical Design, ISPD - Napa Valley, CA, USA
Duration: Apr 14 1997Apr 16 1997


OtherProceedings of the 1997 1st International Symposium on Physical Design, ISPD
CityNapa Valley, CA, USA

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


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

Cite this