Symbolic Layout Compaction Under Conditional Design Rules

Chung-Kuan Cheng; So-Zen Yao; Xiaotie Deng; Yuh-Zen Liao

doi:10.1109/43.125095

Symbolic Layout Compaction Under Conditional Design Rules

Chung-Kuan Cheng
, So-Zen Yao
, Xiaotie Deng
, Yuh-Zen Liao

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

10 Citations (Scopus)

Abstract

This paper addresses the compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, we first formulate each conditional spacing rule with a set of arcs in the constraint graph representation. We prove that finding the optimal solution under one bridge rule is NP-complete. We then propose a graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution. © 1992 IEEE

Original language	English
Pages (from-to)	475-486
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	11
Issue number	4
DOIs	https://doi.org/10.1109/43.125095
Publication status	Published - Apr 1992
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

Manuscript received August 7, 1990; revised February 25, 1991. This work was funded in part by a grant from the NSF (Project MIP-9009260) and by grants from Amdahl, AT&T, Cadence, Elite, and Hughes under MICRO. This paper was recommended by Associate Editor M. Marek-Sadowska. C.-K. Cheng and S.-Z. Yao are with the Department of Computer Science and Engineering, University of California at San Diego, La Jolla, CA 92093. X. Deng is with the School of Computing Science, Simon Fraser University, Burnaby, BC V5AlS6. Y.-Z. Liao is with ArcSys, Inc., 3080 Olcott Street, Suite 120A, Santa Clara, CA 95054. IEEE Log Number 9104583.

Access Output

10.1109/43.125095

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{16a100c04ee8498eafa0f1b37bd4256f,

title = "Symbolic Layout Compaction Under Conditional Design Rules",

abstract = "This paper addresses the compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, we first formulate each conditional spacing rule with a set of arcs in the constraint graph representation. We prove that finding the optimal solution under one bridge rule is NP-complete. We then propose a graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution. {\textcopyright} 1992 IEEE",

author = "Chung-Kuan Cheng and So-Zen Yao and Xiaotie Deng and Yuh-Zen Liao",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1992",

month = apr,

doi = "10.1109/43.125095",

language = "English",

volume = "11",

pages = "475--486",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "IEEE",

number = "4",

}

TY - JOUR

T1 - Symbolic Layout Compaction Under Conditional Design Rules

AU - Cheng, Chung-Kuan

AU - Yao, So-Zen

AU - Deng, Xiaotie

AU - Liao, Yuh-Zen

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1992/4

Y1 - 1992/4

N2 - This paper addresses the compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, we first formulate each conditional spacing rule with a set of arcs in the constraint graph representation. We prove that finding the optimal solution under one bridge rule is NP-complete. We then propose a graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution. © 1992 IEEE

AB - This paper addresses the compaction of IC layouts subjected to conditional spacing rules in multiple-level metal technology. The constraints imposed by conditional rules make the automatic compaction of layout much more difficult than when the usual minimum separation rules are applied. To solve the problem, we first formulate each conditional spacing rule with a set of arcs in the constraint graph representation. We prove that finding the optimal solution under one bridge rule is NP-complete. We then propose a graph-theory method of compaction which, by reducing the problem size, can efficiently obtain an optimal solution. © 1992 IEEE

UR - https://www.scopus.com/pages/publications/0026850592

UR - https://www.scopus.com/pages/publications/0026850592#tab=impact

U2 - 10.1109/43.125095

DO - 10.1109/43.125095

M3 - RGC 21 - Publication in refereed journal

SN - 0278-0070

VL - 11

SP - 475

EP - 486

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 4

ER -

Symbolic Layout Compaction Under Conditional Design Rules

Abstract

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this