(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 202011120020.4
(22)申请日 2020.10.19
(71)申请人 上海交通大学
地址 200240 上海市闵行区东川路800号
(72)发明人 骆源 伏开宇
(74)专利代理机构 上海汉声知识产权代理有限
公司 31236
代理人 胡晶
(51)Int.Cl.
G06F 9/48(2006.01)
G06N 3/12(2006.01)
(54)发明名称
度系统及方法
(57)摘要
本发明提供了一种基于遗传算法和计算拓
M1：根据并行任务各个子任务所需要的处理时间
所构成的向量X、每个节点的数据处理能力组成
模型；模块M2：将并行任务各个子任务之间的依
赖关系以及各个任务所需要的完成时间通过遗
传算法得到次优调度方案；模块M3：将得到的次
优调度方案通过计算拓扑模型得到任务调度方
案，根据任务调度方案得到各个任务所需要的完
成时间，重复触发模块M2至模块M3，直至迭代次
数达到预设次数，得到最优SKA任务调度方案。本
发明输入简单，用户可以方便快捷地构造任务依
赖拓扑图文件，
然后将其作为算法的输入。权利要求书2页 说明书9页 附图1页CN 112199177 A 2021.01.08
C N 112199177
A
1.一种基于遗传算法和计算拓扑模型的SKA任务调度系统，其特征在于，包括：
模块M1：服务器根据并行任务各个子任务所需要的处理时间构成向量X，根据CPU核心数得到每个节点的数据处理能力，将每个节点的数据处理能力组成向量Y，根据向量X、向量Y以及并行任务分配方案A，构建计算拓扑模型；
模块M2：服务器将并行任务各个子任务之间的依赖关系以及各个任务所需要的完成时间通过遗传算法得到次优调度方案；
模块M3：服务器将得到的次优调度方案通过计算拓扑模型得到任务调度方案，根据任务调度方案得到各
个任务所需要的完成时间，重复触发模块M2至模块M3执行，直至迭代次数达到预设次数，得到最优SKA任务调度方案，根据最优SKA任务调度方案对并行任务进行调度。
2.根据权利要求1所述的基于遗传算法和计算拓扑模型的SKA任务调度系统，其特征在于，所述模块M1中计算拓扑模型包括：
Y≈AX (1)
Y max≥AX (2)
其中，Y表示每个节点的数据处理能力组成的向量Y；A表示并行任务分配方案用0-1矩阵表示；X表示每个任务需要的处理时间所构成的向量。
3.根据权利要求1所述的基于遗传算法和计算拓扑模型的SKA任务调度系统，其特征在于，所述模块M2中并行任务各个子任务之间的依赖关系包括：将SKA天文计算管线任务按照依赖关系拆分成DAG图，SKA天文计算管线子任务是DAG图每个任务节点，并对DAG图以预设格式进行描述，输入遗传算法。
4.根据权利要求3所述的基于遗传算法和计算拓扑模型的SKA任务调度系统，其特征在于，所述模块M2包括：
模块M2.1：将SKA天文计算任务的每个子任务根据各自的高度划分到不同的集合G(h)，令NG(h)表示为G(h)的元素个数，生成一个介于0到NG(h)中的随机数r，从集合G(h)中随机挑选出r个子任务，将挑选出的r个子任务移出集合，并将r个子任务分配给当前的节点执行，获得合法的SKA管线计算任务的任务调度方案；重复触发模块M2.1执行，直至得到预设量的任务调度方案的SKA管线任务的次优调度方案。
5.根据权利要求3所述的基于遗传算法和计算拓扑模型的SKA任务调度系统，其特征在于，所述模块M3包括：
模块M3.1：将SKA管线任务的次优调度方案，通过通过计算拓扑模型，基于Y max≥AX约束，得到SKA计算任务调度方案；
模块M3.2：根据SKA计算任务调度方案和任务的执行顺序拓扑图，将同一个处理器上的SKA任务压缩为一个点，并且去除重复边。
6.一种基于遗传算法和计算拓扑模型的SKA任务调度方法，其特征在于，包括：
步骤M1：服务器根据并行任务各个子任务所需要的处理时间构成向量X，根据CPU核心数得到每个节点的数据处理能力，将每个节点的数据处理能力组成向量Y，根据向量X、向量Y以及并行任务分配方案A，构建计算拓扑模型；
步骤M2：服务器将并行任务各个子任务之间的依赖关系以及各个任务所需要的完成时间通过遗传算法得到次优调度方案；
步骤M3：服务器将得到的次优调度方案通过计算拓扑模型得到任务调度方案，根据任务调度方案得到各个任务所需要的完成时间，重复触发模块M2至模块M3执行，直至迭代次数达到预设次数，得到最优SKA任务调度方案，根据最优SKA任务调度方案对并行任务进行调度。
7.根据权利要求6所述的基于遗传算法和计算拓扑模型的SKA任务调度方法，其特征在于，所述步骤M1中计算拓扑模型包括：
Y≈AX (1)
Y max≥AX (2)
其中，Y表示每个节点的数据处理能力组成的向量Y；A表示并行任务分配方案用0-1矩阵表示；X表示每个任务需要的处理时间所构成的向量。
8.根据权利要求6所述的基于遗传算法和计算拓扑模型的SKA任务调度方法，其特征在于，所述步骤M2中并行任务各个子任务之间的依赖关系包括：将SKA天文计算管线任务按照依赖关系拆分成DAG图，SKA天文计算管线子任务是DAG图每个任务节点，并对DAG图以预设格式进行描述，输入遗传算法。
9.根据权利要求8所述的基于遗传算法和计算拓扑模型的SKA任务调度方法，其特征在于，所述步骤M2包括：
步骤M2.1：将SKA天文计算任务的每个子任务根据各自的高度划分到不同的集合G(h)，令NG(h)表示为G(h)的元素个数，生成一个介于0到NG(h)中的随机数r，从集合G(h)中随机挑选出r个子任务，将挑选出的r个子任务移出集合，并将r个子任务分配给当前的节点执行，获得合法的SKA管线计算任务的任务调度方案；重复执行步骤M2.1，直至得到预设量的任务调度方案的SKA管线任务的次优调度方案。
10.根据权利要求8所述的基于遗传算法和计算拓扑模型的SKA任务调度方法，其特征在于，所述步骤M3包括：
步骤M3.1：将SKA管线任务的次优调度方案，通过通过计算拓扑模型，基于Y max≥AX约束，得到SKA计算任务调度方案；
步骤M3.2：根据SKA计算任务调度方案和任务的执行顺序拓扑图，将同一个处理器上的SKA任务压缩为一个点，并且去除重复边。
基于遗传算法和计算拓扑模型的SKA任务调度系统及方法
技术领域
[0001]本发明涉及大数据领域，具体地，涉及一种基于遗传算法和计算拓扑模型的SKA任务调度系统及方法，更为具体地，涉及一种针对平方公里阵列(SKA)射电天文望远镜通过遗传算法和计算拓扑模型到一种优化的任务调度方案。
背景技术
[0002]随着数据收集和存储技术的发展，人类已经积累了大量的天文观测数据。在天文学领域，图像在这些数据中占据着越来越大的比重。因此，寻最适合天文图像大数据处理的框架至关重要，而天文图像处理系统的目的则是通过提供可扩展和高效的数据存储和分析手段，帮助天文学家轻松使用编程模型。
[0003]平方公里阵列(SKA)是下一代望远镜，它将会产生世界上最大的数据量，其参与国家包括中国，澳大利亚，加拿大，意大利，新西兰，荷兰，南非，英国等。该项目预计总投资20亿美元。SKA项目的初衷是21世纪的宇宙论仍然有许多基本问题需要解决，如基本粒子的性质和基本力，宇宙的形成和演化以及暗物质的起源。因此，为了便于天文学家进一步观察早期宇宙的结构，需要建立更高灵敏度和探测速度的望远镜，SKA就是其中之一。SKA由数千个无线电波接收器和天线组成。这些设备连接到近1平方公里的接收区，使SKA成为历史上规模最大，最灵敏的射电望远镜。
[0004]在以往的天文学观测模式中，一般都会有一个专家团队的工程师在专用服务器上处理收集的图像，
再将其结果提炼成文本目录以供其他天文学家分析。相反，SKA的目标之一是为全球的天文学家提供对图像的直接接触，使得他们能够自行地对图像进行分析而不需要借助额外的计算机工程团队的帮助。这个案例强调需要有效的系统来支持图像数据的管理和分析：高效，易扩展且易于编程的系统，无需深入的系统专业知识进行部署和调整。令人惊讶的是，目前围绕支持大规模图像管理和分析的系统构建所进行的研究工作相当有限。Ras-daman和SciDB是两个众所周知的DBMS(数据库管理系统)，专门用于存储和处理多维数组数据，经常用作图像分析。除了这些系统之外，为存储图像数据而开发的大多数其他工作主要针对基于关键字或相似性搜索的图像存储和检索。
[0005]除此之外，现如今许多数据流作业都是计算密集型和数据密集型的。例如，天文数据流应用程序产生大量的数据，并且需要巨大的计算能力来处理数据。传统上，高性能计算(HPC)设施针对处理这种计算密集型科学应用进行了优化。但是，它们不适合处理数据密集型工作负载。天文数据流管线的一个重要特征是管线既是数据密集型又是计算密集型。例如，对于SKA low，需要超过1TB/s的I/O和3PFLOPS/s的计算能力，这对计算架构和执行框架构成了巨大挑战。为了应对SDP(科学数据处理)数据流管道的巨大挑战并确其正确功能，主要研究当前成熟的SKA-SDP管道商用系统。
[0006]对于目前已有的一些大数据框架例如Spark，Flink或者Storm等等，他们普遍针对的是一些数据密集型的场景，对于科学界特别是天文界这种计算密集型的任务并不能完全契合。他们普遍的一个特点就是所有的任务的调度都是完全流水线化的，即每个任务每个
阶段的触发顺序都是相同的，完全不需要针对任务的调度顺序有任何规划。对于一个通用框架来说这样做可以简化整个程序的任务调度，并且有较不错的性能，是可以接受的。但是这种方案因为其固定的调度顺序，没有考虑到不同场景下不同任务的特性，做到因地制宜，所以其并不是一个最优解。对于天文界的海量数据，即使是微小的性能差异也能产生巨大的影响。而如果对于每个任务我们都穷尽每一种调度方式从中到最优解，那这个计算量也是目前的算力所不能承受的。所以当前的环境下，我们需要的是一个能够自动化到并行任务调度方案的启发式算法，这个算法不一定需要到最优的调度方案，只要能够在可以接受的时间内到一个次优方案即可。于是我们的基于遗传算法和计算拓扑模型的任务调度算法应运而生。
[0007]专利文献CN102508708A(申请号：201110386958.5)公开了一种基于改进遗传算法的异构多核节能任务调度方法，它由用来确定任务优先级的改进遗传算法以及基于缩放优先级的节能调度算法组成，其流程为：(1)进行种信息初始化；(2)进入循环体通过遗传算法确定任务优先级；(3)根据任务DAG图和划分策略，确定任务在处理器上的调度顺序；(4)根据任务节省能量与延长时间之间的关系，在可行的任务调度基础上进行动态电压缩放；
(5)计算当前体适应度并排序；(6)采用改进的遗传算法对种进行更新，确定新的任务优先级，如果满足终止条件则退出，否则继续迭代。
发明内容
[0008]针对现有技术中的缺陷，本发明的目的是提供一种基于遗传算法和计算拓扑模型的SKA任务调度系统及方法。
[0009]根据本发明提供的一种基于遗传算法和计算拓扑模型的SKA任务调度系统，包括：[0010]模块M1：服务器根据并行任务各个子任务所需要的处理时间构成向量X，根据CPU 核心数得到每个节点的数据处理能力，将每个节点的数据处理能力组成向量Y，根据向量X、向量Y以及并行任务分配方案A，构建计算拓扑模型；
[0011]模块M2：服务器将并行任务各个子任务之间的依赖关系以及各个任务所需要的完成时间通过遗传算法得到次优调度方案；
[0012]模块M3：服务器将得到的次优调度方案通过计算拓扑模型得到任务调度方案，根据任务调度方案得到各个任务所需要的完成时间，重复触发模块M2至模块M3执行，直至迭代次数达到预设次数，得到最优SKA任务调度方案，根据最优SKA任务调度方案对并行任务进行调度。
[0013]优选地，所述模块M1中计算拓扑模型包括：
[0014]Y≈AX (1)
[0015]Y max≥AX (2)
[0016]其中，Y表示每个节点的数据处理能力组成的向量Y；A表示并行任务分配方案用0-1矩阵表示；X表示每个任务需要的处理时间所构成的向量。
[0017]优选地，所述模块M2中并行任务各个子任务之间的依赖关系包括：将SKA天文计算管线任务按照依赖关系拆分成DAG图，SKA天文计算管线子任务是DAG图每个任务节点，并对DAG图以预设格式进行描述，输入遗传算法。
[0018]优选地，所述模块M2包括：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议