UET-UCT Schedules on Arbitrary Networks

C. PICOULEAU

IBP-Litp 1994/09: Rapport de Recherche Litp / Litp research reports
17 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: UET-UCT Schedules on Arbitrary Networks

Résumé : De nombreux résultats de complexité pour les problèmes d'ordonnancement avec délais de communication ont récemment été prouvés. Pour ces problèmes, il est supposé que le réseau de processeurs est entièrement connecté. Dans cet article, le réseau de processeurs n'est pas nécessairement entièrement connecté, et les délais de communication dépendent de la distance entre les processeurs. Nous définissons 'UET-UCT-topo' une nouvelle classe de problèmes d'ordonnancement : les durées d'exécution sont unitaires, les délais de communication sont égaux à la longueur de la plus courte chaîne reliant les processeurs affectés aux tâches et 'topo' est la topologie du réseau. Nous prouvons que le problème 'UET-UCT-chain' est NP-complet dans le cas où le graphe de pécédence est une arborescence ou une anti-arborescence et que le réseau consiste en une chaîne de longueur illimitée. Ensuite, nous montrons que pour toute topologie fixée avec un nombre arbitraire de processeurs, l'ordonnancement d'un graphe arbitraire est un problème NP-complet. Finalement, nous prouvons que l'ordonnancement d'une arborescence sur un réseau en étoile est aussi un problème NP-complet.

Abstract : Numerous complexity results on scheduling problems with communication delays have recently been proved. In these problems, it is assumed that the processor network is entirely connected. In this paper, the processor network is connected but not assumed to be complete, and the communication delays depend on the distance between the processors. We define 'UET-UCT-topo' as a new classe of scheduling problems : tasks have unit execution time, communication delays are the length of the shortest chain between the processors assigned to the tasks, and 'topo' is a network topology. We prove that 'UET-UCT-chain' is NP-complete even when the task graph is an intree or an outtre and the network is an infinite chain. Afterwards, we show that for any fixed network with an arbitrary number of processors, to schedule an arbitrary 'UET-UCT' task graph is NP-complete. Finaly, we prove that to schedule an intree on a star network is NP-complete.

Publications internes Litp 1994 / Litp research reports 1994