This thesis describes the applications of neural network principles to the layout design problems for integrated circuits, such as placement, module orientation via minimization.
First, we present an algorithm called SOAP (Self-Organization Assisted Placement) for circuit placement in arbitrarily-shaped region including 2dimensional rectilinear regions, nonplanar surfaces of three-dimensional objects, and 3-dimensional volume. SOAP is based on a learning algorithm for neural networks proposed by Kohonen [1] called self-organization which adjusts the weights of synapses connected to neurons such that topologically close neurons become sensitive to inputs that are physically similar. Unlike earlier methods on circuit placement in rectilinear region where the final placement heavily depends on the arbitrary partition of the whole region into a number of rectangular subregions thus leading to suboptimal results, SOAP is a general algorithm for circuit placement in arbitrarily-shaped region without these drawbacks. Standard cell placement, circuit placement on nonplanar surfaces and 3-D volumes, and global placement method for macro cells using SOAP algorithm are also described. Experimental results on benchmark circuits show that SOAP algorithm is competitive with the state-of-the-art algorithms even for the case of placement in rectangular region, which is a special case of 2-D rectilinear region.
Second, a new module orientation algorithm using mean field annealing for minimizing the half-perimeter routing length of all the nets in a circuit based on a multi-pin net model is presented. Mean field annealing is a neural network model derived from simulated annealing using a technique similiar to the mean field approximation used in physics[2]. Using the proposed module orientation algorithm we can find optimal results for small circuits, and obtain significantly reduced half-perimeter routing length for larger circuits. The whole computation time for the module orientation procedure is reduced due to a preprocessing step where pins are simply eliminated which do not affect the half-perimeter net length regardless of the orientation of the module to which the pin belongs.
Third, we present an algorithm based on Hopfields's model[3] for minimizing the number of vias which consume large chip area and degrade circuit performance and reliability. This algorithm can be applied to multi-pin nets as well as two-pin nets. We can obtain optimal results for small size problems by properly adjusting the weight of each term in the given energy function. However, for the large size problems, it is difficult to obtain optimal results using the afore-mentioned method. Therefore, we introduce a heuristic partitioning method based on the divide-and-conquer strategy.
