一种基于差分约束系统与迭代模的高层次综合调度方法

摘要

本发明公开了一种基于差分约束系统与迭代模的高层次综合调度方法，其特征在于，包括：获取输入的电路描述后构建对应的控制数据流图；将控制数据流图划分为循环部分和非循环部分；采用迭代模调度算法对控制数据流图的循环部分进行调度；采用差分约束系统调度算法对控制数据流图的非循环部分进行调度；对得到的调度结果进行数学整合后，获得综合调度结果。本发明对高层次综合的调度流程进行了优化，提高了调度性能，而且调度实现过程方便、快速，可以全面、及时地实现调度，调度效率高，可广泛应用于高层次综合调度领域中。

说明书

技术领域

本发明涉及一种高层次综合调度方法，特别是一种基于差分约束系统与迭代 模的高层次综合调度方法。

背景技术

高层次综合的目标是在目标集合中得到一个满足既定的数字系统的算法级 行为描述、约束条件等条件的基础上的结构结果。高层次综合流程包括：编译与 转换、算子调度、资源分配、寄存器分配、连线网络生成与优化。其中，算子调 度即调度算法是为编译转换生成的控制数据流图中的每一个操作和运算分配到 各个控制步，从而实现满足约束条件下的最优或较优算子调度方案，是高层次综 合流程中最为重要的一个步骤。高层次调度方法中基本分为两类，一类是循环调 度，一类是非循环调度，目前的高层次调度方法中，并没有明确地对这两种情况 进行区分，都是采用现有技术中的构造法、变换法或整数线性规划法等方法进行 调度，调度过程较为复杂，而且无法及时、全面地进行调度，调度效率低，渐渐 不能满足集成电路设计的发展需求。

发明内容

为了解决上述的技术问题，本发明的目的是提供一种基于差分约束系统与迭 代模的高层次综合调度方法。

本发明解决其技术问题所采用的技术方案是：

一种基于差分约束系统与迭代模的高层次综合调度方法，包括：

S1、获取输入的电路描述后构建对应的控制数据流图；

S2、将控制数据流图划分为循环部分和非循环部分；

S3、采用迭代模调度算法对控制数据流图的循环部分进行调度；

S4、采用差分约束系统调度算法对控制数据流图的非循环部分进行调度；

S5、对步骤S3和S4中得到的调度结果进行数学整合后，获得综合调度结 果。

进一步，所述步骤S2，包括：

S21、使用深度优先算法对控制数据流图中的所有操作节点进行排序；

S22、采用支配图迭代算法将排序后的控制数据流图的节点构建成对应的支 配树；

S23、检测提取支配树中的所有回边后，获取由回边构成的所有回路作为控 制数据流图的循环部分，进而获得控制数据流图的非循环部分。

进一步，所述步骤S3，包括：

S31、对控制数据流图的循环部分进行最小迭代启动间隔时间计算；

S32、将计算得到的最小迭代启动间隔时间作为初始的迭代启动间隔时间， 使用列表调度算法对控制数据流图的循环部分进行调度；

S33、迭代进行调度尝试直到满足以下条件时，继续执行步骤S34：调度成 功或者调度的迭代尝试次数大于预设上限阈值；

S34、判断是否调度完毕，若是，则结束，反之增加迭代启动间隔时间后， 继续使用列表调度算法进行下一轮调度，并返回执行步骤S33。

进一步，所述步骤S4，包括：

S41、对控制数据流图的非循环部分的节点构建相应的调度变量；

S42、根据调度变量，将所有调度约束都转化为对应的差分约束公式后，将 获得的所有差分约束公式转化成整形规划矩阵；

S43、根据高层次综合的需求结果，构建相应的目标函数；

S44、将整形规划矩阵作为目标函数的约束条件，进行线性规划求解，判断 是否能求解获得目标函数的最优值，若否，则返回执行步骤S43，反之获得该目 标函数的最优值，同时获得对应的整形规划矩阵的值，进而获得每个节点的调度 值。

进一步，所述步骤S42中所述调度约束包括依赖约束、时序约束以及资源约 束。

