Michael S. Littman
Christopher D. Metcalf
July 22, 1990
In this paper, we develop the idea of asynchronous data-parallelism; that is, data-parallel programs in which the processing elements may be performing different computations at any given time. We suggest that since synchronous machines are forced to sequentialize the clauses of conditional statements, programming is hindered. Programmers must waste time factoring and merging expensive expressions from conditional clauses. This is still not always sufficient to use the machines at their maximum efficiency.
We propose a method by which a synchronous machine can be used to simulate a MIMD machine language called Milan. Milan can be used as an efficient target for existing data-parallel languages such as Crystal and PARALATION LISP. By keeping Milan's instruction set small and regular, we are able to keep the simulation overhead to a minimum and achieve impressive performance on a few simple problems.
We believe that Milan could be used as a research tool for computational models which require fine-grained asynchronous machines, such as very complex neural networks, CSP or parallel symbolic processing.