TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 05101

Scheduling for Parallel Architectures: Theory, Applications, Challenges

( Mar 06 – Mar 11, 2005 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/05101

Organizers
  • Erik Altman (IBM TJ Watson Research Center, US)
  • James Dehnert (Palo Alto, US)
  • Christoph W. Kessler (Linköping University, SE)
  • Jens Knoop (TU Wien, AT)



Summary

Scheduling, the task of mapping computation units to time slots on computing resources for execution, is important for the effective use of resources in all kinds of parallel systems, ranging from the level of more coarse­grain tasks in multiprocessors, clusters and computational grids, via medium­grain tasks at the loop level, down to instruction­level parallelism (ILP)

Scheduling issues are of crucial importance in very diverse areas ranging from operating systems and realtime systems to network management to static and dynamic program optimization and code generation. Likewise, they evolve on very different levels of granularity, from coarse grain task and job scheduling over loop scheduling to fine­grain instruction scheduling. Though highly interrelated, these fields are tackled by usually independently working communities. However, emerging processor architectures such as chip multiprocessors will demand effective hybrid scheduling strategies that unify previously separate scopes of scheduling.

In practice, scheduling problems often do not appear in isolation but come with a domain-specific context that---explicitly or implicitly---introduces interdependencies with other optimization problems. For instance, when compiling for parallel execution platforms, decisions made in scheduling depend on and influence other aspects of the problem of generating efficient parallel code, such as resource allocation, clustering, or program transformations, such that scheduling can rarely be considered as an isolated problem. Such interdependences, even though perhaps most apparent for instruction­level parallelism, appear at all levels of parallelism and are solved by various techniques, including heuristics, integer programming, dynamic programming, or genetic programming. Integrated approaches are generally more flexible but suffer from an increased problem complexity.

Interestingly, the research communities for task-level, loop-level and instruction-level scheduling appear to be quite separated from each other. Furthermore, there appears to be a gap between the theoretical foundations of scheduling, formulated in terms of abstract machine models, and the algorithms developed in both academia and industry for concrete scheduling problems in compilers and run-time systems for parallel computer architectures. This gap is exacerbated by requirements that practical schedulers deal with the complexities of irregular architectures.

The purpose of this seminar was therefore to gather leading experts from these scheduling communities, to identify common approaches, techniques, frameworks and tools, and to stimulate cross­fertilization between the various scheduling communities. Moreover, we intended to bridge the gap between scheduling theory and methods currently applied in compilers and run­time systems for parallel architectures. A third goal was to encourage a constructive dialog between scheduling algorithm designers and developers of parallel architectures, specifically in the embedded systems domain.

31 researchers accepted the invitation to the seminar and met 6--11 March 2005 at Schloss Dagstuhl, Germany. The seminar participants represented a broad spectrum of research on scheduling, including instruction scheduling, job scheduling, task scheduling, loop scheduling, parallel computer architecture, and scheduling theory.

With the invitation and the opening address, we provided the following guiding questions:

  • How can we bridge the gap between scheduling theory and practice?
  • Can the practical ILP scheduling problems broaden the theory models?
  • In particular, do recent micro­architectural trends such as clustered architectures add fundamentally different factors to the problem?
  • Is there current theory that can lead to interesting practical algorithms?
  • What are the interference effects between task­level, loop­level and instructionlevel scheduling?
  • Can existing scheduling approaches be transferred to other problem domains, granularities, or architecture models?
  • What are the phase­ordering effects, and the techniques, potential, and limitations of integrating scheduling with other transformations or code generation phases?
  • Can we define generic scheduling approaches for flexible optimization goals (execution time, stack/register space, energy consumption)?

A central goal of this seminar was thus to bring together leading experts of the various communities to foster discussions on the usability and usefulness of approaches developed for specific areas and the impact they may have to others. By means of cross­fertilization and synergy the seminar should contribute to both a better understanding of the key issues of scheduling and to further advancing the state-of-the-art in the various fields. The specific atmosphere of Dagstuhl Seminars, which can be characterized by openness, accessibility and cooperation, and which is supported by Schloss Dagstuhl's architecture, its services and facilities, encourages both formal and informal meetings and discussions and therefore provided a perfect environment to achieve these goals.


Participants
  • Erik Altman (IBM TJ Watson Research Center, US)
  • Saman Amarashinghe (MIT - Cambridge, US) [dblp]
  • Peter Aronsson (Linköping University, SE)
  • Ioana Banicescu (Mississippi State University, US)
  • Andrzej Bednarski (Linköping University, SE)
  • Florent Blachot (Universite Joseph Fourier, FR)
  • Peter Brucker (Universität Osnabrück, DE)
  • Alain Darte (ENS - Lyon, FR) [dblp]
  • James Dehnert (Palo Alto, US)
  • Christine Eisenbeis (University of Paris South XI, FR)
  • M. Anton Ertl (TU Wien, AT)
  • Aleksei Fishkin (MPI für Informatik - Saarbrücken, DE)
  • Franz Franchetti (Carnegie Mellon University, US) [dblp]
  • Stefan M. Freudenberger (STMicroelectronics - Singapore, SG)
  • Ramaswamy Govindarajan (Raman Research Institute - Bangalore, IN)
  • David Gregg (University College Dublin, IE) [dblp]
  • Guillaume Huard (Universite Joseph Fourier, FR)
  • Helen Karatza (Aristotle University of Thessaloniki, GR)
  • Daniel Kästner (AbsInt - Saarbrücken, DE) [dblp]
  • Christoph W. Kessler (Linköping University, SE) [dblp]
  • Jens Knoop (TU Wien, AT) [dblp]
  • Andreas Krall (TU Wien, AT) [dblp]
  • Welf Löwe (Linnaeus University - Växjö, SE) [dblp]
  • Markus Pister (Universität des Saarlandes, DE) [dblp]
  • Daniel J. Quinlan (LLNL - Livermore, US) [dblp]
  • Thomas Rauber (Universität Bayreuth, DE) [dblp]
  • Gudula Rünger (TU Chemnitz, DE) [dblp]
  • Markus Schordan (TU Wien, AT) [dblp]
  • Sid Ahmed Ali Touati (University of Versailles, FR)
  • Frédéric Vivien (ENS - Lyon, FR) [dblp]
  • Sebastian Winkel (Intel - Santa Clara, US)
  • Wolf Zimmermann (Martin-Luther-Universität Halle-Wittenberg, DE)