Parallel Computing as a Commodity

Massively parallel computers have become undisputed champions in the supercomputing arena. The global computer industry, however, is increasingly dominated by consumer machines. In this thesis, we argue that everyday computers must become highly parallel machines in order to sustain the performance gains we have come to expect. For parallel computation to become a commodity, there must be an architecture which can be scaled as easily as memory arrays are now. We also need to establish that parallelism can benefit everyday applications and that operating systems for such machines can provide as comfortable and robust an environment as we have on sequential machines. We introduce an architecture based on cellular automata---meshes of simple, locally-connected processors in either 2 or 3 dimensions. We argue that this architecture is easily scalable, and from a theoretical viewpoint it is essentially as efficient as any other scalable architecture. We show two instances of this architecture, a simple one implemented in silicon and a more complex one implemented through a simulator. To show the viability of this architecture for everyday tasks, we have developed fast parallel algorithms for RSA encryption (using residue number systems and a new method for converting one RNS to another) and for document formatting (using a space-filling curve for data layout to achieve optimal $O(\droot{n})$ running time on a $d$-dimensional mesh). We also describe the design of an operating system for a cellular array based on the notion of the OS as the periphery, rather than the kernel, and show several advantages in security and performance this confers. Finally, we investigate the 3-dimensional dynamic allocation problem faced by such a system. This problem is NP-hard even in its static form, but we describe a simple best-fit allocator that works well in practice