Trunk Decomposition Based Global Routing Optimization

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 (D. Jariwala and J. Lillis, 2004) 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 (R. Kastner et al. 2002) with average total overflow reduction of more than 88% while taking only 61% of runtime required by rip up 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