Ayalvadi Ganesh

University of Bristol

Job parallelism for latency reduction

Probability Seminar

29th April 2022, 4:15 pm – 5:00 pm
Fry Building, 2.04

We consider a system with a large number of identical servers into which jobs arrive as a Poisson process. Job sizes are independent and exponentially distributed. Upon arrival, a job is assigned to d servers chosen uniformly at random. Servers split their effort equally amongst all jobs they are currently serving (processor sharing). When the total work done on a job by all servers to which it has been assigned equals its job size, the job departs the system.

The system can be analysed exactly only if d=1, i.e., there is no parallelism. We present a mean-field analysis if d is 2 or more, analogous to the cavity method in statistical physics. This involves analysing an index queue assuming all other queues are in their (unknown) equilibrium distribution, and yields a fixed-point equation for this unknown distribution, which can be solved numerically.

We provide evidence from simulations that the mean-field analysis is correct. We also present some very preliminary steps towards rigorously justifying the mean-field analysis. Finally, we describe a connection between the above model and a random graph/ hypergraph process.

Joint work with Arpan Mukhopadhyay (Warwick).

Organisers: Benjamin Lees, Jessica Jay

Comments are closed.