At Imperial College we have developed a language for structured parallel programming (SPP(X)) using functional skeletons to compose and co-ordinate concurrent activities written in a standard imperative language. The kernel language, which is currently under construction, is based around the distributed array data type. The language is thus highly suitable for expressing regular computations.
The kernel language is less suitable for expressing programs over irregular data structures. We propose the introduction of Parallel Abstract Data Types (PADT) to enable such programs to be expressed naturally. A PADT consists of a data type definition of the irregular data structure and a set of parallel operators over this type.
The introduction of PADTs raises the question of how they are to be implemented. A direct approach would be to hand code the operators in some imperative language with message passing. In this approach the PADT becomes part of the kernel language. This is undesirable as this could possibly lead to an ever increasing kernel language as new PADTs are found to be necessary. The disadvantages of increasing the kernel language with the introduction of each new PADT include the need to extend and reformulate any system for optimising combinations of skeletons and any system for compiling programs.
We propose an alternative approach to implementing PADTs. The philosophy of our approach is to build the PADTs on top of the existing language constructs rather than to extend the kernel language. The encoding of a PADT into the kernel language can be arrived at through several data type transformations thus ensuring correctness and providing the opportunity for reasoning about optimisations. We demonstrate the approach by outlining a derivation from an example program over an irregular triangular mesh to its final regular array encoding.
We conclude the talk by suggesting that the concept can be applied to High Performance Fortran (HPF). Currently, HPF-1 cannot directly express irregular applications. There are proposals to extend the language with constructs for expressing irregular applications. It may be possible to apply our techniques to HPF-1, thus enabling irregular applications to be expressed without the need for kernel language extensions.
There are open questions including whether HPF-1 or SPP(X) are sufficiently rich to build all "useful" PADTs.