Institut für Kommunikationstechnik Institut Aktuelles
New Paper in IEEE Transactions on Parallel and Distributed Systems

New Paper in IEEE Transactions on Parallel and Distributed Systems

Non-Asymptotic Delay Bounds for Multi-Server Systems with Synchronization Constraints Markus Fidler, Brenton Walker, Yuming Jiang

Parallel computing has become a standard tool with architectures such as Google MapReduce, Hadoop, and Spark being broadly used in applications such as data processing and machine learning.  Common to these systems are a fork operation, where jobs are first divided into tasks that are processed in parallel, and a join operation where completed tasks wait for the other tasks of the job before leaving the system.  The synchronization constraint of the join operation makes the analysis of fork-join systems challenging, and few explicit results are known.  In this work, we formulate a max-plus server model for parallel systems which allows us to derive performance bounds for a variety of systems in the GI|GI and G|G cases. We contribute end-to-end delay bounds for multi-stage fork-join networks. We perform a detailed comparison of different multi-server configurations, including an analysis of single-queue fork-join systems that achieve a fundamental performance gain. We compare these results to both simulation and a live Spark system.

arxiv.org/abs/1610.06309

ieeexplore.ieee.org/document/8242677/