Directed Acyclic Graph (DAG) scheduling in a heterogeneous environment is aimed at assigning the on-the-fly jobs to a cluster of heterogeneous computing executors in order to minimize the makespan while meeting all requirements of scheduling. The problem gets more attention than ever since the rapid development of heterogeneous cloud computing. A little reduction of makespan of DAG scheduling could both bring huge profits to the service providers and increase the level of service of users. Although DAG scheduling plays an important role in cloud computing industries, existing solutions still have huge room for improvement, especially in making use of topological dependencies between jobs. In this paper, we propose a task-duplication based learning algorithm, called \textit{Lachesis}, for the distributed DAG scheduling problem. In our approach, it first perceives the topological dependencies between jobs using a specially designed graph convolutional network (GCN) to select the most likely task to be executed. Then the task is assigned to a specific executor with the consideration of duplicating all its precedent tasks according to a sophisticated heuristic method. We have conducted extensive experiments over standard workload data to evaluate our solution. The experimental results suggest that the proposed algorithm can achieve at most 26.7\% reduction of makespan and 35.2\% improvement of speedup ratio over seven strong baseline algorithms, including state-of-the-art heuristics methods and a variety of deep reinforcement learning based algorithms.


翻译:定向环形图(DAG) 在不同环境中的定向环形图(DAG) 列表旨在将现场工作分配给一组混合计算执行者,以便在满足所有排期要求的同时最大限度地减少差幅,从而在满足所有排期要求的同时最大限度地减少差幅。自多种云计算迅速发展以来,问题比以往更加受到关注。DAG的排程如果稍微缩小,既能给服务供应商带来巨大的利润,又能提高用户的服务水平。虽然DAG的排程在云计算行业中发挥着重要作用,但现有的解决方案仍有很大的改进余地,特别是在使用工作之间的地形依赖性方面。在本文中,我们为分布式DAG的排程安排问题提出了一个基于任务重复的学习算法,称为\ textit{Lachesis}。在我们的方法中,它首先认识到使用专门设计的图形革命网络(GCN) 来选择最可能完成的任务之间的工作在结构上的依赖性。随后,任务被指派给一个特定的执行者,考虑按照复杂的超度方法重复其所有先例性任务。我们进行了广泛的基于35级的学习比重比率的计算,我们进行了广泛的实验,在标准级算算算算法上了最大幅度的工作量比重的工作量递减速度数据,包括最大幅度递减压后,从而得出了最大幅度递减后,他进行最重的进度进度的进度的进度的进度分析结果。

0
下载
关闭预览

相关内容

【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
76+阅读 · 2021年1月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
元学习(meta learning) 最新进展综述论文
专知会员服务
278+阅读 · 2020年5月8日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
Arxiv
38+阅读 · 2020年3月10日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Heterogeneous Deep Graph Infomax
Arxiv
12+阅读 · 2019年11月19日
Learning to Weight for Text Classification
Arxiv
8+阅读 · 2019年3月28日
Using Scene Graph Context to Improve Image Generation
Arxiv
5+阅读 · 2018年4月30日
VIP会员
相关VIP内容
【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
76+阅读 · 2021年1月30日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
元学习(meta learning) 最新进展综述论文
专知会员服务
278+阅读 · 2020年5月8日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
CCF推荐 | 国际会议信息8条
Call4Papers
9+阅读 · 2019年5月23日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
相关论文
Top
微信扫码咨询专知VIP会员