An orthogonal simulated annealing algorithm for large floorplanning problems

Shinn-Ying Ho; Shinn Jang Ho; Yi Kuang Lin; William Cheng Chung Chu

doi:10.1109/TVLSI.2004.831464

An orthogonal simulated annealing algorithm for large floorplanning problems

Shinn-Ying Ho^*, Shinn Jang Ho, Yi Kuang Lin, William Cheng Chung Chu

^*Corresponding author for this work

Department of Biological Science and Technology

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

The conventional simulated annealing with some random generation mechanism using the sequence-pair topological representation in block placement and floorplanning is effective for a very small number of modules (40-50). This paper proposes an orthogonal simulated annealing algorithm (OSA) with an efficient generation mechanism (EGM) for solving large floorplanning problems. EGM samples a small number of representative floorplans and then efficiently derives a high-performance floorplan by using a systematic reasoning method for the next move of OSA based on orthogonal experimental design. Furthermore, an improved swap operation is proposed which cooperates with EGM to make OSA efficient. Excellent experimental results using the Microelectronics Center of North Carolina and the Gigascale Sysems Research Center benchmarks show that OSA performs better than existing methods for large floorplanning problems.

Original language	English
Pages (from-to)	874-876
Number of pages	3
Journal	IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume	12
Issue number	8
DOIs	https://doi.org/10.1109/TVLSI.2004.831464
State	Published - 1 Aug 2004

Keywords

Floorplanning
Optimization
Orthogonal experimental design
Simulated annealing
Very large scale integration (VLSI)

Access to Document

10.1109/TVLSI.2004.831464

Link to publication in Scopus

Fingerprint Dive into the research topics of 'An orthogonal simulated annealing algorithm for large floorplanning problems'. Together they form a unique fingerprint.

Cite this

@article{7e6444b84dbf4be9ae3c2e601efa8331,

title = "An orthogonal simulated annealing algorithm for large floorplanning problems",

abstract = "The conventional simulated annealing with some random generation mechanism using the sequence-pair topological representation in block placement and floorplanning is effective for a very small number of modules (40-50). This paper proposes an orthogonal simulated annealing algorithm (OSA) with an efficient generation mechanism (EGM) for solving large floorplanning problems. EGM samples a small number of representative floorplans and then efficiently derives a high-performance floorplan by using a systematic reasoning method for the next move of OSA based on orthogonal experimental design. Furthermore, an improved swap operation is proposed which cooperates with EGM to make OSA efficient. Excellent experimental results using the Microelectronics Center of North Carolina and the Gigascale Sysems Research Center benchmarks show that OSA performs better than existing methods for large floorplanning problems.",

keywords = "Floorplanning, Optimization, Orthogonal experimental design, Simulated annealing, Very large scale integration (VLSI)",

author = "Shinn-Ying Ho and Ho, {Shinn Jang} and Lin, {Yi Kuang} and Chu, {William Cheng Chung}",

year = "2004",

month = aug,

day = "1",

doi = "10.1109/TVLSI.2004.831464",

language = "English",

volume = "12",

pages = "874--876",

journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",

issn = "1063-8210",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "8",

}

TY - JOUR

T1 - An orthogonal simulated annealing algorithm for large floorplanning problems

AU - Ho, Shinn-Ying

AU - Ho, Shinn Jang

AU - Lin, Yi Kuang

AU - Chu, William Cheng Chung

PY - 2004/8/1

Y1 - 2004/8/1

N2 - The conventional simulated annealing with some random generation mechanism using the sequence-pair topological representation in block placement and floorplanning is effective for a very small number of modules (40-50). This paper proposes an orthogonal simulated annealing algorithm (OSA) with an efficient generation mechanism (EGM) for solving large floorplanning problems. EGM samples a small number of representative floorplans and then efficiently derives a high-performance floorplan by using a systematic reasoning method for the next move of OSA based on orthogonal experimental design. Furthermore, an improved swap operation is proposed which cooperates with EGM to make OSA efficient. Excellent experimental results using the Microelectronics Center of North Carolina and the Gigascale Sysems Research Center benchmarks show that OSA performs better than existing methods for large floorplanning problems.

AB - The conventional simulated annealing with some random generation mechanism using the sequence-pair topological representation in block placement and floorplanning is effective for a very small number of modules (40-50). This paper proposes an orthogonal simulated annealing algorithm (OSA) with an efficient generation mechanism (EGM) for solving large floorplanning problems. EGM samples a small number of representative floorplans and then efficiently derives a high-performance floorplan by using a systematic reasoning method for the next move of OSA based on orthogonal experimental design. Furthermore, an improved swap operation is proposed which cooperates with EGM to make OSA efficient. Excellent experimental results using the Microelectronics Center of North Carolina and the Gigascale Sysems Research Center benchmarks show that OSA performs better than existing methods for large floorplanning problems.

KW - Floorplanning

KW - Optimization

KW - Orthogonal experimental design

KW - Simulated annealing

KW - Very large scale integration (VLSI)

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

U2 - 10.1109/TVLSI.2004.831464

DO - 10.1109/TVLSI.2004.831464

M3 - Article

AN - SCOPUS:4043104116

VL - 12

SP - 874

EP - 876

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

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

SN - 1063-8210

IS - 8

ER -