RÉSUMÉ. Cet
article présente une stratégie d'ordonnancement
des graphes de tâches associés à une fonction
de temps linéaire dans le contexte de la programmation
parallèle. Cette stratégie d'ordonnancement est
utilisée pour exécuter un graphe cubique de tâches,
dont les tâches ont la même durée d'exécution
et les temps de communications inter-tâches sont négligés,
sur un réseau de processeurs bi-dimensionnel et asymptotiquement
optimal par rapport à la fonction de temps. Ce résultat
améliore la meilleure borne précédemment
connue.
ABSTRACT. This work proposes
a scheduling strategy, based on re-indexing transformations, for
task graphs associated with a linear timing function. This scheduling
strategy is used to execute a cubical task graph, for which all
the tasks have the sane execution time and inter-tasks communication
delays are neglected, on a two-dimensional array of processors
which is asymptotically space-optimal with respect to the timing
function.
MOTS-CLÉS : ordonnancement,
graphe de tâches, calcul parallèle, fonction de temps
linéaire, fonction d'allocation, ré-indexation,
optimalité.
KEYWORDS: Scheduling, task
graph, parallel processing, linear time function, allocation function,
re-indexation, optimality.
|