(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210934594.8 (22)申请日 2022.08.04 (71)申请人 湖南大学 地址 410013 湖南省长 沙市岳麓区麓山 南 路 (72)发明人 李肯立　黄文港　肖正　段明星　 肖国庆　唐卓　周旭　 (74)专利代理 机构 华进联合专利商标代理有限 公司 44224 专利代理师 黄晓庆 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) G06F 9/54(2006.01) G06K 9/62(2022.01) (54)发明名称 基于复制和去冗余的聚类调度方法和装置 (57)摘要 本申请涉及一种基于复制和去冗余的聚类 调度方法、 装置、 存储介质和计算机程序产品， 包 括： 获取处理目标任务的第一处理子队列， 第一 处理子队列中包括目标任务的缩略有向无环 图 的多个任务节 点； 基于缩略有向无环图的任务节 点与目标任务的分区有向无环 图的子任务节点 的对应关系， 将第一处理子队列分解为第二处理 子队列； 获取第二处理子队列中的各子任务节点 的预估完成时间； 发送第一通知信息， 第一通知 信息包括各子任务节点的预估完成时间， 第一通 知信息用于指示执行任务的处理器删除第一目 标子任务节 点， 第一目标子任务节 点为在执行任 务的处理器上的预估完成时间， 晚于第一通知信 息中的预估完成时间的子任务节 点。 采用本方法 能够提高调度效率。 权利要求书3页 说明书17页 附图9页 CN 115168015 A 2022.10.11 CN 115168015 A 1.一种基于复制和去冗余的聚类调度方法， 其特 征在于， 包括： 获取处理目标任务的第 一处理子队列， 所述第 一处理子队列中包括所述目标任务的缩 略有向无环图的多个任务节点； 基于所述缩略有向无环图的任务节点与所述目标任务的分区有向无环图的子任务节 点的对应关系， 将所述第一处理子队列分解为第二处理子队列， 所述第二处理子队列中包 括各所述任务节点对应的多个子任务节点； 获取所述第 二处理子队列中的各所述子任务节点的预估完成时间， 任意一个子任务节 点的所述预估完成时间， 为所述第二处理子队列中的所述子任务节点的前相 邻子任务节点 的预估完成时间， 与所述子任务节点的预估处 理时间的和值； 发送第一通知信息， 所述第一通知信息包括各所述子任务节点的所述预估完成时间， 所述第一通知信息用于指示执行任务的处理器删除第一目标子任务节点， 所述第一目标子 任务节点为在所述执行任务的处理器上的预估完成时间， 晚于所述第一通知信息中的预估 完成时间的子任务节点。 2.根据权利要求1所述的方法， 其特征在于， 所述获取处理目标任务的第一处理子队 列， 包括： 获取所述目标任务的缩略有向无环图； 对所述缩略有向无环图中的任务节点进行划分， 获得两个以上的队列； 将所述两个以上的队列中的其中一个队列， 确定为所述第一处 理子队列。 3.根据权利要求2所述的方法， 其特征在于， 所述对所述缩略有向无环图中的任务节点 进行划分， 获得两个以上的队列， 包括： 若所述缩略有向无环图中存在多个叶子任务节点， 将各所述叶子任务节点分别分配在 第一队列中， 各 所述叶子任务节点 为出度为0的任务节点； 确定各所述叶子任务节点对应的关键前驱任务节点， 以及对应的所述关键前驱任务节 点的多个前驱任务节 点， 并将对应的所述关键前驱任务节点以及对应的所述关键前驱任务 节点的多个前驱任务节点分配在对应的所述第一队列中； 若所述缩略有向无环图中不存在叶子任务节点， 获取所述缩略有向无环图中未分配队 列的多个任务节点； 将未分配处理队列的各所述任务节点分配在第 二队列中； 所述两个以上的队列包括所 述第一队列以及所述第二队列。 4.根据权利要求3所述的方法， 其特征在于， 所述确定所述叶子任务节点的关键前驱任 务节点， 包括： 计算所述叶子任务节点的多个前驱任务节点的最早完成时间； 所述最早完成时间为各 所述前驱任务节点的最早开始时间与各所述前驱任务节点的预估处理时间的和值， 所述最 早开始时间为各 所述前驱任务节点的多个前驱任务节点的最晚完成时间； 将各所述前驱任务节点中的最早完成时间最大的前驱任务节点， 确定为所述关键前驱 任务节点。 5.根据权利要求1所述的方法， 其特征在于， 所述获取处理目标任务的第一处理子队 列， 包括： 接收目标处理器发送的所述第一处理子队列； 其中， 所述第一处理子队列为所述目标权　利　要　求　书 1/3 页 2 CN 115168015 A 2处理器获取所述目标任务的缩略有向无环图， 对所述缩略有向无环图中的任务节点进 行划 分， 获得的两个以上的队列中的其中一个队列。 6.根据权利要求1所述的方法， 其特 征在于， 所述方法还 包括： 接收第二通知信 息， 所述第 二通知信 息包括执行任务的处理器执行的处理子队列中的 各子任务节点的预估完成时间； 确定是否存在第 二目标子任务节点， 所述第 二目标子任务节点为所述第 二处理子队列 中， 预估完成时间晚于所述第二 通知信息中的预估完成时间的子任务节点； 若存在所述第二目标子任务节点， 删除所述第二处理子队列中的第二目标子任务节 点， 获得更新后的第二处 理子队列。 7.根据权利要求6所述的方法， 其特 征在于， 所述方法还 包括： 获取更新后的所述第二处 理子队列中的各 所述子任务节点的预估完成时间； 发送第三通知信 息， 所述第 三通知信 息包括更新后的所述第 二处理子队列中的各所述 子任务节点的预估完成时间， 所述第三通知信息用于指示执行任务的处理器删除第三目标 子任务节点， 所述第三 目标子任务节点为在所述执行任务的处理器上 的预估完成时间， 晚 于所述第三 通知信息中的预估完成时间的子任务节点。 8.一种基于复制和去冗余的聚类调度方法， 其特 征在于， 包括： 向任务处理器发送 处理目标任务的第 一处理子队列； 所述第 一处理子队列中包括所述 目标任务的缩略有向无环图的多个任务节点； 接收第一通知信 息； 所述第 一通知信 息包括所述任务处理器的第 二处理子队列中的各 所述子任务节点的预估完成时间， 所述第二处理子队列为所述任务处理器基于所述缩略有 向无环图的任务节点与所述目标任务的分区有向无环图的子任务节点的对应关系， 对所述 第一处理子队列分解得到的； 向目标任务处理器发送所述第 一通知信 息， 所述目标任务处理器至少包括与 所述第二 处理子队列存在至少一个相同的子任务节点的任务处理器， 所述第一通知信息用于指示所 述目标任务处理器删除第一目标子任务节点， 所述第一目标子任务节点为在所述目标任务 处理器上的预估完成时间， 晚于所述第一 通知信息中的预估完成时间的子任务节点。 9.一种基于复制和去冗余的聚类调度装置， 其特 征在于， 包括： 队列获取模块， 用于获取处理目标任务的第一处理子队列， 所述第一处理子队列中包 括所述目标任务的缩略有向无环图的多个任务节点； 队列分解模块， 用于基于所述缩略有向无环图的任务节点与 所述目标任务的分区有向 无环图的子任务节点的对应关系， 将所述第一处理子队列分解为第二处理子队列， 所述第 二处理子队列中包括各 所述任务节点对应的多个子任务节点； 时间获取模块， 用于获取所述第二处理子队列中的各所述子任务节点的预估完成时 间， 任意一个子任务节点的所述预估完成时间， 为所述第二处理子队列中的所述子任务节 点的前相邻子任务节点的预估完成时间， 与所述子任务节点的预估处 理时间的和值； 处理模块， 用于发送第一通知信息， 所述第一通知信息包括各所述子任务节点的所述 预估完成时间， 所述第一通知信息用于指示执行任务的处理器删除第一 目标子任务节点， 所述第一目标子任务节点为在所述执行任务的处理器上的预估完成时间， 晚于所述第一通 知信息中的预估完成时间的子任务节点。权　利　要　求　书 2/3 页 3 CN 115168015 A 3