M. Pedicini and F. Quaglia. A parallel implementation for optimal lambda-calculus reduction. In 2nd International Conference on Principles and Practice of Declarative Programming (PPDP 2000, Montreal), ACM Proceedings, pages 3-14. ACM Press, Berlin, 2000.

In this paper we present a parallel implementation of Lévy's optimal reduction for the lambda-calculus citeLev78. In a similar approach to Lamping's one in [?], we base our work on a graph reduction technique known as directed virtual reduction citeDPR97 which is actually a restriction of Danos-Regnier virtual reduction citeDanosRegnier93. The parallel implementation relies on a strategy for directed virtual reduction, namely half combustion, which we introduce in this paper. We embed 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 fine. Through this technique we obtain 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.

[ bib | .ps ]

Back