One-Step Algorithm for Mixed Data and Task Parallel Scheduling Without Data Replication
Résumé
In this paper we propose an original algorithm for mixed data and task parallel scheduling. The main specificities of this algorithm are to simultane- ously perform the allocation and scheduling processes, and avoid the data replication. The idea is to base the scheduling on an accurate evaluation of each task of the application depending on the processor grid. Then no assumption is made with regard to the homogeneity of the execution platform. The complexity of our algorithm are given. Performance achieved by our schedules both in homogeneous and heterogeneous worlds, are compared to data-parallel executions for two applications: the complex matrix multiplicati- on and the Strassen decomposition.
Dans cet article, nous proposons un algorithme original d'ordonnancement mixte. Les principales spécificités de cet algorithme sont d'effectuer simultanément l'allocation et l'ordonnancement, et d'interdire la réplication de donnés. L'idée est de baser l'ordonnancent sur une évaluation précise de chacune des tâches de l'application en fonction de la grille de processeurs utilisée. Aucune hypothèses concernant l'homogénéité de la plateforme n'est donc effectuée. La complexité de notre algorithme est donnée. les performances obtenus par nos ordonnancement, aussi bien en homogène qu'en 'hétérogène, sont comparées à des exécutions utilisant le parallélisme de données pour deux applications : la multiplication de matrices complexes et la décomposition de Strassen
Fichier principal
RR-4591.pdf (301.64 Ko)
Télécharger le fichier
LIP-RR2002-34.pdf (274.54 Ko)
Télécharger le fichier