Planification des calculs multithreads par vol de travail

Cet article étudie le problème de la planification efficace des calculs multithreads entièrement stricts (c'est-à-dire bien structurés) sur des ordinateurs parallèles. Une méthode populaire et pratique de planification de ce type de calcul dynamique de style MIMD est le « vol de travail », dans lequel les processeurs ayant besoin de travail volent des fils de calcul à d'autres processeurs. Dans cet article, nous présentons le premier planificateur de vol de travail prouvablement efficace pour des calculs multithreads avec des dépendances. Plus précisément, notre analyse montre que le temps d'exécution attendu d'un calcul entièrement strict sur P processeurs utilisant notre planificateur de vol de travail est T 1 / P + O ( T ∞ , où T 1 est le temps d'exécution sériel minimum du calcul multithread et ( T ∞ est le temps d'exécution minimum avec un nombre infini de processeurs. De plus, l'espace requis par l'exécution est au plus S 1 P , où S 1 est l'exigence d'espace sériel minimum. Nous montrons également que la communication totale attendue de l'algorithme est au plus O ( PT ∞ ( 1 + n d ) S max ), où S max est la taille de l'enregistrement d'activation le plus grand de n'importe quel fil et n d est le nombre maximum fois qu'un fil se synchronise avec son parent. Cette limite de communication justifie la sagesse populaire selon laquelle les planificateurs de vol de travail sont plus efficaces en communication que leurs homologues de partage de travail. Tous ces trois limites sont existentiellement optimales à l'intérieur d'un facteur constant.