THE PARALLEL PROGRAMMING LANGUAGE Id AND ITS COMPILATION FOR PARALLEL MACHINES
Rishiyur S. Nikhil · International Journal of High Speed Computing · 1993
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).