Title :
On shifting blocks and terminals to minimize channel density
Author :
Cai, Yang ; Wong, D.F.
Author_Institution :
ArcSys Inc., Sunnyvale, CA, USA
fDate :
2/1/1994 12:00:00 AM
Abstract :
We study in this paper the problem of minimizing channel density by simultaneously shifting the blocks that form the two sides of a channel and the terminals on the boundary of each block. Several special cases of this problem have been investigated, but no optimal algorithm was known for the general case. We present an optimal algorithm for solving this problem. For long channels, we also propose effective heuristic techniques to speed up our algorithm. Extensions as well as applications of our algorithms to detailed routing in building-block layout design are also discussed
Keywords :
circuit layout CAD; minimisation; network routing; VLSI circuit design; block shifting; building-block layout design; channel density minimization; channel pin assignment; heuristic techniques; optimal algorithm; routing; terminal shifting; Algorithm design and analysis; Circuits; Computer aided instruction; Helium; Pins; Routing; Scholarships; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
