Heuristic algorithms for standard cell placement in VLSI design

Abstract

In this thesis, we consider the standard cell placement problem in VLSI design works. At first, we present two fast heuristic algorithms for the constructive placement of standard cells based on Constrainted Multi-Stage Graph(CMSG) model for the rectangle-shaped chip. One has a linear time complexity and another has $O(n^{1.5})$ time complexity in the number of cells. Experimental results on the benchmarking testing data show that the proposed algorithms yield near optimal results in terms of the feed-through cells and channel density, which was verified by the comparison of the proposed algorithm with the simulated annealing and other iterative improvement algorithms. So the ample experimental results prove that CMSG model is a naturally reasonable and more efficient model for standard cell placement in the rectangle region than models of the previously studied algorithm such as min-cut partition. Moreover we studied the standard cell placement for the arbitrary rectilinear region, which is the remaining region after some macro modules such as ROM, RAM and PLA were placed in building block design. For this problem we propose a new model called Flow Model in the Closed Region (FMCR). In FMDR the quantity of flows running over the boundary is approximated to the number of signal wires crossing over the boundary line. Rather than placement in the rectangle, arbitrary rectilinear region may have a very congested region, which is carefully considered. So it is a critical work to suppress the number of wires on the region to guarantee the complete routing work. For this we propose the concept of the maximal flow-density for the plane subdivision. We proved that partition which maximizes the flow-density is the bipartition. And some properties on the maximal flow density bipartition are characterized. Several experiments to support the validity of our flow model are presented. By these experiments we show that the proposed algorithm gives the comparable wiring length...