Information Technology Reference
In-Depth Information
multi-terminal nets. While extending these algorithms for multi terminal nets
the common feature has been the construction of Steiner tree for each net [5-
11]. The popularity of sequential techniques has risen recently, because of their
ability to handle large problem instance. The popular sequential techniques,
usually order the nets according to their criticality, half-perimeter wire length,
and number of terminals [12]. For example, some nets might be timing critical
and hence would require to be routed early. Various techniques has been de-
vised to minimize the effect of net ordering. These techniques include rip-up &
reroute schemes, heirarchical methods, simulated annealing and a myriad other
heuristics based methods. The traditional approach is to route each net, without
taking congestion into account and then identify heavily congested areas. These
heavily congested areas are then decongested by local rerouting of net segments.
NTHU-Route [13] is an example of GR using iterative rip-up and reroute tech-
nique that uses a history-based cost function to distribute overflow, followed by
identification of congested regions to specify the order in which rip-ups are per-
formed. [14] presents a global routing algorithm that performs layer assignment
before routing. This algorithm is based on a new flow for multi-layer routing,
and uses bounding box of the nets to estimate the congestion, and distributes
them to different layer pairs based on the aim of even congestion. The Archer
router [15] employs a spectrum of point-to-point routing techniques, ranging
from relatively cheap operations to expensive but flexible procedures (e.g., tra-
ditional maze routing). For a given 2-pin connection, the specific technique used
depends on congestion histories. Steiner trees are modified dynamically using
a novel Lagrangian formulation for topology optimization. Fairly Good Router
(FGR) [16] extends the PathFinder router originally developed for FPGAs [17]
to handle the scale and sophistication of an ASIC environment with multiple
routing layers. It offers several technical novelties, such as a particular function
for congestion penalty, and closely linked algorithmic innovations, such as shar-
ing in conjunction with continual net restructuring, and fast layer assignment
followed by a 3D clean-up. With respect to runtime, FastRoute [18] remains
one of the more competitive solvers to date. It uses a congestion map to warp
the structure of a Hanan grid during Steiner tree generation, followed by edge
shifting and a form of pattern routing. DpRouter [19] is based upon a conges-
tion aware algorithm that combines two principal techniques: a dynamic pattern
routing method to achieve optimal routing solutions for two-pin nets, and a
segment move technique to extend its search space. Two elementary edge-based
operations -extreme edge shifting and edge retraction- form the high-level opera-
tions of MAIZEROUTER [20]. These techniques are supported by an underlying
foundation of interdependent net decomposition, in which routing solutions are
implicitly maintained by at collections of intervals. Rather than operate on en-
tire nets, individual segments are manipulated one-at-a time, enabling support
for cheap incremental operations.
Concurrent global routing methods find routes for all nets in a circuit si-
multaneously. Doing so, helps in avoiding the net ordering problem faced by
the sequential approaches. On account of unavailability of ecient polynomial
