The development of parallel-processing computer technology has proceeded at rapid pace over the past decade. Computers have progressed from systems with a single high-functionality processor to ones with hundreds of thousands or millions of low-functionality processors. These latter systems rely more on the parallelism of a problem than raw processor power to find a time-efficient solution. When millions of processors need to be connected, the interconnection strategy becomes a serious problem; in order to decrease the routing distance between processors, high-dimensional networks must be used, which in turn lead to problems in physical layout. A different approach is to arrange the processors in a regular-interconnect mesh. While this does not provide for easy communication between distant processors, it is easy to wire. It is also well-suited for some classes of applications, including those that require simple data flow, such as FFTs. One class of such architectures, developed by Alan Huang of AT&TBell Laboratories, is called computational origami. While this class of architectures can include any grain of processors from 2-input/2-output boolean gates to Cray-2s, a simple, fine-grained version is ideal for some currently planned optical computers [5][13][3][14].
This thesis does not dwell on the properties of an origami architecture, although a brief overview is given in Chapter 2. More thorough treatments can be found in [16][4][6][3][19][15]. Instead, it deals with the software problem of assigning tasks to the processors in such a machine. Since this is such a large problem, only one particular case is examined, that of a machine consisting of simple 2-input/2-output processors connected by a 2-dimensional alternate-slant interconnect. A program for compiling a simple language into task assignments is described.
Chapter 2 provides an overview of the concepts of computational origami. Chapter 3 describes the destination architecture for the compiler, and introduces the algorithms used by the compiler. Chapter 4 describes several probabilistic optimization methods for the compiler, and presents results on trial programs. Chapter 5 discusses future work that can be performed. Appendix A describes the compiler itself in detail. A second appendix, not available in the hypertext version of this document, provides the complete code listing of the compiler.