An architecture for a loosely-coupled parallel processor

technical reportAn architecture for a large (e. g. 1000 processor) parallel computer is presented. The processors are loosely-coupled, in the sense that communication among them is fully asynchronous, and each processor is generally not unduly delayed by any immediate need for specific data values. The network supporting this communication is tree shaped, with the individual processors connected at leaf nodes. The machine executes a graphical version of applicative Lisp. The program execution model is demand-driven, with a special deferred interpretation for dotted pair evaluation, termed "lenient cons". Opportunities for concurrency arise in the parallel evaluation of arguments to strict operators, i. e. those known to require evaluation of their full set of arguments. Such opportunities are exploited by exporting function application tasks to neighboring processor nodes in the tree, subject to a hierarchical notion of load balancing. Locality of task allocation and communication is a key objective of the machine. An integrated design toward that end is presented, combining language issues, firm semantic foundations, and anticipated hardware technologies