Module Placement

The first step in the algorithm is to place the modules in an array so that routing between them is as short as reasonably possible. Modules are first ordered vertically into distinct levels (this is a logical placement-the physical placement won't be determined until later), and then are placed horizontally within each level.

The ordering of modules vertically is a simple process:

1. Mark all the modules as unused.
2. Add all the input modules to level 0, and mark them as used; set the level number to 1.
3. Add to the current level all modules (which are not output modules) that depend only on modules that have already been added to previous levels.
4. Increment the level number by 1.
5. If all modules that are not output modules are marked as used, add the outputs to the current level and stop.
6. Go to step 3.

Note that step 3 must eventually use all the modules because there can be no circular dependencies between modules (the modules form a strict hierarchy).

Once the modules have been ordered vertically, they must be arranged horizontally. This is done in two stages: ideal placement, and shifting to allow room for routing. During the ideal placement stage, the modules are placed in such a way that the total idealized routing distance to each module is minimized. For a given module, , the idealized routing distance is the sum of the squares of the horizontal displacements for each module that feeds data to an input of . The horizontal position of these modules will always be known since module placement proceeds in order down the hierarchy. For each level, modules are picked one by one and placed in such a manner that their idealized routing distance is minimized and they do not overlap.

Once the modules are ordered vertically and placed horizontally in an ideal manner, some may need to be shifted to make room for wires that need to go between modules. This is done by tracing the ideal path of each wire while keeping counters (which we will call and ) indicating how much space adjacent modules need between them. The algorithm is:

1. For all , let .
2. For each , follow the routing from its source to its destination in a straight diagonal line. Whenever would intersect a module, , increment either or depending on whether the wire is intersecting the right half or left half of the module, respectively. Keep track of which modules needs to pass between, and whether it needs to pass on the right or the left.
3. Shift the modules (keeping their same relative horizontal position) such that the distance between adjacent modules and is at least .
4. For each , find the new position of each pair of modules it is going to pass between, and assign it a goal column for that level such that no two wires have the same goal column for that level (there must be enough columns because of steps 2 and 3). The goal column for the wire's starting level is the horizontal position of the appropriate output of the source module, and the goal column for the destination level is the horizontal position of the appropriate input of the destination module. The only time two wires can have the same goal column is at the wires' starting level. This will happen when the output of a module needs to be sent to two other modules.

Once this step is completed, all modules have been placed in such a manner that routing, using the appropriate goal columns, must be possible without backtracking.