FPGA HLS: Pipelining

在大多数应用中, 循环过程都是时间占比最大的地方. 大多数算法中涉及到两种类型的循环迭代: 空间迭代, 指的是在不同的数据元素上执行相同的操作; 时间迭代, 指的是在同一数据元素上重复执行相同的操作. 例如科学计算里面的 Stencil 问题, 既有空间迭代(对不同的网格点进行计算), 也有时间迭代(对同一网格点进行多次迭代计算). 因此在 FPGA HLS 中将算法映射为硬件实现的过程中, 循环优化是非常重要的, 而决定一个循环需要的时间最重要的指标是循环的启动间隔 (Initiation Interval, II) (而不是单次迭代的延迟, 稍后会看到原因).

循环调度涉及到同一条代码的多次执行, 简单的通过 CDFG 进行调度会导致循环不同迭代之间的硬同步 (也就是每次迭代都要等前一次迭代完全结束才能开始). 因此针对循环, 我们需要专门的流水化方法来重叠不同迭代的执行, 以提高循环的吞吐量. 这一节我们讨论一下循环流水化的实现方法.

并行 v.s. 流水

常见的两种提升硬件吞吐的方法是空间并行 (Spatial Parallelism) 和流水化 (Pipelining).

• 空间并行是通过"复制"硬件单元来同时处理多个数据元素.
• 流水线则是将处理多个数据元素的过程划分成不同阶段, 每个阶段分配专用硬件. 数据像流水一样经过各个阶段, 每个阶段同时处理不同数据元素的不同处理步骤.

衡量空间并行程度的指标是并行度 (Parallelism), 它表示在同一个时刻可以同时开始处理多少个数据元素. 例如一个 4 路并行的加法器, 每个时钟周期可以同时处理 4 对输入数据, 那么它的并行度就是 4.

衡量流水化程度的指标是启动间隔 (Initiation Interval, II), 它表示在流水线中每隔多少个时钟周期就可以开始处理一个新的数据元素. 例如一个 II 为 1 的流水线, 每个时钟周期都可以开始处理一个新的数据元素; 一个 II 为 2 的流水线, 则每两个时钟周期才能开始处理一个新的数据元素.

下面两幅图展示了空间并行和流水化的区别.

同样是增加吞吐的方法, 空间并行化简单直接, 但会几乎线性地增加硬件资源开销; 而流水化在理想情况下除了寄存器以外 (用来储存中间状态), 几乎不增加其他硬件资源开销. 在设计中这两种方式会结合使用.

资源和递归

上面显示了一个 II=1 的流水线, 但并非所有循环都能实现 II=1. 限制流水化因素主要分成两种: 资源冲突 (Resource Conflict) 和 递归依赖 (Recurrence Dependency).

资源冲突相对容易解决, 可以通过暴力增加硬件资源来避免. 例如一个循环中需要从同一块 RAM 里面读 4 次, 而一块 RAM 最多只有 2 个端口. 那么下一次循环在当次循环读完这 4 个元素 (分两次) 之后才能开始. 而两次读取至少要 2 个时钟周期, 此时循环的 II 至少就是 2 了. 解决的方法也相对简单, 将要读取的数据分到 2 块 RAM 里面, 保证 4 次读取能分解为同时对两块 RAM 的读取, 那么就能实现 II=1 了.

递归依赖就不太好解决了. 递归依赖指的是循环某个迭代的计算结果, 或者某个中间状态, 依赖于其他迭代的计算结果或中间状态 (可以依赖前面的迭代, 也可以依赖后面的迭代). 简洁讲, 递归依赖就是跨迭代数据依赖 (Loop-carried Dependence). 在编译器分析中数据依赖主要分为三种, 分别是 RAW (Read After Write), WAR (Write After Read), WAW (Write After Write). 分别又称为流依赖, 反依赖, 输出依赖. 其中 RAW 是最难解决的依赖类型, 其他两个在 CPU 中可以通过寄存器重命名解决, FPGA HLS 中也有别的方法解决. 但 RAW 反映的是数据的真实流向, 它是算法本身的固有属性, 不能通过增加硬件资源来解决.

例如下面的代码片段就是一个典型的 RAW 依赖

for (int i = 0; i < N; i++) {
    a[i] += a[i - 1];
}

第 i 次迭代最开始加载 a[i-1] 的操作依赖于第 i-1 次迭代对 a[i-1] 的更新. 因此第 i 次迭代必须等到第 i-1 次迭代完成之后才能开始.

由于这两种限制因此可能同时存在, 因此实际能达到的最低 II 应该取决于两种限制的最大值:

如果考虑第 $i$ 个递归依赖的依赖距离 (Dependence Distance) 为 $d_i$, 那么递归依赖对 II 的限制可以表示为:

