A matrix synthesis approach to thermal placement

Author

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

Author_Institution

Dept. of Comput. Sci., Texas Univ., Austin, TX, USA

Volume

17

Issue

11

fYear

1998

fDate

11/1/1998 12:00:00 AM

Firstpage

1166

Lastpage

1174

Abstract

In this paper, we consider the thermal placement problem for gate arrays. We introduce a new combinatorial optimization problem, matrix synthesis problem (MSP), 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 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

Keywords

VLSI; circuit optimisation; integrated circuit layout; integrated circuit packaging; integrated circuit reliability; logic CAD; logic arrays; wiring; NP-complete; combinatorial optimization problem; matrix synthesis approach; matrix synthesis problem; nonnegative real numbers; provably good approximation algorithms; thermal placement; wiring; Approximation algorithms; Bandwidth; Circuits; Clocks; Energy consumption; Frequency; Packaging; Transmission line matrix methods; Very large scale integration; Wiring;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.736189

Filename

736189