As the gap between compute and I/O performance tends to grow, modern High-Performance Computing (HPC) architectures include a new resource type: an intermediate persistent fast memory layer, called burst buffers. This is just one of many kinds of renewable resources which are orthogonal to the processors themselves, such as network bandwidth or software licenses. Ignoring orthogonal resources while making scheduling decisions just for processors may lead to unplanned delays of jobs of which resource requirements cannot be immediately satisfied. We focus on a classic problem of makespan minimization for parallel-machine scheduling of independent sequential jobs with additional requirements on the amount of a single renewable orthogonal resource. We present an easily-implementable log-linear algorithm that we prove is $2\frac56$-approximation. In simulation experiments, we compare our algorithm to standard greedy list-scheduling heuristics and show that, compared to LPT, resource-based algorithms generate significantly shorter schedules.


翻译:随着计算与I/O性能之间的差距日益扩大,现代高性能计算(HPC)结构包括一种新的资源类型:中间的持久性快速内存层,称为防爆缓冲层。这只是对处理者本身具有正正反的多种可再生资源之一,例如网络带宽或软件许可。当仅为处理者做出时间安排时,忽略正反资源可能导致工作意外延误,而资源需求无法立即得到满足。我们集中关注一个典型的问题,即对独立的连续连续工作的平行机器排班进行最小化,同时对单一可再生或远方资源的数量提出额外要求。我们提出了一个易于执行的日志线算法,我们证明这种算法是2\frac56$-appronomication。在模拟实验中,我们将我们的算法与标准的贪婪列表安排外观作比较,并表明,与LPT相比,基于资源的算法的算法会产生大大短的时间表。

0
下载
关闭预览

相关内容

专知会员服务
91+阅读 · 2021年6月3日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
专知会员服务
115+阅读 · 2019年12月24日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
4+阅读 · 2017年11月1日
Arxiv
0+阅读 · 2021年10月20日
Arxiv
0+阅读 · 2021年10月19日
VIP会员
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
已删除
将门创投
4+阅读 · 2017年11月1日
Top
微信扫码咨询专知VIP会员