其中 $L_i$ 是依赖路径的延迟 (注意它不等于单次迭代的延迟). 某个依赖关系的依赖距离指的是该依赖关系跨越的迭代数. 例如上面的代码片段中 RAW 依赖只跨越了 1 次迭代, 因此依赖距离为 1. 下面这种情况依赖距离则是 2:

for (int i = 0; i < N; i++) {
    a[i] += a[i - 2];
}

下面的图展示了一个矩阵乘法 (GEMM) 的 CDFG, 其中红色路径表示递归依赖路径, 蓝色路径表示单次迭代路径. 可以看到递归依赖路径并不等于迭代路径, 因此单次迭代的延迟和 II 之间没有什么必然联系.

模调度

前面已经提到流水线的概念, 接下来考虑怎么实现循环流水化调度. 最常用的一种算法是模调度 (Modulo Scheduling). 模调度的核心思想是将循环的不同迭代映射到一个有限长度的时间窗口 (称为模长 (Modulo Length)), 这个时间窗口的长度等于循环的启动间隔 II. 这里模的含义指的是, 在流水线达到稳定之后, 每隔 II 个时钟周期, 硬件执行的操作模式是重复的.

但不要忘记在流水线达到稳定这个前提. 流水线除了稳态以外, 还有流水线填充 (称为 Prologue) 和流水线排空 (称为 Epilogue) 两个阶段. 尽管模调度之后通常这两个阶段的调度自然确定了, 但不要忽略了这两个阶段的存在.

模调度的步骤如下:

1. 根据资源和数据依赖分析找到理论上最小的可能 II. 这利用上面的公式即可得到.
2. 尝试在当前 II 下进行调度. 需要引入模预留表 (Modulo Reservation Table, MRT) 的概念.
   • MRT 是一个二维表格, 行数等于硬件资源的数量, 列数等于 II. 每个单元格表示在某个时间步上某个资源是否被占用. (也可以用行表示时间槽, 列表示资源)
3. 对每一个操作, 计算它被调度到的时间步 T.
   • T 需要满足时间依赖, 即一个操作必须在它所有前驱操作完成之后才能开始.
   $$T \geq \operatorname{max} (T_{\text{pre}} + \text{latency}_{\text{pre}})$$
   • 检查资源冲突. 假设一个操作在时间 T 上需要使用资源 R, 那它在 MRT 的位置是 $(R, T\operatorname{mod} II)$. 检查 MRT 表, 如果这个位置是空的, 那么调度成功, 这个操作占据这个位置. 如果这个位置已经被占据, 那么会不断递增 T, 直到找到一个空闲位置为止. (对于多周期操作, 则需连续检查多个时间步)
4. 如果所有操作都能成功调度, 那么调度成功. 否则表示当前 II 不可行, 需要增加 II 然后重新尝试调度.

模调度的核心在于用 MRT 实现了节省了大量的状态储存. 传统的调度方法需要为每一个时间步都储存所有资源的使用情况, 而模调度利用循环的周期性, 只需要储存 II 个时间步的资源使用情况即可. 由于循环迭代次数通常非常大, 因此模调度比起传统调度方法 (需要完全展平) 节省了大量运行时开支.

代码实现

参照上一章给出的调度器代码框架, 添加一段模调度算法的实现. 首先添加模预留表的定义和实现:

using RT = ResourceType; // an enum class
struct MRT {
    int ii;
    std::vector<std::vector<int>> table; // 储存某个资源的可用数量
    MRT(int ii, int num_resources)
        : ii(ii), table(num_resources, std::vector<int>(ii, 10)) {}
    bool reserve(RT resource, int start, int latency);
};

bool MRT::reserve(RT resource, int start) {
    int res_id = static_cast<int>(resource);
    // check availability
    if (table[res_id][start % ii]] <= 0)
        return false;
    // reserve
    table[res_id][start % ii]--;
    return true;
}

接着实现模调度函数:

class Scheduler {
public:
    void schedule_modulo(int ii = -1); // ii=-1 means auto detect
private:
    int compute_min_ii() { return std::max(compute_res_mii(), compute_rec_mii()); }
    int compute_rec_mii();
    int compute_res_mii();
};

void Scheduler::schedule_modulo(int ii) {
    reset_schedule();
    if (ii = -1)
        ii = compute_min_ii();

    // compute time frames
    std::unordered_map<Node*, TimeFrame> frames;
    compute_time_frames(frames);
    
    // 这个方式隐含地保证了后继节点不可能早于前驱节点调度
    auto cmp = [](Node *a, Node *b) {
        return frames[a].alap > frames[b].alap; // ALAP-based priority
    };
    std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);
    for (auto &node : nodes) {
        pq.push(node);
    }

    MRT mrt(ii, get_num_resources());
    while (!pq.empty()) {
        auto node = pq.top();
        pq.pop();
        // recompute asap based on previous schedule results
        int asap = node->asap;
        for (auto pred : node->preds) {
            if (pred->scheduled_time != -1)
                asap = std::max(asap, pred->scheduled_time + pred->duration);
        }
        bool scheduled = false;
        for (int t = asap; t < asap + ii; t++) {
            if (mrt.reserve(node->resource, t)) {
                node->scheduled_time = t;
                scheduled = true;
                break;
            }
        }
        if (!scheduled) {
            throw std::runtime_error("Scheduling failed: cannot achieve target ii");
        }
    }
}

从代码中可以看出来, 模调度应该接受循环单次迭代中的所有操作, 为其构建数据依赖关系, 然后进行优先级排序. 优先级判断依据这里选择了 ALAP 时间, 这和列表调度是一样的. 接着对每一个操作, 计算它的 ASAP 时间, 然后尝试在 [ASAP, ASAP+II) 区间内找到一个可用的时间槽进行调度.

这段代码中隐含了一个假设, 所有的资源都可以在每个周期接受一个新输入 (完全流水化). 这在大多数情况下是对的, 例如 DSP 可以完全流水地, 每周期开始一次新加法/乘法. 但如果硬件资源并不满足这一点, 则相邻两次操作开始之间, 操作必须占满 MRT 表上对应的单元格.

例如一个乘法器每次乘法需要 8 个周期, 需要隔 3 个周期才能开始下一次操作, 那么在 MRT 表上占据的单元格是连续的 3 个时间步. 这时 MRT 的 reserve 函数需要修改为:

bool MRT::reserve(RT resource, int start, int latency) {
    int res_id = static_cast<int>(resource);
    // check availability
    for (int i = 0; i < latency; i++) {
        if (table[res_id][(start + i) % ii] <= 0)
            return false;
    }
    // reserve
    for (int i = 0; i < latency; i++) {
        table[res_id][(start + i) % ii]--;
    }
    return true;
}

模调度实际上无法单独使用, 它必须依赖一个调度算法预先确定好对 MRT 的搜索范围, 这里使用的是 ASAP 调度. 模调度并非一个完整的调度算法, 它只实现将单次迭代中的调度结果扩展到全体迭代的功能. 对于一个完整的模调度器, 不断调整 ii 直到找到一个可行的调度结果才是完整的, 这里省略了迭代的过程.

一旦通过模调度得到了单次迭代的调度结果, 就可以利用以下公式计算出第 k 次迭代中某个操作的调度时间:

其中 $T_{0}$ 是该操作在单次迭代中的调度时间步.

SDC-based 模调度

工业级更常用的算法是将模调度合并到 SDC 里面去做. 这需要扩展原始的 SDC 约束方程, 将循环迭代之间的依赖关系也纳入到约束方程中去. 基于上一章中的 SDC 建模过程, 我们额外添加以下约束:

假设有一个操作实例 (Instance, 指的是操作的每一次调用) $(u,i)$, 表示操作 u 在第 i 次迭代中被调用. 那么对跨循环的数据依赖 $(u,v)$ (后者依赖前者), 其约束方程为:

其中 $d$ 是依赖距离, $L(u)$ 是操作 u 的延迟. 结合周期性条件

可以得到:

换而言之, 约束方程的建立不需要依赖循环迭代次数 $i$. 因此我们不要为每一个操作实例都建立一个调度时间变量 $x_{u,i}$, 只需要考虑循环的单次迭代中的操作 $u$ 即可, 这样大大减少了变量数量.

接着是建模资源约束. 上一章已经提到了, 我们不会直接在 SDC 中添加资源约束方程, 这会导致问题无法通过寻找 LP 弛豫解来解决. 资源约束应该被放在 SDC 迭代过程中添加. 过程如下:

1. 假设我们在不考虑资源约束的情况下找到一个调度. 计算循环中所有操作的迭代时间 (相对循环开始, 而非全局时间), 对 II 取模, 这样就得到要实现当前 II 所需的 MRT 表.
2. 检查 MRT 表看是否满足物理资源限制, 如果不满足, 那么和上一章一样, 对于冲突的资源, 计算一个优先级列表, 将优先级较差的操作踢掉, 强制让它们之间先后执行 (手动添加额外的时间约束).
3. 重新运行 SDC 求解器, 得到新的调度结果, 直到 SDC 方程组无解 (出现负环) 或者满足资源限制为止.
4. 如果无法满足资源限制, 那么增加 II 然后重新开始整个过程.

这样就能在 SDC 框架下实现模调度. 这也是 SDC 在工业界中被广泛使用的原因之一, 它能在同一个框架下处理各种各样的调度约束.