Preliminaries

For the purposes of this algorithm, an origami array is a two-dimensional staggered array of nodes as described above. In a fully automated logical compiler it might be desirable to treat each node independently for placement. However, in a large application the number of nodes may be very large (equal to the number of discrete logical functions that need to be performed) and compilation time quickly increases beyond the realm of practicality. Therefore it is frequently desirable to break down the problem into subproblems, and place and route the nodes required for each subproblem separately or perhaps even by hand. Once the placement and routing for a subproblem has been produced, we can consider the result to be an atomic unit for future connection to other nodes and subproblems. Such a subproblem is called a module, and is considered in this algorithm to be an by rectangular set of nodes with defined input and output locations. Typical modules might be adders, multipliers, and bus multiplexors. Individual ungrouped nodes are also considered to be modules.

This algorithm assumes that there are four flavors dedicated to routing. They are:

1. passthrough : copy the left input to the left output, and the right input to the right output.
2. crossover : copy the left input to the right output, and the right input to the left output.
3. left broadcast : copy the left input to both the left and right outputs, and discard the right input.
4. right broadcast : copy the right input to both the left and right outputs, and discard the left input.

A series of connected routing flavors is called a wire.

The algorithm requires the following data as input:

• , the set of all the modules that need to be placed.
• , the set of dependencies between the modules. A dependency is the set of modules that provide inputs to a particular module.
• , the set of routings between the modules. Each routing indicates an output pin of a module () and the input pin of another module () to which it should be connected.

Program inputs and outputs are treated as special modules that are used during routing, but are not actually placed in the physical array.