DocumentCode
1088171
Title
Algorithms and bounds for layer assignment of MCM routing
Author
Heydari, Mohammad H. ; Tollis, Ioannis G. ; Chunliang Xis
Author_Institution
Dept. of Math. & Comput. Sci., Wisconsin Univ., Whitewater, WI, USA
Volume
2
Issue
2
fYear
1994
fDate
6/1/1994 12:00:00 AM
Firstpage
265
Lastpage
270
Abstract
We present new algorithms for the layer assignment problem of multichip modules (MCM´s). Our algorithms produce results that require between 70% and 25% of the number of layers required by the previous algorithms. We also present a new model for the problem that results in a better utilization of the routing area of the MCM, thus reducing the number of required layers even more. We provide lower and upper bounds on the performance of our algorithms which are tighter than the ones obtained before. Through our experimental results we show that the solutions obtained by our algorithms are close to the lower bounds.<>
Keywords
circuit layout CAD; multichip modules; multiterminal networks; network routing; MCM routing; algorithm performance; layer assignment; lower bounds; multichip modules; routing area; upper bounds; Computer science; Costs; Energy consumption; Integrated circuit interconnections; Multichip modules; Packaging; Pins; Routing; Solid state circuits; Very large scale integration;
fLanguage
English
Journal_Title
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
Publisher
ieee
ISSN
1063-8210
Type
jour
DOI
10.1109/92.285755
Filename
285755
Link To Document