AN ALGORITHM OF K-LINE LOCATION FOR BBL IN LSI/VLSI

A K-line location algorithm for buillding block cells in LSI/VLSI is presented. When the relative positions of rectangular cells are given, there are 2n states according to thetwo orientations of a cell. It is proved that to find the optimum solution from 2n states canbe reduced to calculate the n states in k-line algorithm. So the algorithm is very effectiveand can be used with association for cluster method in BBL placement. Under certain conditions, this method can also be used to pesudo BBL placement directly.