【作者】 蒋建春；

【导师】 汪同庆；

【作者基本信息】 重庆大学 ， 仪器科学与技术， 2011， 博士

【摘要】 如何充分利用异构多核处理器的异构特性,将单核的应用软件快速的移植到多核处理器上以及快速地开发基于多核处理器的应用程序是多核处理器应用中面临的主要问题。而解决这些问题的方法要求主要集中在多核软件等关键技术研究上,只有开发出与异构多核硬件相适应的操作系统及其应用软件,才能真正地发挥异构多核处理器的性能。由于异构多核处理器中不同性质程序在不同内核的执行效率存在差异,且应用系统存在功耗、效率、实时性等要求,这就要求操作系统能够对任务进行有效的管理,如分配调度、通信、同步等,以实现多核处理器的最大化利用。而要实现这些功能必须针对异构多核处理器特点研究和设计相应的操作系统架构、调度算法、通信与同步机制等关键技术。传统的多处理器和分布式计算机与异构多核处理器在架构和通信机制上存在巨大差别,相应的分布式操作系统也不适用于异构多核处理器,特别是在嵌入式系统领域。本课题针对嵌入式系统领域,通过研究异构多核处理器的结构特点,分别在操作系统架构、任务划分、异构核间的任务分配以及同构核间动态任务调度等几个关键问题方面进行了大量深入的研究,主要完成了以下工作:1.研究了异构多核的操作系统架构针对多处理器系统的分布式结构以及应用于同构多核系统的主从式结构操作系统不能解决异构多核处理器的实时调度和效率问题,本课题提出一种适用异构多核处理器的多主模式实时操作系统架构。这种架构将通信总线中的多主模式引入多核操作系统架构中,采用对称式结构及组件模式设计操作系统模型,使多核处理器中每个内核都可以作为主核实现对资源、任务的实时管理,提高系统性能,同时可以解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求存在的瓶颈问题。通过这种单一架构模型可以进行灵活配置适应不同结构及功能要求处理器内核,降低操作系统开发难度。2.研究了异构多核处理器的任务划分问题任务的调度与任务的属性、粒度、任务之间的关系等因素密不可分。异构多核的任务划分是多目标优化问题,怎样针对具体的任务执行环境进行任务分割,使任务在粒度大小、通信调度花费、并行化处理、负载均衡等方面得到一个有效的综合,从而通过调度获得系统的最大执行效率,是任务划分需要解决的关键问题。本课题从任务本身属性和调度两个方面针对异构多核处理器的任务划分中的重要影响因素进行分类分析,提出一种基于聚合性的微粒群分层任务划分方法,通过参数匹配,获得一个较好的划分结果,从而提高任务调度和执行的效率。3.研究了异构多核处理器的任务静态调度问题在异构多核处理器中,任务有最小最大完成时间、负载均衡、最低功耗等要求,异构环境下的任务分配和作业调度问题往往是局部目标和全局目标是相互制约,不能同时满足,任务静态调度被证明是一个NP-Hard的组合优化问题。本课题针对异构并行系统的作业调度和任务分配问题进行研究,提出一种基于Sufferage启发式算法和DPSO(Discrete Particle Swarm Optimization)算法的混合离散微粒群SDPSO (Sufferage Discrete Particle Swarm Optimization)独立任务分配算法,改进DPSO算法效率和搜索精度。由于实际的任务之间存在耦合性,针对独立任务设计的静态调度算法不能很好解决非独立任务的调度问题。因此,本课题在SDPSO算法的基础上,根据任务划分实际存在的耦合性,研究并提出一种基于耦合性的SDPSO静态任务调度改进算法。4.研究了异构多核中同构核间的任务动态调度问题在异构多核处理器中,有可能存在多个同构核,在这些同构核中的任务除了进行任务的静态分配以外,还存在运行过程中的动态调度问题。在动态调度中主要存在基于任务复制和基于表的动态调度算法,而基于任务复制的动态调度算法对存储空间要求较高不适合实时系统。本课题针对嵌入式系统并行同步任务的实时性要求在动态表的基础上提出一种基于任务划分的最小最大关键点执行时间MMKPT(Min-Max Key Point Time)算法,该算法根据同步任务的同步执行时间点和任务之间的耦合性对就绪任务和执行内核进行选择和调度,以满足嵌入式系统的实时性要求。通过这些关键技术的研究工作及成果,可以为异构多核处理器的实时操作系统的研究与开发提供一些帮助和参考,以促进异构多核处理器的应用推广。更多还原

