Serial combinators: “optimal” grains of parallelism

Reviewer: James Russell McGraw

This paper presents a general strategy for automatically decomposing and dynamically distributing functional programs. The approach uses ideas from data flow computing, reduction machines, and conventional compiler technology. In overly simplistic terms, the authors propose to find reasonable partitions of code by finding maximally sequential groups of operations and then combining them into larger chunks, until the resulting units are sufficiently large to allow the work to be sent to independent processors. This paper is closely related to a previous paper published by these authors [1]. It describes a three phase strategy that is quite different and considerably clearer than the previous one, but it generates essentially the same combinators. This paper is a complex research paper. It requires a detailed understanding of combinators and supercombinators (good references are given). As far as the specific results are concerned, they are the same as those presented in the earlier paper (which is not surprising since the new algorithms produce the same combinators). These results do show interesting speedups for some small programs running on a hypercube and torus. However, it is not clear how good the baseline program is as a source of comparison. Also, the authors do not compare costs between the new algorithm and the one previously reported; the bulk of this paper is devoted to just describing the new algorithm. In summary, I would recommend this paper to people who are interested in the algorithmic details of the serial combinator approach; for others, the more readily available paper mentioned above [1] should suffice.