Folding a stack of equal width components

Author

Thanvantri, Venkat ; Sahni, Sartaj

Author_Institution

Dept. of Comput. & Inf. Sci., Florida Univ., Gainesville, FL, USA

Volume

14

Issue

6

fYear

1995

fDate

6/1/1995 12:00:00 AM

Firstpage

775

Lastpage

780

Abstract

We consider two versions of the problem of folding a stack of equal width components. In both versions, when a stack is folded, a routing penalty is incurred at the fold. In one version, the height of the folded layout is given and we are to minimize width. In the other, the width of the folded layout is given and its height is to be minimized. We develop a normalization technique that permits the first version to be solved in linear time by a greedy algorithm. The second version can be solved efficiently using normalization and parametric search. Experimental results are presented

Keywords

circuit layout CAD; computational complexity; integrated circuit layout; network routing; search problems; equal width components; folded layout; greedy algorithm; layout synthesis; normalization technique; parametric search; routing penalty; stack folding; CMOS technology; Circuit faults; Circuit testing; Delay; Design automation; Fault tolerance; Logic design; Logic testing; Robustness; Semiconductor device modeling;

fLanguage

English

Journal_Title

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

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.387739

Filename

387739