February 17 – 21 , 1997, Dagstuhl Seminar 9708

Theory and Practice of Higher-Order Parallel Programming


M. Cole (Edinburgh), S. Gorlatch (Passau), Ch. Lengauer (Passau), D. Skillicorn (QU Kingston, Canada)

For support, please contact

Dagstuhl Service Team


External Homepage
Dagstuhl-Seminar-Report 169


The diversity and complexity of parallel computers (both proposed and implemented) drives the quest for portable, tractable and efficiently implementable parallel programming models and languages. One approach to the problem focuses on the design and exploitation of higher-order programming and algorithmic constructs which can become the fundamental building blocks in such a model. An analogy can be drawn with the historical development of sequential programming, in which simple, relatively unstructured mechanisms, closely tied to the underlying architecture, have given way to more powerful, structured and abstract concepts. Similar progress in the parallel case would raise the level of abstraction from models in which communications (or the like) are primitive to a world in which more complex patterns of computation and interaction are combined and presented as parameterized higher-order program-forming constructs.

There are three more or less interwoven threads of research in the area. Work on algorithmic skeletons focuses on the selection and implementation of appropriate primitives (the “skeletons”), typically with a bias towards coarse-grain primitives and control-parallel implementation. Researchers in program development apply and extend techniques from the sequential branch of the field to the parallel case, developing new design methodologies and models in which, as discussed above, the level of abstraction is raised from the base level of simple concurrent activities, and in which there are facilities for understanding the cost of the program under development during its design. The final thread seeks to design and understand the formal models which underpin the area, whether by viewing existing models in a parallel light (for example, work on the Bird-Meertens Formalism as a parallel programming model) or by developing new ones. Much work in this thread takes a more data-parallel view of the process.

The concerns spanned by these groups range from the very pragmatic questions of implementation techniques and real applications to the abstract world of formal program development. Many researchers from all of the areas had already been brought together electronically, via e-mail lists and WWW pages. The seminar was an opportunity to establish the community and intensify the contacts.

Questions discussed at the seminar included:

  • Which primitives are suitable for a parallel programming model?
  • Can the selection of primitives be justified pragmatically and/or theoretically?
  • To what extent should the parallelism within the primitives be apparent to the programmer?
  • To what extent can and should the implementation mechanisms attempt to optimize the parallel structure of composed primitives?
  • To what extent can this optimization be reflected in a compositional cost model (or cost calculus)?
  • To what extent do ‘sequential’ techniques in program development shed light on the parallel case?
  • What are the new transformations for the new primitives?
  • How well does the approach compare with conventional models in its ability to express ‘classical’ parallel algorithms and to derive new ones?

The 43 participants of the workshop came from 10 countries: 16 from Germany, 8 from the UK, 6 from the USA, 5 from France, 2 from Italy and 1 from each Australia, Canada, Japan, New Zealand and Sweden. The organizers would like to thank everyone who has helped to make this workshop a success.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.