处理嵌套循环 - 2023.2 简体中文

Vitis 高层次综合用户指南 (UG1399)

Document ID
UG1399
Release Date
2023-12-18
Version
2023.2 简体中文

为了在处理嵌套循环时获得最佳性能(最低时延),创建完美嵌套的循环就变得至关重要。在完美嵌套循环中,循环边界为常量,仅限最内层的循环才包含任何功能(如下所示)

Perfect_nested_loop_1: for (int i = 0; i < N; ++i) {
    Perfect_nested_loop_2: for (int j = 0; j < M; ++j) {
        // Perfect Nested Loop Code goes here and no where else
    }
}
 
Imperfect_nested_loop_1: for (int i = 0; i < N; ++i) {
    // Imperfect Nested Loop Code contains code here
    Imperfect_nested_loop_2: for (int j = 0; j < M; ++j) {
        // Imperfect Nested Loop Code goes here
    }
    // Imperfect Nested Loop Code may contain code here as well
}
完美循环嵌套
仅限最内层的循环才有循环主体内容,逻辑语句之间未指定任何逻辑,所有循环边界均为常量
半完美循环嵌套
仅限最内层的循环才有循环主体内容,逻辑语句之间未指定任何逻辑,所有循环边界均为常量。
非完美循环嵌套
内层循环具有变量边界,或者循环主体未完全包含在内层循环内。在此情况下,设计人员应尝试重构代码或者将循环主体中的循环展开以创建完美循环嵌套。

已展开的嵌套循环之间的移动也需要额外的时钟周期。从外层循环移至内层循环需要一个时钟周期,从内层循环移至外层循环同样如此。在此处所示小型示例中,这暗示执行 Outer 循环需 200 个额外时钟周期。

void foo_top { a, b, c, d} {
    ...
    Outer: while(j<100)
        Inner: while(i<6) // 1 cycle to enter inner
            ...
            LOOP_BODY
            ...
        } // 1 cycle to exit inner
    }
 ...
}

LOOP_FLATTEN 编译指示或指令允许将已标记为完美和半完美的嵌套循环平铺,这样就无需通过重新编码来最优化硬件性能,并且还可减少执行循环中的运算所需的周期数。将 LOOP_FLATTEN 最优化应用于一组嵌套循环时,应将其应用于包含循环主体的最内层循环。循环平铺还可通过如下方式来执行:将循环平铺单独应用于各循环,或者在函数级别将其应用于函数中的所有循环。

对嵌套循环进行流水打拍时,通常可通过对最内层循环进行流水打拍来实现面积与性能之间的最优平衡。这样同时也可达成最短的运行时间。GitHub 上的 pipelined_loop 提供了如下所示代码示例,此示例演示了循环和函数流水打拍的优缺点取舍。

#include "loop_pipeline.h"
 
dout_t loop_pipeline(din_t A[N]) { 
    int i,j;
    static dout_t acc;
   
    LOOP_I:for(i=0; i < 20; i++){
        LOOP_J: for(j=0; j < 20; j++){
            acc += A[j] * i;
        }
    }
    return acc;
}

在以上示例中,如果将最内层循环 (LOOP_J) 流水打拍,那么硬件中包含 1 份 LOOP_J 副本(单次乘法)。Vitis HLS 会尽可能自动将循环平铺(如此例所示),并有效创建 1 个含 20*20 次迭代的新循环(称为 LOOP_I_LOOP_J)。这样只需调度 1 次乘法操作并访问 1 个阵列,即可将循环迭代调度为单一循环主体实体(20x20 次循环迭代)。

提示: 当循环或函数进行流水打拍时,所在层级比流水打拍的循环或函数层级更低的所有循环都必须展开。

如果对外部循环 (LOOP_I) 进行流水打拍,则内部循环 (LOOP_J) 将展开,以创建 20 份循环主体副本:这样必须调度 20 次乘法和 1 次阵列访问。然后,LOOP_I 的每次迭代都必须作为单一实体来调度。

如果对顶层函数流水打拍,则 2 个循环都必须展开:这样就必须调度 400 次乘法和 20 次阵列访问。Vitis HLS 生成含 400 次乘法的设计的可能性很低,因为在大部分设计中,数据依赖关系通常会阻止最大程度并行化,例如,即使针对 A 使用双端口 RAM,设计也只能在任意时钟周期内访问 2 个 A 值。否则,阵列必须分区为 400 个寄存器,随后即可在单一时钟周期内全部读取,这样硬件成本极高。

选择适合流水打拍的层级时应遵循的概念是:对最内层的循环进行流水打拍所涉及的硬件量最少,并且产生的吞吐量对大部分应用都可接受。对较上层的层级进行流水打拍则会将所有下层循环全部展开,从而导致显著增加要调度的操作数量(可能影响编译时间和内存容量),但在吞吐量和时延方面通常可产生最高性能的设计。数据访问带宽必须与应并行执行的运算的要求相匹配。这暗示您可能需要对阵列 A 进行分区才能使之生效。

总结上述选项:

  • LOOP_J 流水打拍:时延约为 400 个周期 (20x20),需少于 250 个 LUT 和寄存器(I/O 控制和 FSM 始终存在)。

    图 1. Performance & Resource Estimates
  • LOOP_I 流水打拍:时延 13 个周期,但需要数百个 LUT 和寄存器。逻辑数量约为第 1 个选项的 2 倍,扣除可执行的所有逻辑最优化。

    图 2. Performance & Resource Estimates
  • 函数 loop_pipeline 流水打拍:在此情况下,由于存在 20 次并行寄存器访问,因此时延仅为 3 个周期,但所需逻辑数量接近第 2 个选项的 2 倍(约为第 1 个选项的 4 倍),扣除可执行的所有逻辑最优化。

    图 3. Performance & Resource Estimates

Vitis HLS 无法平铺非完美嵌套循环。这将导致进入和退出循环时额外增加时钟周期。当设计包含嵌套循环时,请分析结果以确认已尽可能将更多嵌套循环平铺:复查 log 日志文件或者查看综合报告中是否存在如上所示已合并循环标签的案例(LOOP_ILOOP_J 现已报告为 LOOP_I_LOOP_J)。