A matrix synthesis approach to thermal placement

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

Research output: Contribution to journalArticle

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 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 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)
Pages (from-to)1166-1174
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume17
Issue number11
DOIs
StatePublished - Dec 1 1998
Externally publishedYes

Keywords

  • Approximation algorithm
  • Thermal placement

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

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

  • Cite this