Detailed routing has generally evolved out of four basic approaches: maze routing, line probe routing, left-edge routing, and greedy channel scanning. The problem is formulated as a routing area containing connection points or pins on a rectilinear (usually rectangular) region or channel. Pins can be located on any of the four sides of the region or within the region. The connection points are generally constrained to reside in certain layers to make them easier to connect to. Even single-layer routing problems are NP-complete, which means that an optimal solution cannot be achieved in a reasonable time. For this reason, detailed routing solutions are heuristic in nature. The factors in determining a solution's usability are the number of terminals, net width, via restrictions, boundary shape, number of layers, and net types such as power, ground, and clock wires. Maze routers abstract the channel routing problem with a grid-based model. Wires are restricted to follow paths along the grid lines. Routing is accomplished by laying down wires on the grid one at a time. Obstacles are modeled as disallowed portions of the grid. Therefore, maze routing can handle arbitrary obstacles.
|Published - 2007
- Criteria for net ordering
- Extensions to multi-terminal nets
- Rip-up and reroute
- Sequential routing approach