Maze routing in IC design

Gisli Thorsteinsson*, Tom Page

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

Abstract

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.

Original languageEnglish
Publication statusPublished - 2007

Other keywords

  • Algorithm
  • Criteria for net ordering
  • Extensions to multi-terminal nets
  • Rip-up and reroute
  • Sequential routing approach

Fingerprint

Dive into the research topics of 'Maze routing in IC design'. Together they form a unique fingerprint.

Cite this