Towards the Classification of Algorithmic Skeletons

Duncan K. G. Campbell

Department of Computer Science,

University of York

December 3, 1996

Abstract

Algorithmic skeletons are seen as being high-level, parallel programming language constructs encapsulating the expression of parallelism, communication, synchronisation, embedding, and costing. This report examines the classification of algorithmic skeletons, proposing one classification, and examining others which have been devised. Various algorithmic skeletons are examined, and these are categorised to form a core of algorithmic skeletons suitable for a general classification which is based on practical experience in the use of such skeletons. This categorisation is compared with others which have been proposed. Similarly, other skeleton-like approaches are briefly examined.

1 Introduction

1.1 Algorithmic Skeletons

Algorithmic skeletons are envisaged as high-level, parallel programming language constructs encapsulating the expression of parallelism, communication, synchronisation and embedding, and having an associated cost complexity. Skeletons are to parallel threads as sequential looping constructs are to goto and label [BdRP93] providing structured expression of certain algorithmic forms. So algorithmic skeletons can help reduce parallel programming errors as part of a concurrency toolbox" with which programmers can construct the abstraction required to solve their problems.

Indeed, the requirement for algorithmic skeletons has been long known. In 1978 Backus [Bac78] called for programming languages to be designed from a fixed set of high-level constructions capturing common computation patterns.

These constructs are necessary because parallel programming is more complex than serial programming due to the greater degrees of freedom involved. Serial programming involves only a single thread of computation at any one time, while parallel programming involves multiple threads of computation which also need to communicate and synchronise with each other. This complexity is increased with massively parallel processing, which increases the number of threads executing concurrently and needing to communicate and synchronise with each other.

Furthermore, algorithmic skeletons correspond to the programming level in terms of McColl's classification of models of parallel computation [McC93], as they provide a notation for the precise, high-level description of correct and efficient methods for the solutions of computational problems.

1.2 Overview

A survey of several example skeletons is presented in Section 2. This is then summarised in Section 3, where the basis for a general classification of algorithmic skeletons is presented