面向复杂并行架构的高性能低功耗任务调度的研究

发布时间：2020-10-16 03:55

　　 受芯片制造工艺、芯片材料的物理特性、能耗、散热等问题的限制，单核处理器的频率提升速度已无法跟上高性能计算对计算能力需求的增长速度。有鉴于此，基于多核处理器的并行架构得到了广泛的发展。如何充分地利用各种并行架构中大量的计算资源已成为高性能计算领域的研究热点之一。特别地，如何通过优化任务调度在不修改并行程序的前提下提高并行程序的性能、节省执行并行程序的能耗、均衡并发运行的程序的性能更是重中之重。 针对目前主流的各种并行架构，本文完整并深入地研究了这些架构中的高性能低能耗的优化任务调度策略，设计并实现了面向复杂并行架构的运行时高性能低功耗任务调度系统：HPEE系统。HPEE系统由缓存感知双层任务窃取模块（CAB）、位置感知任务窃取模块（LAWS）、带宽感知核分配模块（BWC）、负载感知任务调度模块（WATS）、高能效负载感知任务调度模块（EEWA）等五个主要模块组成。这些模块涉及的并行架构包括：多路多核架构、使用NUMA内存系统的多路多核架构、非对称多核架构、以及支持动态电压频率调节技术的多核架构。 在多路多核架构中，同一处理器中的核之间共享缓存但是不同处理器中的核之间仅共享主存。因此，针对多路多核架构，我们主要对共享缓存的使用进行优化。如果该架构仅执行一个程序，HPEE系统使用缓存感知双层任务窃取模块，将该程序共享数据的任务调度到同一个处理器中。基于此方法，各任务间的共享数据只需要被读入共享缓存一次，同一处理器中的核可以直接从共享缓存中高速访问该数据。实验结果表明，和传统任务窃取策略相比，缓存感知双层任务窃取模块可以减少并行程序74.4%的运行时间。 如果该多路多核架构底层使用NUMA内存架构，HPEE系统使用位置感知任务窃取模块，将一个程序的数据集平均分配到不同的内存节点中，并将各任务分配到本地内存节点存储其数据的处理器中。使用该方法，各任务都能从本地内存节点或者共享缓存中高速地访问数据。实验结果表明，和传统任务窃取调度器相比，位置感知任务窃取模块可以减少并行程序54.2%的运行时间。 然而，如果一个多路多核架构上有多个并行程序并发运行，那么这些程序将竞争计算资源（核）和存储资源（缓存、缓存带宽）。如何合理地将计算资源和存储资源动态分配给并发运行的并行程序是使这些程序获得良好且均衡性能所亟需解决的问题。针对该问题，基于各程序的实时需求，HPEE系统使用带宽感知核分配模块周期性地对计算资源和存储资源进行重分配。在保证每个程序需求的前提下，如果一个处理器的共享缓存带宽已被大量占用，那么带宽感知核分配模块将该处理器中的空闲核分配给计算密集型程序。反之亦然，通过这种方式，带宽感知核分配模块可以最小化共享缓存竞争并进而提高并发运行的程序的性能。实验结果表明，和传统的空分共享相比，带宽感知核分配模块能够减少并发运行程序高达54.7%的运行时间。 在非对称多核架构中，不同的核运行于不同的频率且每个核的频率在执行程序过程中不可变。在此种架构中，如何保证不同频率的核间的负载均衡是最优化并行程序性能所面临的关键问题。针对该问题，基于实时采集的程序中各任务的负载信息，HPEE系统使用负载感知任务调度模块来进行优化任务调度。基于任务类型及同类任务的历史负载，该模块使用一种基于历史的任务分配策略将待执行的高负载的任务分配给高频率的核。与此同时，由于历史信息具有部分不精确性，所以该模块进一步使用一种动态的基于偏好的任务窃取策略在运行时均衡负载。实验结果表明，和采用传统随机任务窃取系统相比，负载感知任务调度模块能够减少并行程序82.7%的运行时间。 在支持动态电压频率调节技术的多核架构中，HPEE系统使用高能效负载感知任务调度模块来进行高能效优化任务调度。基于任务类型及同类任务的历史负载，该模块使用一种负载感知频率调节器按照并行程序的负载自动搜索执行该程序所应该使用的最佳频率配置。与此同时，由于历史信息具有部分不精确性，所以该模块进一步使用一个基于偏好的任务调度器来平衡各核间负载。实验表明，高能效负载感知任务调度模块能够在仅轻微降低程序性能的条件下减少能耗高达29.8%（性能损失少于3.7%）。
【学位单位】：上海交通大学
【学位级别】：博士
【学位年份】：2014
【中图分类】：TP332;TP38
【文章目录】：
摘要
ABSTRACT
目录
表格索引
插图索引
第一章 引言
    1.1 并行架构
        1.1.1 多路多核架构
        1.1.2 非对称多核架构
    1.2 任务调度策略/并行编程环境
        1.2.1 手动任务调度策略/编程环境
        1.2.2 自动任务调度策略/编程环境
    1.3 现有任务窃取调度系统
        1.3.1 MIT Cilk
        1.3.2 TBB
        1.3.3 X10
    1.4 HPEE 任务调度系统概述
