M. Pedicini and F. Quaglia. Scheduling vs. communication in PELCR. In Euro-Par'2002 - Parallel Processing, (Paderborn 2002), volume 2400 of Lecture Notes in Comput. Sci., pages 648-654. Springer, Berlin, 2002.

PELCR is an environment allowing reduction of lambda-terms on parallel/distributed computing systems. The computation performed in this environment is a distributed graph rewriting and a major optimization to achieve efficient execution consists of a message aggregation technique exhibiting the potential for strong reduction of the communication overhead. In this paper we discuss the interaction between the effectiveness of aggregation and the schedule sequence of rewriting operations. Then we present a Priority Based (BP) scheduling algorithm well suited for the specific aggregation technique. Experimental results on a classical benchmark lambda-term demonstrate the benefits from PB in allowing PELCR to achieve up to 88% of the ideal speedup while executing on a shared memory parallel architecture.

[ bib | .pdf ]

Back