Les riches heures de l'ordonnancement
Résumé
Parallelizing means executing simultaneously multiple operations. The efficient management of the assignment of tasks on available computing resources is a challenging problem. Whatever the considered execution support, this problem is crucial at any level from basic instructions, library components to full applications. Moreover, it can be studied from various points of view (users, system administrators). Scheduling is the main part for efficient resource management. It consists in determining where and when to execute the tasks while optimizing one or several objectives under hardware constraints. This is an old problem which arised with the first vector machines in the early seventies. Today, it is still a challenging problem since many new constraints should be considered. The purpose of this paper is to review the main constraints and to show how to take them into account in the scheduling policies. We defend a position of well-founded approaches for designing scheduling algorithms that allow to obtain guaranteed performances at a reasonable cost.
Paralléliser c'est exécuter des opérations (instructions ou programmes) sur plusieurs ressources simultanément. Gérer efficacement la répartition de tâches sur ces ressources est un problème qui se pose quel que soit le support d'exécution matériel, le système d'exploitation ou le langage cible choisi pour exécuter une application et à tous les niveaux (instructions élémentaires, composants de bibliothèque, applications). De plus, on peut envisager ce problème de différents points de vue (utilisateurs, administrateurs système). L'ordonnancement est au coeur de la gestion efficace de ressources. Il s'agit de déterminer où et quand exécuter les tâches en optimisant si possible un ou plusieurs objectifs avec des contraintes variées. C'est un problème qui s'est posé dès l'introduction des premières machines vectorielles et parallèles dans les années 1970 et qui reste aujourd'hui toujours d'actualité, souvent avec des déclinaisons bien plus larges comme nous allons essayer de le montrer dans cet article. L'objectif ici est de dresser un bilan des recherches menées lors des dernières décénies autour du thème de l'ordonnancement dans le contexte du parallélisme et d'en discuter les principaux enjeux aujourd'hui. Nous défendons en particulier une approche de conception d'algorithmes bien fondée sur le plan théorique, permettant à faible coût d'obtenir des garanties de performance.