International Journal of High Speed Computing

This paper is a manifesto, a brief tutorial, and a call for experiments on programmable matter machines.

In this paper, we show a novel compilation method from a familiar class of languages to a familiar class of architectures. Id is basically a non-strict functional programming language, but it has a computation rule different from the traditional lazy evaluation rule, leading to enormous amounts of parallelism. Then, instead of using graph reduction (the traditional compilation method), we translate Id programs via two intermediate languages: first to dataflow graphs and then to code for an abstract machine called P-RISC. We describe how to implement the P-RISC abstract machine on a message-passing multicomputer and we describe optimizations at all levels. Throughout, the underlying theme is efficient fine-grained, data-driven execution, which we believe is essential for large-scale MIMD machines. We also remark on the suitability of the approach for other source languages (including FORTRAN).

We study several models for (possibly nondeterministic) dataflow. These models are based on histories, streams and traces. In the literature there are several proposals about how to built these models (for example, from specifications of the nodes in a network). Important issues are compositionality and full abstraction.

The paralation model consists of a new data structure and a small number of operators. The model has two main goals. As a model, it must be high-level and abstract. It should ask programmers to describe an algorithm, not every detail of the algorithm to hardware mapping. This leads to programming languages that are easy to use for general application programming. On the other hand, the constructs of the model must be easy to compile into efficient code for a variety of architectures (for example, MIMD or SIMD processors; bus-based, butterfly, or grid interconnect; and so on). An inefficient programming language, no matter how expressive and easy-to-use, cannot gain widespread acceptance.

This paper explains a calculational design technique for fine-grained parallel programs by means of an example. The example deals with the recognition of K-rotation invariant (or K-rotated) segments which is a generalization of the well known square recognition problem. Two parallel programs are derived. The first one determines for each segment of N successive inputs whether it is K-rotated, the latter determines whether the whole sequence thus far received is K-rotated.