Optimization techniques for implementing parallel skeletons in distributed environments

Skeletons are common patterns of parallelism such as farm and pipeline that can be abstracted and offered to the application programmer as programming primitives. We describe the use and implementation of skeletons in a distributed computation environment, with the Java-based system Lithium as our reference implementation. Our main contribution is optimization techniques based on an asynchronous, optimized RMI interaction mechanism, which we integrated into the macro data flow (MDF) evaluation technology of Lithium. In detail, we show three different optimizations: 1) a lookahead mechanism that allows to process multiple tasks concurrently at each single server and thereby increases the overall degree of parallelism, 2) a lazy task-binding technique that reduces interactions between remote servers and the task dispatcher, and 3) dynamic improvements based on process monitoring that optimize the collection of results and the work-load balancing. We report experimental results that demonstrate the achieved improvements due to the proposed optimizations on various testbeds, including heterogeneous environments.