The authors present a linear time optimal algorithm to determine positions of the pins of nets on the top and the bottom sides of a channel, which is partitioned into several intervals. The pins are permutable within their associated intervals. The proposed algorithm is optimal in the sense that it can minimize both the density and the total wire length of the channel. Experimental results show that sufficient reduction of the channel density and the total wire length is, in fact, obtained by the use of the algorithm.
展开▼