Scalable and Modular Scheduling.

Scheduling a program (i.e. constructing a timetable for the execution of its operations) is one of the most powerful methods for automatic parallelization. A schedule gives a blueprint for constructing a synchronous program, suitable for an ASIC or VLIW processor. However, constructing a schedule entails solving a large linear program. Even if one accept the (experimental) fact that the Simplex is almost always polynomial, the scheduling time is of the order of a large power of the program size. Hence, the method does not scale well. The present paper proposes two methods for improving the situation. Firstly, a big program can be divided in smaller units (processes) which can be scheduled separately. This is \em modular scheduling Second, one can use projection methods for solving linear programs incrementatly. This is specially efficient if the dependence graph is sparse.Ordonnancer un programme est l’une des méthodes les plus puissantes en parallélisation automatique. Un ordonnancement fournit un schéma de construction pour un programme synchrone, bien adapté`à un circuit spécialisé(ASIC) ou à un processeur VLIW. Cependant, pour construire un ordonnancement il faut en général résoudre un programme linéaire de grande taille. Même si l’on accepte le fait expérimental que le Simplex est presque toujours de complexité polynomiale, le temps d’ordonnancement est de l’ordre d’une puissance élevée de la taille du programme. En conséquence,la méthode ne passe pas bien à l’ échelle. Cet article propose deux méthodes pour améliorer la situation. On montre tout d’abord comment diviser un programme en petites unités (processus) qui peuvent être ordonnancées individuellement. D’autre part, les méthodes de projection permettent de résoudre les programmes linéaires de façon incrémentale, ce qui est spécialement efficace quand le graphe de dépendance est creux