17. – 21. Februar 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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Externe 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 der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.