第二章 缓存感知双层任务窃取模块 (CAB)
    2.1 研究背景
    2.2 研究动机
        2.2.1 问题描述
        2.2.2 解决方案
    2.3 模块设计
    2.4 任务图切分器
        2.4.1 FTO 方案
        2.4.2 GTO 方案
    2.5 双层任务窃取调度器
        2.5.1 任务窃取策略
        2.5.2 任务生成模式
    2.6 时间/空间复杂度分析
        2.6.1 传统任务窃取策略的时间/空间复杂度
        2.6.2 CAB 模块的时间复杂度
        2.6.3 CAB 模块的空间复杂度
    2.7 具体实现
        2.7.1 编译器支持
        2.7.2 运行时系统支持
    2.8 实验验证
        2.8.1 CAB-FTO 的性能
        2.8.2 CAB-GTO 的性能
        2.8.3 可用性讨论
        2.8.4 评测结果总结
    2.9 相关工作
    2.10 本章小结
第三章 位置感知任务窃取模块 (LAWS)
    3.1 研究背景
    3.2 研究动机
    3.3 模块设计
        3.3.1 总体设计
        3.3.2 负载均衡任务分配器
        3.3.3 自动任务图切分器
        3.3.4 三层任务窃取调度器
        3.3.5 理论验证
    3.4 具体实现
    3.5 实验验证
        3.5.1 LAWS 模块的性能
        3.5.2 自动任务图切分器的有效性
        3.5.3 LAWS 模块的可扩展性
        3.5.4 可用性讨论
    3.6 相关工作
    3.7 本章小结
第四章 带宽感知核分配模块 (BWC)
    4.1 研究背景
    4.2 研究动机
        4.2.1 核分配策略简介
        4.2.2 研究动机
    4.3 模块设计
        4.3.1 策略设计
        4.3.2 工作线程管理器
        4.3.3 带宽感知的核分配器
    4.4 具体实现
    4.5 实验验证
        4.5.1 实验平台搭建
        4.5.2 BWC 模块的性能
        4.5.3 BWC 模块的平衡性
        4.5.4 BWC 动态调整的有效性
        4.5.5 BWC 模块的可扩展性
        4.5.6 运行周期长度的影响
        4.5.7 BWC 模块的额外开销
        4.5.8 可用性讨论
    4.6 相关工作
    4.7 本章小结
第五章 负载感知任务调度模块 (WATS)
    5.1 研究背景
    5.2 研究动机
        5.2.1 问题描述
        5.2.2 最优解决方案
        5.2.3 近最优解决方案
    5.3 模块设计
        5.3.1 基于历史的任务分配
        5.3.2 基于偏好的任务窃取
    5.4 具体实现
    5.5 实验验证
        5.5.1 WATS 模块的性能
        5.5.2 基于历史任务分配的可扩展性
        5.5.3 基于偏好任务窃取的有效性
        5.5.4 加入任务抢夺策略
        5.5.5 可用性讨论
    5.6 相关工作
    5.7 本章小结
第六章 高能效负载感知任务调度模块 (EEWA)
    6.1 研究背景
    6.2 研究动机
        6.2.1 问题描述
        6.2.2 解决方案
    6.3 模块设计及实现
        6.3.1 负载感知频率调节器
        6.3.2 基于偏好的任务调度器
    6.4 实验验证
        6.4.1 EEWA 模块的能效
        6.4.2 探测阶段变化的有效性
        6.4.3 EEWA 的额外开销
        6.4.4 EEWA 的可扩展性
        6.4.5 可用性讨论
    6.5 相关工作
    6.6 本章小结
第七章 全文总结
    7.1 研究总结
    7.2 研究展望
参考文献
致谢
攻读学位期间发表的学术论文目录
攻读学位期间参与的项目

【参考文献】

相关期刊论文 前1条

1 陈全;邓倩妮;;云计算及其关键技术[J];计算机应用;2009年09期

本文编号：2842718