非对称多核处理器的若干调度问题研究

发布时间：2018-05-30 03:25

本文选题：非对称多核处理器 + 操作系统调度　；参考：《华南理工大学》2013年博士论文

【摘要】：随着芯片集成规模极限的逼近以及能耗和成本等因素，多核处理器逐渐占据了市场。相对于对称多核处理器，非对称多核处理器在效能、芯片面积、适用范围等方面有着巨大的优势，将成为未来的主流体系结构。现有调度算法从单核处理器发展而来，并为对称多处理器做了相应扩展，不能利用非对称多核处理器的特性和优势。本文致力于研究非对称多核处理器的调度问题，以提高系统的效能、性能和公平性。具体来说，本文从以下4个方面进行了深入研究： (1)针对非对称多核处理器上操作系统的单线程任务调度问题，本文建模分析各种因素，提出了一种综合性调度算法。该算法采用行为匹配、减少迁移和负载均衡的调度策略，包括两个部分：1)集成负载表征，提出集成行为的概念，全面衡量任务的整体性和阶段性行为；2)基于集成行为的调度算法，有效开发非对称多核处理器的特性，能够保证各核心负载均衡，同时可以避免不必要的任务迁移。另外，该算法通过参数调整机制实现了算法的通用性。该算法是一种综合处理任务的整体性和阶段性行为，并具备通用性的调度算法。实验结果表明：该算法可通用于多种环境，且性能比其他同类算法提高6%~22%。 (2)针对非对称多核处理器上操作系统的多线程任务调度问题，本文建模分析各种因素，，提出了一个集成调度算法。该算法具有以下特性：1)全面考虑多线程任务同步特性、核心非对称性以及核心负载；2)通过集成线程调度和动态电压频率调整来提高效能；3)通过参数调整机制实现了算法的通用性。该算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法。实验结果表明：该算法可适用于多种环境，且效能比其他同类算法高24%~50%。 (3)针对非对称多核处理器上的虚拟处理器公平调度问题，本文建模分析各种因素，提出了一个组合调度算法。该算法具有以下特性：1)全面考虑虚拟处理器同步特性、核心非对称性以及核心负载；2)定义了效用因子、比例系数、比例资源的概念，结合虚拟处理器的同步特性和核心的非对称性对资源和负载进行全面度量；3)通过运行队列分解降低调度开销。实验结果表明：该算法实现了公平调度，并且性能比其他同类算法提高19%~48%。 (4)针对非对称多核处理器上的虚拟处理器高效能调度问题，本文提出一个并行度感知调度器，该调度器综合利用了虚拟处理器调度和动态电压频率调整。并行度感知调度器用一种非入侵的方法动态监测虚拟机的并行度，然后选择并调度相关的虚拟处理器同时执行。提出的推迟协同调度算法使多个并行的虚拟机可以同时进行协同调度，而不会导致冲突。实际平台上的实验表明，并行度感知调度器的性能和效能优势明显，分别达到26%和65%。此外，并行度感知调度器的开销接近默认调度器，低于其他非对称多核处理器上的虚拟机调度器。
[Abstract]:With the approximation of chip integration scale limit, energy consumption and cost and other factors, multi core processors gradually occupy the market. Compared with symmetric multicore processors, asymmetric multicore processors have great advantages in efficiency, chip area, application scope and so on, and will become the mainstream architecture in the future. The existing scheduling algorithms are from single core processing. The device has developed and expanded for symmetric multiprocessors, and can not take advantage of the characteristics and advantages of asymmetric multicore processors. This paper is devoted to the research of scheduling problems of asymmetric multicore processors to improve system performance, performance and fairness.
Specifically, this paper makes an in-depth study from the following 4 aspects:
(1) aiming at the single thread task scheduling problem of the operating system on the asymmetric multi core processor, this paper presents a comprehensive scheduling algorithm based on the modeling and analysis of various factors. This algorithm uses behavior matching to reduce the migration and load balancing scheduling strategy, including two parts: 1) integration of load characterization, the concept of integrated behavior and a comprehensive balance. The overall and phased behavior of a task; 2) a scheduling algorithm based on integrated behavior, which can effectively develop the characteristics of asymmetric multicore processors, can guarantee the balance of all core loads and avoid unnecessary task migration. In addition, the algorithm realizes the generality of the algorithm through the parameter adjustment mechanism. This algorithm is a comprehensive treatment. The experimental results show that the algorithm can be used in many environments, and the performance of the algorithm is improved by 6%~22%. compared with other similar algorithms.
(2) aiming at the multi thread task scheduling problem of the operating system on the asymmetric multi core processor, this paper presents an integrated scheduling algorithm based on the modeling and analysis of various factors. This algorithm has the following characteristics: 1) taking into account the synchronization characteristics of multithreading tasks, core asymmetry and core load; 2) through integrated thread scheduling and dynamic voltage frequency integration. The algorithm is the first scheduling algorithm combined with thread scheduling and dynamic voltage frequency adjustment on an asymmetric multi core processor. The experimental results show that the algorithm can be applied to a variety of environments and the efficiency is 24%~50%. higher than the other similar algorithms, 24%~50%..
(3) aiming at the fair scheduling problem of virtual processors on asymmetric multicore processors, this paper presents a combination scheduling algorithm based on the modeling and analysis of various factors. This algorithm has the following characteristics: 1) taking into account the synchronization characteristics of the virtual processor, core asymmetry and core negative load; 2) defines the utility factor, the ratio coefficient, and the proportional resource. The concept, combining the synchronization characteristics of the virtual processor and the non symmetry of the core, makes a comprehensive measurement of the resources and the load; 3) reducing the scheduling overhead through the run queue decomposition. The experimental results show that the algorithm achieves fair scheduling and improves the performance of 19%~ 48%. compared with other similar algorithms.
(4) aiming at the efficient scheduling problem of virtual processors on asymmetric multi core processors, a parallel degree aware scheduler is proposed. The scheduler uses virtual processor scheduling and dynamic voltage frequency adjustment. The parallel degree aware scheduler dynamically monitors the parallelism of the virtual machine with a non intrusive method, and then selects and adjusts the degree. The proposed deferred collaborative scheduling algorithm enables multiple parallel virtual machines to perform collaborative scheduling at the same time without causing conflicts. Experiments on the actual platform show that the performance and effectiveness advantage of the parallel degree aware scheduler is obvious, up to 26% and 65%. respectively, and the parallel degree aware scheduler is open, respectively. The pin is close to the default scheduler, which is lower than the virtual machine scheduler on other asymmetric multi-core processors.
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP332;TP301.6

【参考文献】