New optimization model for VLSI placement algorithms

Abstract

This research presents a new model which can be used to formulate cost functions for various VLSI placement problems. A formal proof indicating the close relationship of the parameter, namely crossing, with the conventional channel density is given. Such proof, which has never been established in the net length model. Theoretically, the crossing model has a lower bound of zero, i.e. no nets will make crosses with another. In addition, the crossing notion of a standard cell is inherently a two-dimensional model and its computation is localized to those cells connected it. Crossing model is intended to be applied on parallel optimization algorithm in future. The above advantages of our model will be illustrated by a post-optimization step after standard cell placement. At the same time, a heuristic algorithm with the complexity of the algorithm of O(n)+O(m2) is also proposed using the crossing model. A reduction of up to 5% of the layout area was achieved.