Optimality of a feedthrough assignment algorithm in a CMOS logic cell layout

Three kinds of feedthrough assignment algorithm are suggested for CMOS logic cell layout, and their solutions and processing times are compared. One is based on the idea that the feedthrough requirement with fewest feedthrough candidates is first assigned. The second is an optimum algorithm that solves the problem by formalizing it as an integer programming problem. The third is a combination of the two, in which the first algorithm is applied until all of the uniquely determined feedthroughs are assigned, and then the second one is applied. The second and third algorithms attain the optimum solution, but the first one does- not. The deviation of the first algorithm from the optimum solution is shown to be within 3.5% of the optimum. and the cell area increases less than 3.5%. The processing times of the first and third algorithms are 1/27.5 and 1/3.0, respectively, on average, of that of the optimum one. Thus it is concluded that the first algorithm, although not optimum, is practical, and may well be incorporated into the feedthrough assignment process