Benoit et al 2011a - Revision history

Scipediacontent at 16:16, 25 January 2021

2021-01-25T16:16:22Z

Scipediacontent at 13:40, 21 January 2021

2021-01-21T13:40:17Z

Scipediacontent: Scipediacontent moved page Draft Content 843678797 to Benoit et al 2011a

2020-10-14T10:57:18Z

Scipediacontent moved page Draft Content 843678797 to Benoit et al 2011a

Scipediacontent: Created page with " == Abstract == In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications..."

2020-10-14T10:57:15Z

Created page with " == Abstract == In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications..."

New page

== Abstract ==

In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécu\-tives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée.

Document type: Part of book or chapter of book

== Full document ==
<pdf>Media:Draft_Content_843678797-beopen249-8427-document.pdf</pdf>

== Original document ==

The different versions of the original document can be found in:

* [https://hal.archives-ouvertes.fr/hal-01222766 https://hal.archives-ouvertes.fr/hal-01222766]

* [https://hal.inria.fr/inria-00565151/file/RR-7532.pdf https://hal.inria.fr/inria-00565151/file/RR-7532.pdf]

← Older revision		Revision as of 16:16, 25 January 2021
Line 2:		Line 2:
	== Abstract ==		== Abstract ==

−	In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous ~~Ã©tudions~~ le ~~problÃ¨me~~ de l'optimisation du ~~dÃ©bit~~ d'applications de type pipeline dans un environnement ~~hÃ©tÃ©rogÃ¨ne~~ sujet Ã des pannes. Les applications sont ~~constituÃ©es~~ d'un ensemble de ~~tÃ¢ches consÃ©cu~~\-tives ~~typÃ©es~~ et ~~organisÃ©es~~ selon une ~~chaÃ®ne linÃ©aire~~ ou pipeline. Le but est ici de ~~spÃ©cialiser~~ les machines de la plate-forme d'~~exÃ©cution~~ afin qu'elles ne traitent qu'un seul type de ~~tÃ¢ches~~, sachant qu'au ~~dÃ©part~~ elles peuvent ~~exÃ©cuter~~ tous les types. Cela permet d'~~Ã©viter~~ des reconfigurations ~~coÃ»teuses~~ entre ~~tÃ¢ches~~ de types ~~diffÃ©rents~~ sur une ~~mÃªme~~ machine. Ainsi, les instances d'une ~~mÃªme tÃ¢che~~ peuvent ~~Ãªtre distribuÃ©es~~ sur plusieurs machines ~~spÃ©cialisÃ©es~~ pour le type de cette ~~tÃ¢che~~, ce qui permet une ~~rÃ©partition~~ de la charge du ~~systÃ¨me~~ sur un ensemble de machines ~~spÃ©cialisÃ©es~~. Lorsque la plate-forme est ~~composÃ©e~~ de machines identiques, nous prouvons qu'une solution optimale peut ~~Ãªtre trouvÃ©e~~ en temps polynomial. Par contre, le ~~problÃ¨me~~ devient NP-complet ~~dÃ¨s~~ lors que deux machines peuvent traiter une ~~mÃªme tÃ¢che Ã~~ des vitesses ~~diffÃ©rentes~~. Ce faisant, plusieurs heuristiques sont ~~prÃ©sentÃ©es~~ dans le cas le plus ~~rÃ©aliste~~ d'un ~~systÃ¨me spÃ©cialisÃ©~~. Les ~~rÃ©sultats expÃ©rimentaux~~ montrent que les meilleures heuristiques obtiennent de bons ~~rÃ©sultats~~ en terme de ~~dÃ©bit~~, meilleurs qu'avec une allocation ~~alÃ©atoire~~, et que les ~~dÃ©bits~~ atteints sont ~~trÃ¨s~~ proches des ~~dÃ©bits~~ optimaux dans les cas particuliers pour lesquels une solution optimale peut ~~Ãªtre calculÃ©e~~.	+	In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécu\-tives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée.

@@ Line 2: / Line 2: @@
 == Abstract ==
-In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous étudions le problème de l'optimisation du débit d'applications de type pipeline dans un environnement hétérogène sujet à des pannes. Les applications sont constituées d'un ensemble de tâches consécu\-tives typées et organisées selon une chaîne linéaire ou pipeline. Le but est ici de spécialiser les machines de la plate-forme d'exécution afin qu'elles ne traitent qu'un seul type de tâches, sachant qu'au départ elles peuvent exécuter tous les types. Cela permet d'éviter des reconfigurations coûteuses entre tâches de types différents sur une même machine. Ainsi, les instances d'une même tâche peuvent être distribuées sur plusieurs machines spécialisées pour le type de cette tâche, ce qui permet une répartition de la charge du système sur un ensemble de machines spécialisées. Lorsque la plate-forme est composée de machines identiques, nous prouvons qu'une solution optimale peut être trouvée en temps polynomial. Par contre, le problème devient NP-complet dès lors que deux machines peuvent traiter une même tâche à des vitesses différentes. Ce faisant, plusieurs heuristiques sont présentées dans le cas le plus réaliste d'un système spécialisé. Les résultats expérimentaux montrent que les meilleures heuristiques obtiennent de bons résultats en terme de débit, meilleurs qu'avec une allocation aléatoire, et que les débits atteints sont très proches des débits optimaux dans les cas particuliers pour lesquels une solution optimale peut être calculée.
+In this report, we study the problem of optimizing the throughput of applications for heterogeneous platforms subject to failures. The considered applications are composed of a sequence of consecutive tasks linked as a linear graph (pipeline), with a type associated to each task. The challenge is to specialize the machines of a target platform to process only one task type, given that every machine is able to process all the types before being specialized, to avoid costly context or setup changes. Each instance can thus be performed by any machine specialized in its type and the workload of the system can be shared among a set of specialized machines. For identical machines, we prove that an optimal solution can be computed in polynomial time. However, the problem becomes NP-hard when two machines can compute the same task type at different speeds. Several polynomial time heuristics are presented for the most realistic specialized settings. Experimental results show that the best heuristics obtain a good throughput, much better than the throughput obtained with a random mapping, and close to the optimal throughput in the particular cases on which the optimal throughput can be computed.; Dans ce rapport, nous Ã©tudions le problÃ¨me de l'optimisation du dÃ©bit d'applications de type pipeline dans un environnement hÃ©tÃ©rogÃ¨ne sujet Ã  des pannes. Les applications sont constituÃ©es d'un ensemble de tÃ¢ches consÃ©cu\-tives typÃ©es et organisÃ©es selon une chaÃ®ne linÃ©aire ou pipeline. Le but est ici de spÃ©cialiser les machines de la plate-forme d'exÃ©cution afin qu'elles ne traitent qu'un seul type de tÃ¢ches, sachant qu'au dÃ©part elles peuvent exÃ©cuter tous les types. Cela permet d'Ã©viter des reconfigurations coÃ»teuses entre tÃ¢ches de types diffÃ©rents sur une mÃªme machine. Ainsi, les instances d'une mÃªme tÃ¢che peuvent Ãªtre distribuÃ©es sur plusieurs machines spÃ©cialisÃ©es pour le type de cette tÃ¢che, ce qui permet une rÃ©partition de la charge du systÃ¨me sur un ensemble de machines spÃ©cialisÃ©es. Lorsque la plate-forme est composÃ©e de machines identiques, nous prouvons qu'une solution optimale peut Ãªtre trouvÃ©e en temps polynomial. Par contre, le problÃ¨me devient NP-complet dÃ¨s lors que deux machines peuvent traiter une mÃªme tÃ¢che Ã  des vitesses diffÃ©rentes. Ce faisant, plusieurs heuristiques sont prÃ©sentÃ©es dans le cas le plus rÃ©aliste d'un systÃ¨me spÃ©cialisÃ©. Les rÃ©sultats expÃ©rimentaux montrent que les meilleures heuristiques obtiennent de bons rÃ©sultats en terme de dÃ©bit, meilleurs qu'avec une allocation alÃ©atoire, et que les dÃ©bits atteints sont trÃ¨s proches des dÃ©bits optimaux dans les cas particuliers pour lesquels une solution optimale peut Ãªtre calculÃ©e.
-−
-Document type: Part of book or chapter of book
-−
-== Full document ==
-<pdf>Media:Draft_Content_843678797-beopen249-8427-document.pdf</pdf>
@@ Line 17: / Line 12: @@
 * [https://hal.inria.fr/inria-00565151/file/RR-7532.pdf https://hal.inria.fr/inria-00565151/file/RR-7532.pdf]

← Older revision	Revision as of 10:57, 14 October 2020
(No difference)