Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles

Jai-Ming Lin, You Lun Deng, Szu Ting Li, Bo Heng Yu, Li Yen Chang, Te Wei Peng

Research output: Contribution to journalArticle

Abstract

This paper introduces a routability-driven macro placement algorithm for mixed-size circuits and pays special attention to the effect of regular placement of macros. Once macros are placed with regularity, powerplanning will become easier and better routability can be obtained. Our methodology consists of two stages. First, placement prototyping stage distributes cells and macros over a placement region while keeping those macros and cells with a strong connection and in similar hierarchies tied together. This is facilitated by clustering macros and cells properly in advance. In the second stage, a deterministic macro legalization algorithm is proposed to arrange macros without deteriorating the result obtained in the previous stage. Although several macro legalization algorithms have been proposed in recent years, most of these works adopt the simulated annealing algorithm which usually takes longer runtime. Moreover, they either cannot handle preplaced macros or require preplaced macros to be abutted to chip boundaries. Unlike these approaches, our method iteratively places a macro by extracting available space for it. Experimental results demonstrate the efficiency and effectiveness of our method according to real industry circuits.

Original languageEnglish
Article number8478776
Pages (from-to)57-68
Number of pages12
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume27
Issue number1
DOIs
Publication statusPublished - 2019 Jan 1

Fingerprint

Macros
Networks (circuits)
Simulated annealing

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Lin, Jai-Ming ; Deng, You Lun ; Li, Szu Ting ; Yu, Bo Heng ; Chang, Li Yen ; Peng, Te Wei. / Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2019 ; Vol. 27, No. 1. pp. 57-68.
@article{0fdc53ad46424f7c80be50bfee9c4ea1,
title = "Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles",
abstract = "This paper introduces a routability-driven macro placement algorithm for mixed-size circuits and pays special attention to the effect of regular placement of macros. Once macros are placed with regularity, powerplanning will become easier and better routability can be obtained. Our methodology consists of two stages. First, placement prototyping stage distributes cells and macros over a placement region while keeping those macros and cells with a strong connection and in similar hierarchies tied together. This is facilitated by clustering macros and cells properly in advance. In the second stage, a deterministic macro legalization algorithm is proposed to arrange macros without deteriorating the result obtained in the previous stage. Although several macro legalization algorithms have been proposed in recent years, most of these works adopt the simulated annealing algorithm which usually takes longer runtime. Moreover, they either cannot handle preplaced macros or require preplaced macros to be abutted to chip boundaries. Unlike these approaches, our method iteratively places a macro by extracting available space for it. Experimental results demonstrate the efficiency and effectiveness of our method according to real industry circuits.",
author = "Jai-Ming Lin and Deng, {You Lun} and Li, {Szu Ting} and Yu, {Bo Heng} and Chang, {Li Yen} and Peng, {Te Wei}",
year = "2019",
month = "1",
day = "1",
doi = "10.1109/TVLSI.2018.2867833",
language = "English",
volume = "27",
pages = "57--68",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles. / Lin, Jai-Ming; Deng, You Lun; Li, Szu Ting; Yu, Bo Heng; Chang, Li Yen; Peng, Te Wei.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 27, No. 1, 8478776, 01.01.2019, p. 57-68.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles

AU - Lin, Jai-Ming

AU - Deng, You Lun

AU - Li, Szu Ting

AU - Yu, Bo Heng

AU - Chang, Li Yen

AU - Peng, Te Wei

PY - 2019/1/1

Y1 - 2019/1/1

N2 - This paper introduces a routability-driven macro placement algorithm for mixed-size circuits and pays special attention to the effect of regular placement of macros. Once macros are placed with regularity, powerplanning will become easier and better routability can be obtained. Our methodology consists of two stages. First, placement prototyping stage distributes cells and macros over a placement region while keeping those macros and cells with a strong connection and in similar hierarchies tied together. This is facilitated by clustering macros and cells properly in advance. In the second stage, a deterministic macro legalization algorithm is proposed to arrange macros without deteriorating the result obtained in the previous stage. Although several macro legalization algorithms have been proposed in recent years, most of these works adopt the simulated annealing algorithm which usually takes longer runtime. Moreover, they either cannot handle preplaced macros or require preplaced macros to be abutted to chip boundaries. Unlike these approaches, our method iteratively places a macro by extracting available space for it. Experimental results demonstrate the efficiency and effectiveness of our method according to real industry circuits.

AB - This paper introduces a routability-driven macro placement algorithm for mixed-size circuits and pays special attention to the effect of regular placement of macros. Once macros are placed with regularity, powerplanning will become easier and better routability can be obtained. Our methodology consists of two stages. First, placement prototyping stage distributes cells and macros over a placement region while keeping those macros and cells with a strong connection and in similar hierarchies tied together. This is facilitated by clustering macros and cells properly in advance. In the second stage, a deterministic macro legalization algorithm is proposed to arrange macros without deteriorating the result obtained in the previous stage. Although several macro legalization algorithms have been proposed in recent years, most of these works adopt the simulated annealing algorithm which usually takes longer runtime. Moreover, they either cannot handle preplaced macros or require preplaced macros to be abutted to chip boundaries. Unlike these approaches, our method iteratively places a macro by extracting available space for it. Experimental results demonstrate the efficiency and effectiveness of our method according to real industry circuits.

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

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

U2 - 10.1109/TVLSI.2018.2867833

DO - 10.1109/TVLSI.2018.2867833

M3 - Article

AN - SCOPUS:85054547106

VL - 27

SP - 57

EP - 68

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 1

M1 - 8478776

ER -