A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2002

A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs

Résumé

In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous processor farm. The master processor and the p slaves have different computation and communication capabilities. We assume communication-computation overlap for each slave (and for the master), but the communication medium is exclusive: the master can only communicate with a single slave at each time-step. We give a polynomial-time algorithm to solve the following scheduling problem: given a time-bound T, what is the maximal number of tasks that can be processed by the master and the p slaves within T time-units?.
Nous nous intéressons à l'ordonnancement des tâches indépendantes sur une plateforme maitre-esclave hétérogène, modélisée par un graphe fork. Le maitre et les p esclaves ont des vitesses de calcul différentes D e même , les liens de communication entre le maître et chaque esclave ont des capacités différentes. Le modèle autorise le recouvrement calcul-communication sur chaque processeur, mais on suppose que toutes les communications s'effectuent en mode 1-port : à tout instant, le maître ne peut envoyer qu'un seul message ( à un esclave donné). Nous présentons un algorithme polynomial pour résoudre le problème d'ordonnancement correspondant : étant donnée une borne temporelle T, maximiser le nombre total de tâches qui peuvent être effectuées par le maître et les p esclaves en temps T.
Fichier principal
Vignette du fichier
RR2002-07.pdf (254.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101974 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101974 , version 1

Citer

Olivier Beaumont, Arnaud Legrand, Yves Robert. A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs. [Research Report] LIP RR-2002-07, Laboratoire de l'informatique du parallélisme. 2002, 2+10p. ⟨hal-02101974⟩
33 Consultations
62 Téléchargements

Partager

Gmail Facebook X LinkedIn More