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

发布时间：2019-01-08 07:01

【摘要】：传统的单核处理器主要借助提升主频或增加指令级并行度来提高处理器性能,但主频提升带来了功耗急剧增加及电流泄露等问题,而指令级并行度又受到指令间数据相关、控制相关以及结构相关的限制,很难进一步提高单核处理器性能。多核处理器以其高主频、低功耗和高并行性等优点迅速成为当前处理器发展主流,备受广大用户和研究者青睐。由于处理器有多个内核,要提高多核处理器整体性能就必需充分发挥每一个内核的作用,单核处理器的任务调度算法并不适合多核处理器,而多核处理器任务调度已经被证明为NP完全问题,因此如何利用高效的任务调度算法使多核处理器充分发挥其性能成为当前研究热点之一。由于动态任务调度比静态任务调度具有较高性价比,所以本文围绕异构多核处理器对动态任务调度算法进行研究。通过分析现有动态调度算法的基本原理和执行过程,结合负载均衡策略,提出一种DSMDQ动态调度器模型。DSMDQ采用集中式调度模式,便于控制内核的任务调度情况,根据异构多核处理器内核处理性能差异设置内核负载上下限,控制各个内核负载保持在同一活跃水平,实现负载均衡;使用全局调度队列和局部调度队列结合的方式,在克服集中式调度模式性能瓶颈的同时降低调度频率,从而减少调度消耗时间。在DSMDQ基础上设计了一种基于异构多核处理器的STDS动态任务调度算法,算法采用基于优先级列表的启发式调度思想,依据等待时间长短、任务间通信大小和内核负载轻重三种因素计算任务优先级,调度时优先分配优先级最高的任务;STDS算法为调节这三种因素对优先级的影响比重,引入了实时因子、负载因子等参数,可以满足不同的应用需求。本文最后对SDTS算法进行实验验证,选择调度时间、负载均衡和任务等待时间作为评价指标,使用TGFF工具生成不同特性的随机任务图作为测试用例,并在Simics模拟器上观察算法执行结果。对实验结果数据统计分析表明,STDS算法在内核数目较多系统中具有较好的优势,在保证速度性能的同时有较理想的内核负载均衡效果。
[Abstract]:The traditional single-core processor mainly improves the performance of the processor by raising the main frequency or increasing the parallelism of instruction level. However, the main frequency upgrade brings problems such as sharp increase in power consumption and leakage of current, and the parallelism of instruction level is dependent on the data between instructions. It is difficult to further improve the performance of single-core processors due to the constraints of control and architecture. Because of its advantages of high main frequency, low power consumption and high parallelism, multicore processor has become the mainstream of processor development, and has been favored by users and researchers. Because the processor has multiple cores, to improve the overall performance of the multi-core processor, it is necessary to give full play to the role of each kernel. The task scheduling algorithm of the single-core processor is not suitable for the multi-core processor. The task scheduling of multi-core processors has been proved to be a complete problem of NP, so how to make use of efficient task scheduling algorithm to give full play to the performance of multi-core processors has become one of the current research hotspots. Because dynamic task scheduling has higher performance-price ratio than static task scheduling, this paper studies dynamic task scheduling algorithm around heterogeneous multi-core processors. By analyzing the basic principle and execution process of the existing dynamic scheduling algorithm and combining the load balancing strategy, a DSMDQ dynamic scheduler model is proposed. The centralized scheduling mode is adopted by DSMDQ to facilitate the task scheduling in the kernel. The upper and lower limits of kernel load are set according to the performance difference of heterogeneous multi-core processor kernel, and each kernel load is kept at the same active level to realize load balancing. Using the combination of global scheduling queue and local scheduling queue, the performance bottleneck of centralized scheduling mode is overcome and the scheduling frequency is reduced, thus reducing the scheduling time. Based on DSMDQ, a dynamic task scheduling algorithm for STDS based on heterogeneous multi-core processor is designed. The algorithm adopts the heuristic scheduling idea based on priority list, according to the waiting time. The task priority is calculated by three factors: the communication size between tasks and the kernel load, and the task with the highest priority is assigned first in scheduling. In order to adjust the influence of these three factors on priority, the STDS algorithm introduces parameters such as real time factor and load factor, which can meet different application requirements. Finally, the SDTS algorithm is verified by experiments. Scheduling time, load balancing and task waiting time are selected as evaluation indexes, and random task diagrams with different characteristics are generated by using TGFF tools as test cases. The algorithm execution results are observed on the Simics simulator. The statistical analysis of the experimental results shows that the STDS algorithm has a good advantage in the system with a large number of kernels, and has an ideal kernel load balancing effect while ensuring the speed performance.
【学位授予单位】：哈尔滨工程大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;TP332

【相似文献】