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)下,可以实现下限。

0
下载
关闭预览

相关内容

服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。
服务器的构成包括处理器、硬盘、内存、系统总线等,和通用的计算机架构类似,但是由于需要提供高可靠的服务,因此在处理能力、稳定性、可靠性、安全性、可扩展性、可管理性等方面要求较高。
【硬核书】Linux 基础第二版,500页pdf
专知会员服务
88+阅读 · 2022年9月12日
专知会员服务
23+阅读 · 2021年9月5日
专知会员服务
51+阅读 · 2020年12月14日
还在修改博士论文?这份《博士论文写作技巧》为你指南
深度强化学习策略梯度教程,53页ppt
专知会员服务
180+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
104+阅读 · 2019年10月9日
重磅开讲:图灵奖得主—— Joseph Sifakis
THU数据派
0+阅读 · 2022年6月13日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
10+阅读 · 2019年3月6日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Arxiv
0+阅读 · 2023年5月26日
VIP会员
相关VIP内容
【硬核书】Linux 基础第二版,500页pdf
专知会员服务
88+阅读 · 2022年9月12日
专知会员服务
23+阅读 · 2021年9月5日
专知会员服务
51+阅读 · 2020年12月14日
还在修改博士论文?这份《博士论文写作技巧》为你指南
深度强化学习策略梯度教程,53页ppt
专知会员服务
180+阅读 · 2020年2月1日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
104+阅读 · 2019年10月9日
相关资讯
重磅开讲:图灵奖得主—— Joseph Sifakis
THU数据派
0+阅读 · 2022年6月13日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
已删除
将门创投
10+阅读 · 2019年3月6日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Top
微信扫码咨询专知VIP会员