TY - JOUR
T1 - Optimal Net Assignment
AU - Wang, Ting Chi
AU - Wong, D. F.
AU - Sun, Yachyang
AU - Wong, C. K.
N1 - Publisher Copyright:
© 1995 IEEE
PY - 1995/2
Y1 - 1995/2
N2 - We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem, and provide experimental results to support our algorithm.
AB - We study in this paper the net assignment problem subject to the capacity constraint, selection constraint and routing constraint. Given two adjacent channels separated by a cell row, and a set of nets in each of the two channels, this problem is to assign to the cell row a subset of nets in each channel such that without violating any given constraint, the sum of the remaining densities of the two channels is minimized. The capacity constraint requires the density caused by the nets, which are assigned to the cell row, to be no more than a user-specified number k, where k is no more than the number of tracks available for routing over that cell row. The selection constraint specifies in each channel the subset of nets which are candidates to be assigned to the cell row. The routing constraint requires each net to be either completely assigned to the cell row or to stay in its channel. This problem can find its application in modeling a practical over-the-cell routing problem in which the whole region over the cell row is two-layer routable for the nets in the two adjacent channels. We present an optimal algorithm to solve this problem, and provide experimental results to support our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=0029255819&partnerID=8YFLogxK
U2 - 10.1109/43.370420
DO - 10.1109/43.370420
M3 - Journal article
AN - SCOPUS:0029255819
SN - 0278-0070
VL - 14
SP - 265
EP - 269
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 2
ER -