管理流水线依赖关系 - 2023.2 简体中文

Vitis HLS 会构造对应于 C/C++ 语言源代码的硬件数据路径。如果没有流水线指令，将始终按顺序执行，并且工具不需要考虑任何依赖关系。但如果设计功能特性已流水打拍，那么该工具需要确保在 Vitis HLS 生成的硬件内遵循所有可能依赖关系。

“数据依赖关系”或“存储器依赖关系”的典型用例是在完成上一次读操作或写操作后再次发生读操作或写操作。

• 先写后读 (RAW) 操作也称为真性依赖关系，它表示指令（及其读取/使用的数据）从属于前一次操作的结果。
  • I1: t = a * b;
  • I2: c = t + 1;

  语句 I2 中的读操作取决于语句 I1 中的 t 的写操作。如果对指令进行重新排序，它会使用 t 的前一个值。

• 先读后写 (WAR) 操作也称为反依赖关系，它表示当前一条指令完成数据读取后，下一条指令才能更新寄存器或存储器（通过写操作）。
  • I1: b = t + a;
  • I2: t = 3;

  语句 I2 中的写操作无法在语句 I1 之前执行，否则 b 的结果无效。

• 先写后写 (WAW) 依赖关系表示必须按特定顺序写入寄存器或存储器，否则可能破坏其他指令。
  • I1: t = a * b;
  • I2: c = t + 1;
  • I3: t = 1;

  语句 I3 中的写操作必须晚于语句 I1 中的写操作。否则，语句 I2 结果将出错。

• 先读后读不含任何依赖关系，因为只要变量未声明为易变，即可随意对指令进行重新排序。如果变量声明为易变，则必须保留指令顺序不变。

例如，生成流水线时，工具需确保先前写操作不会修改后续阶段读取的寄存器或存储器位置。这属于真性依赖关系或先写后读 (RAW) 依赖关系。具体示例如下：

int top(int a, int b) {
 int t,c;
I1: t = a * b;
I2: c = t + 1;
 return c;
}

在语句 I1 完成前，无法对语句 I2 求值，因为与 t 变量之间存在依赖关系。在硬件中，如果乘法需耗时 3 个时钟周期，那么 I2 将发生等同于此时间量的延迟。如果对以上函数进行流水打拍，那么 Vitis HLS 会将其检测为真性依赖关系，并对操作进行相应调度。它使用数据转发最优化来移除 RAW 依赖关系，因此函数可按 II =1 来运行。

当此示例应用于阵列而非变量时，就会出现存储器依赖关系。

int top(int a) {
 int r=1,rnext,m,i,out;
 static int mem[256];
L1: for(i=0;i<=254;i++) {
#pragma HLS PIPELINE II=1
I1:     m = r * a; mem[i+1] = m;    // line 7
I2:     rnext = mem[i]; r = rnext; // line 8
 }
 return r;
}

在以上示例中，L1 循环的调度导致出现调度警告消息：

WARNING: [SCHED 204-68] Unable to enforce a carried dependency constraint 
(II = 1, distance = 1) between 'store' operation (top.cpp:7) of variable 'm', top.cpp:7 
on array 'mem' and 'load' operation ('rnext', top.cpp:8) on array 'mem'.
INFO: [SCHED 204-61] Pipelining result: Target II: 1, Final II: 2, Depth: 3.

只要写入的索引不同于读取的索引，那么循环的同一次迭代内就不会发生任何问题。而 2 条指令可同时并发执行。但请观测多次迭代中的读写操作：

// Iteration for i=0
I1:     m = r * a; mem[1] = m;      // line 7
I2:     rnext = mem[0]; r = rnext; // line 8
// Iteration for i=1
I1:     m = r * a; mem[2] = m;      // line 7
I2:     rnext = mem[1]; r = rnext; // line 8
// Iteration for i=2
I1:     m = r * a; mem[3] = m;      // line 7
I2:     rnext = mem[2]; r = rnext; // line 8

当考量 2 次连续迭代时，来自 I1 语句的乘法结果 m（时延 = 2）将写入某一位置，而循环的下一次迭代的 I2 语句将把位于该位置的结果读取到 rnext 中。在此情况下，存在 RAW 依赖关系，因为上一次计算的写操作完成后，下一次循环迭代才能开始读取 mem[i]。

如果增大时钟频率，那么乘法器将需要更多流水线阶段，从而导致时延增加。这也会迫使 II 增大。

请注意以下代码，其中操作发生交换，导致功能发生更改：

int top(int a) {
 int r,m,i;
 static int mem[256];
L1: for(i=0;i<=254;i++) {
#pragma HLS PIPELINE II=1
I1:     r = mem[i];             // line 7
I2:     m = r * a , mem[i+1]=m; // line 8
 }
 return r;
}

调度警告为：

