多核处理器中具有临界区的多线程调度方法研究

发布时间：2018-10-18 09:21

【摘要】：随着多核技术以及多线程技术的发展,多线程在多核处理器上的调度问题成为研究热点。由于多核处理器结构的复杂性,使得资源管理更困难。当多线程在多核平台上运行时,怎样更好的利用多核资源,让多线程能够正确快速的执行,决定了系统性能的提高。一个优秀的针对多核处理器的线程调度算法可以有效利用资源,提高系统吞吐率,兼顾公平性,降低程序的响应时间和周转时间。对于多核多线程的调度方法的研究,一般都先提出一种多线程的模型,并在这种模型的基础上针对不同的多核平台提出不同的调度方法。在多线程模型上,很多人都选择DAG图,但是传统的DAG图有其自身的缺陷,例如不能对任务间的关系进行近一步的刻画。本文针对具有临界区的线程,提出一种基于Forest的多线程调度模型,通过该模型维护线程间的前后依赖、数据资源和共享资源关系。为有效的提高系统性能,减少计算资源空闲时间,提出了综合考虑线程共享资源情况以及前后依赖关系的调度方法CSTS算法。该算法以临界区作为线程间共享资源的依据,对具有相同临界区线程进行同核调度。并且由于临界区不可同时执行的特点,临界区成为限制系统整体性能的重要因素。为减少由临界区而造成的堵塞,算法提出了基于临界区的优先级计算方法,并且兼顾公平性。在多核处理器中,由于各核间计算能力的不同,异构多核处理器较同构多核处理器更具有实用性。因此,本文除针对一般多核处理器设计了多线程模型以及基于该森林模型的调度方法外,还针对异构多核处理器各核间处理能力的不同,优化了加速临界区算法。加速临界区算法可以有效缩短具有临界区的线程的执行时间,但是有可能会造成无关临界区串行化的问题。本文在加速临界区算法基础上提出改进加速临界区算法。该算法跟踪记录所有包含临界区的线程在核上的执行情况,对线程的优先级因子进行调整,通过该优先级因子指导线程在高速核与低速核间的动态迁移。该算法不仅加速了临界区的执行而且能有效解决加速临界区方法所造成的线程在高速核上的堵塞的问题。本文采用模拟实验的方法对基于森林线程模型的算法进行模拟验证。较同类算法对于临界区密集型任务具有较高的性能,核利用率也较高。针对于适应于异构平台改进临界区迁移算法,本文采用Simics仿真平台进行异构多核系统仿真,输入为12个临界区密集型负载,实验结果表明,该方法较原始加速临界区算法和朴素算法拥有更好的性能。
[Abstract]:With the development of multi-core technology and multi-thread technology, the scheduling problem of multi-thread on multi-core processor has become a hotspot. Because of the complexity of multi-core processor architecture, resource management is more difficult. When multi-thread is running on multi-core platform, how to make better use of multi-core resources, so that multi-thread can execute correctly and quickly, determines the improvement of system performance. An excellent thread scheduling algorithm for multi-core processors can effectively utilize resources, improve system throughput, take fairness into account, and reduce program response time and turnaround time. For the research of multi-core multi-thread scheduling methods, a multi-thread model is proposed firstly, and based on this model, different scheduling methods are proposed for different multi-core platforms. In multithreading model, many people choose DAG diagram, but the traditional DAG graph has its own defects, such as the relationship between tasks can not be further described. In this paper, a multi-thread scheduling model based on Forest is proposed for threads with critical region. The model maintains the relationship among threads, data resources and shared resources. In order to improve the performance of the system and reduce the idle time of computing resources, a scheduling method, CSTS algorithm, is proposed, which considers the resource sharing of threads and the relationship between threads and dependencies. The algorithm uses the critical region as the basis for sharing resources among threads, and schedules the threads with the same critical region with the same core. Because the critical region can not be executed simultaneously, the critical region becomes an important factor that limits the overall performance of the system. In order to reduce the blockage caused by the critical region, the algorithm proposes a priority calculation method based on the critical region and takes fairness into account. In multi-core processors, heterogeneous multi-core processors are more practical than isomorphic multi-core processors because of their different computing power. Therefore, in addition to designing multi-thread model and scheduling method based on the forest model for general multi-core processors, this paper also optimizes the accelerated critical region algorithm for the different processing capabilities of different cores of heterogeneous multi-core processors. The accelerated critical region algorithm can effectively shorten the execution time of threads with critical region, but it may cause serialization of independent critical regions. This paper presents an improved accelerated critical region algorithm based on the accelerated critical region algorithm. The algorithm tracks the execution of all threads with critical region on the kernel, adjusts the priority factor of the thread, and guides the dynamic migration of the thread between the high speed kernel and the low speed kernel. The algorithm not only accelerates the execution of the critical region but also effectively solves the problem of thread blockage on the high speed kernel caused by the accelerated critical region method. In this paper, the algorithm based on forest thread model is simulated and verified by simulation experiment. Compared with similar algorithms, it has higher performance for critical region intensive tasks and higher kernel utilization ratio. In order to adapt to the improved critical region migration algorithm for heterogeneous platforms, this paper uses Simics simulation platform to simulate heterogeneous multi-core systems, and inputs 12 critical zone intensive loads. The experimental results show that, This method has better performance than the original accelerated critical region algorithm and naive algorithm.
【学位授予单位】：华北电力大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP332

【参考文献】