A corner stitching compliant B-tree representation and its applications to analog placement

Hui Fang Tsao*, Pang Yen Chou, Shih Lun Huang, Yao Wen Chang, Po-Hung Lin, Duan Ping Chen, Dick Liu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

20 Scopus citations

Abstract

Modern circuit placement, especially analog placement, often needs to consider various constraints, such as symmetry, proximity, preplaced, variant, fixed-boundary, minimum separation, boundary, and fixed-outline constraints, for better electrical effects and higher performance. To handle these diverse constraints, topo-logical floorplan representations are pervasively used because of their higher flexibility and smaller solution space. Due to their intrinsic limitation in deriving module adjacency information directly from the representations themselves, however, they might incur difficulties in handling related constraints. In this paper, we work on B-trees, which have been shown to be most effective and efficient for floor-plan/placement problems, and present a corner stitching compliant B-tree (CB-tree, for short) to remedy the significant deficiency in its module adjacency handling. A CB-tree is a B-tree integrated with modified corner stitching to offer much higher flexibility/efficiency, especially for adjacent module identification/packing. Compared with the previous works, CB-trees can achieve the lowest time complexity for module packing with the aforementioned constraints. Experimental results show that the CB-trees achieve the best solution quality and consume the least running time for industrial designs with various constraints. In particular, our work provides key insights into the handling of comprehensive placement constraints with a topological representation.

Original languageEnglish
Title of host publication2011 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2011
Pages507-511
Number of pages5
DOIs
StatePublished - 1 Dec 2011
Event2011 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2011 - San Jose, CA, United States
Duration: 7 Nov 201110 Nov 2011

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Conference

Conference2011 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2011
CountryUnited States
CitySan Jose, CA
Period7/11/1110/11/11

Fingerprint Dive into the research topics of 'A corner stitching compliant B-tree representation and its applications to analog placement'. Together they form a unique fingerprint.

Cite this