A parallel implementation for optimal lambda-calculus reduction
Marco Pedicini, Francesco Quaglia · 2000
In this paper we present a parallel implementation of L evy's optimal reduction for the -calculus [11].In a similar approach to Lamping's one in [10], we base our work on a graph reduction technique known as directed virtual reduction [3] which is actually a restriction of Danos-Regnier virtual reduction [4].The parallel implementation relies on a strategy for directed virtual reduction, namely half combustion, which w e introduce in this paper.We e m bed in the implementation both a message aggregation technique, allowing a reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors.The aggregation technique is mandatory as the granularity of the computation is ne.Through this technique we o btain a linear speedup close to 80% of the ideal one on a shared memory multiprocessor.This result points out the viability of parallel implementations for optimal reduction.