Skk's Blog|

Dynamatic: 为C/C++ HLS设计生成动态调度电路

现有问题

现有的高层次综合(HLS, High-Level Synthesis)工具通常只能做静态调度(Static Scheduling), 也就是在编译/综合的时候就确定电路中的每个操作在哪个时钟周期执行. 例如处理C/C++中的循环时, HLS工具会将循环展开成一个大的数据流图, 然后基于这个图做调度(比如分析数据依赖关系). 但如果循环中出现了随机性内存操作这种不可在编译期进行预测的行为, 那么静态调度的HLS工具就无法进行任何优化. 比如下面这段代码:

void histogram(int feature[], float weight[], float hist[], int n) {
	for (int i = 0; i < n; i++) {
		int m = feature[i]; // read m from memory
		float wt = weight[i];
		float x = hist[m]; // use m as an index to access memory
		hist[m] = x + wt;
	}
}

这是一个典型的读-修改-写(read-modify-write)模式. 问题出在访问hist数组的索引m是在运行时动态生成的, 具有随机性内存访问的特性. 因此基于静态调度的HLS工具完全无法对这个循环进行流水线优化, 因为它无法在编译/综合的时候预测内存访问的顺序. 于是就造成了性能损失.

Dynamatic是为了解决类似的问题, 它主要引入了动态调度(Dynamic Scheduling)的机制. 一会能看到, 对于这段代码, 它在生成的电路中插入了一个LSQ(Load Store Queue)组件来处理访存问题, 这个LSQ允许在运行时对访存操作(如LD/ST)进行调度, 甚至允许将访存操作乱序重排(Out-of-Order Execution). 这样能让HLS工具对同一段源代码综合出来的电路具有动态调度的能力, 一定程度上提升性能.

概念

论文中使用到了以下概念:

  1. 数据流电路中的各个组件通过某种握手机制(比如ready/valid)交换数据, 这些交换的数据被称为tokens.
  2. 数据流图(DFG, Data Flow Graph), 它是一个有向图, 节点表示对数据进行的操作, 边表示数据之间的依赖关系. 例如下面这个图, 表示数据a和b先做乘法, c和d根据选择信号sel选择一个输出, 然后将乘法器结果和选择器结果相加, 最后将结果存储到内存中.
  1. 基本块(Basic Block), 指的是一段连续的代码的集合, 其中没有分支选择的指令. 例如下面这段代码可以分为两个基本块. 基本块中的指令在语义上是顺序执行的(实际上可以并行, 也可以乱序), 可以用数据流图来表示一个基本块.
b = 1;
if (cond == 0) {
	// Basic Block 1
	a = b * 2;
	c = a + 1;
} else {
	// Basic Block 2
	a = b * 3;
	c = a + 2;
}
  1. 控制流图(CFG, Control Flow Graph), 它是一个有向图, 节点表示基本块, 边表示基本块之间的控制依赖关系, 例如对于上面这段代码, 它的控制流图如下: (这里将部分数据流图也一并画出来了)

将一段代码转换为数据流电路

论文中使用了以下的流程根据一段中间表达(IR)生成对应的数据流电路:

  1. 实现控制流:
    • 每一个基本块都必须且只能向它的直接后继(immediate successor)基本块发送数据, 但一个基本块可以有几个直接后继基本块.
    • 每一个基本块都必须且只能从它的直接前驱(immediate predecessor)基本块接收数据, 但一个基本块可以有几个直接前驱基本块.

这样可以保证控制流和数据流在基本块之间的传递是同步的.

  1. 实现顺序控制网络: 对于一些特殊的组件, 比如Constant操作, 它只是固定输出一个值, 并不需要接受任何输入. 为了让所有电路组件能正常被触发, 我们可以根据控制流生成一条独立的控制通路(Control Path). 在这条通路上传递的是一个"无数据变量"(A Data-less Variable), 它不携带任何数据, 只用来表示"控制流已经到达了这里". 因此这个"无数据变量"应该是每一个基本块的输入(Livein)和输出(Liveout)内容之一.

  2. 实现数据流. 实现以上两点后实现数据流的方法就很直接了, 将对数据的操作映射为其对应的数据流组件, 比如一个基本块对应一个组件. 如果一个组件有多个直接后继组件, 那么它的输出需要做fork操作, 然后分发到各个后继组件. 如果一个组件的输出未被使用(比如被分支选择之后结果被丢弃), 那么这个输出应该被连接到一个sink组件上.

论文中通过以上三个方面保证了转换出的电路在功能上是正确的.

基本数据流组件

Dynamatic中采用了以下基本的数据流组件用于构建数据流电路:

  • eager fork: 类似操作系统里面的fork系统调用, 它将同一份token做复制, 然后分发到多个后继组件上. 它是"异步", 只要后继组件中有一个准备好了, 就会将token分发出去. 但只有当所有后继组件都接收到前一个token后, fork组件才会接收下一个token.
  • lazy fork: 和eager fork类似, 但它是"同步"的, 它只会在所有后继组件都准备好之后, 才会将token分发出去.
  • join: 它可以理解成fork的反操作, 它是"同步"的, 只有当所有前驱组件的输出都有效时, 才会将输入token合并并传递给其后继组件. 它可以用来做fence操作.
  • merge: 和join类似, 但它是"异步"的, 它只要有一个前驱组件的输出有效, 就会将输入token合并并传递给其后继组件.
  • mux: 多路选择器
  • cmerge: 在merge的基础上增加了一条输出信号, 用来表明merge组件使用了哪个前驱组件的输出.
  • source: 数据流电路的输入组件, 它永远准备好发送token, 并且只有一个后继组件. (可以用source+fork来实现向多个后继组件分发token, 组件应该是"最小化"的, 因此source组件本身不应该有多个后继组件, 那是fork的工作)
  • sink: 它永远准备好接收token, 并且没有任何后继组件. 类似的, 它只有一个前驱组件.

插入LSQ

如果内存依赖不能在编译期被预测, 就比如开头所讲的情形, 那Dynamatic会在数据流电路中插入一个LSQ(Load Store Queue)组件. 这个LSQ组件内部会对访存操作进行调度, 保证语义上的正确性和顺序性.

本页内容