进一步，所述依赖约束包括由电路描述中的数据依赖性引起的数据依赖约束 以及由电路描述中的控制依赖性引起的控制依赖约束；

所述调度约束为数据依赖约束时，采用以下公式将其转化为对应的差分约束 公式：

$\forall e\left(v_i{,v}_j\right)\in E_d:{\mathrm{sv}}_{\mathrm{end}}\left(v_i\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(v_j\right)\le 0$

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量结束值，节点V_i和节点V_j是具有数据依赖约束的两个操作节点且节点 V_i必须在节点V_j调度前就调度完毕，e(v_i,v_j)表示节点V_i和节点V_j的数据依赖 约束边，E_d表示控制数据流图中的所有数据依赖约束边的集合；

所述调度约束为控制依赖约束时，采用以下公式将其转化为对应的差分约束 公式：

$\forall e_c({\mathrm{bb}}_i,{\mathrm{bb}}_j)\in E_c:{\mathrm{sv}}_{\mathrm{end}}\left(\mathrm{ssnk}\left({\mathrm{bb}}_i\right)\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(\mathrm{ssrc}\left({\mathrm{bb}}_j\right)\right)\le 0$

上式中，sv_beg(ssrc(bb_j))表示基础块bb_j的调度变量起始值，sv_end(ssnk(bb_i)) 表示基础块bb_i的调度变量结束值，基础块bb_i和基础块bb_j是具有控制依赖约束 的两个基础块且基础块bb_j的操作节点必须在基础块bb_i的所有操作节点均调度 完毕之后才可调度，e_c(bb_i,bb_j)表示基础块bb_i和基础块bb_j的控制依赖约束边， E_c表示控制数据流图中的所有控制依赖约束边的集合。

进一步，所述时序约束包括相对时序约束和延时约束，相对时序约束包括最 小相对时序约束和最大相对时序约束；

所述调度约束为最小相对时序约束时，采用以下公式中将其转换为对应的差 分约束公式：

sv_beg(v_i)-sv_beg(v_j)≤-l_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_beg(v_i)表示节点V_i的调 度变量起始值，l_ij为自然数，节点V_i和节点V_j是具有最小相对时序约束的两个 操作节点且节点V_j的调度必须比节点V_i的调度至少晚l_ij个时钟周期；

所述调度约束为最大相对时序约束时，采用以下公式中将其转换为对应的差 分约束公式：

sv_beg(v_j)-sv_beg(v_i)≤u_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量起始值，u_ij为自然数，节点V_i和节点V_j是具有最大相对时序约束的两个 操作节点且节点V_j与节点V_i之间的最大延迟路径为u_ij个时钟周期；

所述调度约束为延时约束时，采用以下公式中将其转换为对应的差分约束公 式：

sv_end(ssnk(bb_j))-sv_beg(ssrc(bb_i))≤T_lat

其中，sv_end(ssnk(bb_j))表示基础块bb_j的调度变量结束值，sv_beg(ssrc(bb_i))表 示基础块bb_i的调度变量起始值，基础块bb_i和基础块bb_j是具有延时约束的两个 基础块且基础块bb_i和基础块bb_j之间的最大延迟路径为T_lat个时钟周期。

进一步，所述调度约束为资源约束时，采用以下公式中将其转换为对应的差 分约束公式：

sv_beg(v^π_i)-sv_beg(v^π_j)≤-Latency(v^π_i)

上式中，sv_beg(v^π_i)表示节点V^π_i的调度变量起始值，sv_beg(v^π_j)表示节点V^π_j的 调度变量起始值，节点V^π_i和节点V^π_j表示具有相同资源的一对节点，Latency(v^π_i) 表示节点V^π_i执行所需的延迟时间。

进一步，所述步骤S22，包括：

S221、将控制数据流图的入口节点的支配集合初始化为该入口节点，同时将 控制数据流图的其它节点的支配集合均初始化为全集；

S222、针对控制数据流图的除了入口节点外的任一节点，求取该节点的支配 集合与其前驱结点的支配集合的交集后，将该节点与该交集的并集作为该节点的 支配集合；

S223、重复执行步骤S222，直到所有节点的支配集合均不再变动后，根据 所有节点的支配集合构建支配树。

本发明的有益效果是：本发明的一种基于差分约束系统与迭代模的高层次综 合调度方法，获取输入的电路描述后构建对应的控制数据流图后，将控制数据流 图划分为循环部分和非循环部分，进而分别采用迭代模调度算法和差分约束系统 调度算法对控制数据流图的循环部分和非循环部分进行调度，对高层次综合的调 度流程进行了优化，提高了调度性能，而且调度实现过程方便、快速，可以全面、 及时地实现调度，调度效率高。

附图说明

下面结合附图和实施例对本发明作进一步说明。

图1是本发明的一种基于差分约束系统与迭代模的高层次综合调度方法中 的控制数据流图的示意图；

图2是本发明的一种基于差分约束系统与迭代模的高层次综合调度方法中 的循环结构示意图；

图3是本发明的一种基于差分约束系统与迭代模的高层次综合调度方法的 处理流程示意图；

图4是本发明的一种基于差分约束系统与迭代模的高层次综合调度方法中 采用迭代模调度算法将循环体进行局部调度的局部调度结果；

图5是采用迭代模调度算法对图4中的局部调度结果进行迭代调度后的最 终调度结果。

具体实施方式

本发明提供了一种基于差分约束系统与迭代模的高层次综合调度方法，包 括：

S1、获取输入的电路描述后构建对应的控制数据流图；

S2、将控制数据流图划分为循环部分和非循环部分；

S3、采用迭代模调度算法对控制数据流图的循环部分进行调度；

S4、采用差分约束系统调度算法对控制数据流图的非循环部分进行调度；

S5、对步骤S3和S4中得到的调度结果进行数学整合后，获得综合调度结 果。

进一步作为优选的实施方式，所述步骤S2，包括：

S21、使用深度优先算法对控制数据流图中的所有操作节点进行排序；

S22、采用支配图迭代算法将排序后的控制数据流图的节点构建成对应的支 配树；

S23、检测提取支配树中的所有回边后，获取由回边构成的所有回路作为控 制数据流图的循环部分，进而获得控制数据流图的非循环部分。

进一步作为优选的实施方式，所述步骤S3，包括：

S31、对控制数据流图的循环部分进行最小迭代启动间隔时间计算；

S32、将计算得到的最小迭代启动间隔时间作为初始的迭代启动间隔时间， 使用列表调度算法对控制数据流图的循环部分进行调度；

S33、迭代进行调度尝试直到满足以下条件时，继续执行步骤S34：调度成 功或者调度的迭代尝试次数大于预设上限阈值；

S34、判断是否调度完毕，若是，则结束，反之增加迭代启动间隔时间后， 继续使用列表调度算法进行下一轮调度，并返回执行步骤S33。

进一步作为优选的实施方式，所述步骤S4，包括：

S41、对控制数据流图的非循环部分的节点构建相应的调度变量；

S42、根据调度变量，将所有调度约束都转化为对应的差分约束公式后，将 获得的所有差分约束公式转化成整形规划矩阵；

S43、根据高层次综合的需求结果，构建相应的目标函数；

S44、将整形规划矩阵作为目标函数的约束条件，进行线性规划求解，判断 是否能求解获得目标函数的最优值，若否，则返回执行步骤S43，反之获得该目 标函数的最优值，同时获得对应的整形规划矩阵的值，进而获得每个节点的调度 值。

进一步作为优选的实施方式，所述步骤S42中所述调度约束包括依赖约束、 时序约束以及资源约束。

进一步作为优选的实施方式，所述依赖约束包括由电路描述中的数据依赖性 引起的数据依赖约束以及由电路描述中的控制依赖性引起的控制依赖约束；

所述调度约束为数据依赖约束时，采用以下公式将其转化为对应的差分约束 公式：

$\forall e\left(v_i{,v}_j\right)\in E_d:{\mathrm{sv}}_{\mathrm{end}}\left(v_i\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(v_j\right)\le 0$

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量结束值，节点V_i和节点V_j是具有数据依赖约束的两个操作节点且节点 V_i必须在节点V_j调度前就调度完毕，e(v_i,v_j)表示节点V_i和节点V_j的数据依赖 约束边，E_d表示控制数据流图中的所有数据依赖约束边的集合；

所述调度约束为控制依赖约束时，采用以下公式将其转化为对应的差分约束 公式：

$\forall e_c({\mathrm{bb}}_i,{\mathrm{bb}}_j)\in E_c:{\mathrm{sv}}_{\mathrm{end}}\left(\mathrm{ssnk}\left({\mathrm{bb}}_i\right)\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(\mathrm{ssrc}\left({\mathrm{bb}}_j\right)\right)\le 0$

上式中，sv_beg(ssrc(bb_j))表示基础块bb_j的调度变量起始值，sv_end(ssnk(bb_i)) 表示基础块bb_i的调度变量结束值，基础块bb_i和基础块bb_j是具有控制依赖约束 的两个基础块且基础块bb_j的操作节点必须在基础块bb_i的所有操作节点均调度 完毕之后才可调度，e_c(bb_i,bb_j)表示基础块bb_i和基础块bb_j的控制依赖约束边， E_c表示控制数据流图中的所有控制依赖约束边的集合。

进一步作为优选的实施方式，所述时序约束包括相对时序约束和延时约束， 相对时序约束包括最小相对时序约束和最大相对时序约束；

所述调度约束为最小相对时序约束时，采用以下公式中将其转换为对应的差 分约束公式：

sv_beg(v_i)-sv_beg(v_j)≤-l_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_beg(v_i)表示节点V_i的调 度变量起始值，l_ij为自然数，节点V_i和节点V_j是具有最小相对时序约束的两个 操作节点且节点V_j的调度必须比节点V_i的调度至少晚l_ij个时钟周期；

所述调度约束为最大相对时序约束时，采用以下公式中将其转换为对应的差 分约束公式：

sv_beg(v_j)-sv_beg(v_i)≤u_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量起始值，u_ij为自然数，节点V_i和节点V_j是具有最大相对时序约束的两个 操作节点且节点V_j与节点V_i之间的最大延迟路径为u_ij个时钟周期；

所述调度约束为延时约束时，采用以下公式中将其转换为对应的差分约束公 式：

sv_end(ssnk(bb_j))-sv_beg(ssrc(bb_i))≤T_lat

其中，sv_end(ssnk(bb_j))表示基础块bb_j的调度变量结束值，sv_beg(ssrc(bb_i))表 示基础块bb_i的调度变量起始值，基础块bb_i和基础块bb_j是具有延时约束的两个 基础块且基础块bb_i和基础块bb_j之间的最大延迟路径为T_lat个时钟周期。

进一步作为优选的实施方式，所述调度约束为资源约束时，采用以下公式中 将其转换为对应的差分约束公式：

sv_beg(v^π_i)-sv_beg(v^π_j)≤-Latency(v^π_i)

上式中，sv_beg(v^π_i)表示节点V^π_i的调度变量起始值，sv_beg(v^π_j)表示节点V^π_j的 调度变量起始值，节点V^π_i和节点V^π_j表示具有相同资源的一对节点，Latency(v^π_i) 表示节点V^π_i执行所需的延迟时间。

进一步作为优选的实施方式，所述步骤S22，包括：

S221、将控制数据流图的入口节点的支配集合初始化为该入口节点，同时将 控制数据流图的其它节点的支配集合均初始化为全集；

S222、针对控制数据流图的除了入口节点外的任一节点，求取该节点的支配 集合与其前驱结点的支配集合的交集后，将该节点与该交集的并集作为该节点的 支配集合；

S223、重复执行步骤S222，直到所有节点的支配集合均不再变动后，根据 所有节点的支配集合构建支配树。

下面结合具体实施例对本发明做详细说明。

首先，对控制数据流图进行说明，图1是控制数据流图的示意图，控制数据 流图(Control data flow graph，简称CDFG)是调度算法的执行操作对象，它是 包含了输入到系统的电路描述中的数据运算、数据依赖、控制跳转等相关信息的 有向图。控制数据流图可以分为节点(调度单元)和边(调度单元之间的关系) 这两个部分。其中，节点包括操作节点(Operation node)和基础块(Basic block)。 操作节点指的是输入的电路描述中出现的运算操作集合，而根据控制关系的不 同，一个或多个操作节点集合可构成一个基础块。在图1中，实线部分象征着的 是数据依赖关系边，虚线部分象征着的是控制依赖关系边，每个椭圆代表一个操 作节点，每个方框代表一个基础块。每个电路描述均可用这样的一个有向图进行 表示。实际操作中，可以通过LLVM编译系统建立数据流图，将指令类型、数 据依赖关系及控制跳转等信息抽象成为模型，构建控制数据流图，便于各项优化 包括调度、资源分配及复用等工作，本申请中，构建控制数据流图用于进行高层 次综合调度。

参照图1，一种基于差分约束系统与迭代模的高层次综合调度方法，包括：

S1、获取输入的电路描述后构建对应的控制数据流图；

S2、将控制数据流图划分为循环部分和非循环部分；

S3、采用迭代模调度算法对控制数据流图的循环部分进行调度；

S4、采用差分约束系统调度算法对控制数据流图的非循环部分进行调度；

S5、对步骤S3和S4中得到的调度结果进行数学整合后，获得综合调度结 果。

具体的，步骤S2，包括S21～S23：

S21、使用深度优先算法对控制数据流图中的所有操作节点进行排序；

S22、采用支配图迭代算法将排序后的控制数据流图的节点构建成对应的支 配树，具体包括S221～S223：

S221、将控制数据流图的入口节点的支配集合初始化为该入口节点，同时将 控制数据流图的其它节点的支配集合均初始化为全集；这里，全集是指控制数据 流图的所有节点。

S222、针对控制数据流图的除了入口节点外的任一节点，求取该节点的支配 集合与其前驱结点的支配集合的交集后，将该节点与该交集的并集作为该节点的 支配集合。节点的支配集合是指支配该节点的所有节点的集合，节点的前驱结点 是指控制数据流图中按照数据流方向遍历时位于该节点前面的节点。例如，节点 A为入口节点，节点A支配节点B、C，节点B支配节点D，则对于节点B的支 配结合，首先求得节点B的支配集合(节点B的支配集合初始化为全集)与节 点A的支配集合的交集为{A}，然后将节点B与该交集的并集{A，B}作为节点 B的支配集合；类似的，对于节点D的支配集合，首先求得节点D的支配集合 与节点B的支配集合的交集为{A，B}，然后将节点D与该交集的并集{A，B， D}作为节点D的支配集合。

S223、重复执行步骤S222，直到所有节点的支配集合均不再变动后，根据 所有节点的支配集合构建支配树。所有节点的支配集合均不再变动，则获得了控 制数据流图的支配树关系，因此根据支配树关系可以构建对应的支配树。步骤 S221～S223的迭代运算过程即为步骤S22提到的支配图迭代算法。

S23、检测提取支配树中的所有回边后，获取由回边构成的所有回路作为控 制数据流图的循环部分，进而获得控制数据流图的非循环部分。参照图2所示， 图中回路是由回边构成的回路，即一个循环，获取控制数据流图中的所有循环即 构成控制数据流图的循环部分。

图3是本调度方法的处理流程示意图，本方法在构建控制数据流图后，划分 循环部分及非循环部分，然后针对循环部分和非循环部分，分别执行不同的操作， 如图3中所示，最后，将两种操作获得的调度结果进行整合，即获得本调度方法 的调度结果。

具体地，步骤S3，包括S31～S34：

S31、对控制数据流图的循环部分进行最小迭代启动间隔时间计算。

S32、将计算得到的最小迭代启动间隔时间作为初始的迭代启动间隔时间， 使用列表调度算法对控制数据流图的循环部分进行调度。

列表调度算法也称表调度算法，其基本思想是通过对节点的优先级别进行排 序来构造一个调度列表，然后重复以下两个步骤直到所有节点被调度完毕：①从 调度列表中顺序按优先级取出一个节点；②在满足约束条件的基础上将节点调度 到使它的启动时间最早的控制步上，该算法是较为成熟的算法，这里不进行详细 描述。

S33、迭代进行调度尝试直到满足以下条件时，继续执行步骤S34：调度成 功或者调度的迭代尝试次数大于预设上限阈值。

调度成功从输出结果来看是指获得节点的具体的调度值；预设上限阈值指为 了限制调度时间而限定的每轮调度中调度尝试的次数，例如预设上限阈值为10， 那么若调度尝试次数达到10次还没有调度成功，也不再进行调度尝试，直接执 行步骤S34。

S34、判断是否调度完毕，若是，则结束，反之增加迭代启动间隔时间后， 继续使用列表调度算法进行下一轮调度，并返回执行步骤S33。增加迭代启动间 隔时间是指增加迭代启动间隔时间的值，例如将迭代启动间隔时间由6个时钟周 期增加到7个时钟周期。

可以结合图4及图5进一步理解步骤S31～S34所体现的采用迭代模调度算 法对控制数据流图的循环部分进行调度的过程，图4中及图5中的j表示迭代次 数，将循环体进行局部调度后得到一个局部调度结果的情况如图4所示，将图4 中的局部调度结果以迭代启动间隔时间进行迭代，得到的最终调度结果如图5 所示，当迭代的循环次数增多到一定程度时，程序将进入稳定状态，例如图5 中的椭圆部分所圈出来的范围，即本调度方法不断重复执行相同顺序的指令，实 现不同循环体之间的并行执行，从而可以获得更快的运行速度。

接下来介绍最小迭代启动间隔时间的计算过程以及迭代启动间隔时间的获 取方法，为了便于描述，用II来代表迭代启动间隔时间，用MII来代表通过计 算得到的预期的最小迭代启动间隔时间II。

对于最小迭代启动间隔时间的计算需要考虑资源依赖约束和数据依赖约束 两种情况，在资源依赖约束下的最小迭代启动间隔时间为ResMII，在数据以来 约束下的最小迭代启动间隔时间为RecMII，在考虑这两种情况下分别求得 ResMII与RecMII，从而得到MII＝Max(ResMII，RecMII)，进而将获得的MII 作为初始的迭代启动间隔时间II进行调度尝试。

在计算ResMII时，我们通过对其目标机器提供的可用资源与最终调度结果 中的任一时刻i的所有并行运算的指令所占用的资源总数的关系进行建模来得到 ResMII的计算公式。

令目标机器的可用资源表示为R＝[r₁,r₂,r₃,......]，其中r_j(j＝1,2,3,......)表示第 j种类型资源的可用数目。显然，为了满足资源约束关系，在最终调度结果的任 意时刻i都应该满足：

RT_S[i,j]≤r_j

其中，RT_S[i,j]表示最终调度结果中的时刻i的所有并行运算的指令所占用 的j类型资源的数目。结合图5可知，稳定状态包含的时刻数目等于II，对最终 调度结果中的稳定状态的所有时刻进行叠加，则有：

$\underset{i}{\Sigma }{\mathrm{RT}}_s[i,j]\le \mathrm{II}\times r_j$

要注意的是，由于调度只是改变了运算执行的顺序，并不会减少或增加指令 的数目。故同样完成一次循环，资源消耗在调度前后并没有改变，于是有：

$\underset{i}{\Sigma }{\mathrm{RT}}_s[i,j]=\underset{i}{\Sigma }\mathrm{RT}[i,j]$

其中，表示最终调度结果中也即调度后完成一次循环所消耗的j 类型资源的总数。表示局部调度结果中也即调度前完成一次循环所消 耗的j类型资源的总数。

于是为了满足j类型资源的资源约束，资源以来约束下的迭代启动间隔时间 II应满足下式：

$\mathrm{II}\ge \frac{{\Sigma }_i\mathrm{RT}[i,j]}{r_j}$

而当考虑所有类型资源约束，即可以得到ResMII表达式：

$\mathrm{ResMII}=\underset{j}{\max }\frac{{\Sigma }_i\mathrm{RT}[i,j]}{r_j}$

而在计算RecMII时，由于循环会导致存在一个运算依赖于前一次迭代中的 同一运算的结果，导致数据依赖关系形成环，我们要考虑延时、迭代距离并区分 不同迭代间的运算实例。迭代内与迭代间的数据依赖关系，可统一表达为：

(δ×II)+S(n₂)-S(n₁)≥d

其中δ表示迭代距离，II表示迭代启动间隔时间，n₁、n₂为两条存在依赖关 系的运算指令，S(n₁)、S(n₂)分别代表n₁、n₂的调度结果。

故对于一个依赖环可得：

$\mathrm{II}\ge \frac{d-(S\left(n_2\right)-S\left(n_1\right))}{\delta }=\frac{d_c}{\delta }$

其中，d_c为依赖环的总延时。

所以考虑控制数据流图中所有的依赖环，可得到RecMII表达式：

其中，G代表所构建的控制数据流图(即CDFG的简写)，d_c是数据依赖环的 总延时，而δ_c是数据依赖环的总迭代距离。

根据资源依赖约束和数据依赖约束分别计算出对应的最小迭代启动间隔时 间，将两者中的最大值作为最小迭代启动间隔时间MII，该计算出来的MII即为 预期的最小的迭代启动间隔时间，然而以MII作为实际的迭代启动间隔时间II 的调度尝试不一定可以成功，MII的意义是作为所有可能调度成功的迭代启动间 隔时间II的下限值。实际上，结合以上描述可知，最小迭代启动间隔时间MII 是计算迭代启动间隔时间II过程中的中间结果，因此在MII的公式推导过程中也 使用了II的概念，本申请中权利要求中为了更好地进行区分，分别采用不同的定 义来对其进行描述。

参照图3，步骤S4，包括S41～S44：

S41、对控制数据流图的非循环部分的节点构建相应的调度变量。

S42、根据调度变量，将所有调度约束都转化为对应的差分约束公式后，将 获得的所有差分约束公式转化成整形规划矩阵。

将调度约束转化为对应的差分约束公式，即实现对调度约束的建模，将每个 调度约束转化成类似x-y≤b的形式，其中，x、y为调度变量，b为常数。

S43、根据高层次综合的需求结果，构建相应的目标函数。

高层次综合的需求结果是指设计者对集成电路设计中的参数需求，例如运算 速度、面积等，若需求结果为面积，则构建面积表达式作为目标函数，若需求结 果为运算速度，则构建运算速度的表达式作为目标函数。

S44、将整形规划矩阵作为目标函数的约束条件，进行线性规划求解，判断 是否能求解获得目标函数的最优值，若否，则返回执行步骤S43，反之获得该目 标函数的最优值，同时获得对应的整形规划矩阵的值，进而获得每个节点的调度 值。

这里，结合目标函数以及作为约束条件的整形规划矩阵，采用线性规划求解 方式进行求解，求得目标函数在满足约束条件(即整形规划矩阵)的前提下的最 优值，例如面积最小值或运算速度最大值，相应地，获得此时的整形规划矩阵的 值，因为整形规划矩阵是由调度变量构成的，获得整形规划矩阵的值即可获得调 度变量的值，相当于获得每个节点的调度值，完成调度。对目标函数进行线性规 划求解时，可以采用现有技术中的任一种线性规划求解方法，例如采用线性规划 求解工具lp_solve5.5进行求解，求解过程中，目标函数及整形规划矩阵即为差 分约束系统的线性规划模型。本步骤的目的是求解获得目标函数的最优值，实际 上，进行线性规划求解时，不一定能获得最优值，若无法获得最优值，则需返回 步骤S43，重新构建目标函数后再进行线性规划求解直到求解获得最优值。

步骤S42中调度约束包括依赖约束、时序约束以及资源约束。

依赖约束包括由电路描述中的数据依赖性引起的数据依赖约束以及由电路 描述中的控制依赖性引起的控制依赖约束；

调度约束为数据依赖约束时，采用以下公式将其转化为对应的差分约束公 式：

$\forall e\left(v_i{,v}_j\right)\in E_d:{\mathrm{sv}}_{\mathrm{end}}\left(v_i\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(v_j\right)\le 0$

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量结束值，节点V_i和节点V_j是具有数据依赖约束的两个操作节点且节点 V_i必须在节点V_j调度前就调度完毕，e(v_i,v_j)表示节点V_i和节点V_j的数据依赖 约束边，E_d表示控制数据流图中的所有数据依赖约束边的集合。

调度约束为控制依赖约束时，采用以下公式将其转化为对应的差分约束公 式：

$\forall e_c({\mathrm{bb}}_i,{\mathrm{bb}}_j)\in E_c:{\mathrm{sv}}_{\mathrm{end}}\left(\mathrm{ssnk}\left({\mathrm{bb}}_i\right)\right)-{\mathrm{sv}}_{\mathrm{beg}}\left(\mathrm{ssrc}\left({\mathrm{bb}}_j\right)\right)\le 0$

上式中，sv_beg(ssrc(bb_j))表示基础块bb_j的调度变量起始值，sv_end(ssnk(bb_i)) 表示基础块bb_i的调度变量结束值，基础块bb_i和基础块bb_j是具有控制依赖约束 的两个基础块且基础块bb_j的操作节点必须在基础块bb_i的所有操作节点均调度 完毕之后才可调度，e_c(bb_i,bb_j)表示基础块bb_i和基础块bb_j的控制依赖约束边， E_c表示控制数据流图中的所有控制依赖约束边的集合。

时序约束包括相对时序约束和延时约束，相对时序约束包括最小相对时序约 束和最大相对时序约束；

调度约束为最小相对时序约束时，采用以下公式中将其转换为对应的差分约 束公式：

sv_beg(v_i)-sv_beg(v_j)≤-l_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_beg(v_i)表示节点V_i的调 度变量起始值，l_ij为自然数，节点V_i和节点V_j是具有最小相对时序约束的两个 操作节点且节点V_j的调度必须比节点V_i的调度至少晚l_ij个时钟周期；

调度约束为最大相对时序约束时，采用以下公式中将其转换为对应的差分约 束公式：

sv_beg(v_j)-sv_beg(v_i)≤u_ij

上式中，sv_beg(v_j)表示节点V_j的调度变量起始值，sv_end(v_i)表示节点V_i的调 度变量起始值，u_ij为自然数，节点V_i和节点V_j是具有最大相对时序约束的两个 操作节点且节点V_j与节点V_i之间的最大延迟路径为u_ij个时钟周期；

调度约束为延时约束时，采用以下公式中将其转换为对应的差分约束公式：

sv_end(ssnk(bb_j))-sv_beg(ssrc(bb_i))≤T_lat

其中，sv_end(ssnk(bb_j))表示基础块bb_j的调度变量结束值，sv_beg(ssrc(bb_i))表 示基础块bb_i的调度变量起始值，基础块bb_i和基础块bb_j是具有延时约束的两个 基础块且基础块bb_i和基础块bb_j之间的最大延迟路径为T_lat个时钟周期。

调度约束为资源约束时，采用以下公式中将其转换为对应的差分约束公式：

sv_beg(v^π_i)-sv_beg(v^π_j)≤-Latency(v^π_i)

上式中，sv_beg(v^π_i)表示节点V^π_i的调度变量起始值，sv_beg(v^π_j)表示节点V^π_j的 调度变量起始值，节点V^π_i和节点V^π_j表示具有相同资源的一对节点，Latency(v^π_i) 表示节点V^π_i执行所需的延迟时间。该公式表示且节点V^π_j的调度必须比节点V^π_i的调度至少晚Latency(v^π_i)个时钟周期。

以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于实施 例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做出种种的等同变 形或替换，这些等同的变型或替换均包含在本申请权利要求所限定的范围内。