一个新的基于通信竞争的任务调度算法

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (33): 9-11.

一个新的基于通信竞争的任务调度算法

杨斌¹,张建军²

1.海军工程大学管理工程系,武汉 430033
2.海军工程大学理学院,武汉 430033

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-21 发布日期:2007-11-21
通讯作者: 杨斌

New scheduling algorithm with communication contention

YANG Bin¹,ZHANG Jian-jun²

1.Department of Management,Naval University of Engineering,Wuhan 430033,China
2.College of Science,Naval University of Engineering,Wuhan 430033,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-11-21 Published:2007-11-21
Contact: YANG Bin

摘要/Abstract

摘要： 任务调度是并行处理的一个非常关键的方面。目前的调度算法大多假定处理器完全互连、可以并行接收数据,而没有考虑实际应用中通信链路的竞争及延迟,进而导致调度算法在具体应用中效率较低。论文研究异构计算环境下具有依赖关系任务的边调度问题,结合传统任务调度问题中的有效策略,提出一种新的调度算法,该算法通过串行化通信边使通信竞争集成化。实验结果表明,与各种经典调度方案相比,该算法显著地改善了精确性和效率。

关键词: 通信竞争, 任务调度, 串行化

Abstract: Task scheduling is an essential aspect of parallel processing.However,many previous works assume fully connected processors and concurrent communication,while ignoring the contention and delay on data links in real applications,which leads to low efficiency.This paper focuses on the issue of edge scheduling for dependent tasks in heterogeneous environment.Combining with classically efficient heuristics,this paper proposes a new scheduling algorithm that integrates communication contention by serializing the communications edges,which produces significantly more accurate and efficient schedules than classic schedule schemes in experiments.

Key words: communication contention, task scheduling, serializing

杨斌¹,张建军². 一个新的基于通信竞争的任务调度算法[J]. 计算机工程与应用, 2007, 43(33): 9-11.

YANG Bin¹,ZHANG Jian-jun². New scheduling algorithm with communication contention[J]. Computer Engineering and Applications, 2007, 43(33): 9-11.

[1]	张驰，王宇新，冯振，郭禾. 双层虚拟化云架构下任务调度能耗优化算法[J]. 计算机工程与应用, 2021, 57(3): 103-111.
[2]	田倬璟，黄震春，张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11.
[3]	向敏，戴柯宇，周恩，刘榆，雷儒杰. 面向物联网终端的任务相关性调度策略[J]. 计算机工程与应用, 2020, 56(23): 95-102.
[4]	于巧玉，吴耀华，王艳艳. 跨层穿梭车双提升机系统料箱拣选任务调度[J]. 计算机工程与应用, 2020, 56(20): 270-278.
[5]	吴波，许道强，邹云峰，王甜甜，李鑫. 阶段感知的跨域数据分析作业保障机制[J]. 计算机工程与应用, 2019, 55(23): 78-85.
[6]	朱永超，周川，郭健，吴益飞，崔玉伟. 异构分布式系统中一种新型主副版本调度算法[J]. 计算机工程与应用, 2019, 55(21): 93-98.
[7]	汤琳煜，蒋加伏，谷科. 基于雾计算的计算资源分配方案[J]. 计算机工程与应用, 2019, 55(19): 96-104.
[8]	贾丽云，张向利，张红梅. 分布式系统下的启发式任务调度算法[J]. 计算机工程与应用, 2017, 53(12): 63-69.
[9]	王向华1，陈特放1，张必明2，颜剑1. 基于时间序列和任务调度的Web数据聚类算法[J]. 计算机工程与应用, 2016, 52(9): 159-163.
[10]	林若男，李强. 云计算环境下基于模板的任务调度策略与算法[J]. 计算机工程与应用, 2016, 52(19): 48-52.
[11]	李岩，崔浩鑫，杜永斌. μC/OS-II二级调度算法的硬件实现[J]. 计算机工程与应用, 2016, 52(12): 1-4.
[12]	王波，张晓磊. 基于粒子群遗传算法的云计算任务调度研究[J]. 计算机工程与应用, 2015, 51(6): 84-88.
[13]	孙凌宇1，冷明1，2，朱平1，李金忠1. 基于赋权有向超图的云计算依赖任务调度研究[J]. 计算机工程与应用, 2015, 51(24): 34-39.
[14]	王振超. 融合DEA和田口方法的云计算多任务调度方案[J]. 计算机工程与应用, 2015, 51(2): 140-145.
[15]	李静梅，张大虎，吴艳霞. 基于异构CMP的改进蚁群优化任务调度策略[J]. 计算机工程与应用, 2015, 51(18): 47-51.