Enhanced perturbing algorithm for floorplan design using the O-tree representation

Yingxin Pang; Chung Kuan Cheng; Takeshi Yoshimura

Enhanced perturbing algorithm for floorplan design using the O-tree representation

Yingxin Pang^*, Chung Kuan Cheng, Takeshi Yoshimura

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

62 Citations (Scopus)

Abstract

Recently, a deterministic algorithm based on the O-tree representation has been proposed. This method generates excellent layout results on MCNC test cases with O(n³) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n²). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time.

Original language	English
Title of host publication	Proceedings of the International Symposium on Physical Design
Place of Publication	New York, NY, United States
Publisher	ACM
Pages	168-173
Number of pages	6
Publication status	Published - 2000
Externally published	Yes
Event	ISPD-2000: International Symposium on Physical Design - San Diego, CA, USA Duration: 2000 Apr 9 → 2000 Apr 12

Other

Other	ISPD-2000: International Symposium on Physical Design
City	San Diego, CA, USA
Period	00/4/9 → 00/4/12

ASJC Scopus subject areas

Engineering(all)

Cite this

@inproceedings{181ab786e1ab441a95f2ad5187264a28,

title = "Enhanced perturbing algorithm for floorplan design using the O-tree representation",

abstract = "Recently, a deterministic algorithm based on the O-tree representation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time.",

author = "Yingxin Pang and Cheng, {Chung Kuan} and Takeshi Yoshimura",

year = "2000",

language = "English",

pages = "168--173",

booktitle = "Proceedings of the International Symposium on Physical Design",

publisher = "ACM",

note = "ISPD-2000: International Symposium on Physical Design ; Conference date: 09-04-2000 Through 12-04-2000",

}

TY - GEN

T1 - Enhanced perturbing algorithm for floorplan design using the O-tree representation

AU - Pang, Yingxin

AU - Cheng, Chung Kuan

AU - Yoshimura, Takeshi

PY - 2000

Y1 - 2000

N2 - Recently, a deterministic algorithm based on the O-tree representation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time.

AB - Recently, a deterministic algorithm based on the O-tree representation has been proposed. This method generates excellent layout results on MCNC test cases with O(n3) complexity, where n is the number of blocks. In this paper, we reduce the complexity of the deterministic algorithm to O(n2). Experimental results indicate our algorithm maintains the high quality of the deterministic algorithm at a fraction of the CPU time.

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

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

M3 - Conference contribution

AN - SCOPUS:0033704928

SP - 168

EP - 173

BT - Proceedings of the International Symposium on Physical Design

PB - ACM

CY - New York, NY, United States

T2 - ISPD-2000: International Symposium on Physical Design

Y2 - 9 April 2000 through 12 April 2000

ER -

Enhanced perturbing algorithm for floorplan design using the O-tree representation

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this