并行任务调度在多核系统中的在线模型及其算法研究

随着多核和众核系统的发展，如何有效的利用和挖掘并行性是一个具有挑战和有意义的事情。本项目对并行任务调度因多核出现而产生的新模型和在线算法进行研究。本项目从算法的设计与分析的角度入手（如在线原始-对偶法，随机算法等），在不改变硬件结构和操作系统的前提下，抽象出基于多核计算系统中的并行任务调度数学模型，并利用组合优化和算法设计的相关理论知识来设计高效的算法，并给出算法的性能保证。本项目的主要研究内容为基于多机多核的并行任务调度在线算法研究和基于缓存分割的并行任务调度在线算法研究。首先，对多机器且核数不相同的并行任务调度算法进行研究，继而考虑核间带网络拓扑结构的并行任务调度算法，同时对并行任务在不同机器间可以迁移的情况进行调度算法研究。另外，我们考虑了缓存因素对并行任务的影响，即研究基于缓存分割的平行非同类机的在线调度算法和研究基于缓存分割的并行任务调度算法；最后实现部分算法、并分析比较。

随着多核和众核系统的发展, 如何有效的利用和挖掘并行性是一个具有挑战和 有意义的事情。本项目对并行任务调度因多核出现而产生的新模型和在线算法进行研究。本项目的主要研究内容为基于多机多核的并行任务调度在线算法研究，及基于缓存分割的并行任务在线调度算法研究。项目根据研究计划和研究内容顺利进展并完成了预先设定的计划。具体来讲，主要的研究成果有：.1、.多机多核的在线并行任务调度：研究核速度不相同、集群中核数不同的并行任务调度在线算法，分别给出了常数竞争比的算法。 .2、基于缓存分割的资源加速调度：将缓存分割成若干相同大小的块数,每个任务只使用一块缓存来加速。对于双核结构我们设计的在线算法的竞争比，且证明任何在线算法的竞争比与该上届很接近。并将问题推广至任意m核的情况。.3、可迁移的并行任务调度算法研究：我们首次提出排序模型中迁移代价显性的模型，并给出了近似算法、在线算法的分析。.4、基于多机多核的并行任务调度协调机制设计：多机多核系统或者是云计算往往是分布式计算。本项目研究了计算任务是属于不同的用户，且每个用户可以选择计算资源。这个模型是用户与用户之间的博弈，每个用户希望能尽快的完成所提交的任务，即完工时间最小。本项目研究平台提供方需要设计相关的机制并使得社会效益得到优化。我们首次提出了两类的协调机制并分析其社会效益。.5、基于资源竞争的并行任务调度博弈：我们将计算任务多维化，如一个任务需要CPU、内存、带宽等d－维资源，这里d为任意的整数。每个任务都有各自的玩家（如虚拟机）控制，为了获得更好的资源，玩家将根据系统的负载等信息自由选择自己的处理资源。我们考虑了两种场景，负载均衡和虚拟机放置博弈，首次提出多维资源竞争的博弈模型。 .6、基于混合CPU-GPU的任务调度：给定混合的CPU－GPU系统，我们根据CPU和GPU数目的不同情况，分别设计在线算法。该模型的创新在于给出了介于平行机调度与非同型机调度的在线模型和算法设计，解决特定处理器异构的调度算法。..本项目预期发表国际期刊或者国际会议论文10～13篇。目前，我们已经发表的论文有14篇论文，其中SCI期刊7篇，国际会议7篇（EI检索），重要期刊有Future Generation Computer Systems, Journal of Global Optimization，Information processin