We study in this paper the channel pin assignment (CPA) problem subject to position constraints, order constraints, and separation constraints. The problem is to assign two sets of terminals to the top and the bottom of a channel to minimize channel density. The position constraints are given by associating with each terminal a set of allowable positions. The order constraints specify the relative orderings of the terminals on the top and the bottom of the channel by a pair of partially ordered sets. The separation constraints require the distance between each pair of consecutive terminals to be within a certain range. We show that the problem is NP-hard in general, and present polynomial time optimal algorithms for an important special case in which the order constraints are specified by two linearly ordered sets (i.e., relative orderings of the terminals on the top and the bottom of the channel are completely fixed). We introduce the problem of channel routing with movable modules and show that it is a special case of our problem, and hence, can be solved optimally. We also discuss how our algorithms can be incorporated into standard-cell and building-block layout design systems. Experimental results indicate that substantial reduction in channel density can be obtained by allowing movable terminals.
|Original language||English (US)|
|Number of pages||12|
|Journal||IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems|
|State||Published - Nov 1991|
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering