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 x n matrix out of the given numbers such that the maximum sum among all t x 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. High performance circuits consume a considerable amount of power due to increases of frequency, bandwidth, and system integration. For examples, the two recent high-performance chips, Alpha 21164 and PowerPC 620, consume 50 W and 30 W, respectively, on 3 cm* dies. It can be extrapolated that a 10 cm next-generation microprocessor, clocked at 500 MHz would consume 300 W [S]. Consumed power is converted directly into dissipated heat. In the past decade, heat produced by a chip has increased from 2.2 to 10 W/cm' due to the continuous increase of the clock frequency and the total number of transistors [S]. Higher temperature not only affects circuit performance directly by slowing down the tranBiBtOm on CMOS chips but also decreases their reliability. A circuit with considerable power consumption requires extra expensive cost to remove heat at the packaging level, and therefore the reduction of power dissipation is required at the chip design stages. (See [6] for a survey of current research efforts in power minimization in IC design.) Even when the total power consumption of a chip is constrained, an unevenly distributed heat dissipation by the gates in the chip may produce hot spots which can lead to reliability problems. It is also desirable to have an even temperature distribution for the temperature-sensitive circuit (whose characteristic, such as the gain factor, p, of a CMOS or bipolar circuit, affects its output). Therefore, during physical design of a VLSI chip, it is important to place the gates such that heat dissipation by the gates are evenly distributed. *This work was partially supported by a grant from the Avant! Corporation, Iknnission IO mnke digilnbllnrd copies of all or part ofthis mnterinl for persowd or clnssroom use is grannbzd wiUlout fee provided (1~ the copies nrc not mnde or dislributcd for prolit or commercial ndvnntnge. Ihe copyriglit nolice, Ule tiUe of the publication nnd its date appear. and notice is givcii 111nt copyright is by permission of the ACM, Inc. To copy olhwwise. to republiall. to post on scrvcrs or lo rediskibute 10 lists, requires specific pemiission nnd/or Tea The thermal placement problem has been studied in the past for placing chips during the packaging stage (for PCBs and MCMs) [2, 4, 51. However, since thermal placement of gates within a single chip was not of major concern in the past, existing placement algorithms [7] only focus on minimizing area and delay but do not consider heat dissipation. One exception is [l] but it only addresses thermal issues during IC floorplanning. 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. Basically, MSP is to synthesize a matrix out of a given list of numbers such that no sub-matrix of a particular size has a large sum. In this paper, sub-matrix means those consisting of consecutive rows and columns. It is not difficult to see that MSP models the thermal placement problem for gate arrays. We represent the amount of heat generated by each gate by a non-negative real number. (If we have less gates than the number of array slots, we can add some zeros.) A sub-matrix in St(M) corresponds to a region of size t x t on the chip. The sub-matrix with the largest sum corresponds to the hottest region on the chip. So MSP is equivalent to finding a placement of the gates such that the temperature of the hottest region is the lowest among all possible placements. 163
Chu and Wong proposed a matrix synthesis approach to thermal placement REF .
A matrix synthesis approach to thermal placement
ISPD '97
Computer Science