The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Provisioning and performance evaluation of parallel systems with output synchronization

Author:Wasiur R. Khudabukhsh, Sounak Kar, Amr Rizk, Heinz Koeppl
Date:March 2019
Kind:Article - use for journal articles only
Journal:ACM Transactions on Modeling and Performance Evaluation of Computing Systems
Keywords:Performance evaluation, Queuing systems, Fork-Join queues, Markov additive processes, Parallel systems
Research Area(s):Communication Services
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 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 paper, 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 LDP 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.
Full paper (pdf)

[Export this entry to BibTeX]