Abstract
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 nonnegative 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 submatrices is minimized. We show that MSP is NPcomplete 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 language  English 

Title of host publication  ISPD '97 
Subtitle of host publication  Proceedings of the 1997 International Symposium on Physical Design 
Publisher  Association for Computing Machinery (ACM) 
Pages  163168 
Number of pages  6 
ISBN (Print)  9780897919272 
DOIs  
Publication status  Published  14 Apr 1997 
Event  1997 International Symposium on Physical Design, ISPD 1997  Napa Valley, United States Duration: 14 Apr 1997 → 16 Apr 1997 https://dl.acm.org/doi/proceedings/10.1145/267665 (Conference proceedings ) 
Publication series
Name  Proceedings of the International Symposium on Physical Design, ISPD 

Symposium
Symposium  1997 International Symposium on Physical Design, ISPD 1997 

Country/Territory  United States 
City  Napa Valley 
Period  14/04/97 → 16/04/97 
Internet address 

Scopus Subject Areas
 Electrical and Electronic Engineering