清晨好,您是今天最早来到科研通的研友!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您科研之路漫漫前行!

Performance-effective and low-complexity task scheduling for heterogeneous computing

计算机科学 关键路径法 调度(生产过程) 分布式计算 动态优先级调度 公平份额计划 对称多处理机系统 作业车间调度 单调速率调度 并行计算 算法 服务质量 数学优化 计算机网络 数学 布线(电子设计自动化) 工程类 系统工程
作者
Haluk Rahmi Topcuoglu,Salim Hariri,Min‐You Wu
出处
期刊:IEEE Transactions on Parallel and Distributed Systems [Institute of Electrical and Electronics Engineers]
卷期号:13 (3): 260-274 被引量:3359
标识
DOI:10.1109/71.993206
摘要

Efficient application scheduling is critical for achieving high performance in heterogeneous computing environments. The application scheduling problem has been shown to be NP-complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied and various algorithms have been proposed in the literature which are mainly for systems with homogeneous processors. Although there are a few algorithms in the literature for heterogeneous processors, they usually require significantly high scheduling costs and they may not deliver good quality schedules with lower costs. In this paper, we present two novel scheduling algorithms for a bounded number of heterogeneous processors with an objective to simultaneously meet high performance and fast scheduling time, which are called the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm. The HEFT algorithm selects the task with the highest upward rank value at each step and assigns the selected task to the processor, which minimizes its earliest finish time with an insertion-based approach. On the other hand, the CPOP algorithm uses the summation of upward and downward rank values for prioritizing tasks. Another difference is in the processor selection phase, which schedules the critical tasks onto the processor that minimizes the total execution time of the critical tasks. In order to provide a robust and unbiased comparison with the related work, a parametric graph generator was designed to generate weighted directed acyclic graphs with various characteristics. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithms significantly surpass previous approaches in terms of both quality and cost of schedules, which are mainly presented with schedule length ratio, speedup, frequency of best results, and average scheduling time metrics.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
10秒前
大医仁心完成签到 ,获得积分0
11秒前
潇洒小海豚完成签到,获得积分10
13秒前
22秒前
39秒前
43秒前
淡定的夜云完成签到 ,获得积分10
47秒前
50秒前
55秒前
圈圈圆了发布了新的文献求助100
57秒前
58秒前
1分钟前
顺心的一德完成签到,获得积分10
1分钟前
圈圈圆了完成签到,获得积分10
1分钟前
1分钟前
yc关闭了yc的文献求助
1分钟前
1分钟前
amiee发布了新的文献求助10
1分钟前
高高从霜完成签到 ,获得积分10
1分钟前
1分钟前
开朗的尔蝶的应助被amiee采纳,获得10
2分钟前
2分钟前
冷酷冬卉完成签到,获得积分10
2分钟前
2分钟前
whc发布了新的文献求助10
2分钟前
2分钟前
2分钟前
小星河完成签到 ,获得积分10
2分钟前
itsnotover发布了新的文献求助10
2分钟前
3分钟前
itsnotover完成签到,获得积分10
3分钟前
3分钟前
3分钟前
3分钟前
007关注了科研通微信公众号
3分钟前
007关注了科研通微信公众号
3分钟前
搞怪的白云完成签到 ,获得积分0
3分钟前
3分钟前
3分钟前
充电宝的应助被007采纳,获得30
3分钟前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 2000
Sex, Aging, and Death in a Medieval Medical Compendium: Trinity College Cambridge MS R.14.52, Its Texts, Language, and Scribe 500
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
基于界面调控的高效湿气发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8190159
求助须知:如何正确求助?哪些是违规求助? 9577264
关于积分的说明 21852314
捐赠科研通 7788621
什么是DOI,文献DOI怎么找? 3436279
关于科研通互助平台的介绍 2560058
邀请新用户注册赠送积分活动 2482880