(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210350072.3 (22)申请日 2022.04.02 (71)申请人 合肥工业大 学 地址 230000 安徽省合肥市合肥屯溪路193 号 (72)发明人 张多利　王杰　葛虎　曾树铭　 王宇　宋宇鲲　 (74)专利代理 机构 北京律谱知识产权代理有限 公司 11457 专利代理师 孟德洲 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) (54)发明名称 一种可区域扩展重映射的动态任务调度方 法 (57)摘要 本申请公开了一种可区域扩展重映射的动 态任务调度方法， 包括： 步骤100： 确定执行后续 任务的预映射节点及链路； 步骤200， 当判定预映 射节点占用或链路拥塞时， 确定待重映射任务， 对待重映射任务进行重映射， 并判断重映射后的 待重映射任务对应的映射链路与预映射链路之 间是否链路相关， 若否， 更新并上传预映射链路， 若是， 执行步骤300， 将链路相关的预映射链路对 应的后继任务进行重映射， 当判定后继任务均对 应一条不相关的预映射链路时， 上传预映射链路 对应的节点坐标， 否则， 执行步骤400， 选取中继 节点为新的源节点， 重新对链路相关的待重映射 任务进行映射， 执行步骤300。 实现了扩大任务调 度的搜索映射空间的目的， 提升异构多核处理器 系统的计算 性能。 权利要求书1页 说明书9页 附图6页 CN 114880085 A 2022.08.09 CN 114880085 A 1.一种可区域扩展重映射的动态任务调度方法， 其特 征在于， 所述方法包括： 步骤100： 根据异构多核处理器系统中各节点的网路布局， 对后继任务进行预映射， 通 过预映射方式， 检测 确定执行所述后续任务的预映射节点， 并标记对应的预映射链路； 步骤200， 启动拥塞感知算法， 当判定所述预映射节点被占用或者所述预映射链路存在 拥塞时， 根据拥塞的预映射链路或者被占用的预映射节点， 确定待重映射任务， 对所述待重 映射任务进行重映射， 并判断重映射后的待重映射任务对应的映射链路与所述预映射链路 之间是否链路相关， 若否， 根据所述映射链路更新预映射链路， 并上传更新后的预映射链路 对应的节点 坐标， 若是， 执 行步骤300； 步骤300， 将链路相关的预映射链路对应的后继任务进行重映射， 重 复执行步骤200， 对 链路相关进行检测， 当判定后继任务均对应一条不相关的预映射链路时， 上传预映射链路 对应的节点 坐标， 否则， 执 行步骤40 0； 步骤400， 以所述源节点SRC为中心， 选取中继节点， 并以所述中继节点为新的源节点 SRC， 重新对链路相关的待重映射任务进行映射， 并执 行步骤300。 2.如权利要求1所述的可区域扩展重映射的动态任务调度方法， 其特征在于， 所述后继 任务为下一时刻需要执 行且任务状态为 “计算完成、 数据未发出 ”的任务。 3.如权利要求1所述的可区域扩展重映射的动态任务调度方法， 其特征在于， 所述后继 任务的预映射链路 由源节点SRC、 有限跳数以及后继任务信息确定， 其中， 所述后继任务信 息用于确定执 行所述后继任务的节点 坐标信息、 方位信息 。 4.如权利要求1所述的可区域扩展重映射的动态任务调度方法， 其特征在于， 所述步骤 200中， 所述待重映射任务包括： 当前进行预调度的后继任务仅能由已预映射任务的目的节点DST执行时的已预映射任 务， 或者， 具有相同的拥塞预映射链路的已预映射任务。 5.如权利要求4所述的可区域扩展重映射的动态任务调度方法， 其特征在于， 所述待重 映射任务还包括： 与当前进行预调 度的后继任务的链路存在链路相关的链路对应的已预映 射任务， 所述 步骤200中还包括： 当判定所述待重映射任务仅能由与执行所述当前进行预调度的后继任务的目的节点 DST执行时， 执行步骤40 0。 6.如权利要求1所述的可区域扩展重映射的动态任务调度方法， 其特征在于， 所述选取 中继节点， 具体包括： 以源节点SRC为X ‑Y坐标原点， 以有限跳数为距离， 选取XY轴上状态为空闲的节点作为 所述中继节点， 或者， 以源节点SRC为中心点， 以有限跳数为曼哈顿距离， 构建菱形区域， 选取所述菱形区域 边界上状态为空 闲的节点作为所述中继节点， 或者， 以源节点SRC为中心点， 以有限跳数为曼哈顿距离， 构建菱形区域， 选取所述菱形区域 内状态为空 闲的节点作为所述中继节点。权　利　要　求　书 1/1 页 2 CN 114880085 A 2一种可区域扩展重映射的动态任务调度方 法 技术领域 [0001]本申请涉及多核微处理器任务调度的技术领域， 具体而言， 涉及一种可区域扩展 重映射的动态任务调度方法。 背景技术 [0002]随着计算机技术和微电子技术的快速发展， 具有多个计算内核的微处理器， 即多 核处理器应运而生， 多核处理器分为同构多核处理器和异构多核处理器， 其中， 异构多核处 理器在一块芯片上集成了多个不同结构的内核， 因此， 异构多核处理器可依据任务特性将 其任务分配至适 合的处理内核进行处理。 [0003]在异构多核处理器系统中， 如何充分利用性能不 同的处理器资源， 采用何种任务 分配策略对这些资源进行管理， 如何实现处理器资源的自动调节和负载均衡， 同时又保持 任务分配的灵活性、 可塑性， 是异构多核环境下资源调度和管理的关键问题， 这将对充分利 用处理器资源， 发挥 异构多核处理器系统的特点具有极其重要的意 义。 [0004]而现有技术中， 针对于解决异构多核处理器系统任务调度问题的方法主要分为两 大类， 其一是静态任务调度技术， 其二是动态调度技术。 在此类任务调度技术中， 任务执行 之前通常需要利用调度算法对任务进 行了分配， 但是没有对任务调 度空间进 行大范围的搜 索， 导致任务映射链路可能存在拥堵的情况， 同时存在无法获得局部最优或者全局 最优的 映射链路， 导 致任务链路具有一定的局限性， 进 而影响了异构多 核系统的计算 性能。 发明内容 [0005]本申请的目的在于： 如何扩大任务调度的搜索映射空间， 通过动态生成任务 映射 链路的方式， 提升异构多 核处理器系统的计算 性能。 [0006]本申请的技术方案是： 提供了一种可区域扩展重映射的动态任务调度方法， 该方 法包括： 步骤100： 根据异构多核处理器系统中各节点的网路布局， 对后继任务进 行预映射， 通过预映射方式， 检测确定执行后续任务的预映射节点， 并标记对应的预映射链路； 步骤 200， 启动拥塞感知算法， 当判定预映射节点被占用或者预映射链路存在拥塞时， 根据拥塞 的预映射链路或者被占用的预映射节 点， 确定待重映射任务， 对待重映射任务进 行重映射， 并判断重映射后的待重映射任务对应的映射链路与预映射链路之间是否链路相关， 若否， 根据映射链路更新预映射链路， 并上传更新后的预映射链路对应的节点坐标， 若 是， 执行步 骤300； 步骤300， 将链路相关的预映射链路对应的后继任务进行重映射， 重复执行步骤200， 对链路相关进行检测， 当判定后继任务均对应一条不相关的预映射链路时， 上传预映射链 路对应的节 点坐标， 否则， 执行步骤400； 步骤400， 以源节 点SRC为中心， 选取中继节 点， 并以 中继节点 为新的源节点SRC， 重新对链路相关的待重映射任务进行映射， 并执 行步骤300。 [0007]上述任一项技术方案中， 进一步地， 后继任务为下一时刻需要执行且任务状态为 “计算完成、 数据未发出 ”的任务。 [0008]上述任一项技术方案中， 进一步地， 后继任务的预映射链路由源节点SRC、 有限跳说　明　书 1/9 页 3 CN 114880085 A 3