A Compiler Algorithm to Guide Runtime Scheduling

Un algorithme de compilation pour guider l'ordonnancement dynamique

Christophe Alias (1) , Samuel Thibault (2, 3) , Laure Gonnord (1)

1 CASH - CASH - Compilation and Analysis, Software and Hardware
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique
3 STORM - STatic Optimizations, Runtime Methods

Task-level parallelism is usually exploited by a runtime scheduler, after tasks are mapped to processing units by a compiler. In this report, we propose a compilation-centric runtime scheduling strategy. We propose a complete compilation algorithm to split the tasks in three parts, whose properties are intended to help the scheduler to take the right decisions. In particular, we show how the polyhedral model may provide a precious help to compute tricky scheduling and parallelism informations. Our compiler is available and may be tried online at http://foobar. ens-lyon.fr/kut.

Le parallélisme de tâches est habituellement explotié par un ordonnanceur dynamique, après que les tâches aient été compilées sur les différentes unités d'exécution. Dans ce rapport, nous proposons une nouvelle stratégie d'ordonnancement qui donne une place centrale au compilateur. Nous proposons un algorithme de compilation complet et un compilateur pour diviser les tâches en trois parties, dont les propriétés permettent à l'ordonnanceur de prendre les bonnes décisions. En particulier, nous montrons que le modèle polyédrique permet de construire et de raffiner ce type de stratégie.

Mots clés: automatic parallelization; Compilation; polyhedral model; runtime scheduling

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Langage de programmation [cs.PL]

Christophe Alias, Samuel Thibault, Laure Gonnord. A Compiler Algorithm to Guide Runtime Scheduling. [Research Report] RR-9315, INRIA Grenoble; INRIA Bordeaux - Sud-Ouest. 2019. ⟨hal-02421327⟩