A matrix synthesis approach to thermal placement

In this paper, we consider the thermal placement problem for gate arrays. W e introduce a new combinatorial optimization problem, matrix synthesis prob lem (MSP), to model the thermal placement problem. Given a list of mn nonne gative real numbers and an integer t, MSP constructs a m x n matrix out of the given numbers such that the maximum sum among all t x t submatrices is minimized. We show that MSP is NP-complete and present several provably goo d approximation algorithms for the problem. We also demonstrate that our th ermal placement strategy is flexible enough to allow simultaneous considera tion of other objectives such as wiring.