The main goal of this paper is to develop deeper insights into viable placement-level optimization of routing. Two primary contributions are made. First, an experimental framework in which the viability of "predictive" or "probabilistic" models of routing congestion for optimization during detailed placement can be evaluated is developed. The main criterion of consideration in these experiments is how (un)reliably various models from the literature detect routing hot spots. It was concluded that such models appear to be too unreliable for detailed placement optimization. Second, motivated by the first result, a single combinatorial framework in which cell placement and "exact" routing structures are captured and optimized is presented; the framework relies on the "trunk decomposition" of global routing structures, and optimization is performed by generalization of the "optimal interleaving" algorithm. An implementation of this framework is studied in the field-programmable gate array domain. The technique can reduce the number of channels at maximum density by more than 60% on average with maximum reduction of more than 81% for optimized global routing taking only 75% of the Versatile Place and Route (VPR) placement and routing runtime combined. For the standard cell domain, routing-based interleaving, on average, reduces the maximum track count by more than two tracks with a maximum reduction of nine tracks

We present global routing optimization methods which are not based on rip-up and re-route framework. In particular, the routing optimization is based on trunk decomposition [13] of the global routing. In this framework, the route of a net is decomposed into sets of wiring segments. By viewing a wiring segment as an "atomic object" of perturbation, we can efficiently evaluate the effect of routing tree perturbation. We propose two complementary routing optimization methods, namely segment partitioning and segment migration. These targeted optimizers can improve congestion related routing objectives by quickly shuffling wiring segments across different routing channels. Our routing approach produces better results compared to rip-up and re-route method based router Labyrinth [14] with average total overflow reduction of more than 88% while taking only 61% of runtime required by ripup and reroute phase of Labyrinth. When applied to the output of Labyrinth, the approach, on average, reduces the total overflow by more than 97% with complete overflow elimination for four circuits, while requiring additional runtime of just 33%. On a larger benchmark suite, the total overflow reduction of more than 86% is obtained, with complete overflow elimination for eight circuits, while requiring only 19% additional runtime.

Placement strategies for cell-based designs which use a linear programming (LP) relaxation are widely believed to have certain weaknesses. Among these is the phenomenon that the relaxed placement produced by the LP-solver often has excessive cell overlap; this makes the relaxed solution quite distant from a legal one and raises questions about the value of the relaxed solution. An implication of this phenomenon is that, while the objective function value (HPWL) yielded by the LP is a valid lower bound on the achievable wire-length, it is quite distant from known upper bounds produced by quality placement tools - i.e., the lower bounds appear to be loose. In this paper we experiment with some straightforward generalizations of the basic LP-formulation aimed at tightening the lower bound. We show that this approach has an interesting dual effect: in addition to tightening lower bounds, it also results in a quantifiably better cell distribution than the simpler LP-formulation. Based on this idea, we have developed a placer which employs the Relaxation Based Local Search framework. Experimental results are reported for PEKO and MCNC FPGA benchmarks.

The main goal of This work is to develop deeper insights into viable placement-level optimization of routing. Two primary contributions are made. First, an experimental framework in which the viability of predictive models of routing congestion for optimization during detailed placement can be evaluated, is developed. The main criteria of consideration in these experiments is how (un)reliably various models from the literature detect routing hot-spots. We conclude that such models appear to be too unreliable for detailed placement optimization. Second, motivated by the first result, we present a unified combinatorial framework in which cell placement and exact routing structures are captured and optimized; the framework relies on the trunk-decomposition of global routing structures and optimization is performed by a generalized optimal interleaving algorithm (Hur and Lillis, 2000). A proof of concept implementation of this framework is studied in the FPGA domain. The technique can reduce the number of channels at maximum density by almost 45% on average with maximum reduction of 68% for optimized global routing.