PELCR, parallel environment for optimal lambda-calculus reduction. In this article we present the implementation of an environment supporting Lévy’s optimal reduction for the λ-calculus on parallel (or distributed) computing systems. In a similar approach to Lamping’s, we base our work on a graph reduction technique, known as directed virtual reduction, which is actually a restriction of Danos-Regnier virtual reduction. 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. While developing PELCR we adopted both a message aggregation technique, allowing 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 the parallelism intrinsic to λ-terms while performing the reduction. 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, that is, MPI, thus making PELCR itself a highly portable software package.
Keywords for this software
References in zbMATH (referenced in 4 articles , 1 standard article )
Showing results 1 to 4 of 4.
- Lai, Anna Chiara; Pedicini, Marco; Piazza, Mario: Abstract machines, optimal reduction, and streams (2019)
- Solieri, Marco: Geometry of resource interaction and Taylor-Ehrhard-Regnier expansion: \textitaminimalist approach (2018)
- Pedicini, Marco; Quaglia, Francesco: PELCR: parallel environment for optimal lambda-calculus reduction (2007)
- Pedicini, Marco; Quaglia, Francesco: PELCR: Parallel environment for optimal lambda-calculus reduction (2004) ioport