Now that we've gone over the algorithm in detail, an example may help to get a more intuitive feel for the process. The language used in this example is described in detail in section A.1. The program that we will examine is:
INPUT a<2>@0, b<2>@4, c<1>@3; OUTPUT o<1>@0, p<1>@4, q<1>@3; o = AND(a<0>, b<0>); p = AND(a<1>, b<1>); q = c;
This program takes two two-bit inputs, a and b, ANDs them together pair-wise, and generates two one-bit outputs in o and p. There is also a single input, c, that is copied unchanged to the output q. The inputs have been specifically arranged in this example to cause the signals to cross during routing. The vertical hierarchy for this program is:
After ideal placement and moving to avoid routing conflicts, the position of the modules is as shown in Figure 3.2. The final array, after routing with this algorithm, is shown in Figure 3.3. The processors are staggered by half on each level, which is equivalent to the alternate-slant interconnect we've been discussing. The coordinates on the bottom correspond to those specified in an INPUT or OUTPUT statement.
A number of observations can be made about this array. The position of the inputs and outputs is obviously very critical. The last row of processors is devoted solely to moving the outputs to the desired locations, and the first three rows are devoted to permuting the inputs to reach the AND gates properly. This is obviously a very bad use of processor hardware. Some hand-tweaking can produce a much better result. For example, seeing how this result came out, we can rearrange the inputs and outputs by hand:
INPUT a<2>@[1,3], b<2>@[2,4], c<1>@5; OUTPUT o<1>@1, p<1>@3, q<1>@5; o = AND(a<0>, b<0>); p = AND(a<1>, b<1>); q = c;
This produces the optimal array shown in Figure 3.4. From this array we also see that the height of the array must always be an even number of processors tall, so that the array will fold properly. It is definitely a problem that the user must rearrange the inputs and outputs in order to achieve a good array. As the arrays get larger, the inputs and outputs have less of a direct impact, though, and the exact positioning of the modules, over which the user has no control, becomes the overriding factor. The automatic optimization of module placement will be the subject of the next chapter. Optimization of inputs and outputs is not dealt with in this thesis, but is discussed briefly in Chapter 5.
