IC Layout Generation and Compaction Using Mathematical Optimization

Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1984. Simultaneously published in the Technical Report series.This Ph.D research is in the area of automatic IC mask generation and compaction. It develops a new method of mask compaction. It formulates a mixed integer linear programming problem from a user defined stick diagram, a dimensionless topological representation of IC layout. By solving this mixed integer program, a compacted and design rule violation free layout is obtained. A specialized algorithm was developed for solving this mixed integer program for the purpose of efficiency. This algorithm is based on a branch and bound method and a longest path algorithm on acyclic graphs. In this formulation, a vertical graph and a horizontal graph are generated from the input stick diagram. These two graphs are strongly related to each other by binary decision variables. For every fixed set of decision variables, we solve two independent longest path problems, one for the horizontal direction and the other for the vertical one. The interaction between the horizontal and vertical compaction is via the binary decision variables. The branch and bound method is used for setting values of decision variables. The formulation can incorporate the following: (1) Simultaneous consideration of two directions of compaction (2) Goal directed compaction and generation of the layout. The research is aimed at the final end of a spectrum of research for a silicon compiler. The method developed is suitable to be used in the final stage (mask generation stage) of a silicon compiler. For example, having a library of cells in stick diagram form together with a set of procedures to translate them into layout is much more flexible and therefore more useful than a standard cell library. The cells could be scaled automaticaIly according to fan in and fan out considerations. Their shapes could be altered automatically to fit other parts. Moreover changes in design rules will not render the cells obsolete. The algorithm can also be incorporated into an IC design work station as a compaction procedure. An experimental program was developed which implemented the compaction algorithm. The program demonstrated that the algorithm is flexible, powerful, and efficient