TU Darmstadt / ULB / TUbiblio

Optimizing Stochastic Scheduling in Fork-Join Queueing Models: Bounds and Applications

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:
Zugehörige Links:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen