Fractional cut: improved recursive bisection placement

In this paper, we present improvements to recursive bisection based placement. In contrast to prior work, our horizontal cut lines are not restricted to row boundaries; this avoids a "narrow region" problem. To support these new cut line positions, a dynamic programming based legalization algorithm has been developed. The combination of these has improved the stability and lowered the wire 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 than those of the recursive bisection based tool Capo and the analytic placement tool Kraftwerk.