Adaptive cut line selection in min-cut placement for large scale sea-of-gates arrays

We present a new min-cut based placement algorithm for large scale sea-of-gates arrays. In the past all such algorithms used a fixed cut line sequence that is determined before min-cut partitioning is performed. In our approach, we adaptively select a next partitioning pattern based on the current parameter value; we then perform the corresponding min-cut partitionings and measure a new parameter value. We repeat this process until all cut lines are processed. As a parameter, we introduce a new global objective function based on wire congestions on cut lines. We establish a close relation between this function and cut line sequences. This relation is used to develop an innovative method of adaptively determining a cut line sequence so as to minimize this global function. With this adaptive selection of cut lines along with a new cluster-based min-cut partitioning technique, our algorithm can produce, in a short time and at a low cost, final placement results that achieve the 100% completion of wiring on chips of fixed sizes. This has led to its successful production use, having generated more than 400 CMOS sea-of-gates array chips.