(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211122545.0 (22)申请日 2022.09.15 (71)申请人 北京航空航天大 学 地址 100191 北京市海淀区学院路37号 (72)发明人 史晓华　姜胜虎　 (74)专利代理 机构 北京永创新实专利事务所 11121 专利代理师 周长琪 (51)Int.Cl. G06F 8/41(2018.01) G06F 9/48(2006.01) G06N 20/00(2019.01) (54)发明名称 一种基于多面体模型的自动调度生成方法 (57)摘要 本发明提出了一种基于多面体模型的自动 调度生成方法， 涉及计算机、 编译器等领域。 本发 明方法以算子计算描述的多面体模型的实例集 和依赖关系为输入， 对状态进行自动调度， 生成 调度树的过程是一个递归的过程， 每一步可能有 多种优化操作可以进行； 本发明利用机器学习模 型预测调度优化操作的收益， 将进行的各优化操 作预测到的收益的对数和作为调度收益的预测 结果； 根据预测的调度收益选取最优调度， 输出 调度树形式的多面体模型的调度， 用于后端代码 生成。 本发 明方法使用的机器学习模 型只需要进 行预训练， 即可适用不同算子， 与计算方式无关， 在实际的编译期无需再调整， 能加快编译时间， 适应难以定义调度优化的目标或有多个调度优 化目标的场景。 权利要求书1页 说明书5页 附图2页 CN 115469879 A 2022.12.13 CN 115469879 A 1.一种基于多面体模型的自动调度生成方法， 其特 征在于， 包括如下步骤： (1)获取算子计算描述的多面体模型的实例集和依赖关系， 生成状态集S和调度池； 调 度池初始为空； 状态集中每个状态包括算子计算描述和调度树， 调度树初始只包含一个根 节点， 算子计算描述 为多面体模型的实例集和依赖关系； 所述调度树和ISL的调度树的结构一致， 叶节点包含的子问题 的输入信息包括到上一 子节点的实例集、 实例之间的依赖关系、 以及实例计算结果所分配到的内存； 实例集使用 ISL形式化的集 合表示， 依赖关系使用ISL形式化的二元关系表示； ISL表示整数集库； (2)判断状态集S中状态是否都被枚举过， 若否， 取一个没有被枚举过的状态， 继续执行 下一步， 若是， 转下面 步骤(6)执 行； (3)判断当前被枚举到的状态 的调度是否生成完毕， 即该状态所生成的调度树将实例 集完全进 行了调度， 且后续无可进行的优化操作， 若 是， 将该状态所生成的调度放入调 度池 中， 转步骤(7)执 行； 否则， 继续执 行下一步； (4)对状态根据 预先定义的优化操作进行调度优化， 将执行一个或多个优化操作， 将进 行的各优化操作预测到的收益的对数和作为调 度收益的预测结果； 预测的调 度收益将保存 在状态中； 预训练一个机器学习模型， 用于预测优化操作的收益， 该机器学习模 型的输入是 量化的状态； 训练该机器学习模型时， 将硬件理论计算效率与实际生成的算子的计算效率 的比值作为训练样本标注的收益； (5)根据预测的调度收益， 从中选择收益 高的调度执行， 生成新的状态加入状态集T， 预 先设置状态 集T的大小， 当有新的调度收益更高时， 替换掉状态集T中 收益低的调度； 然后转 步骤(2)执 行； (6)用状态集T更新状态集S， 将状态集T初始化为空集， 若状态集S为空， 进入步骤(7)执 行， 否则转 步骤(2)执 行； (7)若状态集S为空， 或者调度池中的调度数量达到预期阈值， 则结束调度生成， 继续执 行下一步， 否则， 转 步骤(2)执 行； (8)根据用户需求， 输出当前调度池中所有的调度， 或者输出预测收益最高的调度； 调 度为调度树形式的多面体模型的调度。 2.根据权利要求1所述的方法， 其特征在于， 所述的方法， 生成调度树的过程， 是在递归 地生成调度， 包括： (a)将已生 成的调度树、 叶节点的子问题的输入信息作为状态， 对每个状 态， 从可进行 的操作中选择预测收益最高的一个或多个操作， 从新生成的状态中保留总 预 测收益最高的多个 状态， (b)对新 生成的状态继续执 行(a)。 3.根据权利要求1所述的方法， 其特征在于， 所述的步骤(3)中， 预先定义的优化操作包 括： 生成ISL的整数仿射， 对状态进 行循环分块操作， 构建调度树的Band节 点； 在确定中间计 算结果的内存分配情况下， 进 行实例集分割的操作， 生成过滤器节点； 为计算结果分配内存 或寄存器， 生成Mark节点； 将输入状态进行向量 化或张量 化。权　利　要　求　书 1/1 页 2 CN 115469879 A 2一种基于多面体模型的 自动调度生成方 法 技术领域 [0001]本发明涉及计算机、 编译器等领域， 具体涉及一种基于多面体模型的自动调度生 成方法。 背景技术 [0002]多面体模型相关的技术在编译优化领域中通常被用于程序的表示、 分析和变换， 比如嵌套循环的变换和优化。 随着深度学习的部署等技术的发展， 多面体模型也被用于深 度学习编译器， 用于深度学习算子的代码生成和调度优化。 [0003]如今， 在深度学习、 高性能计算等领域中， 针对不同的硬件平台， 有很多种加速计 算的手段。 一个常用的手段是将一些计算量大、 比较常用的算子包装成独立的库， 即算子 库， 但这样的手段需要 大量的人力和时间， 对算子在相应的硬件平台上的实现进 行调整、 优 化， 开发和维护的成本都很高， 通用性也比较差， 并且很难支持自定义算子的场景； 另一种 思路是将“计算”和“调度”单独抽象出来， 对不同的算子描述其计算的方式， 并为不同的硬 件平台设计相应的 “调度”； 更进一步地， 则是让 “调度”的生成也自动化起来， 为不同的硬件 或平台设计通用的 “调度”优化流程。 TVM是一款开源的、 端到端的深度学习模型编译框架， 用于优化深度学习模型在CPU、 GPU、 ARM等任意目标环 境下的推理运行速度。 TVM实现从深度 学习模型到算子(硬件上可执行的代码)编译。 TVM中， Tensor  Expression模块是为了能描 述深度学习算子的计算方式； AutoTVM模块需要用户使用TVM的调度 原语来描述算子调度优 化方式， 并提供调度优化参数的范围， 比如分块大小的范围， 然后AutoTVM模块通过自动调 优的方式， 来搜索效果 最好的调度优化的参数。 [0004]“计算”库的建立相对比较轻松， 并且也很适合自定义算子等场景的二次开发， 因 此一些项目已经有了成熟的 “计算”的描述方式和 “计算”库， 并且通常也比较容易转换为多 面体模型的实例集和依赖 关系。 但对于 “调度”生成的自动化， 相关的项目则比较少， 而调度 生成等相关的问题解决起 来也比较困难。 发明内容 [0005]针对上述现有问题， 本发明的目的是提供一种基于多面体模型的自动调度生成方 法， 基于多面体模 型， 实现一种自动的、 相对通用的调度生成技术， 从多面体模型的实例集、 依赖关系等计算相关的信息， 从而生成相 应的调度。 除了通常的编译优化任务会有自动调 度生成的需求， 在深度学习领域 也有相应的需求， 本发明方法可以满足这种需求。 [0006]本发明提供的基于多面体模型的自动调度生成方法， 包括如下步骤： [0007](1)获取算子计算描述的多面体模型的实例集和依赖关系， 生成状态集S和调度 池； 调度池初始 为空； 状态集中每个状态包括算子计算描述和调 度树， 调度树初始只包含一 个根节点， 算子计算描述 为多面体模型的实例集和依赖关系； [0008]所述调度树的结构和ISL(整数集库)的调度树的结构一致， 叶节点的子问题的输 入信息包括到上一子节点的实例集、 实例之间的依赖关系、 以及实例计算结果所分配到的说　明　书 1/5 页 3 CN 115469879 A 3