La gestion de plusieurs soumissions dans les systèmes parallèles: l'approche d'ordonnancement équitable

Nous etudions le probleme d'ordonnancement de multiples soumissions dans des systemes paralleles. Nous analyson des scenarios avec de nombreux memoires issues de plusieurs utilisateurs au fil du temps . Chaque soumissions libere un ensemble de tâches independantes et, avant tous les travaux soient executes, aucune autre soumission est faite par l'utilisateur. Chaque utilisateur est interesse a minimiser les temps d'ecoulement de l' ensemble des tâches. Nous appelons cela le probleme d'ordonnancement de campagnes. Nous definissons un modele theorique pour l'ordonnancement de campagnes et on montre que, dans le cas general, il est NP-difficile. Pour le cas mono-utilisateur, on montre qu'un algorithme d'ordonnancement p-approximation pour le probleme classique avec de travails parallele donne aussi un p-approximation pour l'ordonnancement de campagnes, ou p est le facteur de rapprochement. Pour le cas general avec k utilisateurs , nous etablissons un critere d'equite inspire par le partage du temps. Pour un scenario plus strict, ou k est fixe et il n'y a des temps d'inactivite, nous proposons FAIRCAMP , un algorithme d'ordonnancement qui utilise date limite pour assurer l'equite entre les utilisateurs entre consecutive campagnes. Nous prouvons que FAIRCAMP augmente le temps d'ecoulement de chaque utilisateur par un facteur de k.p, comparee a une machine dediee a l' utilisateur, ou p est le facteur d'approximation de l'algorithme utilise pour ordonnancer les tâches a l'interieur de campagnes. Nous prouvons egalement que FAIRCAMP est un algorithme p-approximation pour le maximum stretch. FAIRCAMP est comparee par simulation agains FCFS. On montre que, comparativement aux FCFS , FAIRCAMP reduit l' etirement maximal pouvant aller jusqu'a 3,4 fois. La difference est significative dans les systemes utilises par de nombreux utilisateurs ( k> 5). Ensuite, pour un scenario plus general et plus realiste (avec des temps d'inactivite et une dynamique k ), nous proposons OStrich. Cet algorithme garantit que le stretch de chaque campagne soit proportionnelle a la charge de travail de la campagne et le nombre d'utilisateurs actifs dans le systeme. Le principe de l'OStrich est de creer un ordonnancement virtuel de partage juste qui determine les priorites d'execution des campagnes dans le ordonnancement reel. L'algorithme maintient une liste de campagnes pret-a-executer commandes par leurs priorites et selectionne interactivement la tâche suivante de la campagne avec la plus haute priorite. Il existe deux versions de l'OStrich, un pour les tâches consecutives et une pour les travaux paralleles, dont le fonctionement sont legerement different en ce qui concerne la facon dont l'ordonnancement virtuel de partage juste est construit. La performance theorique de l'OStrich est evaluee par comparaison avec les trois algorithmes : FCFS, Fairshare et l'implementation fairshare de le systeme Slurm.