On the Power of Little Job Parallelism for Latency Reduction
# 88
Abstract
Modern datacentres often handle computing jobs that are highly parallelisable. Such jobscan be processed at multiple servers in parallel. Although parallel processingreduces the latency of jobs, it comes at the cost of increased communicationoverhead between the servers. Therefore, a natural question in this context is whetherit is possible to achieve significant latency reduction with only a small degreeof parallelism, i.e., a small number of parallel servers per job. Motivatedby this key question, we consider a model in which each job can be servedsimultaneously by multiple distinct processorsharing (PS) servers. The job is considered complete when the total amount ofwork done on it by all the servers equals its size. We analyse the system assumingthat the jobs arrive according to a Poisson process with a rate proportional tothe total number of servers and that each job brings exponentially distributedamount of work with unit mean. We show by a mean-field analysis that in thelarge system limit an exponential reduction in the mean response time isobtained in the heavy traffic limit even with a small degree of parallelism. Wemake significant progress towards rigorously justifying the mean-fieldanalysis.
Arpan Mukhopadhyay, University of Warwick
Dr.Arpan Mukhopadhyay received the B.E. degree in electronics andtelecommunication engineering from Jadavpur University, India, in 2009, theM.E. degree in telecommunications from the Indian Institute of Science, India,in 2011, and the Ph.D. degree in electrical and computer engineering from theUniversity of Waterloo, Canada, in 2016. He is currently an Assistant Professorat the Department of Computer Science, University of Warwick, U.K. His researchinterests include applied probability, stochastic processes, algorithm design,and optimization with applications to computer and communication networks. Hehas received Best Paper Awards at IFIP Performance 2015 and the InternationalTeletraffic Congress (ITC) 2015. He was also awarded the Rising Scholar Awardat the International Teletraffic Congress 2018 for his contributions to meanfield analysis of large heterogeneous networks.