A Polynomial-Time Algorithm for Allocating Independent Tasks on Heterogeneous Fork-Graphs

Olivier Beaumont 1 Arnaud Legrand 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we consider the problem of allocating a large number ofindependent, equal-sized tasks to a heterogeneous processor farm. Themaster processor P 0 can process a task within w 0 time-units; it communicatesa task in d i time-units to the i-th slave P i , 1 i p, which requiresw i time-units to process it. We assume communication-computationoverlap capabilities for each slave (and for the master), but the communicationmedium is exclusive: the master can only communicate with asingle slave at each time-step.
Complete list of metadatas

https://hal.inria.fr/hal-00789456
Contributor : Arnaud Legrand <>
Submitted on : Monday, February 18, 2013 - 11:51:48 AM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Identifiers

  • HAL Id : hal-00789456, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. A Polynomial-Time Algorithm for Allocating Independent Tasks on Heterogeneous Fork-Graphs. ISCIS XVII, Seventeenth International Symposium On Computer and Information Sciences, 2002, Unknown, pp.115―119. ⟨hal-00789456⟩

Share

Metrics

Record views

136