KhudaBukhsh, W. R. ; Kar, S. ; Koeppl, H. ; Rizk, A. (2019)
Provisioning and Performance Evaluation of Parallel
Systems with Output Synchronization.
In: ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), 4 (1)
doi: 10.1145/3300142
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
Parallel server frameworks are widely deployed in modern large-data processing applications. Intuitively, splitting and parallel processing of the workload provides accelerated application response times and scaling flexibility. Examples of such frameworks include MapReduce, Hadoop, and Spark. For many applications, the dynamics of such systems are naturally captured by a Fork-Join (FJ) queuing model, where incoming jobs are split into tasks each of which is mapped to exactly one server. When all the tasks that belong to one job are executed, the job is reassembled and leaves the system. We consider this behavior at the output as a synchronization constraint. In this article, we study the performance of such parallel systems for different server properties, i.e., work-conservingness, phase-type behavior, and as suggested by recent evidence, for bursty input job arrivals. We establish a Large Deviations Principle for the steady-state job waiting times in an FJ system based on Markov-additive processes. Building on that,we present a performance analysis framework for FJ systems and provide computable bounds on the tail probabilities of the steady-state waiting times. We validate our bounds using estimates obtained through simulations. In addition, we define and analyze provisioning, a flexible division of jobs into tasks, in FJ systems. Finally, we use this framework together with real-world traces to show the benefits of an adaptive provisioning system that adjusts the service within an FJ system based on the arrival intensity.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2019 |
| Autor(en): | KhudaBukhsh, W. R. ; Kar, S. ; Koeppl, H. ; Rizk, A. |
| Art des Eintrags: | Bibliographie |
| Titel: | Provisioning and Performance Evaluation of Parallel Systems with Output Synchronization |
| Sprache: | Englisch |
| Publikationsjahr: | März 2019 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS) |
| Jahrgang/Volume einer Zeitschrift: | 4 |
| (Heft-)Nummer: | 1 |
| DOI: | 10.1145/3300142 |
| URL / URN: | https://dl.acm.org/citation.cfm?id=3300142 |
| Zugehörige Links: | |
| Kurzbeschreibung (Abstract): | Parallel server frameworks are widely deployed in modern large-data processing applications. Intuitively, splitting and parallel processing of the workload provides accelerated application response times and scaling flexibility. Examples of such frameworks include MapReduce, Hadoop, and Spark. For many applications, the dynamics of such systems are naturally captured by a Fork-Join (FJ) queuing model, where incoming jobs are split into tasks each of which is mapped to exactly one server. When all the tasks that belong to one job are executed, the job is reassembled and leaves the system. We consider this behavior at the output as a synchronization constraint. In this article, we study the performance of such parallel systems for different server properties, i.e., work-conservingness, phase-type behavior, and as suggested by recent evidence, for bursty input job arrivals. We establish a Large Deviations Principle for the steady-state job waiting times in an FJ system based on Markov-additive processes. Building on that,we present a performance analysis framework for FJ systems and provide computable bounds on the tail probabilities of the steady-state waiting times. We validate our bounds using estimates obtained through simulations. In addition, we define and analyze provisioning, a flexible division of jobs into tasks, in FJ systems. Finally, we use this framework together with real-world traces to show the benefits of an adaptive provisioning system that adjusts the service within an FJ system based on the arrival intensity. |
| Freie Schlagworte: | Mathematics of computing, Queueing theory, Theory of computation, Performance evaluation, queuing systems, Fork-Join queues, Markov 22 additive processes, Parallel systems, B4E |
| ID-Nummer: | TOMPECS0401-06 |
| 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 Datentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Nachrichtentechnik 18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Datentechnik > Multimedia Kommunikation DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > B: Adaptionsmechanismen DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > B: Adaptionsmechanismen > Teilprojekt B4: Planung DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > C: Kommunikationsmechanismen DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1053: MAKI – Multi-Mechanismen-Adaption für das künftige Internet > C: Kommunikationsmechanismen > Teilprojekt C3: Inhaltszentrische Sicht |
| Hinterlegungsdatum: | 26 Feb 2019 08:50 |
| Letzte Änderung: | 23 Sep 2021 14:30 |
| PPN: | |
| Zugehörige Links: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum