Grid Computing: Optimization Techniques for Skeletons on Grids
Skeletons are common patterns of parallelism in distributed computing systems. These often-used components, such as farm, map, and pipeline, can be abstracted and offered to application programmers as programming primitives. This article introduces the motivation for implementing algorithmic skeletons and demonstrates use of Lithium, a programming environment based on Java and Remote Method Invocation, for this purpose. Also discussed are three optimizations for skeletons on grids: a look ahead mechanism that increases the overall degree of grid parallelism, a lazy taskbinding technique that reduces interactions between grid servers and the task dispatcher, and dynamic improvements that optimize the collection of results and work-load balance. The transparent integration of these optimizations within Lithium improves performance and communication for heterogeneous computational grids. Although Lithium is used as an example throughout this article, the optimizations being introduced can be used in other skeleton-based programming systems and are not exclusive to Lithium.