通过无序执行并行化我的自定义编译器

Question

我已经构建了自己的解析器，至少现在，它只会处理类似于

的语句

return a * b * c * (d + e) / f

沿着它生成的抽象语法树 (AST) 行走时我将看到的内容如下所示

（按照我看到的确切顺序，并且是希望描述性伪语言）：

RETURN_STMT
BO(left: a, right: BO, op: *)
BO(left: BO, right: f, op: /)
BO(left: BO, right: PE, op: *)
BO(left: b, right: c, op: *)
PE(BO)
BO(left: d, right: e, op: +)

其中 BO 是 Binary Ooperator 的缩写， PE代表P括号Expression.

我现在开始构建我的编译器，它将能够采用上面的 AST，并且运行它在我也生成的自定义硬件中。

关于硬件的一些信息：一种类似 VHDL 的语言，包含一组基本组件，如乘法器、除法器、加法器等。它可能看起来像这样（同样在希望描述性伪代码）：

reg a, b, c, d, e, f
int i <- 0
b <- buffer[4]                                 // a simple FIFO queue

...                                            // some initialization

m1 <- MUL(a, b, if: i == 0)                    // 2 cycles
m2 <- ADD(d, e, if: i == 0){i++}               // 1 cycle
m3 <- MUL(c, m2, if: i == 1){i++}              // 2 cycles
m4 <- MUL(m1, m3, if: i == 2){i++, b.put(m4)}  // 2 cycles
m4 <- DIV(b.get(), f, if: i == 3){i++}         // 6 cycles

if 说明符将决定（在每个循环中）操作何时触发。这样我就可以让我的硬件并行执行操作。

如果我们想象无限量的流 a, b, c, d, e, f 值，那么我们需要为每个运算符处理周期性的延迟。如果 MUL 操作需要 2 个周期，而 DIV 需要 6 个周期，那么我将执行 3 次乘法才能完成一次除法。因此，我可以将中间值存储在 缓冲区 中，这将确保（在此处讨论的流式传输场景中）不会丢失任何内容。

实际上，如果我想将我的自定义 c-like 语言与我的自定义（暂时模拟）硬件联系起来，我的编译器必须生成这些内容。

出现了一些问题：

我可以重复使用硬件组件，但最少需要多少？我需要的组件（MUL、DIV 等）？
所需缓冲区的最小大小是多少？
鉴于最初显示的我的（递归）步行算法的输出上面，我如何创建一系列优化的基本操作，同时尊重硬件延迟要求？

Answer 1

您实际上是在解决约束规划问题。您有诸如“操作 a 取决于 b 的结果”、“操作结果在 3 个时钟周期内可用”、“a 和 c 共享相同资源”（例如乘法器）等约束。一个快速而肮脏的技巧如何免费获得此类解决方案是简单地重用现有的 CLP(FD) 引擎，例如 SWI-Prolog。例如，在我的 HLS 编译器 [1] 中，我只生成 SWI-Prolog 程序并运行它们来安排资源。如果您想实现自己的约束求解器，请准备好进入一个非常非常深的兔子洞。

现在，困难的部分来了 - 资源分配。一方面，你有你的表达式（我想，一个内部循环体？），它必须以最大可能的吞吐量执行，理想情况下每个时钟周期一个结果退出。另一方面，您的区域有限，因此您可能希望共享昂贵的资源，例如除法器、平方根等。一种方法是在编译器中设置反馈循环。首先，围绕您选择共享的资源将表达式拆分为多个部分，然后完成编译管道并测量生成的吞吐量和面积。如果它们在您的限制范围内，请继续，如果不是，请回溯并 select 另一组资源进行共享。先从最贵的开始尝试。

另一件事 - 不要做缓冲。不要将您的表达式表示为 FSM。这效率不高。而是将其流水线化，并将过早出现的结果存储在流水线寄存器中（理想情况下，您不会有太多，因为您的约束求解器应该有效地安排它们）。这样，您的硬件编译表达式将适合作为内部循环体，每个时钟周期获取新的输入值并在每个时钟周期退出结果（如果您共享资源并将任务重新发布回管道，则速度会更慢）。

[1] https://github.com/combinatorylogic/soc/tree/a1d282d793548030cba940496bed90ff3a29c0ba

通过无序执行并行化我的自定义编译器

Parallelizing my custom compiler with out of order execution

c++

compiler-construction

algorithm

parallel-processing

hardware-acceleration