基于动态任务调度的STDS算法设计研究

PDF下载HTML

Title:

Research on STDS algorithm designing based on dynamic task scheduling

作者:

刘正

哈尔滨工程大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001

Author(s):

LIU Zheng

College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China

关键词:

动态任务调度; 负载均衡; 调度粒度; 等待时间; 异构多核系统

Keywords:

dynamic task scheduling; load balancing; scheduling granularity; waiting time; heterogeneous multi-core system

分类号:

TP316.4

DOI:

10.3969/j.issn.1673-4785.201503013

文献标志码:

A

摘要:

任务调度是计算机多核处理器系统获得高性能的关键,而现有的多核任务调度算法研究,大多侧重于静态调度下的算法优化和负载均衡,对动态调度及动态负载均衡研究较少。针对动态调度,并结合异构多核的特点,提出一种基于核负载均衡的动态任务调度算法STDS。算法通过合理设定调度粒度,降低调度频率,从而减少调度消耗时间;根据异构多核处理器各核处理性能的差异,设置内核负载上下限值,控制内核负载保持在同一水平,以达到负载均衡效果。算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度,并可通过实时因子、负载因子等参数设置3种因素的影响比重,以满足系统的不同需求。仿真实验显示,在内核数目较多的系统中,STDS算法更加高效,在保证任务处理速度的同时有较好负载均衡。

Abstract:

Efficient task scheduling is the key for multi-core systems to achieve high performance. However, most of the existing multi-core researches on task scheduling algorithms focus on algorithm optimization and load balancing under the static scheduling rather than dynamic scheduling and dynamic load balancing. Scalable task duplication based scheduling (STDS) is a new dynamic-balanced algorithm based on core load balancing. STDS was put forward specifically for dynamic scheduling and integrating the characteristics of heterogeneous multi-core. It shortens scheduling time by reasonably setting the scheduling granularity and reducing the frequency of scheduling. STDS sets the maximum and minimum ranges of the kernel load according to the different processing performance of each core of the heterogeneous multi-core processor, therefore controlling the core load at the same level and achieving the effect of load balance. The wait time of task and communications between tasks and kernel load will be considered together to pick up the most appropriate task during scheduling. The importance of each element can be adjusted by assigning another value to the real-time factor and load factor enabling it to adapt to various environment. The experimental results verified that the STDS algorithm is more efficient in the system with the most kernels. It also keeps a good load balance while maintaining the speed of task execution processing.