To the first issue, we argue that very general skeletons may be inadequate for expressing certain algorithms and may lead to implementations that are not very efficient, whereas too specialized skeletons may degenerate to plain parallel library functions. Our approach is therefore somewhere in between these two extremes, more precisely, we try to design skeletons that can be used in solving related problems, or problems from different areas, but having a similar (e.g. hierarchical) structure.
We choose as our class of applications adaptive multigrid algorithms. There are several reasons for this. Firstly, multigrid methods are non-trivial numerical applications. Secondly, there is an entire class of multigrid methods, which build however on the same blocks, thus fitting naturally in the skeletal concept. Thirdly, multigrid skeletons can be used in the implementation of other classes of hierarchically structured algorithms, like for instance N-body methods.
We have then analyzed the data dependencies and access patterns that occur in multigrid and have derived from them two kinds of operations: `horizontal' or intra-grid operations, like relaxation or correction computation and `vertical' or inter-grid operations like grid refinement/coarsening and data prolongation and restriction.
Based on these data dependencies, we have derived a series of skeletons for multigrid. Besides point-wise operations like `map', we also employed `environment operations', which are applied to single points, together with their environment, i.e. their neighboring points in the horizontal case and their parents/children in the vertical case, respectively.