Serial combinators: "optimal" grains of parallelism


Paul Hudak and Benjamin Goldberg


A method is described for translating a high-level functional program into combinators suitable for execution on  multiprocessors with no shared memory.  It is argued that the granularity of the standard set of fixed combinators is too fine, whereas the granularity of user-defined functions is too coarse.  The notion of a serial combinator is introduced that in some sense has optimal granularity, and that takes into account pragmatic issues such as the complexity of expressions and communication costs between processors.  The technique improves on the standard notion of super-combinators by making them larger to retain locality and improve efficiency, and by ensuring that they have no concurrent substructure that could result in lost  parallelism.  Simulation results demonstrate improved performance on both sequential and parallel computing models.


    ,author={Hudak, P. and Goldberg, B.}
    ,title={Serial combinators: ``optimal'' grains of parallelism}
    ,booktitle={Functional Programming Languages and Computer Architecture}
    ,publisher={Springer-Verlag LNCS 201}