Routing

Now that the modules have been placed horizontally and ordered vertically, and each wire that needs to be routed has a goal column for every level it must pass through, routing can proceed. Routing proceeds from the outputs, up through the levels, to the inputs (thus routing proceeds in the opposite direction of the flow of data). The routing algorithm maintains the following state: the current level and the set of wires, , that are currently being routed. It proceeds as follows:

1. Set equal to all whose destination module is an output, and set each wire's current position to the horizontal position of the output. Set the current level to the level on which all outputs reside minus 1.
2. Determine the goal column for each wire for the current level.
3. Route each wire toward its goal column by the method outlined below. When all the wires destined for a given module are at their respective goal columns, and placing that module here would not block other wires from reaching their goal columns on this level, place this module in the array, and delete all whose source module has now been placed.
4. Continue routing as in step 3. Whenever the top of a freshly placed module is reached, add the wires whose destinations are that module to . Continue until the tops of all modules on this level have been reached.
5. Decrement the current level number.
6. Repeat until level 0 (the level containing only array inputs) is reached.
7. Continue routing wires until all wires have reached their goal columns (the positions of the appropriate inputs).

As wires are being routed, a number of conflicts can arise. These include two wires interacting (such as needing to cross) or a wire needing to move left or right and not being able to (because it is already at the left or right side of a processor, and thus can't go sideways on the current level). Such conflicts are resolved according to the appropriate entry in Table 3.1. For example, if the wire entering on the left side of the node needs to go right and the wire entering on the right side of the node needs to go left, a crossover should be placed at the current location. Likewise if only one wire is entering the node, is entering on the left, and needs to go left, a passthrough should be placed since the wire will be able to move left on the next level up (because of the alternate-slant architecture).

The only conflict not covered by this table is the case where two wires are entering a node and have the same goal column for the current level. In this case, the wires should be combined by using a left or right broadcast and removing one of the wires from the current wire list .