Multiserver jobs, which are jobs that occupy multiple servers simultaneously during service, are prevalent in today's computing clusters. But little is known about the delay performance of systems with multiserver jobs. We consider queueing models for multiserver jobs in scaling regimes where the system load becomes heavy and meanwhile the total number of servers in the system and the number of servers that a job needs become large. Prior work has derived upper bounds on the queueing probability in this scaling regime. However, without proper lower bounds, the existing results cannot be used to differentiate between policies. In this paper, we study the delay performance by establishing sharp bounds on the mean waiting time of multiserver jobs, where the waiting time of a job is the time spent in queueing rather than in service. We first characterize the exact order of the mean waiting time under the First-Come-First-Serve (FCFS) policy. Then we prove a lower bound on the mean waiting time of all policies, which has an order gap with the mean waiting time under FCFS. Finally, we show that the lower bound is achievable under a priority policy that we call Smallest-Need-First (SNF).
翻译:多服务器作业是占据多台服务器进行服务的作业,在当今的计算集群中很常见。但是对于具有多服务器作业的系统的延迟性能很少有研究。我们考虑多服务器作业的排队模型,其中系统负载变得沉重,与此同时系统中的总服务器数量和作业所需服务器数量变得更大。以这种缩放规模为基础,以前的研究已经推导出了排队概率的上限。然而,缺少适当的下限,现有结果无法用于区分策略。在本文中,我们通过建立多服务器作业的平均等待时间的尖锐界限来研究延迟性能,其中作业的等待时间是指在排队而不是在服务期间花费的时间。我们首先确定了先到先服务(FCFS)策略下平均等待时间的精确顺序。然后,我们证明了所有策略的平均等待时间的下限,其与FCFS下的平均等待时间有一定的差距。最后,我们展示了在我们称之为最小需求策略(SNF)下,可以实现下限。