Fractional Cut: Improved Recursive Bisection Placement

In this paper, we present improvements to recursive bisection basedplacement. In contrast to prior work, our horizontal cut lines arenot restricted to row boundaries; this avoids a "narrow region"problem. To support these new cut line positions, a dynamic programmingbased legalization algorithm has been developed. Thecombination of these has improved the stability and lowered thewire lengths produced by our Feng Shui placement tool.On benchmarks derived from industry partitioning examples,our results are close to those of the annealing based tool Dragon,while taking only a fraction of the run time. On synthetic benchmarks,our wire lengths are nearly 23% better than those of Dragon.For both benchmark suites, our results are substantially better thanthose of the recursive bisection based tool Capo and the analyticplacement tool Kraftwerk.