多核计算系统中任务的调度和数据分配方法与技术

摘要

随着科学研究规模的不断扩大以及云计算与大数据技术的出现，高性能计算已经从计算密集型向数据密集型转变。庞大的数据对高性能计算提出了更大的挑战，研究人员需要采集与处理海量的数据用于研究与解决复杂的科学计算问题。同时，由于“绿色计算”已经成为一种趋势，如何减少各种计算系统在执行应用时所消耗的资源、能量和预算等成本问题已经成为当前工业界和学术界共同关注和研究的热点。在高性能计算中，任务的调度和数据分配是达到高性能与节能减排的一个关键研究点。任务的调度和数据分配是相互关联的，任务调度会影响其所需数据的放置位置，数据分配会影响其所支持任务的调度节点的位置，不合理的数据放置与任务调度方案容易导致存储访问时间过长，降低任务的吞吐率，影响系统的工作效率。此外，不合理的数据分配与任务放置还会影响系统的能耗及可靠性。因此，对任务的调度和数据分配作为一个不可分割的整体进行研究具有重要的理论价值和实际意义。本文着重于多核环境下的任务的调度和数据分配关键技术的研究，通过合理的任务调度和数据分配使系统总能耗最小化、并行任务总体执行时间缩短、满足应用需求，并能隐藏存储延迟。
　　本文首先研究了多核计算上的嵌套循环应用的调度问题。大多数科学应用与信号处理应用都是循环迭代的，当把这些用于放在多核处理器执行时会面临两方面的挑战。一方面，大多数应用都是计算敏感型和数据敏感型的应用，一个效率低下的调度有可能产生大量的写操作，从而消耗大量时间和能耗;另一方面，由于CPU的执行速度在快速上升，缓慢的存储访问速度降低了系统的整体性能。针对上述问题，本文建立了基于多维循环数据流图(MDFG)任务调度模型，使用高速暂存存储器(SPM)来代替缓存，提出了两层分块调度技术。这种多层分块技术基于预取技术，通过把嵌套循环进行多层分块，从而以块为单位进行调度来减少写操作，并且通过重叠处理器计算与存储访问操作的时间来提高处理器计算的吞吐率和系统的整体性能。模拟实验结果表明，两层分块调度技术与IRP技术相比，可以减少45.35％的写操作以及调度时间可以缩短23.7％。
　　其次，针对分布式共享存储计算系统的计算异构、通信异构和存储异构等特点，本文致力于解决异构数据分配与任务调度（HDATS）的能耗问题，使数据依赖的实时应用在异构分布式共享多核系统中执行时，给每个任务分配一个合适的处理器，把每个数据放置到合适的存储器上，并产生一个高效的调度，使之在满足时间约束的条件下最小化能量消耗。针对HDATS的能耗问题，建立了整数线性规划(ILP)模型来寻求最佳解。然而，整数线性规划模型的复杂度随着应用规模的增大而呈指数级增长，当应用规模较大时，整数规划不能在可接受的时间内得到最佳解。因此，我们提出了TAC-DA与TRGS两种启发式算法来解决该问题。模拟实验结果表明，TAC-DA与TRGS算法能够有效的找到一个近似解，且性能优于greedy算法。
　　再次，本文致力于解决混合存储多核系统上的数据分配与任务调度问题。当数据依赖应用运行在SRAM+NVM混合本地存储的多核计算机时，需要解决下列问题:改善系统能耗、减少NVM的写操作（改善NVM的寿命）以及缩短应用调度时间。为了解决这些问题，本文首先为单核系统提出一种写感知的数据分配算法，然后结合数据分配与任务调度提出EADA与BDAEW两种算法来解决CMP的数据分配与任务调度问题，在保证系统性能满足资源限制的前提下最小化能量消耗。模拟实验结果表明，本文所提出的算法具有优良的性能优势，且优于greedy算法。
　　最后，探讨了内存计算平台中混合内存的高效数据管理方案。针对Flash与PCM具有不同的特征，本文提出一种写意识的数据分配方案，此方法根据数据的大小及读写次数为数据放置到一个合适的存储器来降低能耗与减少不必要的读写操作。为了更有效的管理PCM与flash以及提高PCM与flash的寿命，本文提出BBWL算法来管理PCM上的数据更新与写操作，提出重复使用垃圾回收算法(RGC)来管理flash存储器的无效页。模拟实验表明本文所提出的算法能够有效的改善混合存储器的系统能耗与延长混合内存的寿命。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景

1．1．1 任务调度与数据分配技术发展现状

1．1．2 非易失性存储器

1．2 国内外研究现状

1．2．1 DFG任务调度与资源分配

1．2．2 数据分配与管理

1．2．3 数据分配与任务调度综合研究

1．2．4 存储系统优化

1．3 本文工作

1．4 本文组织结构

第2章 存储感知的多层分块调度技术研究

2．1 引言

2．2 背景知识与定义

2．2．1 结构模型

2．2．2 嵌套循环模型

2．2．3 迭代空间分块与迭代重定时技术

2．2．4 对第一层分块空间进行分块

2．2．5 TLP算法框架

2．3 TLP调度

2．3．1 算法

2．3．2 分块大小

2．4 实验评估

2．5 本章小结

第3章 异构多核系统的能耗感知数据分配与任务调度技术研究

3．1 引言

3．2 模型

3．2．1 结构模型

3．2．2 计算模型

3．2．3 问题定义

3．3 动机实例

3．4 整数线性规划模型

3．4．1 任务分配与处理器约束

3．4．2 数据放置与存储器约束

3．4．3 优先约束

3．4．4 执行时间与访问时间

3．4．5 能量消耗

3．4．6 目标函数

3．5 启发式算法

3．5．1 TAC-DA算法

3．5．2 TRGS算法

3．6 性能评估

3．6．1 实验配置

3．6．2 实验结果及分析

3．7 本章小结

第4章 基于SRAM+NVM混合存储的数据分配与任务调度能量优化技术研究

4．1 引言

4．2 模型

4．2．1 结构模型

4．2．2 计算模型

4．2．3 问题定义

4．3 动机实例

4．4 算法

4．4．1 单核系统的数据分配机制

4．4．2 多核系统的数据分配与任务调度

4．5 性能评估

4．5．1 实验配置

4．5．2 实验结果与分析

4．6 本章小结

第5章 混合内存的高效数据管理方案

5．1 引言

5．2 系统结构为问题定义

5．2．1 系统结构

5．2．2 问题定义

5．3 算法

5．3．1 数据分配方案

5．3．2 PCM的耗损均匀算法

5．3．3 flash的管理

5．4 性能评估

5．4．1 实验配置

5．4．2 性能标准

5．4．3 实验结果与分析

5．5 本章小结

结论

参考文献

攻读学位期间所取得的学术成果

攻读学位期间所参与的科研项目

致谢