|
The HORE mazerouter includes:
Arbitrary initial ordering: Ripup and Reroute allows HORE to
arbitrarily route nets in any order during the initial routing phase.
Later passes of HORE will correct overloaded nets. Minimum spanning tree-esque routing of multipoint nets:
Multipoint nets are decomposed into 2-point nets. A source-target pair
is selected from the available nodes on a multipoint net, routed, and
then becomes the source for the next source-target pair. The next
closest node is selected by calculating the minimum distance from a
rectangle, formed from the new source cells, to the remaining nodes.
This minimum spanning tree-esque procedure is continued until the
entire multipoint net is routed. Depth first prediction: Added to the cost of expansion is the a
directional cost that points from the source to the target. Those
cells closest to the target are encouraged to expand first, while
those cells in the wrong direction are penalized. A "fudge factor"
must be included to allow nets to route around blockages, such as the
pins of the logic cells. This technique is crucial to providing fast
routing solutions since it drastically decreases the number of grid
cells expanded.
Path Dependent Penalty Costs: As the wavefront expands, the
cost of the net is calculated by penalizing for wire bends, vias, and
wrong way direction routing. Each of these costs can be set through
flags passed to the HORE router, but the default costs are 1 for
bends, 10 for vias, and 10 for wrong way wiring. Via costs and wrong
way wiring costs share a symbiotic relationship: they are designed to
allow nets to route in the wrong direction for short distances but
provide cost advantages for using vias and crossing in the grid in
another plane, in the correct direction for long distances.
|
|
The HORE ripup and reroute includes:
Path History Dependent Penalty Cost: Non-linear
varying of the overloaded node penalty using previous pass experience
as a guide. The cost for routing over another net varies inversely
proportional to the number of violations on the previous pass wiring
of that net. During wavefront expansion, this penalty is added to the
cost of expanding a grid, encouraging the net to find another path.
The overall effect is to allow those nets with many violation to get
worse, sparing good nets from being violated.
Ralph Linsker's Trick #1: Violated nets are not removed
from the routing solution. They are allowed to remain and affect each
successive pass of ripup and reroute (through the path history
dependent penalty cost). The final solution also returns routes
for violated net; they are, however, marked for manual intersection.
Ralph Linsker's Trick #2: The final and most important
element to ripup and reroute is a per-pass increase in the overloaded
node penalty. In the first passes, the cost for crossing other nets
is relatively low. Gradually this cost is increased until the cost
for crossing another net is very expensive. At some point this cost
is reduced, to escape from local minima routing solutions, and the
cost is again increased through the final passes of ripup and reroute.
|