PELCR: Parallel Environment for Optimal Lambda-Calculus Reduction

Simple item page
dc.creatorPedicini, M.
dc.creatorQuaglia, F.
dc.date2004-07-22
dc.date2004-07-23
dc.date.accessioned2026-07-07T03:21:35Z
dc.date.available2026-07-07T03:21:35Z
dc.descriptionIn this article we present the implementation of an environment supporting Lévy's \emph{optimal reduction} for the $λ$-calculus \cite{Lev78} on parallel (or distributed) computing systems. In a similar approach to Lamping's one in \cite{Lamping90}, we base our work on a graph reduction technique known as \emph{directed virtual reduction} \cite{DPR97} which is actually a restriction of Danos-Regnier virtual reduction \cite{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 {\em 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 {\tt C} language and using a standard interface for message passing, i.e. MPI, thus making PELCR itself a highly portable software package.
dc.identifierhttps://arxiv.org/abs/cs/0407055
dc.identifierhttp://arxiv.org/abs/cs/0407055
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32259
dc.subjectLogic in Computer Science
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectF.4.1
dc.titlePELCR: Parallel Environment for Optimal Lambda-Calculus Reduction
dc.typetext

Files

Collections

arXiv