论文部分内容阅读
异构多核处理器是当今处理器发展的主流方向,因为拥有灵活性高、性能卓越等其他同构多处理器没有的特点,所以它更受市场的欢迎。在异构多核处理器系统关键技术的研究中,依赖任务调度问题已经被证明是NP完全问题。因此探索相应的任务调度算法以更高效地分配任务给异构处理器和保证每个异构处理器负载均衡是学者一直以来面临的难题。近年来,众多学者开始从智能搜索算法去探索解决此类问题的有效途径。本文针对异构多核处理器系统任务调度过程中处理器负载不均的问题进行了探索研究。主要进行了如下工作:(1)针对异构多核处理器微内核系统在调度过程中处理器负载不够均衡的问题,通过改造蚁群算法,提出一种基于改进的蚁群算法(Modified Ant Colony Optimization,MACO)的任务调度算法,使之能够应用于异构多核平台系统任务调度中。该算法通过修改蚁群算法并根据任务调度的特点引入了相关参数,删掉了需要等待很长时间进行迭代生成近似解的过程。通过蚁群概率公式生成概率矩阵,计算后获得相对负载均衡的处理器-任务分配映射表。实验证明了该算法在调度大于等于50个依赖任务时能够获得较好的负载均衡调度效果。(2)针对基于MACO的任务调度算法在处理依赖任务数量少于50时其负载均衡调度效果不佳的问题,通过引入遗传重组优化方法,提出了一种基于遗传改进的蚁群(Genetic Improvement Based Ant Colony Optimization,GI-ACO)算法的任务调度算法。该算法对处理器-任务分配映射表进行了进一步地负载均衡调整,在调度过程中能获得较高的负载均衡值。实验证明该算法在调度小于50个依赖任务时能实现较好的负载均衡调度效果。本文针对上述提出的两个算法分别进行了实验验证。首先,通过TGFF软件生成DAG依赖任务,将基于MACO的任务调度算法和表优先级(List Priority Scheduling for Heterogeneous,LSH)任务调度算法进行对比实验。其次,将基于GI-ACO的任务调度算法分别跟上述两个算法在相同条件下进行对比实验。实验中发现本文提出的两种任务调度算法的任务数阈值是50。因此可以通过在操作系统中部署本文提出的两个算法,当系统遇到依赖任务数的边界值后进行切换使用这两种算法,从而使系统在调度过程中达到最优负载均衡调度的效果。本研究为异构多核处理器下的微内核操作系统在任务调度中解决处理器负载不均的问题提供了理论参考价值。