A Model of Job Parallelism for Latency Reduction in Large-Scale Systems

MaRDI QIDQ6393864zbMATH OpenFDO

Authors Ayalvadi J. Ganesh, Arpan Mukhopadhyay

Publication date 16 March 2022

Mathematics Subject Classification ID

Applications of continuous-time Markov processes on discrete state spaces (60J28) Queueing theory (aspects of probability theory) (60K25)

Abstract: Processing computation-intensive jobs at multiple processing cores in parallel is essential in many real-world applications. In this paper, we consider an idealised model for job parallelism in which a job can be served simultaneously by $d$ distinct servers. The job is considered complete when the total amount of work done on it by the $d$ servers equals its size. We study the effect of parallelism on the average delay of jobs. Specifically, we analyze a system consisting of $n$ parallel processor sharing servers in which jobs arrive according to a Poisson process of rate $nlambda$ ($lambda<1$) and each job brings an exponentially distributed amount of work with unit mean. Upon arrival, a job selects $d$ servers uniformly at random and joins all the chosen servers simultaneously. We show by a mean-field analysis that, for fixed $dgeq2$ and large $n$, the average occupancy of servers is $O(log(1/(1-lambda)))$ as $lambdao1$ in comparison to $O(1/(1-lambda))$ average occupancy for $d=1$. Thus, we obtain an exponential reduction in the response time of jobs through parallelism. We make significant progress towards rigorously justifying the mean-field analysis.

This page was built for publication: A Model of Job Parallelism for Latency Reduction in Large-Scale Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6393864)