Solving modern mixed-size placement instances

Jarrod A. Roy, Aaron N. Ng, Rajat Aggarwal, Venky Ramachandran, Igor L. Markov

Research output: Contribution to journalArticle

  • 6 Citations

Abstract

Physical design of modern systems-on-chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom register-transfer level (RTL) blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task. To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying pre-existing benchmark instances. Furthermore, we propose algorithms that facilitate placement of these difficult instances. Empirically, our techniques consistently produce legal placements, and on instances where comparison is possible, reduce wirelength by 13% over Capo 9.4 and 31% over PATOMA 1.0-the pre-existing tools that most frequently produce legal placements in our experiments.

Original languageEnglish (US)
Pages (from-to)262-275
Number of pages14
JournalIntegration, the VLSI Journal
Volume42
Issue number2
DOIs
StatePublished - Feb 2009

Fingerprint

Experiments
Digital integrated circuits
Logic gates
Intellectual property
System-on-chip

Keywords

  • Circuit layout
  • Floorplanning
  • Placement
  • RTL

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software
  • Electrical and Electronic Engineering

Cite this

Roy, J. A., Ng, A. N., Aggarwal, R., Ramachandran, V., & Markov, I. L. (2009). Solving modern mixed-size placement instances. Integration, the VLSI Journal, 42(2), 262-275. DOI: 10.1016/j.vlsi.2008.09.003

Solving modern mixed-size placement instances. / Roy, Jarrod A.; Ng, Aaron N.; Aggarwal, Rajat; Ramachandran, Venky; Markov, Igor L.

In: Integration, the VLSI Journal, Vol. 42, No. 2, 02.2009, p. 262-275.

Research output: Contribution to journalArticle

Roy, JA, Ng, AN, Aggarwal, R, Ramachandran, V & Markov, IL 2009, 'Solving modern mixed-size placement instances' Integration, the VLSI Journal, vol 42, no. 2, pp. 262-275. DOI: 10.1016/j.vlsi.2008.09.003
Roy JA, Ng AN, Aggarwal R, Ramachandran V, Markov IL. Solving modern mixed-size placement instances. Integration, the VLSI Journal. 2009 Feb;42(2):262-275. Available from, DOI: 10.1016/j.vlsi.2008.09.003

Roy, Jarrod A.; Ng, Aaron N.; Aggarwal, Rajat; Ramachandran, Venky; Markov, Igor L. / Solving modern mixed-size placement instances.

In: Integration, the VLSI Journal, Vol. 42, No. 2, 02.2009, p. 262-275.

Research output: Contribution to journalArticle

@article{bf61ecac0b044ac1bc6d04b48dc49c2f,
title = "Solving modern mixed-size placement instances",
abstract = "Physical design of modern systems-on-chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom register-transfer level (RTL) blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task. To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying pre-existing benchmark instances. Furthermore, we propose algorithms that facilitate placement of these difficult instances. Empirically, our techniques consistently produce legal placements, and on instances where comparison is possible, reduce wirelength by 13% over Capo 9.4 and 31% over PATOMA 1.0-the pre-existing tools that most frequently produce legal placements in our experiments.",
keywords = "Circuit layout, Floorplanning, Placement, RTL",
author = "Roy, {Jarrod A.} and Ng, {Aaron N.} and Rajat Aggarwal and Venky Ramachandran and Markov, {Igor L.}",
year = "2009",
month = "2",
doi = "10.1016/j.vlsi.2008.09.003",
volume = "42",
pages = "262--275",
journal = "Integration, the VLSI Journal",
issn = "0167-9260",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Solving modern mixed-size placement instances

AU - Roy,Jarrod A.

AU - Ng,Aaron N.

AU - Aggarwal,Rajat

AU - Ramachandran,Venky

AU - Markov,Igor L.

PY - 2009/2

Y1 - 2009/2

N2 - Physical design of modern systems-on-chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom register-transfer level (RTL) blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task. To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying pre-existing benchmark instances. Furthermore, we propose algorithms that facilitate placement of these difficult instances. Empirically, our techniques consistently produce legal placements, and on instances where comparison is possible, reduce wirelength by 13% over Capo 9.4 and 31% over PATOMA 1.0-the pre-existing tools that most frequently produce legal placements in our experiments.

AB - Physical design of modern systems-on-chip is extremely challenging. Such digital integrated circuits often contain tens of millions of logic gates, intellectual property blocks, embedded memories and custom register-transfer level (RTL) blocks. At current and future technology nodes, their power and performance are impacted, more than ever, by the placement of their modules. However, our experiments show that traditional techniques for placement and floorplanning, and existing academic tools cannot reliably solve the placement task. To study this problem, we identify particularly difficult industrial instances and reproduce the failures of existing tools by modifying pre-existing benchmark instances. Furthermore, we propose algorithms that facilitate placement of these difficult instances. Empirically, our techniques consistently produce legal placements, and on instances where comparison is possible, reduce wirelength by 13% over Capo 9.4 and 31% over PATOMA 1.0-the pre-existing tools that most frequently produce legal placements in our experiments.

KW - Circuit layout

KW - Floorplanning

KW - Placement

KW - RTL

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

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

U2 - 10.1016/j.vlsi.2008.09.003

DO - 10.1016/j.vlsi.2008.09.003

M3 - Article

VL - 42

SP - 262

EP - 275

JO - Integration, the VLSI Journal

T2 - Integration, the VLSI Journal

JF - Integration, the VLSI Journal

SN - 0167-9260

IS - 2

ER -