Page 551 - DSP Integrated Circuits

536 Chapter 12 Integrated Circuit Design

Disadvantages are
1. Complications occur where there is a choice of cells in the backtracking,
since in theory any cell numbered (jc-1) may be chosen to follow cell x.
2. The choice of a particular route between S and T may preclude
subsequent net list connections from being routed, with deletion and
rerouting (by hand) of the previously completed nets necessary for 100%
completion.
3. A considerable and unnecessary area of the available wiring space may
be covered and enumerated by the grid radiating outward from S, with
high computer memory requirements and long central processing unit
running time.

Various techniques to refine the basic procedure have been advanced, par-
ticularly to avoid the labeling of matrix squares which are generally running in
an inappropriate direction from the target cell T. The Lee-Moore's algorithm
always finds the optimal path with respect to the metrics used, if it exists,
between any two points in a gridded routing region with any number of obsta-
cles. The drawback of the Lee—Moore's algorithm is that it is memory and time
consuming.

Switchbox Routers
Switchbox routers are used to route wires in a region that is confined on all four
sides. The switchbox routing problem is much more difficult than the channel
routing problem. In fact, a solution to a given switchbox problem may not even
exist.

Channel Routers
The channel routing problem can be defined as follows: A rectangular region,
called a channel, with pins located on the top and bottom edges aligned on the
grid, is given. Horizontal and vertical grid lines are referred to as tracks. The
objective of channel routing is to connect all the nets using a minimum number of
horizontal tracks. Typically, two different layers are used for horizontal and verti-
cal tracks. Efficient algorithms exist for solving the channel routing problem. The
left-edge algorithm is one such algorithm. However, it does not always lead to an
optimal solution with a minimum number of horizontal tracks.

12.2.5 Compaction by Zone Refining

The compaction problem is inherently connected to the floor planning, placement,
and routing problems. Several compaction approaches exist. However, most meth-
ods are only one-dimensional. The resulting compaction of one-dimensional com-
pactors is usually poor.
An interesting approach, based on simulated annealing, is the compaction by
zone refining algorithm. The method is based on an analogy with refinement of sil-
icon rods used for integrated circuits. The modules are initially placed at the top of
the placement area. They are then moved downwards, according to the simulated
annealing algorithm, to the bottom of the placement area where they are placed
properly. This process is repeated several times in all four directions.