Greedy Method

Compulsive algorithm designers adore greedy methods. All that seems to be required for this is to jump in and do whatever seems best at the time. A great example is the first fit algorithm for bin packing shown in the section on approximations. In that algorithm one merely takes items in order and places each in the closest available bin. The fact that the results are often quite good in practice makes techniques like this very attractive.

Another greedy method much in the spirit of first fit is the nearest neighbor algorithm for the closed tour problem. It is very much like the very famous Kruskal algorithm for minimum spanning trees since we merely keep connecting the cities that are closest until we have a tour. An example is pictured in figure 1.

Figure 1 - Nearest Neighbor Closed Tour

Here though, the relationship between tours found by the nearest neighbor algorithm and optimum tours is:

which depends on n, the size of the problem. So, the theoretical bound on performance seems to decrease as the problem instances grow larger.

Our next problem comes from the field of CAD algorithms for VSLI design. It is called channel routing. A routed channel is shown in figure 2 and defined formally as:

Definition. A channel is a sequence of pairs of integers
<t₁, b₁>,<t₂, b₂>, ... , <t_n, b_n>.

Unfortunately the definition, although precise, is not very intuitive and thus does not help one to understand what a channel actually is. The intuition behind the definition is that a channel consists of two rows of pins (or terminals), some of which must have a common electrical connection. The t_i represent the pins on the top of the channel, while the b_i are those on the bottom. Examine figure 2.

Figure 2 - A Routed Channel

Note that there is a row of numbered pins along the top and one along the bottom. (We call these sides shores to go along with the nautical motif of channels.) Those of figure 2 correspond to the sequence:

<1, 2>, <0, 1>, <2, 3>, <2, 1>, <3, 4>, <0, 0>, <4, 5>, <3, 5>

which satisfies the above definition.

Those pins bearing the same label (number) must be connected together. Pins labeled zero however are not connected to any others. A collection of pins which must be connected is called a net. The labels on the pins name the net.

The small dark squares are called vias and indicate where two wires (the lines) are connected, as they are insulated from each other at all other points. The horizontal wires are routed on tracks. An optimum solution contains the fewest tracks or least area. Figure 2 illustrates a 5-track routing.

The greedy router we are about to examine makes one pass over the channel the left to the right. As it progresses along the channel, it brings in wires from pins on the shores column by column (or pin by pin) into the channel and attaches them to wires on horizontal tracks until every pin is connected to the rest of those bearing the identical labels.

Here is an example. First, tracks are assigned to nets, such as net 1, that enter the channel from the left as shown in figure 3. Then nets 1 and 2 were brought in from the top and bottom in the first column. Net 2 is assigned to a new track and extended to the right. Net 1 is attached to the existing net 1 track in both the first and second columns. Then both tracks are extended to column three.

Figure 3 - Beginning a Routing

Next, net 2 is attached to its existing track and net 3 is brought into the channel to an empty track. This is the state of affairs in figure 3. Examine figure 4.

Figure 4 - Continuing the Routing

Now all existing tracks (those for nets 1, 2, and 3) are extended to column 4 and nets 2 and 1 are brought into the channel. Net 1 is attached to the existing net 1 track and net 2 is brought in to an empty track at the top.

At this point a problem arises. We cannot join net 2 to its existing track because this will cause an overlap with net 1. This is not allowed. Thus a new track must then be assigned to net 2 causing it to exist on two tracks. This is shown in the next channel installment in figure 5.

Figure 5 - More of the Routing

Also in figure 5 we see that at the next column, nets 4 and 3 were brought into the channel and net three was connected to an existing track. And, since the next pin for net 3 is on the top shore, the extension of net 3's track was made as near the top as possible. Note also that on the next column we shall be able to consolidate the tracks for net 2 since no nets enter there.

The process of bringing nets into the channel and either assigning them to new tracks or attaching them to existing tracks continues column by column until the end of the channel.

We are ready now to state the entire algorithm, but first we need some terminology. A net is said to be rising if its next pin further along the channel is on the top shore and next pin (if any) does not reside on the bottom shore within a pre-defined distance called the steady net constant. Similarly, a net is falling if its next pin is on the bottom shore and the following pin is not located on the top shore within the distance specified by the steady net constant. In our example, net 1 is falling and net 2 is rising after column one. A steady net by default is that which is neither rising nor falling. Split nets are nets that unfortunately have been placed upon two different tracks at a column. Net 2 has been split on columns four, five, and six.

The greedy algorithm for channel routing is presented as figure 6 below.

Figure 6 - The Greedy Channel Router

The algorithm begins by assigning tracks to left border nets if any. Here, track selection for the nets is done by placing rising nets above steady nets that, in turn are placed above falling nets. This group is placed upon the central tracks of the channel.

The algorithm then continues through each column of the channel by first trying to bring in the non-zero pins from the top and bottom shores to either the first unused track, or to a track containing its net, whichever comes first. The vertical wires that are used to bring in the pins must not cross over each other in the process and if such a situation arises, the pin that requires the shorter distance to be brought into the channel is assigned its existing track, and a new track is created for the other pin such that there is no overlap of vertical wires.

The algorithm next locates all split nets (nets occupying more than one track) and tries to 'collapse' as many of these as possible into one track each by connecting them together with a vertical jog. This obviously frees up one track if a split net occupies two tracks and more if the net is spread on more than two tracks. Care must be taken to see that a vertical jog of one net does not overlap the vertical jog of another net or of an incoming net unless of course they are the same net. Net 2's two tracks were reunited in this manner in column 6.

The next step is to narrow down the distance between as many existing split nets as possible by making nets come closer to each other by the use of vertical wires which must be the minimum jog length. Also, these wires should not be incompatible with vertical wires that may have been placed in earlier steps.

This is followed up by locating all single track nets that are rising or falling, and attempting to move them to higher or lower tracks if possible using vertical wires. This was done to net 3 at column 5 and net 4 at column 6.

As the algorithm progresses through these steps some bookkeeping is done so that when:

• new pins are brought in,
• other vertical wires are placed in the channel, or
• a new track is created,

the list of available tracks is continually updated to reflect the changes in availability of the tracks made along the way.

Now the routing for this column is over and at this point, the column count is incremented and routing begins on the new column.

When the end of the channel is reached, all tracks are checked for their availability and if they are still in use, then there are two possibilities for them. The first is that the tracks contain split nets that were unable to be collapsed earlier within the channel area. They may now be collapsed, one at a time if necessary. This might mean extending the right edge of the channel by some more columns. The second possibility is that the tracks are continuing with those nets because they comprise the list of right border nets. These are as they should be and end there.

In order to calculate the time complexity for this routing algorithm, the parameters are the length of the channel and the number of tracks. The algorithm makes one pass over a channel having length n. As it processes each column, it checks every track. This means that the time taken is equal to the channel length multiplied by the number of tracks. If the number of nets is proportional to n (the length of the channel), then the time complexity comes out to be O(n²) since n tracks could be required in the worst case.