RBI: Simultaneous Placement and Routing Optimization Technique

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