On the Graham's bound for cyclic scheduling

Ph. Chrétienne

LIP6 1999/013: Rapport de Recherche LIP6 / LIP6 research reports
15 pages - Mai/May 1999 - Document en anglais.

PostScript : 65 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Sur la borne de Graham pour l'ordonnancement cyclique
Titre anglais : On the Graham's bound for cyclic scheduling

Résumé : Ce papier concerne la performance des algorithmes de liste pour l'ordonnancement d'un système répétitif de N tâches génériques non préemptives sur m processeurs identiques. Le graphe réduit est supposé fortement connexe mais le nombre d'instances simultanément actives d'une même tâche générique n'est pas restreint. Quelques propriétés des ordonnacements sont d'abord montrées. On se restreint ensuite à la classe des ordonnancements réguliers pour lesquels on montre que le nombre de tâches prêtes ou actives à un instant quelconque est au moins égale à la hauteur minimale H* d'un circuit du graphe réduit. On montre ensuite que le rapport entre temps de cycle moyen d'un ordonnancement de liste régulier et le temps de cycle minimum est au plus égal à 2-(min{H^*,m}/m). Ce résultat qui est similaire à la garantie bien connue 2-1/m due à Graham pour les ordonnancements de liste dans le cas non-cyclique montre jusqu'à quel point les algorithmes de liste prennent en compte le parallélisme des systèmes cycliques de tâches.

Abstract : This paper adresses the performance of list scheduling a cyclic set of N non-preemptive dependent generic tasks on m identical processors. The reduced precedence graph is assumed to be strongly connected but the number of simultaneously active instances of a generic task is not restricted to be at most one. Some properties on arbitrary schedules are first given. Then we restrict to regular schedules for which it is shown that the number of ready or active tasks at any instant is at least the minimum height H* of a directed circuit of the reduced precedence graph. The average cycle time of any regular list schedule is then shown to be at most 2-(min{H^*,m}/m) times the absolute minimum average cycle time. This result, which is similar well-known 2-1/m Graham's bound applying for non cyclic scheduling, shows to what extent regular list schedules take the parallelism of the cyclic task system into account.

Mots-clés : Ordonnancement cyclique, Algorithme de liste, garantie
de performance

Key-words : Cyclic scheduling, List algorithm, performance ratio

Publications internes LIP6 1999 / LIP6 research reports 1999

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr