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.

On the Throughput Optimization in Large-Scale Batch-Processing Systems

Key:KRM+20
Author:Sounak Kar, Robin Rehrmann, Arpan Mukhopadhyay, Bastian Alt, Florin Ciucu, Heinz Koeppl, Carsten Binnig, Amr Rizk
Date:November 2020
Kind:In proceedings - use for conference & workshop papers
Book title:Performance Evaluation
Pages:102-142
Language:English
Keywords:Query batching, Mean-field limit
Research Area(s):IT Architectures
Abstract:We analyze a data-processing system with n clients producing jobs which are processed in batches by m parallel servers; the system throughput critically depends on the batch size and a corresponding sub-additive speedup function. In practice, throughput optimization relies on numerical searches for the optimal batch size, a process that can take up to multiple days in existing commercial systems. In this paper, we model the system in terms of a closed queueing network; a standard Markovian analysis yields the optimal throughput in $\omega\left(n^4\right)$ time. Our main contribution is a mean-field model of the system for the regime where the system size is large. We show that the mean-field model has a unique, globally attractive stationary point which can be found in closed form and which characterizes the asymptotic throughput of the system as a function of the batch size. Using this expression we find the asymptotically optimal throughput in $O(1)$ time. Numerical settings from a large commercial system reveal that this asymptotic optimum is accurate in practical finite regimes.
URL:https://www.sciencedirect.com/science/article/pii/S0166531620300626
Full paper (pdf)

[Export this entry to BibTeX]

[back]