论文部分内容阅读
在高性能计算中,如何根据用户提交的任务需求,对处理核等资源进行合理的按需分配是计算机系统结构的重要研究内容。但目前,该领域还存在诸如调度目标动态性,任务约束多样化及任务对资源需求多样性等问题,这些问题已成为制约众核任务调度效率和系统效能的关键因素。因此,基于调度目标动态性、任务和资源需求多样性,有针对地提出可以支持高效的多目标优化调度算法和调度目标灵活插拔的众核任务调度体系,将有利于调度效率和系统效能的提高。围绕这一研究内容,进行了众核任务调度体系统一范式研究,首次提出众核任务调度体系要素组织模型(FactorOrganizationModel,简称FOM),弥补了当前众核任务调度体系研究理论基础缺失,更好描述了众核任务调度体系。以FOM模型为基础构建可以仿真不同众核任务调度体系的仿真系统simScheduler和可以实现各众核任务调度体系的实际系统Linux插件schdulerArch,解决了构建各众核任务调度体系的技术问题,并基于simScheduler和schdulerArch开展了如下工作:
⑴提出了乐观锁和事务型共享状态(Optimistic-LockandTransactionalSharedState,简称OLTSS)众核任务调度体系以支持高效的多目标优化调度算法,实现调度目标灵活地插拔功能。该体系可以把任务调度策略以插拔式的组件形式加入调度器,允许任务根据自身特性制定资源调度策略,并通过共享计算资源状态将所有底层资源信息公开给任务,为任务提供并行自由竞争资源的途径。提出了基于乐观锁的资源竞争协调算法,以解决OLTSS众核任务调度体系并行执行任务调度而引发的资源竞争问题。该算法运用乐观锁机制提高并行度,以实现资源利用率的提高。实验采用了仿真实验进行验证,结果显示,相对于其它众核任务调度体系,采用了基于乐观锁的资源竞争协调算法的OLTSS众核任务调度体系,其任务平均等待时间、工作负载完成时间、调度器使用率、公平度等方面都有很好的表现,尤其是随着任务数的增多,表现出更大的优势。
⑵为兼顾用户和系统设计者双方利益的目标,在满足存储容量和约束条件下,设计出最小化工作负载完成时间和任务等待时间的MultipleObjectFairnessTradeoff(MOFT)调度算法。该算法结合OLTSS众核任务调度体系,把多目标优化调度简化为由冲突检测和基于不同权重函数进行冲突裁决这两阶段构成,以提高资源按需分配能力和提升系统性能。通过仿真实验,证实该方法与其它相关算法相比,在算法复杂度、执行时间上具有明显的优越性。通过基于Linux的实际环境实验,证实采用MOFT算法的OLTSS众核任务调度体系与其它众核任务调度体系相比,在考虑具体资源分配和满足存储约束、保证公平的条件下,其任务平均等待时间、工作负载完成时间、公平度方面都有更好的表现。
⑶在保证资源公平度的前提下,提出最小化任务集完成时间的冲突消减控制算法,以解决因用户级调度器数量和任务急速增加而引起的资源冲突激增问题,实现OLTSS众核任务调度体系在不降低系统性能和保障资源公平前提下容纳更多用户级调度器的能力,即插拔能力,从而提高其可扩展性。冲突消减控制算法运用P控制实现动态调整系统的插拔能力以适应系统提供的浮动并行能力,采用一个相对的增益计算公式来减少余差的影响,达到消减冲突的目标。对OLTSS和采用冲突消减的OLTSS的插拔能力和可扩展性进行了定量比较,结果表明当用户级调度器数量快速增加时,采用冲突消减的OLTSS在用户级调度器使用率和事务冲突率等方面表现出更大的优势,缓解了冲突激增效应;当任务数量快速增加时,采用冲突消减的OLTSS在任务平均等待时间和任务集完成时间方面均少于OLTSS,体现了冲突消减控制算法有效提升了OLTSS的插拔能力和可扩展性。再对采用冲突消减的OLTSS和静态划分调度体系在任务集完成时间和资源使用率方面进行定量比较,结果再次体现了前者的优越性。
⑴提出了乐观锁和事务型共享状态(Optimistic-LockandTransactionalSharedState,简称OLTSS)众核任务调度体系以支持高效的多目标优化调度算法,实现调度目标灵活地插拔功能。该体系可以把任务调度策略以插拔式的组件形式加入调度器,允许任务根据自身特性制定资源调度策略,并通过共享计算资源状态将所有底层资源信息公开给任务,为任务提供并行自由竞争资源的途径。提出了基于乐观锁的资源竞争协调算法,以解决OLTSS众核任务调度体系并行执行任务调度而引发的资源竞争问题。该算法运用乐观锁机制提高并行度,以实现资源利用率的提高。实验采用了仿真实验进行验证,结果显示,相对于其它众核任务调度体系,采用了基于乐观锁的资源竞争协调算法的OLTSS众核任务调度体系,其任务平均等待时间、工作负载完成时间、调度器使用率、公平度等方面都有很好的表现,尤其是随着任务数的增多,表现出更大的优势。
⑵为兼顾用户和系统设计者双方利益的目标,在满足存储容量和约束条件下,设计出最小化工作负载完成时间和任务等待时间的MultipleObjectFairnessTradeoff(MOFT)调度算法。该算法结合OLTSS众核任务调度体系,把多目标优化调度简化为由冲突检测和基于不同权重函数进行冲突裁决这两阶段构成,以提高资源按需分配能力和提升系统性能。通过仿真实验,证实该方法与其它相关算法相比,在算法复杂度、执行时间上具有明显的优越性。通过基于Linux的实际环境实验,证实采用MOFT算法的OLTSS众核任务调度体系与其它众核任务调度体系相比,在考虑具体资源分配和满足存储约束、保证公平的条件下,其任务平均等待时间、工作负载完成时间、公平度方面都有更好的表现。
⑶在保证资源公平度的前提下,提出最小化任务集完成时间的冲突消减控制算法,以解决因用户级调度器数量和任务急速增加而引起的资源冲突激增问题,实现OLTSS众核任务调度体系在不降低系统性能和保障资源公平前提下容纳更多用户级调度器的能力,即插拔能力,从而提高其可扩展性。冲突消减控制算法运用P控制实现动态调整系统的插拔能力以适应系统提供的浮动并行能力,采用一个相对的增益计算公式来减少余差的影响,达到消减冲突的目标。对OLTSS和采用冲突消减的OLTSS的插拔能力和可扩展性进行了定量比较,结果表明当用户级调度器数量快速增加时,采用冲突消减的OLTSS在用户级调度器使用率和事务冲突率等方面表现出更大的优势,缓解了冲突激增效应;当任务数量快速增加时,采用冲突消减的OLTSS在任务平均等待时间和任务集完成时间方面均少于OLTSS,体现了冲突消减控制算法有效提升了OLTSS的插拔能力和可扩展性。再对采用冲突消减的OLTSS和静态划分调度体系在任务集完成时间和资源使用率方面进行定量比较,结果再次体现了前者的优越性。