New scheduling algorithm with communication contention

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (33): 9-11.

• 博士论坛 • Previous Articles Next Articles

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

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

杨斌¹,张建军²

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

通讯作者: 杨斌

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

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

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

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

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

[1]	ZHANG Chi, WANG Yuxin, FENG Zhen, GUO He. Energy-Efficient Task Scheduling Algorithm in Two-Layer Virtualized Cloud Architecture [J]. Computer Engineering and Applications, 2021, 57(3): 103-111.
[2]	TIAN Zhuojing, HUANG Zhenchun, ZHANG Yinong. Review of Task Scheduling Methods in Cloud Computing Environment [J]. Computer Engineering and Applications, 2021, 57(2): 1-11.
[3]	XIANG Min, DAI Keyu, ZHOU En, LIU Yu, LEI Rujie. Scheduling Strategy for IoT Terminals Considering Task Relevance [J]. Computer Engineering and Applications, 2020, 56(23): 95-102.
[4]	YU Qiaoyu，WU Yaohua，WANG Yanyan. Tasks Scheduling Optimization of Tier-to-Tier Shuttle-Based Storage and Retrieval System with Double Lifts [J]. Computer Engineering and Applications, 2020, 56(20): 270-278.
[5]	WU Bo, XU Daoqiang, ZOU Yunfeng, WANG Tiantian, LI Xin. Stage-Aware Geo-Distributed Data Analytics Job Insurance Mechanism [J]. Computer Engineering and Applications, 2019, 55(23): 78-85.
[6]	ZHU Yongchao, ZHOU Chuan, GUO Jian, WU Yifei, CUI Yuwei. New Primary/Backup Scheduling Algorithm in Heterogeneous Distributed Systems [J]. Computer Engineering and Applications, 2019, 55(21): 93-98.
[7]	TANG Linyu, JIANG Jiafu, GU Ke. Computing Resource Allocation Scheme Based on Fog Computing [J]. Computer Engineering and Applications, 2019, 55(19): 96-104.
[8]	JIA Liyun, ZHANG Xiangli, ZHANG Hongmei. Heuristic task scheduling algorithm for distributed systems [J]. Computer Engineering and Applications, 2017, 53(12): 63-69.
[9]	WANG Xianghua1, CHEN Tefang1, ZHANG Biming2, YAN Jian1. Web data clustering algorithm with time series and task scheduling [J]. Computer Engineering and Applications, 2016, 52(9): 159-163.
[10]	LIN Ruonan, LI Qiang. Template-based task scheduling strategy and algorithm in cloud computing environment [J]. Computer Engineering and Applications, 2016, 52(19): 48-52.
[11]	WANG Bo, ZHANG Xiaolei. Task scheduling algorithm based on Particle Swarm Optimization Genetic Algorithms in cloud computing environment [J]. Computer Engineering and Applications, 2015, 51(6): 84-88.
[12]	SUN Lingyu1, LENG Ming1，2, ZHU Ping1, LI Jinzhong1. Research of dependent task schedule of cloud computing based on weighted directed hypergraph [J]. Computer Engineering and Applications, 2015, 51(24): 34-39.
[13]	WANG Zhenchao. Integration of DEA and Taguchi method of multi-task scheduling scheme in cloud computing [J]. Computer Engineering and Applications, 2015, 51(2): 140-145.
[14]	LI Jingmei, ZHANG Dahu, WU Yanxia. Heterogeneous Chip Multi-core Processor task scheduling method based on ant colony algorithm [J]. Computer Engineering and Applications, 2015, 51(18): 47-51.
[15]	LI Zhaojun1，2, LI Zheng2, WANG Xicheng2, LI Keqiu1. Dynamic cloud task scheduling method based on Kriging surrogate model [J]. Computer Engineering and Applications, 2015, 51(16): 30-35.

New scheduling algorithm with communication contention

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics