Continuous Routing

Abstract

Global routing is an essential stage of a chip design flow: as a simplification of the routing problem, it optimizes global objectives such as wire length, power and timing, while relaxing some constraints, such as wire disjointness and design rules. Its task is twofold: it generates routes that predict the final routing output (to quickly evaluate its properties), and it computes a solution which can be used to drive other tools, such as placement and, especially, detailed routing. <br /> Despite the fast-pacing evolution of chip design tools, the global routing model has remained essentially unchanged in the past decades: routing is performed on a coarsened grid graph, obtained by partitioning the chip. In this dissertation, we propose a shift in paradigm, where we replace the coarse graph with rhomboidal tiles. We build a new global router, the continuous router, from the ground up, starting from a resource sharing formulation. <br /> As a main advantage, we can route directly on pin shapes, with no coarsening steps. This addresses many shortcomings of the traditional model, such as loss of resolution, the necessity of predicting space usage arising from short connections, and inaccuracies in modeling tile-internal wires. Moreover, it significantly improves on the complexity of a modern router, since it can work directly with any shape on the chip, not only those aligned to the coarse grid. <br /> Thus, we introduce a new wire usage model, which supports track patterns, different wire widths and flexible via costs, and we derive, from the resource sharing formulation, a cost function for wires on rhomboidal tiles. We then study the problem of finding Steiner trees of minimal cost, and we show how this can be reduced to a Steiner tree problem in special weighted grid graphs, the rhomboidal Hanan grid, whose density grows quadratically with the number of terminals. We then look at the structure of shortest paths, to conclude that it is not possible to reduce the quadratic dependency without losing optimality; however, we give lower and upper bounds for shortest paths starting from a less dense grid. <br /> We then revisit classical Steiner tree approximation algorithms, and look at several speedup techniques. We then introduce local search algorithms, which find application in a variety of global routing scenarios, ranging from locally improving a Steiner tree, to lifting a planar Steiner tree to the 3D routing space. <br /> With these, we implemented a fully fledged global router. We test the algorithms on real instances in the 7 nm and 5 nm technology nodes, and report runtime and quality of routing and local search algorithms.<br /> Then, we compare results in an industrial routing flow, against a traditional global router. We show that the continuous router is able to improve in several global routing and detailed routing metrics, such as DRC and wire length, even in a flow tuned towards traditional routing. We then analyze specific hard-to-route situations and propose how to refine the continuous router to address them.