面向SKA科学数据处理的调度策略研究

论文摘要

目前处于建设状态中的平方公里阵列(Square Kilometer Array,SKA)将建成为世界最大规模的射电望远镜阵列,并用于进行一系列天文相关的科学研究。其观测数据处理系统称为SDP(Science Data Processor)。由于观测数据庞大,单一的计算中心无法承受如此庞大的数据计算与存储压力,因此需将计算任务分流至下属计算节点,以分布式计算的方式解决此问题。这样一来,自然就产生了计算任务的调度分配问题。而计算任务之间存在依赖,造成了当两个相关的计算任务被分配到不同的计算节点时会需要进行一定量的信息交换,这种信息交换我们称为边通信。本文将边通信纳入考量,对SDP的调度算法进行了研究,并通过实验验证其可行性与有效性。待调度的全部任务集使用DAG(Directed Acyclic Graph)表示,任务集整体执行时间称为makespan,调度的目标在于减少整体执行时间。目前的算法的缺陷在于没有将边通信作为约束条件纳入考虑。虽然现有主要调度方法也是基于DAG,但是主要考虑DAG中每个节点的计算任务复杂度,基本忽略节点之间的海量通信的影响。边通信在实际的调度过程中是不可忽略的,并且往往对调度结果存在较大的影响。本文将针对目前调度算法没有考虑边通信成本这点,进行改进。本文着眼于边通信代价,改进了轮询算法,对不同边通信场景下调度算法展开了讨论。对于同属实时调度系统的IMA(Integrated Modular Avionics)中的分区调度,本文展开了研究,并基于两个场景的相似性设计了面向周期性观测数据场景的调度算法。以边通信成本的大小划分了轻边通信场景与重边通信场景,并对于这些场景提出了修正路径算法与边通信路径算法。轻边通信场景示例中,我们使用DAG边的数量为节点数量10%,边通信成本为上游节点权重的百分之八到十的样本进行了实验。结果表明,修正路径算法相对于轮询调度算法对makespan的降低平均达到21.12%;修正路径算法相对于关键路径算法使makespan平均降低了10.85%。重边通信场景的示例中,我们使用到的DAG边的数量为节点数量的百分之五十,边的权重为上游节点权重的百分之五十到八十。边通信路径算法相对于轮询算法对于makespan的降低平均达到31.88%;相对于关键路径算法对于makespan的降低平均达到20.86%;相对于修正路径算法,边通信算法对makespan平均降低为15.34%。综上实验结果,我们提出的算法对不同场景下的makespan有一定的降低。之后本文讨论了不同场景的划分,并对不同特性的输入数据展开实验,讨论了适用于不同场景的算法。通过实验,我们划分了轻边通信场景和重边通信场景。对于边权重较大,占上游节点权重的55%及以上,边的数量占节点数量的比例较大的数据集,使用边通信路径算法能得到比较好的makespan。对于边权重较小,占上游节点权重的30%及以下且边的数量占节点数量的比例较小的场景,使用修正路径算法能得到比较好的makespan。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景与意义
•   1.2 研究现状与不足
•   1.3 论文组织与章节安排
•     1.3.1 论文研究内容与重难点
•     1.3.2 论文章节安排
• 第二章 面向大规模数据流调度的基本原理与模型描述
•   2.1 基本调度结构与调度过程
•     2.1.1 基本概念
•     2.1.2 接收与预处理流水线
•   2.2 数据流调度方法
•   2.3 大规模数据调度问题描述
•   2.4 本章小结
• 第三章 面向大规模数据流调度方法研究设计
•   3.1 边通信为0的调度场景
•     3.1.1 分区调度研究背景与问题描述
•     3.1.2 分区调度研究现状与不足
•     3.1.3 分区调度算法设计
•     3.1.4 分区调度与SKA调度场景联系
•     3.1.5 周期性观测数据场景下调度算法
•   3.2 轮询调度调度方法
•   3.3 轻边通信成本场景的修正路径算法
•   3.4 重边通信成本场景的边通信路径算法
•   3.5 本章小结
• 第四章 边通信调度的实验数据处理与调度实现
•   4.1 实验数据的获取与模型的构建
•     4.1.1 输入DAG任务节点的构建
•     4.1.2 输入DAG边与边的权重的构建
•     4.1.3 实验的标准输入格式
•   4.2 算法仿真工具与实现技术细节
•     4.2.1 算法仿真工具
•     4.2.2 含边通信成本的调度过程仿真实现细节
•     4.2.3 调度算法实现细节
•   4.3 本章小结
• 第五章 实验结果与分析
•   5.1 分区调度算法与周期性观测数据调度实验结果
•     5.1.1 分区调度实验结果
•     5.1.2 周期性观测数据实验结果
•   5.2 轮询算法实验结果
•   5.3 修正路径算法实验结果
•   5.4 边通信路径算法结果
•   5.5 边通信场景划分
•   5.6 本章小结
• 第六章 总结与展望
•   6.1 主要工作与创新点
•   6.2 后续研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文
• 攻读学位期间参与的项目

文章来源

类型: 硕士论文

作者: 薛琪渲

导师: 祝永新

关键词: 平方公里阵列,调度,边通信,边通信场景

来源: 上海交通大学

年度: 2019

分类: 基础科学

专业: 天文学

单位: 上海交通大学

基金: 国家重点研发计划项目“SKA科学数据处理试验验证系统研制”(2016YFE0100600)

分类号: P111.44

DOI: 10.27307/d.cnki.gsjtu.2019.000661

总页数: 88

文件大小: 5522K

下载量: 7