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

International audienceIn 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