| Invited Talk

Name of the Speaker: Prof. Ayalvadi Ganesh
Guide: Dr. Krishna Jagannathan
Online meeting link: ESB 234 (Malviya)
Date/Time: August 30th @4pm
Title: Job parallelism for latency reduction

Abstract

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.