A matrix synthesis approach to thermal placement

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

doi:10.1145/267665.267708

A matrix synthesis approach to thermal placement

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

42 Citations (Scopus)

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 non-negative 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 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.

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	163-168
Number of pages	6
ISBN (Print)	9780897919272
DOIs	https://doi.org/10.1145/267665.267708
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	https://dl.acm.org/doi/proceedings/10.1145/267665 (Conference proceedings )

Scopus Subject Areas

Electrical and Electronic Engineering

Access to Document

10.1145/267665.267708

Cite this

@inproceedings{103ae976dfca40fd90b7062a482f3adb,

title = "A matrix synthesis approach to thermal placement",

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 non-negative 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 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.",

author = "Chu, {Chris C.N.} and Wong, {D. F.}",

year = "1997",

month = apr,

day = "14",

doi = "10.1145/267665.267708",

language = "English",

isbn = "9780897919272",

series = "Proceedings of the International Symposium on Physical Design, ISPD",

publisher = "Association for Computing Machinery (ACM)",

pages = "163--168",

booktitle = "ISPD '97",

address = "United States",

note = "1997 International Symposium on Physical Design, ISPD 1997 ; Conference date: 14-04-1997 Through 16-04-1997",

url = "https://dl.acm.org/doi/proceedings/10.1145/267665",

}

Chu, CCN & Wong, DF 1997, A matrix synthesis approach to thermal placement. in ISPD '97: Proceedings of the 1997 International Symposium on Physical Design. Proceedings of the International Symposium on Physical Design, ISPD, Association for Computing Machinery (ACM), pp. 163-168, 1997 International Symposium on Physical Design, ISPD 1997, Napa Valley, California, United States, 14/04/97. https://doi.org/10.1145/267665.267708

A matrix synthesis approach to thermal placement. / Chu, Chris C.N.; Wong, D. F.
ISPD '97: Proceedings of the 1997 International Symposium on Physical Design. Association for Computing Machinery (ACM), 1997. p. 163-168 (Proceedings of the International Symposium on Physical Design, ISPD).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - A matrix synthesis approach to thermal placement

AU - Chu, Chris C.N.

AU - Wong, D. F.

PY - 1997/4/14

Y1 - 1997/4/14

N2 - 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 × n matrix out of the given numbers such that the maximum sum among all t×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.

AB - 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 × n matrix out of the given numbers such that the maximum sum among all t×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.

UR - http://www.scopus.com/inward/record.url?scp=0030709769&partnerID=8YFLogxK

U2 - 10.1145/267665.267708

DO - 10.1145/267665.267708

M3 - Conference proceeding

AN - SCOPUS:0030709769

SN - 9780897919272

T3 - Proceedings of the International Symposium on Physical Design, ISPD

SP - 163

EP - 168

BT - ISPD '97

PB - Association for Computing Machinery (ACM)

T2 - 1997 International Symposium on Physical Design, ISPD 1997

Y2 - 14 April 1997 through 16 April 1997

ER -

A matrix synthesis approach to thermal placement

Abstract

Publication series

Symposium

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this