【Abstract】 In the application of the heterogeneous multicore processor (HMP), how to make full use of the heterogeneous multi-core processor and how to quickly transfer and develop the application programs in multi-core processor are the most important issues. The solving methods of these problems focus on the researches of some key software techniques, such as multi-core operating system (OS), application programs, and so on.Since different applications have different requirements for power, efficient, real-time, etc, OS is needed to manage tasks, such as scheduling, communication, synchronization, to utilize processor fully. So, the architecture of OS, the scheduling algorithm, the communication and synchronization mechanism, must be designed according to the characteristics of HMP. However, owing to the difference on architecture and communication mechanism, the traditional multiprocessors OS and distributed OS are not suitable to the HMP, especially in the embedded system application.This thesis studies these key problems based on the research of the characteristics of HMP in embedded system area, including the OS architecture, the communication and synchronic mechanism, the task partitioning, the task static scheduling and the dynamic scheduling. The main contributions of the thesis are as follows:1. OS architectureAim at the executing efficiency and real-time scheduling problems that can not be solved by the distributing structure and master-slave mode architecture OS of multi-processors and homogeneous multicore processor, a new multi-master mode OS architecture for HMP is proposed. In this architecture, because of the introduction of the multi-master mode of communication bus and the adoption of the symmetric structure and the modularization method in OS model design, each core could be as the master core in multi-core processor to manage tasks, resources, and so on. Meanwhile, this OS architecture can solve the bottleneck problem that the master-slave architecture can not do well because of the increasing slave number in single master OS. This model can be configured flexibly based on the requirements of application, and decrease the OS implement difficulty. 2. Task partitionIn multi-core processor, task scheduling is strictly related with the task attribute, the task granularity, the relations between tasks and other factors. The task partition is a multi-goals optimization problem. The key issue of task partition is how to partition tasks based on different application to make system executing efficiently. Some factors, such as scheduling cost, granularity, coupling cost and load balancing, need to be taken into account. This paper firstly classify the tasks according to task attribute and system efficiency, including coupling cost, scheduling cost, and then presents one task partitioning algorithm based on cohesion and coupling of modules. This algorithm can achieve a good partitioning result, improve the task scheduling and executing efficiently through parameters matching.3. Static task schedulingIn the HMP, tasks have the requirements of min-max complement time, load balance, lowest power cost, and so on. The global goals and the local targets are nomal mutually exclusive.The task allocation and scheduling is a multi-goals combinatorial optimization issue, and is proved a NP-hard problem. Through researching the task scheduling and assignation, this thesis puts forward a sufferage discrete particle swarm optimization (SDPSO) independent task static scheduling algorithm based on Sufferage and DPSO, which can improve the search efficiency and precision of DPSO.In the practical application, there are coupling relations between tasks, and the independent task static scheduling algorithm can not settle well for the dependent tasks. So this paper modifies the SDPSO algorithm based on coupling attribute to make it suitable for the dependent tasks.4. Dynamic task schedulingSince there are a few homogeneous cores in HMP, dynamic scheduling is required among homogeneous cores except for static scheduling. The main algorithms are based on task duplication and list scheduling, and the task duplication algorithms is not suitable for embedded real-time system because of the requirement for large memory space. Therefore, this paper presents a min-max key point time (MMKPT) algorithm based on dynamic list scheduling algorithm, in which the ready task and kernel are selected according to the synchronization point executing time and the coupling relation among tasks to meet with the real-time performance requirement of the embedded system. The research results of above key issues can provide some help and references for the HMP OS design and development, and advance the HMP to be applied more and more widely.更多还原