【从零开始学习计算机科学】HLS算子调度

算子调度

调度是HLS 中的核心问题，为无时序或部分时序的输入指定时钟边界，其对最终结果质量具有很大的影响。调度会影响时钟频率、延时、吞吐率、面积、功耗等多种因素。

调度的输入是控制数据流图，其节点表示算子/操作，有向边表示数据依赖，控制依赖，优先依赖。如果没有控制流，其基本结构就是数据流图（DFG）。

调度过程将算子映射到一个状态，每个时钟周期对应着 FSM 中的一个状态，这称为控制步。

无约束的调度方法

无约束的调度方法只考虑依赖，目前，有两种常用的无约束调度方法：

ASAP

一，尽可能早的调度（ASAP），即把算子安排在尽可能早的控制步。其对应的算法伪代码如下：

ASAP G(V,E):
    V’ = Topological_Sort(G)

    foreach $v_i$ in V’:

        if $v_i\in PIs$ : $t_i$ = 1; // PIs, 主输入集合

        //假设每个算子都需要一个时钟周期

        else: $t_i$ = max($t_j$ + 1); //$(v_j,v_i)\in$ E

ALAP

二，尽可能迟的调度（ALAP），即把算子安排在尽可能晚的控制步。

其对应的算法伪代码如下：

ALAP (G(V,E),L): //L 是延时上限

    V’ = Reverse_Topological_Sort(G)

    foreach $v_i$ in V’:

        if $v_i$ $\in$ POs: $t_i$ = L; // POs, 主输出集合

         //假设每个算子都需要一个时钟周期

        else: $t_i$ = min($t_j$) - 1; //$(v_i,v_j)\in$ E

带约束调度方法

带约束调度问题一般是 NP-Hard 问题，目前，有两类问题，分别是资源约束的调度（Resource Constrained Scheduling，RCS），即给定面积或资源约束最小化延时；时间约束的调度（Time Constrained Scheduling，TCS），即给定延时边界最小化资源

对于带约束调度问题，可采用精确建模方法，比如整数线性编程（Integer Linear Programming，ILP）、针对严格约束的 Hu 算法等等；也可以采用启发式算法，包含列表调度、力量引导算法、基于SDC的调度等等。

以下以ILP方法为例，建模并求解带约束的调度问题。

ILP调度

线性编程（Linear Programming, LP）主要是解决目标函数和约束都是线性表示的问题，其在理论上和实际上都能有效求解。而整数线性编程(ILP)除了目标函数和约束都是线性组合之外，变量的取值必须是整数，其通常也是 NP-Hard 问题（0-1 ILP 除外），但是，现代 ILP 求解器可以求解一定规模的 ILP 问题。

资源约束的调度（RCS）表述为硬件功能单元（FU）资源有限，每个时钟周期每个功能单元只能执行一个算子。比如，只有 K 个加法器的时候，同一个时钟周期执行的加法数量不超过 K。

RCS问题的输入：给定每种计算类型的功能单元的数量，最小化延时。

RCS 的 ILP 建模的第一步是定义变量。

首先定义二元决策变量$x_{ik}$，$x_{ik}$=1表示算子 i 在控制步 k 开始执行。i = 1,2,3,…,N，N 表示算子总数，k= 1,2,3,…,L, L 表示延时的上限。
定义 $t_i={\sum }_{k=1}^L(k{x}_{ik})$，$t_i$ 表示算子 i 的起始时间。

第二步是建立约束关系。主要包含以下约束：

起始时间的唯一性 ${\sum }^{}$