Page 550 - DSP Integrated Circuits

12.2 Layout of VLSI Circuits 535

in general NP-complete, different solutions have been derived for special cases. The
most common routers can be classified into one of the following three groups:
1. Area routers. This is the most general case with an arbitrary shape of the
routing area and pin positions.
2. Switchbox routers. The routing area is restricted to be a rectangle.
3. Channel routers. The routing area is two-sided.

Area Routers
"Would you tell me please, which way I ought to go from here?"
"That depends a good deal on where you want to get to," said the cat.
"I don't much care where," said Alice.
"Then it doesn't matter which way you go," said the cat.
—Lewis Carroll
An example of area routers is the Lee-Moore's
algorithm, sometimes referred to as a wavefront
or maze-running router. The path to be routed
follows a rectangular grid, moving from one cell
on the grid to an immediately adjacent cell. For
example, consider the situation illustrated at
the top of Figure 12.5, where the white cells
indicate space available for interconnection
routing, and the black cells are obstructions due
to prior routing or other items. If we require to
route from source cell position S to target posi-
tion T, we first number the available cells as fol-
lows:

1. All cells immediately surrounding S
are numbered "1."
2. All cells immediately surrounding the
cells numbered "1" are numbered "2."
3. Continue numbering cells surrounding
every already numbered cell with the
next higher integer number until the
target T is encountered.
The Lee—Moore's routing algorithm then
selects a routing path between S and T by back-
tracking from T toward S, always moving from
one grid to a next lowernumbered cell, such as
shown in Figure 12.5. The advantages of Lee-
Moore's algorithm are
1. Provided that the initial cell numbering
can be extended from S to T, then a
path between S and T is guaranteed. „ T
o rrn. j-i. T- -n i u j.u Figure 12.5 Lee-Moores
2. The path chosen will always be the , .,,
shortest Manhattan distance between
S and T.
3. It can readily cope with nets with more than two points S and T.