Structured parallel programming: Parallel abstract data types

A key requirement for any parallel programming system is the ability to support abstraction in order to allow programmers to work with familiar and natural concepts from their area of application without having to be too concerned with the low level complexities of parallel programming. However, some control over execution patterns and resource allocation is still required to ensure efficient execution. In this paper we show how these two, apparently conflicting, requirements can be reconciled in the structured parallel programming framework developed in the earlier paper. In particular we show how using the Structured Go-ordination Language (SCL) and its particular Fortran instantiation, Structured Parallel Fortran (SPF), we can systematically define user-oriented Parallel Abstract Data Types (PADTs) which provide a set of higher level co-ordination forms with which a user can construct his or her application. The important point is that parallelism is encapsulated in these operators which are implemented using the lower level co-ordination forms developed in the previous paper which provide explicit control over parallel behaviour. Knowledge available in the abstract structures can be utilised in these implementations to achieve efficient execution. We illustrate this technique by the development and implementation of a PADT to support parallel computation over an unstructured mesh.