INFO: [SCHED 204-61] Pipelining loop 'L1'.
WARNING: [SCHED 204-68] Unable to enforce a carried dependency constraint (II = 1,
distance = 1)
 between 'store' operation (top.cpp:8) of variable 'm', top.cpp:8 on array 'mem'
and 'load' operation ('r', top.cpp:7) on array 'mem'.
WARNING: [SCHED 204-68] Unable to enforce a carried dependency constraint (II = 2,
distance = 1)
 between 'store' operation (top.cpp:8) of variable 'm', top.cpp:8 on array 'mem'
and 'load' operation ('r', top.cpp:7) on array 'mem'.
WARNING: [SCHED 204-68] Unable to enforce a carried dependency constraint (II = 3,
distance = 1)
 between 'store' operation (top.cpp:8) of variable 'm', top.cpp:8 on array 'mem'
and 'load' operation ('r', top.cpp:7) on array 'mem'.
INFO: [SCHED 204-61] Pipelining result: Target II: 1, Final II: 4, Depth: 4.

请观测多次迭代中的连续读写操作：

Iteration with i=0
I1:     r = mem[0];           // line 7
I2:     m = r * a , mem[1]=m; // line 8
Iteration with i=1
I1:     r = mem[1];           // line 7
I2:     m = r * a , mem[2]=m; // line 8
Iteration with i=2
I1:     r = mem[2];           // line 7
I2:     m = r * a , mem[3]=m; // line 8

所需 II 延长，因为存在如下 RAW 依赖关系，从 mem[i] 读取 r、执行乘法并写入 mem[i+1]。

移除假性依赖关系以改善循环流水打拍

假性依赖关系即编译器过于保守时出现的依赖关系。这些依赖关系在真实代码中并不存在，但无法由编译器来判定。这些依赖关系可能阻碍循环流水打拍。

假性依赖关系如下示例所示。在此示例中，针对相同循环迭代内的 2 个不同地址执行读写访问。这 2 个地址均依赖于输入数据，可指向 hist 阵列中的任一元素。有鉴于此，Vitis HLS 假定这 2 个地址可访问同一个位置。因此，它安排按交替周期对阵列执行读写操作，导致循环 II 为 2。但代码显示 hist[old] 和 hist[val] 永远无法访问相同地址，因为这两者包含在 if(old == val) 条件的 else 分支中。

void histogram(int in[INPUT SIZE], int hist[VALUE SIZE]) f
  int acc = 0;
  int i, val;
  int old = in[0];
  for(i = 0; i < INPUT SIZE; i++)
  {
    #pragma HLS PIPELINE II=1
    val = in[i];
    if(old == val)
    {
        acc = acc + 1;
    }
    else
    {
        hist[old] = acc;
        acc = hist[val] + 1;
    }
     
    old = val;
  }
    
  hist[old] = acc;

为克服这一缺陷，您可使用 DEPENDENCE 指令为 Vitis HLS 提供有关这些依赖关系的附加信息。

void histogram(int in[INPUT SIZE], int hist[VALUE SIZE]) {
  int acc = 0;
  int i, val;
  int old = in[0];
  #pragma HLS DEPENDENCE variable=hist type=intra direction=RAW dependent=false
  for(i = 0; i < INPUT SIZE; i++)
  {
    #pragma HLS PIPELINE II=1
    val = in[i];
    if(old == val)
    {
        acc = acc + 1;
    }
    else
    {
        hist[old] = acc;
        acc = hist[val] + 1;
    }
     
    old = val;
  }
    
  hist[old] = acc;

指定依赖关系时，有 2 种主要类型：

• Inter（循环间）：指定相同循环的不同迭代之间存在不同的依赖关系。如指定为 FALSE，则当循环已流水打拍、已展开或已部分展开时，允许 Vitis HLS 并发执行运算，指定为 TRUE 时则阻止此类并发运算。
• Intra（循环内）：指定循环的相同迭代内的依赖关系，例如，在相同迭代开始和结束时访问的阵列。当 intra 依赖关系指定为 FALSE 时，Vitis HLS 可在循环内自由移动运算、提升运算移动性，从而可能改善性能或面积。当此依赖关系指定为 TRUE 时，必须按指定顺序执行运算。

标量依赖关系

部分标量依赖关系较难以解析，且通常需要更改源代码。标量数据依赖关系如下所示：

while (a != b) {
   if (a > b) a -= b;
   else b -= a; 
 }

此循环的当前迭代完成 a 和 b 的更新值计算后才能启动下一次迭代，如下图所示。

如果必须得到上一次循环迭代结果后才能开始当前迭代，则无法进行循环流水打拍。如果 Vitis HLS 无法以指定的启动时间间隔进行流水打拍，那么它会增加启动时间间隔。如果完全无法流水打拍，则它会停止流水打拍并继续输出非流水打拍设计。