KhudaBukhsh, W. R. ; Rizk, A. ; Froemmgen, A. ; Koeppl, H. (2017)
Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications.
In: Technical Program of IEEE INFOCOM 2017
doi: 10.1109/INFOCOM.2017.8057013
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
Fork-Join (FJ) queuing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2017 |
| Autor(en): | KhudaBukhsh, W. R. ; Rizk, A. ; Froemmgen, A. ; Koeppl, H. |
| Art des Eintrags: | Bibliographie |
| Titel: | Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications |
| Sprache: | Englisch |
| Publikationsjahr: | Mai 2017 |
| Verlag: | IEEE |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Technical Program of IEEE INFOCOM 2017 |
| DOI: | 10.1109/INFOCOM.2017.8057013 |
| Zugehörige Links: | |
| Kurzbeschreibung (Abstract): | Fork-Join (FJ) queuing models capture the dynamics of system parallelization under synchronization constraints, for example, for applications such as MapReduce, multipath transmission and RAID systems. Arriving jobs are first split into tasks and mapped to servers for execution, such that a job can only leave the system when all of its tasks are executed. In this paper, we provide computable stochastic bounds for the waiting and response time distributions for heterogeneous FJ systems under general parallelization benefit. Our main contribution is a generalized mathematical framework for probabilistic server scheduling strategies that are essentially characterized by a probability distribution over the number of utilized servers, and the optimization thereof. We highlight the trade-off between the scaling benefit due to parallelization and the FJ inherent synchronization penalty. Further, we provide optimal scheduling strategies for arbitrary scaling regimes that map to different levels of parallelization benefit. One notable insight obtained from our results is that different applications with varying parallelization benefits result in different optimal strategies. Finally, we complement our analytical results by applying them to various applications showing the optimality of the proposed scheduling strategies. |
| Fachbereich(e)/-gebiet(e): | 18 Fachbereich Elektrotechnik und Informationstechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik > Bioinspirierte Kommunikationssysteme 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik |
| Hinterlegungsdatum: | 14 Dez 2016 08:09 |
| Letzte Änderung: | 20 Nov 2023 13:31 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum