基于时间约束的高层次综合调度方法

刘乙力 白利琼 鞠瑜华 向明艳

（成都华微电子科技有限公司 四川省成都市 610000）

随着半导体技术的不断发展，超大规模集成电路变得越来越复杂，设计者在进行电路设计时常常只能给出系统的算法级行为描述，而在进行逻辑综合之前需将算法级的行为描述转化为寄存器传输级的结构描述，这个转换过程称为高层次综合。高层次综合可在一定的约束条件下搜索设计空间，通过对调度或分配算法的比较和选用从而找到一个最佳方案或满意方案，最终实现对资源或运行时间的优化。高层次综合工具的使用大大地减小了设计人员的工作量，缩短设计周期，提高设计质量。

1 调度算法的介绍

操作的调度是指在满足约束的条件下，将操作赋给控制步，从而使给定的目标函数最小。约束通常为时间约束或资源约束，目标函数主要考虑控制步总数、时延或面积。作为高层次综合中的一个重要步骤，调度算法很大程度上决定了高层次综合工具的执行速度、响应延迟性和硬件资源费用。传统的调度算法主要包括ASAP(As soon as possible)、ALAP(As late as possible)调度算法、列表调度（LS，List Scheduling algorithm）算法、力引导调度 (FDS，Force-Directed Schedulingalgorithm)算法。ASAP 和ALAP 算法简单快速，常用于求各操作的可调度区间。列表调度算法可以进行资源约束下的操作调度，因算法复杂性低且可在短时间内找到次优解的优点而被广泛应用[1]，但无法进行时间约束下的调度。力引导算法是一种基于时间约束寻找最小资源调度的构造算法，它精确性好，能找到最佳调度结果，但是计算复杂，时间复杂度最坏情况下为O(n3)[2]。

考虑到高层次综合过程中的调度是一个NP 完全问题，启发式的算法也常常应用于高层次综合调度过程中，如遗传算法(Genetic Algorithm)、模拟退火算(Simulated annealing Algorithm)等。文[3]提出了一种基于遗传算法的调度和分配协同实现的策略；在文[4]中，D Chen 介绍了一种基于FPGA 的增强型模拟退火调度算法。对于计算量大的对象而言，启发式算法能够较快地找到一个近似解，但启发式算法中的参数对算法的效果起着至关重要的的作用，而参数的选取常常取决于经验。

本文提出了一种新颖的基于时间约束的高层次综合调度方法，该方法在满足时间约束的条件下可使得各操作均匀地分布在控制步中，从而提高资源的利用率，减小面积。该调度方法首先建立中间矩阵记录各操作的时间帧分布情况，再引入控制步拥挤度函数C(j)用以表征在当前状态下控制步j 中可能存在的最大操作数之和，最后构造时间帧分布表用于指导下一步选取的待调度操作。在整个调度过程中，各控制步的拥挤度会逐渐减小直至各控制步拥挤度之和等于所有操作数之和。实验证明该方法有效。

图1：HAL 的数据流图

图2：ASAP 和ALAP 调度结果

2 基于时间约束的调度方法

以HAL 基准测试电路为例对该方法进行说明。HAL 的数据流图如图1所示，其中操作类型主要有乘法器、加法器、减法器和比较器，本应分为四组分别进行调度。为了便于说明可简化问题，将数据流图中的操作类型分为两组，一组为所有的乘法操作，另一组为除乘法操作后的剩余操作。

对于数据流图中的任意操作opi(i=1,2,…,n)，n 为操作总数，定义opi的时间帧用以表示操作opi的可调度范围，可通过ASAP 和ALAP 调度算法得到。ASAP 调度算法可求得操作opi所能调度到的最早控制步，用表示；ALAP 算法可得到操作opi所能调度到的最晚控制步，用表示。即为操作opi的可调度范围，又称时间帧。对于opi∈{op1,…,opn}，有则称opi为关键路径上的操作。对于关键路径上的操作，无需进行调度。关键路径的长度决定了调度时的控制步数，由此可确定时间约束。

采用ASAP 和ALAP 算法对上述HAL 数据流图进行调度后可得到图2所示的调度结果。

表1：初始时间帧分布表

表2：一次调度后的时间帧分布表

表3：调度完成后时间帧分布表

定义中间矩阵(aij)n×m，记录各操作的时间帧范围，用于表征操作在控制步的可调度情况，其中n 为操作数，m 为控制步数。令

其中，csj表示第j 个控制步，j=1,2,…m。一个控制步是一个时钟单位，对应若干时钟周期。

拥挤度函数C(j)表示当前情况下在控制步csj中可能存在的最大操作数之和，可表示为

在较坏的调度结果中，操作会聚集在部分控制步，不利于不同控制步的操作对资源的复用，进而导致资源的浪费，面积和造价的增加。因此，需要在调度的过程中不断地降低拥挤度函数C(j)，使得各控制步的C(j)均匀分布，尽可能保证资源利用最大化。

对于操作opi，定义表示在操作opi的时间帧范围内，拥挤度最大控制步与拥挤度最小的控制步的拥挤度之差，可称为操作opi的拥挤度差值。

根据矩阵(aij)n×m和拥挤度函数C(j)可得到时间帧分布表。该时间帧分布表分为两部分，一部分为操作与控制步的关系，可根据中间矩阵的行和列来确定，中间矩阵的行即为时间帧分布表的行，中间矩阵的列即为时间帧分布表的列，HAL 初始时间帧分布表中操作与控制步的关系如迭代完成后，所需资源总数可通过max Ctype(j)得到。

表1（a）所示。考虑更为直观地表示，可隐去中间矩阵中0 的分布情况。另一部分为各控制步拥挤度分布情况，利用拥挤度函数分别对每行同类型操作求和得到该种类型的拥挤度，由此可得到不同操作类型在控制步中的拥挤度，HAL 初始时间帧分布表中各控制步拥挤度分布情况如迭代完成后，所需资源总数可通过max Ctype(j)得到。

表1（b）所示。

本文中调度方法的步骤如下：

步骤1：通过ASAP，ALAP 调度算法得到各操作的时间帧；

步骤2：引入中间矩阵并计算各控制步的初始拥挤度，同时计算拥挤度差值；

步骤3：根据中间矩阵和初始拥挤度分布得到初始时间帧分布图；

步骤4：若还有未被调度的操作（各控制步拥挤度之和不等于操作数），则

（1）选取拥挤度最大的控制步，并寻找该控制步内拥挤度差值最大的操作，将其设为当前操作；

（2）将当前操作调度到其时间帧内拥挤度最小的控制步；

（3）更新当前操作所有前驱和后继的时间帧范围；

（4）更新各控制步的拥挤度，转到步骤4。

迭代完成后，所需资源总数可通过max Ctype(j)得到。

由数据流图可知，HAL 的操作数为11，关键路径长度为4，因此n=11，m=4。假设所有操作的运行均可在一个控制步内完成，首先选择拥挤度最大的控制步cs1、cs2、cs3，由于cs3 中存在拥挤度差值最大的操作，选取cs3 为当前控制步，cs3 中拥挤度差值最大的操作op10 为当前操作，将op10 调度到当前操作类型拥挤度最小的控制步cs1。更新op10 的后继op11 的时间帧时，由于op10 的调度对op11 不产生影响，不需要对op11 的时间帧作出修改。更新各控制步拥挤度，可得到时间帧分布表如表2所示。

图3：FDS 与本文方法的调度结果对比

在表2中，按上述方法选取cs2 为当前控制步，op8 为当前操作。将op8 调度至cs3，由于op9 为其后继操作，更新op9 的时间帧长度后，op9 将被隐式调度至cs4。按同样方式对剩下待调度操作进行迭代处理直至C(j)=n，经过5 次调度，可得到表3所示的结果。通过max Ctype(j)可知，最终需要2 个乘法器，2 个除乘法器之外其他的操作对应的资源。

上述方法的复杂度分析如下：

（1）一次迭代至少实现一个操作的调度，最多迭代n 次；

（2）每次迭代需在c 个控制步中选出拥挤度最大的控制步，再通过拥挤度差值确定当前控制步和当前操作；

（3）需将当前操作调度至其时间帧内拥挤度最小的控制步，时间帧最大为c。

考虑上述3 个方面的影响，可得到最坏情况下本文算法的复杂度为O(c2n2)，c 可忽略不计，相对传统的力引导调度算法而言，时间复杂度降低了n。

3 实验结果

从DSP 基准测试套件和媒体测试电路中选取15 个典型的基准电路作为基准测试电路。通过比较力引导算法和本文算法的总资源消耗数与运行时间，可得到图3所示的调度结果，其中第1 列和第2 列为基准电路的编号和名称，第3、4 列为节点数和关键路径长度，第5、6 列为FDS 与本文方法的总资源消耗数比和运行时间比，可以看出，尽管本文调度方法相对力引导调度算法资源消耗平均增大了2.7%，但是从运行时间来看，本文算法能够明显提升速度，平均可提高3.23 倍，最大可提高5.32 倍。

3 结论

本文实现了一种基于时间约束的高层次综合调度算法，时间约束由输入数据流图的关键路径决定，调度过程按照时间帧分布表确定待调度操作，在不断地迭代过程中使得C(j)越来越小的同时趋于均匀分布。通过对15 组典型的基准测试电路的调度，将本文方法与传统的力引导算法进行对比，可得到在损失平均2.7%的资源的情况下使得速度提高3.23 倍。