Efficient Parallel Skeletons for Nested Data Structures

摘要

Skeleton programming enables programmers to build parallel programs easier by providing efficient ready-made skeletons. In addition to primitive skeletons, diffusion skeleton has been proposed for rather complicated problems, abstracting a good combination of primitive skeletons. However, since they equally treat each element in target data, the existing skeletons are not always efficient for nested data structure where sizes of inner elements may be remarkably different. To resolve this problem, this paper proposes a new parallel skeleton, segmented diffusion, specially for nested data structure. The proposed skeleton is a nested version of the diffusion skeleton and similarly provides a proper combination of primitive nested skeletons. This paper also describes implementation of the skeleton and some experimental results, showing that the proposed skeleton is efficient and can be applied to a wider class of problems.