PELCR: Parallel Environment for Optimal Lambda-Calculus Reduction

Original · EN

In this article we present the implementation of an environment supporting Lévy's optimal reduction for the λ-calculus Lev78 on parallel (or distributed) computing systems. In a similar approach to Lamping's one in Lamping90, we base our work on a graph reduction technique known as directed virtual reduction DPR97 which is actually a restriction of Danos-Regnier virtual reduction DanosRegnier93. The environment, which we refer to as PELCR (Parallel Environment for optimal Lambda-Calculus Reduction) relies on a strategy for directed virtual reduction, namely half combustion, which we introduce in this article. While developing PELCR we have adopted both a message aggregation technique, allowing a reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors. We also present an experimental study demonstrating the ability of PELCR to definitely exploit parallelism intrinsic to λ-terms while performing the reduction. By the results we show how PELCR allows achieving up to 70/80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with the C language and using a standard interface for message passing, i.e. MPI, thus making PELCR itself a highly portable software package.