An Efficient General-Purpose Parallel Computer

Abstract

The question of what is a good way to interconnect a large number of processors is investigated The roam result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors. Categories and Subject Descriptors- F. 1.1 (Computation by Abstract Devicesl: Models of Computation-- automata; bounded-action devices; relations among models; unbounded-action devices, F 1.2 (Computation by Abstract Devices): Modes of Computation--alternation and nondeterminism; parallelism, relations among models; F.I.3 (Computation by Abstract Devices): Complexity Classes--complexuy hierarchies; relations among complexity classes General Terms. Algontl~ns, Design, Theory