Ordonnancement non-clair voyant avec dépendances : analyse de LAPS_β◦ EQUI

International audienceEn 1999, Edmonds introduit un modèle très général de tâches qui traversent différentes phases ayant différentes quantités de travail et capacités à être parallélisées. La force du modèle d'Edmonds est qu'il démontra que même si l'ordonnanceur ne connaît strictement rien des caractéristiques des tâches qu'il est en train d'ordonnancer et est seulement informé de leur arrivée à leur arrivée et de leur complétion à leur complétion, EQUI, qui partage de manière égale les processeurs entre les tâches actives, réussit à être compétitif avec l'ordonnancement optimal hors-line clairvoyant, pour peu qu'EQUI dispose d'un peu plus de deux fois plus de ressources que l'optimum. Ceci signifie que l'ordonnanceur EQUI supporte sans diverger toute charge inférieure à 50%. Nous [SODA'08] avons par la suite étendu l'analyse d'Edmonds au cas où les tâches sont composées d'un DAG de processus traversant des phases arbitraires et démontré que l'algorithme non-clairvoyant EQUIoEQUI supporte dans ce cas également toute charge inférieure à 50%. En 2009, Edmonds et Pruhs ont proposé une nouvelle famille d'algorithmes LAPS qui partagent de manière égale les processeurs entre les tâches de la proportion b des tâches actives arrivées les plus récemment, et ont démontré que ces algorithmes sont (1+b+e)-speed 4(1+b+e)/(b*e)-compétitif, c.-à-d. supportent une charge arbitrairement proche de 1 (< 1-b) sans diverger. À l'aide des mêmes outils que ceux que nous avions développés pour la preuve de la compétitivité de EQUIoEQUI en présence de dépendances, nous montrons ici que l'algorithme LAPSoEQUI, composition naturelle de LAPS et d'EQUI, est (1+b+e)-speed (k+1)(1+b+e)/(b*e)-compétitif, où k est la taille maximale d'une anti-chaîne d'une tâche