IC (Integrated Circuits) Layout Generation and Compaction Using Mathematical Optimization

摘要

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 acyclc 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 dependent 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 research is aimed at the final end of a spectrum of research for a silicon compiler. An experimental compute program was developed which implemented the compaction algorithm. The program demonstrated that the algorithm is flexible, powerful, and efficient.