Throughput optimization for micro-factories subject to failures

Anne Benoit (1, 2) , Alexandru Dobrila (1, 3) , Jean-Marc Nicod (3) , Laurent Philippe (3)

1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)

In this paper, we study the problem of optimizing the throughput for micro-factories subject to failures. The challenge consists in mapping several tasks onto a set of machines. The originality of our approach is the failure model for such applications in which tasks are subject to failures rather than machines. If there is exactly one task per machine in the mapping, then we prove that the optimal solution can be computed in polynomial time. However, the problem becomes NP-hard if several tasks can be assigned to the same machine. Several polynomial time heuristics are presented for the most realistic {\em specialized} setting, in which tasks of a same type can be mapped onto the same machine. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping. Moreover, we obtain a throughput close to the optimal solution in the particular cases on which the optimal throughput can be computed.

Domaines: Réseaux et télécommunications [cs.NI]; Calcul parallèle, distribué et partagé [cs.DC]; Informatique ubiquitaire

Anne Benoit, Alexandru Dobrila, Jean-Marc Nicod, Laurent Philippe. Throughput optimization for micro-factories subject to failures. ISPDC'2009, 8th Int. Symposium on Parallel and Distributed Computing, 2009, Portugal. pp.11--18. ⟨hal-00563300⟩