The Foldability Criteria

Not all regular arrays are foldable. We have already presented the four basic requirements for an array to be considered an origami array:

• Each processing element has identical functionality.
• Each processing element is stateless.
• The processing elements are connected by a regular, tessellable interconnect.
• The interconnect has causal data flow.

There are obviously some arrays that would be desirable to build that do not fit these criteria. Lu [19] showed that any semi-regular array can be turned into an origami array as long as the irregularities can be ``abstracted'' away. Take, for example, the alternate-slant architecture shown in Figure 2.6. This array is not foldable because the data dependencies vary on odd and even levels. However, such an array could be made foldable by taking each group of 1x2 processors and turning them into a new, virtual processor, as shown in Figure 2.7. The new processor has three inputs and three outputs. The architecture is now foldable.

The smallest collection of processors that can be abstracted away to make a foldable architecture is called the kernel. What architectures can be made foldable? Lu [19] rephrases the ``foldability criteria:''

An architecture is foldable if and only if its local architecture has an abstraction which is a standard local mosaic architecture, provided that the boundaries are compatible.

To this must also be added that the system as a whole have causal data flow.