异构多核处理器的任务调度策略研究

发布时间：2018-03-31 23:39

本文选题：异构多核　切入点：分层　出处：《湖南大学》2013年硕士论文

【摘要】：多核处理器的起跳主频比单核处理器低，性能更好，多核处理器已经成为当今的主流处理器。多核处理器根据系统的内核结构是否存在差异，可以分为同构多核处理器和异构多核处理器。异构多核处理器能更好地处理异构的应用程序，比如，快速复杂的核可以执行串行代码部分，而较简单的核则能并行处理数字，这样不仅能提高处理器系统的性能，而且能节省能耗。研究人员普遍相信异构多核处理器将是未来多核处理器发展的趋势，同时，异构多核处理器的发展也为任务调度与负载均衡的研究提供了广阔的发展空间。本文对现有的任务调度算法和任务调度模型进行改进，提出了一种负载均衡的异构多核处理器的任务调度算法，并对提出的算法进一步优化，充分考虑核间的负载均衡问题，本文主要工作包括以下几个方面： (1)对现有的调度模型和方法进行分析，提出了一种负载均衡的启发式任务调度算法，该算法考虑了多核处理器系统的异构性和任务间的依赖关系，将任务间的依赖关系用DAG(Directed Acyclic Graph)模型来刻画。首先，该算法将DAG图中表示的任务根据任务的入度值对任务集进行分层，经过分层处理的DAG图消除了任务间的数据依赖和控制依赖，，能确保同层的任务尽可能的并行执行；然后，将每层内的任务调度到相应的处理器核上，在将任务调度到处理器核上时，充分考虑核的异构性，根据核的计算能力给不同的核分配不同的负载。模拟实验结果表明，提出的任务调度策略在调度长度和负载均衡方面要优于其他的任务调度算法，优化了异构多核处理器系统的性能。 (2)通过分析任务间负载均衡的影响因素，发现提出的调度算法虽然避免了误差的累积现象，但是存在单个核误差并没有减少的问题，这在一定程度上影响了核间的负载均衡，针对此问题，考虑负载均衡影响因素，改进提出的任务调度算法，即在任务组调度阶段，在找到使核总耗时刚好小于等于核参考值的最后一个任务时，还可以继续从最小的任务开始增加任务，尽可能的减少单个核的误差。为了进一步提高计算精度，设计了一种误差下降调度方案，该方案将误差大的核上的任务集进行合并，再将合并的任务集重新调度到相应的核上，保证单个核的误差降到最低。
[Abstract]:The take-off frequency of multi-core processors is lower than that of single-core processors, and the performance of multi-core processors is better than that of single-core processors. It can be divided into isomorphic multicore processors and heterogeneous multicore processors. Heterogeneous multicore processors can better handle heterogeneous applications. For example, fast and complex cores can execute serial code parts, while simpler cores can process numbers in parallel. This will not only improve the performance of processor systems, but also save energy. Researchers generally believe that heterogeneous multicore processors will be the trend of future multi-core processors, at the same time, The development of heterogeneous multi-core processors also provides a broad development space for task scheduling and load balancing. In this paper, the existing task scheduling algorithms and task scheduling models are improved, and a load-balanced task scheduling algorithm for heterogeneous multi-core processors is proposed. The proposed algorithm is further optimized to take full account of the load balancing problem between cores. The main work of this paper includes the following aspects:. 1) based on the analysis of the existing scheduling models and methods, a load balancing heuristic task scheduling algorithm is proposed, which takes into account the heterogeneity of multi-core processor systems and the dependencies between tasks. The dependencies between tasks are described by DAG(Directed Acyclic Graph.Firstly, the tasks represented in the DAG graph are stratified according to the degree of the task, and the hierarchical DAG graph eliminates the data dependency and control dependency between the tasks. It can ensure that the tasks in the same layer are executed in parallel as much as possible; then, the tasks in each layer are scheduled to the corresponding processor core, and the heterogeneity of the core is taken into account when scheduling the task to the processor core. The simulation results show that the proposed task scheduling strategy is superior to other task scheduling algorithms in terms of scheduling length and load balancing. The performance of heterogeneous multi-core processor system is optimized. 2) by analyzing the influencing factors of load balancing between tasks, it is found that the proposed scheduling algorithm avoids the accumulation of errors, but there is a problem that the single kernel error has not been reduced, which to some extent affects the load balance between cores. In order to solve this problem, considering the influence factors of load balancing, the proposed task scheduling algorithm is improved, that is, in the task group scheduling stage, when the last task with the total kernel time is just less than or equal to the kernel reference value, In order to further improve the calculation accuracy, an error descent scheduling scheme is designed, in which the task sets on the kernel with large errors are merged. Then the merged task set is rescheduled to the corresponding kernel to ensure that the error of the single core is minimized.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP332

【参考文献】