List Schedules for Cyclic Scheduling

P. Chretienne

IBP-Litp 1996/34: Rapport de Recherche Litp / Litp research reports
22 pages - Novembre/November 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: List Schedules for Cyclic Scheduling

Résumé : Cet article considère la définition et les propriétés des ordonnancements de liste dans le contexte de problèmes cycliques où un ensemble répétitif de n tâches génériques non préemptives, non réentrantes et liées par un graphe de précédence réduit fortement connexe doivent être exécutées sur m processeurs identiques. On montre d'abord que tout ordonnancement de liste fournit la garantie 2-1/m par rapport au temps de cycle minimal absolu. On montre ensuite que les ordonnancements de liste K-périodiques sont issus de fonctions de priorité particulières appelées "ordres linéaires K-périodiques". Etant donné un algorithme de liste fournissant la garantie r pour un problème non cyclique, il est montré que cette garantie se transmet au problème cyclique associé si la suite Ln des listes associées aux n premières itérations est quasi K-périodique. En prouvant que la liste de Coffman-Graham possède cette propriété, on obtient, pour le problème à durées unitaires, la garantie 2-2/m pour chacun des K ordonnancements issus des K ordres linéaires de la suite des listes de Coffman-Graham.

Abstract : This paper adresses the definition and properties of list scheduling in the context of scheduling a cyclic set of n non-preemptive and non-reentrant dependent tasks on m identical processors when the reduced precedence graph is assumed to be strongly connected. It is first show that the average cycle time of an arbitrary list schedule is at most 2-1/m times the absolute minimum average cycle time. K-periodic list schedules are then shown to be the list schedules associated with special priority mappings called K-periodic linear orders. Moreover, given a list that offers the performance ratio r in the non-cyclic case and whose structure is quasi K-periodic in the cyclic case, it is shown that each of its corresponding K-periodic linear orders provides a list schedule with the same guarantee. Since the well-known Coffman-Graham's list is shown to be quasi K-periodic, its performance may be tranferred to UET cyclic problems.

Publications internes Litp 1996 / Litp research reports 1996