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
fDate :
6/1/1994 12:00:00 AM
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;
Journal_Title :
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
