密码学 - 调试IOps - Zama-Ai

zama-ai
发布于 2025-05-10 10:55
阅读 13

本文主要介绍了在TFHE中使用HPU加速时，如何调试IOps以优化性能和保证正确性。文章详细介绍了HPU mockup的使用方法，以及如何通过分析mockup的输出、指令调度器追踪等工具来解决IOps中出现的问题，并提供实际的性能改进案例。

假设你刚发现了一个 _TFHE_ 的绝佳应用，并决定使用 _HPU_ 对其进行加速。但是，使用高级的 _TFHE-rs_ API 时，你并没有获得想要的性能。与普通 CPU 一样，你可以降低到指令集级别（也就是汇编级别），尝试加速你的特定用例。这种行为我们称之为编写专门的 IOp。为此，你需要更多地了解 _HPU_ 架构及其指令集 [here](https://learnblockchain.cn/article/21145)。本页面假设你已经阅读过，或者已经了解如何编写 IOp。

然而，在编写了你的专门 IOps 之后，你发现你的操作结果是错误的，或者性能不如你预期的好。如果这和你的情况类似，请继续阅读。

## 常规调试选项

在追求完美 IOp 的过程中，你通常在两个主要方面努力：正确性和性能。调试 IOp 的正确性通常使用 mockup 完成——_HPU_ 的软件版本，无需任何 _HPU_ 硬件即可访问中间结果。它比真实的 _HPU_ 慢得多，甚至比在 CPU 上运行 _TFHE_ 还要慢，但它提供了指令集级别的可观察性，使你能够找出 _HPU_ 和你之间的确切不一致之处。mockup 还试图忠实地预测 _HPU_ 的性能，因此它也可以用于优化性能。但是，真实的 _HPU_ 还有其他因素会影响性能，例如运行以将你的密文传输到 _HPU_ 和从 _HPU_ 传输的软件栈，以及系统中的多个内存和 PCIe 参与者，它们会造成 IO 的不确定性，从而导致计算的不确定性。如果你发现 mockup 性能预测和真实的 _HPU_ 性能之间存在很大的差异，那么你还有另一个工具可以使用：指令调度器跟踪。我们将在后续章节中详细介绍这三个选项。

### _HPU_ mockup

_HPU_ mockup 包含在 _TFHE-rs_ _HPU_ 后端中。它基本上是一个独立的 rust 程序，通过 Unix 套接字连接到 _HPU_ 后端，并响应寄存器读取、IOp 请求等，以我们能找到的最忠实的方式来模拟 _HPU_。它也可用于测试其他 _HPU_ 参数集和/或架构假设场景，而无需实际编写 RTL（你可能像我们一样，尽可能快地逃离它）。话虽如此，我们将把这些留到下一集，只关注调试。如果你感到罕见的学习欲望，请阅读 mockup 的 readme
[file](https://github.com/zama-ai/tfhe-rs/blob/main/mockups/tfhe-hpu-mockup/Readme.md)。如果这不能满足你的求知欲，你总是可以阅读代码。要启动 mockup，你可以克隆 _TFHE-rs_ 存储库，编译 mockup 并使用以下命令启动它：

```bash
cargo build --release --bin hpu_mockup --features isc-order-check
source setup_hpu.sh -c sim
target/release/hpu_mockup                                                   \
    --dump-out mockup.dump                                                  \
    --dump-reg                                                              \
    --log-out mockup.log                                                    \
    --report-out mockup.rpt                                                 \
    --report-trace                                                          \
    --params mockups/tfhe-hpu-mockup/params/gaussian_64b_pfail64_psi64.toml \
    --freq-mhz 350
```

> [!NOTE]
> mockup 将作为一个独立的进程运行，上面的命令将为你启动它。它只会停留在那里等待来自 _HPU_ 后端的连接，并且在大多数情况下不会给你任何输出，即使建立了连接。

上面的命令将编译并启动 mockup，同时在后端告诉它做某些事情时，尽可能多地转储调试信息。`--params` 参数指定模拟的 _HPU_ 参数集和架构。提供的只是一个例子。频率只需要将周期转换为时间，并且仅在报告指令延迟统计信息时使用，因此不要太纠结于它。

现在，任何 _TFHE-rs_ 代码都需要使用 _hpu_ 功能进行编译，并通过使用 sim 配置 flavor 来生成 `setup_hpu.sh`：

```
cd tfhe-rs
source setup_hpu.sh -c sim
```

如果你这样做是对的，那么你所有的 _HPU_ _TFHE-rs_ 代码现在都将使用 mockup 而不是真实的 _HPU_。只需让它在不同的终端上运行并忘记它即可。

### 调试正确性

一旦你编写了一个 IOp，你将需要在实际创建到 _TFHE-rs_ 的Hook之前，对其进行独立测试。为此，我们提供了一个名为 `hpu_bench` 的简单程序，你可以使用它来基准测试和验证你的 IOp 是否正确运行。这个 bench 也可以与 mockup 一起使用，尽管延迟报告将是错误的，因为它将测量 _CPU_ 时间，而不是 _HPU_ 时间。例如，以下命令将使用 mockup 对明文 64 位值 _1_ 和 _0_ 进行同态乘法基准测试：

```bash
cargo run --profile devo --features hpu --example hpu_bench -- \
    --integer-w 64 \
    --iop MUL \
    --trivial \
    --src 1  \
    --src 0 \
    --iter 1
```

> [!NOTE]
> 以下是本示例中使用的选项的描述：
> - `--integer-w`，选择整数运算中使用的明文输入的位宽。
> - `--iop`，选择要进行基准测试的 IOp。此示例选择了 _MUL_ IOp。如果你正在测试自己制作的新 IOp，则需要在此处指定它。如果你不指定此选项，则将对所有 IOps 进行基准测试。
> - `--trivial`，通过以简单的方式加密你的明文来运行基准测试。这主要用于调试你的 IOp 正确性。
> - `--src`，用于强制 IOp 的一个输入的明文。你可以多次指定此选项来强制多个输入。如果你不强制输入，它将被随机化。
> - `--iter`，基准测试将通过递归调用指定的 IOps 来完成，通过将输出循环到第一个输入，提供的次数。默认为 1。
>
> 你总是可以调用 `hpu_bench --help` 来了解更多关于接受的选项。

作为输出，你将获得一个延迟报告（暂时忽略它）和以明文形式显示的乘法结果。该结果可用于检查你的 IOp 是否正常工作。你可以测试许多输入组合，甚至省略 `--src` 来尝试随机值，并围绕此编写一个程序，以确保你的 IOp 按预期工作。我们都知道你正在阅读本文，因为它没有，所以下一步是阅读 mockup 输出以帮助你处理问题。

mockup 提供了两个主要信息，这些信息对于调试 IOp 非常有用：
- DOp 执行顺序跟踪；
- 中间 DOp 结果。

你需要知道 DOp 执行顺序的原因有两个——了解性能并能够跟踪中间 DOp 结果。目前，mockup 会在执行 DOp 时将其结果写入使用 `--dump-out` 参数提供的任何文件夹，因此了解执行顺序对于能够将结果与 DOps 匹配是绝对必要的。我们计划在将来简化此步骤，具体取决于我们意识到用户需要调试其 IOps 的频率。

在 `mockup.dump/blwe/run` 下，你将为 DOp 的每个输出找到一个或多个十六进制文件。这取决于 LWE 密文在内存上的打包方式，并且将来可能会更改。但是，我们正在运行简单加密的版本进行调试（正如你可能在调用基准测试程序时通过 `--trivial` 参数注意到的那样）。密文的最后几位包含消息，并且整个密文以小端序、**LSB** 优先的顺序输出。

能够调试 IOp 唯一缺少的是能够将中间输出链接到特定的 DOp。在 `mockup.dump/dop` 下，你将找到 IOp 流的汇编文件列表（因为它已收到）以及 DOps 执行方式的汇编列表。通过打开包含你要调试的 IOp 的汇编文件，你现在可以理解中间结果文件，希望这将使你更进一步地调试你的 IOp。

### 使用 mockup 调试性能

既然你的 IOp 按预期工作，你对其性能感到困惑。在放弃并责怪 _HPU_ 团队之前，你还有其他选择。其中一种方法是查看 mockup 产生的其他信息，以了解问题所在。

正如你从 _HPU_[^1] 上的其他文档页面了解到的那样，_TFHE_ 和 _HPU_ 处理时间的主要瓶颈是可编程自举 (PBS)。在 _HPU_ 上，PBS 的处理时间几乎比线性/分层或 IO 操作的处理时间长 100 倍。这意味着性能将主要由你的 IOp 必须执行的 PBS 批次数量决定。考虑到这一点，mockup 生成一个执行报告，让你深入了解已执行了多少 DOps 及其延迟。如果按照上面的示例操作，你可以在 `mockup.rpt/` 下找到此报告。对于每个执行的不同 IOp 都会生成一个报告，尽管每个 IOp 类型只有一个报告。以下是乘法的示例：

```
Report for IOp: MUL      <I64 I64> <I64@0x40> <I64@0x00 I64@0x20>
TimeRpt { cycle: 44061792, duration: 146.872ms }
InstructionKind {MemLd: 1703, MemSt: 1691, Arith: 1840, Pbs: 1685, Sync: 1}
Processing element statistics:
	 "KsPbs_0" => issued: 1685, batches: 142, by_timeout: 0, usage: 0.9891165172855315
	 "LdSt_0" => issued: 3394, batches: 3394, by_timeout: 0, usage: 1
	 "Lin_0" => issued: 1840, batches: 1840, by_timeout: 0, usage: 1
```

除了实际延迟之外，你可以从本报告中获得的最重要信息是 PBS 批次的数量（在本例中为 142）和 PBS 单元使用率。这将指示批次已满的时间百分比，指示你的 IOp 使用 PBS 单元的效率。**by_timeout** 变量也很重要，因为它指示有多少批次未完全调度满，并且由于无法调度更多 PBS 而超时启动。此超时功能主要是一个安全功能，设置为与批次延迟相当的非常大的值。你的 IOps 应始终指示如果该批次是后续批次的依赖项，则是否刷新该批次。

如果你不明白为什么你的 PBS 单元使用率很低，你将必须检查指令调度器跟踪。在同一目录（示例中的 `mockup.rpt`）中，你将找到每个执行的 IOp 类型的 **json** 文件。这包含指令调度器事件的跟踪，你可以从中访问调度过程的几乎所有详细信息。此跟踪是为了模拟真实的硬件跟踪而制作的，因此以下技术也将有助于使用真实硬件进行调试。

### 使用 _HPU_ 调试性能

在我们深入了解如何使用跟踪调试你的 IOp 的细节之前，你需要更多地了解指令调度器。

#### 指令调度器

_HPU_ 中的指令调度器负责将指令调度到组成 _HPU_ 的多个处理单元。目前只有三个：加载存储单元、线性 FHE 操作单元和 PBS 单元。所有三个单元都可以并行运行，PBS 单元实际上可以并行运行许多引导程序。为了最大化效率，指令调度器会查看 DOp 流并重新排序操作（同时尊重它们的依赖关系），以使所有三个单元尽可能地忙碌。在执行此操作时，它会记录用于做出决策的所有事件，例如将 DOps 排队、将 DOps 调度到处理元素、执行、清除 DOp 的依赖关系等。此事件流将发送到 HBM 内存中的缓冲区，该缓冲区稍后可以通过 PCIe 检索。

mockup 捕获的跟踪与硬件捕获的跟踪之间的主要区别在于，在硬件中，指令调度器实际上并不知道哪个 IOp 正在执行。因此，所有事件都只是按它们被看到的顺序排队到同一内存中，而 mockup 实际上按 IOp 分隔事件。这意味着在调试硬件跟踪之前，你必须找出你的 IOp 在事件流中的位置。这并不难，因为所有 DOp 流都带有同步 ID，该 ID 可用于分隔来自多个 IOps 的事件，因此你只需在许多 DOp 组中搜索你的 IOp 即可。尽管如此，这仍然很麻烦，如果 mockup 重现了 _HPU_ 性能，那么你最好使用它，因为它记录的信息比硬件多。同样，所有这些都是动态目标，我们可能会在将来的迭代中将这些信息添加到跟踪中。

#### 检索硬件跟踪

无论如何，在你使用了你的 _HPU_ 之后，你可以通过编译和执行一个小型的 rust 程序——_hputil_ 来检索跟踪：

```bash
cargo build --release --features hpu,utils,hw-v80 --bin hputil
./target/release/hputil trace-dump -f trace.json
```

这会将所有事件保存到一个 **json** 文件中。HBM 跟踪缓冲区很小，在编写时约为 32MB，但是将所有这些信息解压缩到 **json** 文件会导致文件大小超过 GB。我们计划更改输出格式或允许使用多种输出格式，但是目前不支持。

一旦你有了你的跟踪文件，请妥善保存它，因为它可能是弄清楚你的 IOp 发生了什么的关键。

> [!NOTE]
> 此程序对于从 _HPU_ 提取更多信息很有用，例如转储调试寄存器。它是供内部使用的，如果你清楚地了解每个寄存器包含的内容，那么它的其余功能才有用。尽管如此，大多数寄存器都有一个暗示性的名称，因此你可以阅读 `--help` 输出以了解更多信息。

### 使用指令调度器跟踪进行调试

一旦你有了想要查看的跟踪文件，无论它是硬件跟踪还是 mockup 跟踪，你都可以使用专门为此目的编写的 python 库。你可以在
[_TFHE-rs_](https://github.com/zama-ai/tfhe-rs/tree/main/backends/tfhe-hpu-backend/python) 代码库中找到它。该库的主要目的是将跟踪分成来自不同 IOps 的独立跟踪，并通过筛选不同类型的事件来帮助你分析跟踪，同时收集有关这些事件的统计信息。首先，你导入该库：

```python
from isctrace.analysis import Trace, Refilled, Retired
```

这三个类主要抽象三种类型的事件，重新填充，退休和跟踪事件（所有事件）。当一个操作通过一个处理元素完成时，会看到一个退休事件。通过仅收集那种类型的事件，你可以按执行的顺序查看操作流。你可以阅读跟踪并按如下方式筛选这些事件：

```python
iops = Trace.from_hw("trace.json") # Or Trace.from_mockup, for mockup traces
retired = Retired(iops[x])          # x 是你想要查看的 IOp 索引
```

你可以将它们视为 pandas **DataFrame**：

```python
retired.to_df()
```

**Retired** 类不仅仅是收集退休事件。实际上，它将发布事件与退休事件配对以获得 DOp 延迟。

你可以从 **Retired** 类获得的另一个非常重要的信息是我们所说的 PBS 延迟表，它也是一个 **DataFrame**：

```python
retired.pbs_latency_table(freq_mhz=freq_mhz)
```

这将为你提供一个批处理大小与批处理延迟信息表。如果你在你的流中找到了任何非完整批处理，这将有助于你找到它们以及每个批处理大小的实际延迟。此处测量的延迟是从一个批处理到另一个批处理的延迟，因此它们将包括作为批处理依赖项执行的任何类型的线性/IO 操作的延迟。但是，这些延迟通常非常小，并且指令调度器通常可以交织与当前正在执行的批处理没有共享依赖关系的操作，因此它们不会对最终批处理延迟产生影响。尽管如此，如果不是这种情况，你可以发现一些错误或改进你的 IOp。

显然，如果此信息不足以弄清楚发生了什么，你可以对 **Trace** 类中记录的信息执行任何你想要的操作。

我们现在已经介绍了我们自己实际使用的所有工具和技巧，以调试和改进我们自己的 IOps。尽管如此，这里的大部分魔力在于知道如何为 _HPU_ 正确编写程序，因此我们将以一个性能改进示例结束。

## 一个例子

假设你想编写一个以同态方式比较两个密文的 IOp[^2]。天真地，并假设你已经了解 _HPU_ 指令集，你可以尝试执行以下操作：

其中灰色菱形表示 PBS，如果输入不为零，则输出 1，否则输出零，除非它是负数，在这种情况下它实际上会输出 -1，因为 PBS 是 nega-cyclic 的。从现在开始，我们将此 PBS 称为“**符号 PBS**”。如果你将 1 添加到此结果，你将获得一个顺序值：0 表示小于，1 表示等于，2 表示大于。

黄色菱形是“**顺序合并 PBS**”，我们将从现在开始这样称呼它。它查看打包到一个密文中的两个顺序消息。如果最重要的顺序值等于，则 PBS 选择最不重要的顺序，否则选择最重要的顺序。打包操作是隐式的，但它映射到 a*4 + b，可以使用单个 _MAC_
操作由 _HPU_ 完成，这非常便宜。

粉色菱形是最终比较 PBS，或“**比较 PBS**”，现在将顺序值转换为一个布尔值，这取决于你尝试执行的比较类型。如果你想要进行小于比较，则仅当输入是大于值 (2) 时，你才会输出 0。

图中的所有操作都直接映射到指令集中的 DOp。然后，我们可以尝试通过简单地减去每对密文的每一位数字，在结果上运行 **符号
PBS**，加 1 以获得每个数字的顺序值，并使用 **顺序合并
PBS** 从最高有效位到最低有效位以递归方式合并顺序值来执行比较。最终结果将是通过 **比较
PBS** (粉色) 将最终顺序值转换为布尔值的结果。请注意，_TFHE-rs_ 和我们自己的 IOps 进行了一些进一步的简化，并使用更多的
FHE 技巧来尝试减少使用的 PBS 数量，但为了简单起见，我们将在此处不使用它们。另外，请注意，此示例的最终结果将最终可能与实际实现相媲美，但我将保留理解作为读者的练习。

从上面的图直接翻译成 rust 固件代码实际上非常简单。即使本文的目的不是解释如何为 HPU 编写固件，为了完整起见，我将在此处粘贴它：

```rust
pub fn cmp_gt(prog: &mut Program) {
    // Create Input/Output template entry points to be linked at execution time.
    // 创建在执行时链接的输入/输出模板入口点。
    let mut dst = prog.iop_template_var(OperandKind::Dst, 0);
    let src_a = prog.iop_template_var(OperandKind::Src, 0);
    let src_b = prog.iop_template_var(OperandKind::Src, 1);

// Get the index of the required PBSs
    // 获取所需 PBS 的索引
    let sgn_pbs = new_pbs!(prog, "CmpSign");   // gray   diamond // 灰色   菱形
    let red_pbs = new_pbs!(prog, "CmpReduce"); // yellow diamond // 黄色 菱形
    let gt_pbs = new_pbs!(prog, "CmpGt");      // pink   diamond // 粉色   菱形

dst[0] <<= std::iter::zip(src_a, src_b)
        .rev()
        .fold(prog.new_imm(pbs_macro::CMP_EQUAL), |acc, (a, b)| {
            (&(&a - &b).pbs(&sgn_pbs, false) + &prog.new_imm(1))
                .pack_carry(&acc)
                .pbs(&red_pbs, false)
        })
        .pbs(&gt_pbs, false);
}
```

> [!NOTE]
> 请注意，本例中使用的所有代码都可以在
> [here](https://github.com/zama-ai/tfhe-rs/tree/main/backends/tfhe-hpu-backend/src/fw/fw_impl/demo.rs) 找到。
> 这是一个额外的固件实现，仅用于演示目的。

正如我们所了解的那样，理解此 IOp 性能的第一部分是对其进行基准测试。以下是由 mockup 提供的 64 位操作的上述操作的延迟报告：

```
> cargo run --profile devo --features hpu --example hpu_bench -- \
    --fw Demo --integer-w 64 --iop CMP_GT --src 1 --src 0
> cat mockup.rpt/CMP_GT*.rpt
Report for IOp: CMP_GT   <I2 I64> <I2@0x40> <I64@0x00 I64@0x20>
TimeRpt { cycle: 13166040, duration: 43.886ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 96, Pbs: 65, Sync: 1}
Processing element statistics:
	 "KsPbs_0" => issued: 65, batches: 34, by_timeout: 34, usage: 0.17379679144385018
	 "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
	 "Lin_0" => issued: 96, batches: 96, by_timeout: 0, usage: 1
 >
```

在这个例子中，一个批处理大约需要 1 毫秒，超时设置为 300 微秒。首先弹出的是使用率或 PBS 单元效率为 17%。此外，IOp
需要的 PBS 数量为 65。我们知道 _HPU_ 可以并行运行许多 PBS，在这个例子中是 10 个。这意味着那些
65 个 PBS 可能会在 65/10 * 1ms=6.5ms 上运行，而我们现在为 43ms！你知道你不能信任 _HPU_
团队，但在你发出一些噪音之前，让我们收集更多信息。

为了能够进行调查，你可以读取 mockup 跟踪并打印退休指令和批处理延迟报告，如前几节所示。以下是 8 位比较的结果，为了使事情简单：

```
           latency   delta  reltime opcode             args
timestamp
503482162      422     422      422     LD          R0 @0x3
503482447      681     285      707     LD          R1 @0x7
503482729      807     282      989     LD          R7 @0x2
503483160     1212     431     1420     LD          R8 @0x6
503483458     1354     298     1718     LD         R14 @0x1
503483742     1612     284     2002     LD         R15 @0x5
503484040     1722     298     2300     LD         R21 @0x0
503484485     2141     445     2745     LD         R22 @0x4
503484622     2149     137     2882    SUB         R2 R0 R1
503486697     3530    2075     4957    SUB         R9 R7 R8
503488779     5030    2082     7039    SUB      R16 R14 R15
503490861     6369    2082     9121    SUB      R23 R21 R22
503872701   388072  381840   390961    PBS        R3 R2 @10
503872776   386072      75   391036    PBS       R10 R9 @10
503872858   384072      82   391118    PBS      R17 R16 @10
503872940   382072      82   391200    PBS      R24 R23 @10
503874855     2147    1915   393115   ADDS          R4 R3 1
503876931     4148    2076   395191   ADDS        R11 R10 1
503879014     6149    2083   397274   ADDS        R18 R17 1
503881097     8150    2083   399357   ADDS        R25 R24 1
503883173     8311    2076   401433   ADDS          R5 R4 4
504270837   387657  387664   789097    PBS        R6 R5 @11
504272990     2146    2153   791250    MAC   R12 R6 R11 X4
504660668   387671  387678  1178928    PBS      R13 R12 @11
504662821     2146    2153  1181081    MAC  R19 R13 R18 X4
505050499   387671  387678  1568759    PBS      R20 R19 @11
505052652     2146    2153  1570912    MAC  R26 R20 R25 X4
505440337   387678  387685  1958597    PBS      R27 R26 @11
505828029   387685  387692  2346289    PBS      R28 R27 @12
505828481      445     452  2346741     ST         @0x8 R28

min          avg          max          sum  count
batch size
1           1292.306667  1303.392667  1326.323333  6516.963333      5
4           1304.000000  1304.000000  1304.000000  1304.000000      1
```

你可能注意到的第一件事是我们主要有两种不同的批处理大小，一个批处理大小为 4，五个批处理大小为 1 PBS。尽管我们没有以任何并行方式描述 IOp，但指令调度程序正确地识别出 **符号 PBS** (灰色)
可以全部并行运行，因为它们没有共享依赖关系。对于 8 位，我们使用 4 个密文和 4 个 **符号 PBS**，因此调度程序创建了一个由 4 个 PBS 组成的批处理。对于 64
位，它实际上可以启动 3 批 12 个 [^3]。那么，为什么它也不能将 **顺序合并
PBS** 打包到批处理中呢？原因很简单，因为这个算法是递归的 —— 一个 **顺序合并 PBS** 依赖于先前的合并。换句话说，在上一个 **顺序合并
PBS** 完成之前，一个 **顺序合并 PBS** 无法启动。对于硬件工程师来说，递归性一直困扰着他们，他们试图并行化操作数十年，最近，随着多核 _CPU_ 和大规模并行
_GPU_ 的出现，也困扰着软件工程师。这对于许多算法来说都很常见，包括基本算法，如加法、除法和更具体的算法，如 ECC 码、排序、IIR
滤波器以及无数其他算法。

并行化递归算法的一种常用方法是找到问题的不同公式，你可以将其分解为两个可以合并的并行计算。如果这可行，那么你可以对两个并行计算递归地执行相同的过程，以获得四个并行计算，依此类推，直到你无法进一步减少它为止。这被称为递归加倍，并广泛用于现在著名的，令人难以置信的丰富且大部分被遗忘的 kogge-stone adder
的推导中[^4]。几乎所有递归算法的突破递归都以某种方式或另一种方式使用递归加倍，并且它也可以用于我们简单的比较中。如果你意识到你可以将整数分成两部分，计算最高有效部分的所有数字的顺序，以及最低有效部分的所有数字的顺序，并通过单个合并来合并生成的两个顺序，那么我们已经公式化的比较可以分解为两个使用完全相同的操作的并行问题。如果你递归地不断分割各个部分，你将得到一棵合并树，而不是一个递归的合并流。如果你有足够的 “线程”
或计算元素，树的最终延迟将与 **log(N)** 乘以合并延迟成正比，而不是与 **N** 成正比。有人说一张图片胜过千言万语：

请注意，计算现在分阶段完成，每个阶段都带有前一个阶段一半的并行工作。它并非一直完全并行直到结束，但仍然比原来的递归公式要好得多。

让我们对这个新公式 (**demo.rs** 中的 **cmp_gte()**) 进行基准测试：
```
IOp 报告: CMP_GTE  <I2 I64> <I2@0x40> <I64@0x00 I64@0x20>
TimeRpt { cycle: 3699192, duration: 12.33ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 95, Pbs: 64, Sync: 1}
Processing element statistics:
	 "KsPbs_0" => issued: 64, batches: 10, by_timeout: 7, usage: 0.5636363636363636
	 "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
	 "Lin_0" => issued: 95, batches: 95, by_timeout: 0, usage: 1
```

我们极大地改善了延迟。请注意，我们现在只做了十批次，而不是三十四个。PBS 单元的使用率虽然不完美，但大幅提高。请注意，我们仍然有未满的批次，特别是对于树的最后阶段。如果不向调度器提供应该刷新这些批次的信息，它只会在超时后启动批次。通过在每个阶段结束时正确刷新批次，我们可以得到这个 (**demo.rs** 中的 **cmp_lt()**):

```
Report for IOp: CMP_LT   <I2 I64> <I2@0x40> <I64@0x00 I64@0x20>
TimeRpt { cycle: 3176268, duration: 10.587ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 95, Pbs: 63, Sync: 1}
Processing element statistics:
	 "KsPbs_0" => issued: 63, batches: 10, by_timeout: 2, usage: 0.5545454545454545
	 "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
	 "Lin_0" => issued: 95, batches: 95, by_timeout: 0, usage: 1
```

这几乎是百分之二十的改进。现在，仍然有两个批次超时。你可以读取追踪数据并读取批次延迟报告，以了解这些批次的位置。在这个特殊情况下，发生的情况是两个批次之间的线性运算花费了超过 300us 才能完成。仍然可以隐藏这种延迟，但这需要重新排序 IOp 以避免这种情况。我们正在开发一种新的固件框架，它通过在操作依赖图上运行模拟并尝试以最佳方式调度操作来解决这些细节。你唯一的工作是弄清楚如何并行化操作并将这些操作依赖项编写为图。你可以阅读当前的
[llt](https://github.com/zama-ai/tfhe-rs/blob/main/backends/tfhe-hpu-backend/src/fw/fw_impl/llt/mod.rs)
IOp 实现来学习如何做到这一点，但它尚未被认为是广泛使用的稳定版本。

## 结束语

希望本文档能够启发你了解可用于调试 _HPU_ IOps 的工具。在尝试编写甚至调试 IOps 之前，请确保你还阅读了其他与向 _HPU_ 编写固件相关的文档。

除此之外，祝你同态加密愉快！

[^1]: 如果你还没有阅读它们，现在就去阅读，这篇可以稍后再看。
[^2]: 我们已经有可以做到这一点的 IOps，但它们实际上是关于如何显着提高 IOp 性能的一个非常好的例子，或者从另一个角度来看，如何使 _HPU_ 看起来很糟糕。
[^3]: 尽管在此示例中，典型的最小批量大小为十个 PBS，但是 _HPU_ 运行十二个 PBS 比分别运行两批十个和两个 PBS 效率更高。一批十二个的延迟是单个一批十个的延迟的 12/10，而两批十个和两个的延迟是两倍。这是因为作为 PBS 的一部分要完成的工作量可以分解为许多较小的部分，并且有效延迟变为那些较小的工作块的延迟之和。这表明我们可能会用来自单个 PBS 的工作填充所有十个槽，并使 PBS 延迟降低十倍。但是，我们无法做到这一点，因为获取引导密钥的带宽受到限制，迫使我们在多个 PBS 中共享单个旋转的密钥，从而保持最大的 PBS 吞吐量。
[^4]: 我们都站在巨人的肩膀上，即使有点老，也应该承认巨人。Kogge, Peter M., and Harold S. Stone. "A parallel algorithm for the efficient solution of a general class of recurrence equations." IEEE transactions on computers 100.8 (1973): 786-793.
```

>- 原文链接： [github.com/zama-ai/hpu_f...](https://github.com/zama-ai/hpu_fpga/blob/main/docs/debug.md)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

假设你刚发现了一个 TFHE 的绝佳应用，并决定使用 HPU 对其进行加速。但是，使用高级的 TFHE-rs API 时，你并没有获得想要的性能。与普通 CPU 一样，你可以降低到指令集级别（也就是汇编级别），尝试加速你的特定用例。这种行为我们称之为编写专门的 IOp。为此，你需要更多地了解 HPU 架构及其指令集 here。本页面假设你已经阅读过，或者已经了解如何编写 IOp。

然而，在编写了你的专门 IOps 之后，你发现你的操作结果是错误的，或者性能不如你预期的好。如果这和你的情况类似，请继续阅读。

常规调试选项

在追求完美 IOp 的过程中，你通常在两个主要方面努力：正确性和性能。调试 IOp 的正确性通常使用 mockup 完成——HPU 的软件版本，无需任何 HPU 硬件即可访问中间结果。它比真实的 HPU 慢得多，甚至比在 CPU 上运行 TFHE 还要慢，但它提供了指令集级别的可观察性，使你能够找出 HPU 和你之间的确切不一致之处。mockup 还试图忠实地预测 HPU 的性能，因此它也可以用于优化性能。但是，真实的 HPU 还有其他因素会影响性能，例如运行以将你的密文传输到 HPU 和从 HPU 传输的软件栈，以及系统中的多个内存和 PCIe 参与者，它们会造成 IO 的不确定性，从而导致计算的不确定性。如果你发现 mockup 性能预测和真实的 HPU 性能之间存在很大的差异，那么你还有另一个工具可以使用：指令调度器跟踪。我们将在后续章节中详细介绍这三个选项。

HPU mockup

HPU mockup 包含在 TFHE-rs HPU 后端中。它基本上是一个独立的 rust 程序，通过 Unix 套接字连接到 HPU 后端，并响应寄存器读取、IOp 请求等，以我们能找到的最忠实的方式来模拟 HPU。它也可用于测试其他 HPU 参数集和/或架构假设场景，而无需实际编写 RTL（你可能像我们一样，尽可能快地逃离它）。话虽如此，我们将把这些留到下一集，只关注调试。如果你感到罕见的学习欲望，请阅读 mockup 的 readme file。如果这不能满足你的求知欲，你总是可以阅读代码。要启动 mockup，你可以克隆 TFHE-rs 存储库，编译 mockup 并使用以下命令启动它：

cargo build --release --bin hpu_mockup --features isc-order-check
source setup_hpu.sh -c sim
target/release/hpu_mockup                                                   \
    --dump-out mockup.dump                                                  \
    --dump-reg                                                              \
    --log-out mockup.log                                                    \
    --report-out mockup.rpt                                                 \
    --report-trace                                                          \
    --params mockups/tfhe-hpu-mockup/params/gaussian_64b_pfail64_psi64.toml \
    --freq-mhz 350

[!NOTE] mockup 将作为一个独立的进程运行，上面的命令将为你启动它。它只会停留在那里等待来自 HPU 后端的连接，并且在大多数情况下不会给你任何输出，即使建立了连接。

上面的命令将编译并启动 mockup，同时在后端告诉它做某些事情时，尽可能多地转储调试信息。--params 参数指定模拟的 HPU 参数集和架构。提供的只是一个例子。频率只需要将周期转换为时间，并且仅在报告指令延迟统计信息时使用，因此不要太纠结于它。

现在，任何 TFHE-rs 代码都需要使用 hpu 功能进行编译，并通过使用 sim 配置 flavor 来生成 setup_hpu.sh：

cd tfhe-rs
source setup_hpu.sh -c sim

如果你这样做是对的，那么你所有的 HPU TFHE-rs 代码现在都将使用 mockup 而不是真实的 HPU。只需让它在不同的终端上运行并忘记它即可。

调试正确性

一旦你编写了一个 IOp，你将需要在实际创建到 TFHE-rs 的Hook之前，对其进行独立测试。为此，我们提供了一个名为 hpu_bench 的简单程序，你可以使用它来基准测试和验证你的 IOp 是否正确运行。这个 bench 也可以与 mockup 一起使用，尽管延迟报告将是错误的，因为它将测量 CPU 时间，而不是 HPU 时间。例如，以下命令将使用 mockup 对明文 64 位值 1 和 0 进行同态乘法基准测试：

cargo run --profile devo --features hpu --example hpu_bench -- \
    --integer-w 64 \
    --iop MUL \
    --trivial \
    --src 1  \
    --src 0 \
    --iter 1

[!NOTE] 以下是本示例中使用的选项的描述：

--integer-w，选择整数运算中使用的明文输入的位宽。

--iop，选择要进行基准测试的 IOp。此示例选择了 MUL IOp。如果你正在测试自己制作的新 IOp，则需要在此处指定它。如果你不指定此选项，则将对所有 IOps 进行基准测试。

--trivial，通过以简单的方式加密你的明文来运行基准测试。这主要用于调试你的 IOp 正确性。

--src，用于强制 IOp 的一个输入的明文。你可以多次指定此选项来强制多个输入。如果你不强制输入，它将被随机化。

--iter，基准测试将通过递归调用指定的 IOps 来完成，通过将输出循环到第一个输入，提供的次数。默认为 1。

你总是可以调用 hpu_bench --help 来了解更多关于接受的选项。

作为输出，你将获得一个延迟报告（暂时忽略它）和以明文形式显示的乘法结果。该结果可用于检查你的 IOp 是否正常工作。你可以测试许多输入组合，甚至省略 --src 来尝试随机值，并围绕此编写一个程序，以确保你的 IOp 按预期工作。我们都知道你正在阅读本文，因为它没有，所以下一步是阅读 mockup 输出以帮助你处理问题。

mockup 提供了两个主要信息，这些信息对于调试 IOp 非常有用：

DOp 执行顺序跟踪；
中间 DOp 结果。

你需要知道 DOp 执行顺序的原因有两个——了解性能并能够跟踪中间 DOp 结果。目前，mockup 会在执行 DOp 时将其结果写入使用 --dump-out 参数提供的任何文件夹，因此了解执行顺序对于能够将结果与 DOps 匹配是绝对必要的。我们计划在将来简化此步骤，具体取决于我们意识到用户需要调试其 IOps 的频率。

在 mockup.dump/blwe/run 下，你将为 DOp 的每个输出找到一个或多个十六进制文件。这取决于 LWE 密文在内存上的打包方式，并且将来可能会更改。但是，我们正在运行简单加密的版本进行调试（正如你可能在调用基准测试程序时通过 --trivial 参数注意到的那样）。密文的最后几位包含消息，并且整个密文以小端序、LSB 优先的顺序输出。

能够调试 IOp 唯一缺少的是能够将中间输出链接到特定的 DOp。在 mockup.dump/dop 下，你将找到 IOp 流的汇编文件列表（因为它已收到）以及 DOps 执行方式的汇编列表。通过打开包含你要调试的 IOp 的汇编文件，你现在可以理解中间结果文件，希望这将使你更进一步地调试你的 IOp。

使用 mockup 调试性能

既然你的 IOp 按预期工作，你对其性能感到困惑。在放弃并责怪 HPU 团队之前，你还有其他选择。其中一种方法是查看 mockup 产生的其他信息，以了解问题所在。

正如你从 HPU^1 上的其他文档页面了解到的那样，TFHE 和 HPU 处理时间的主要瓶颈是可编程自举 (PBS)。在 HPU 上，PBS 的处理时间几乎比线性/分层或 IO 操作的处理时间长 100 倍。这意味着性能将主要由你的 IOp 必须执行的 PBS 批次数量决定。考虑到这一点，mockup 生成一个执行报告，让你深入了解已执行了多少 DOps 及其延迟。如果按照上面的示例操作，你可以在 mockup.rpt/ 下找到此报告。对于每个执行的不同 IOp 都会生成一个报告，尽管每个 IOp 类型只有一个报告。以下是乘法的示例：

Report for IOp: MUL      &lt;I64 I64> &lt;I64@0x40> &lt;I64@0x00 I64@0x20>
TimeRpt { cycle: 44061792, duration: 146.872ms }
InstructionKind {MemLd: 1703, MemSt: 1691, Arith: 1840, Pbs: 1685, Sync: 1}
Processing element statistics:
     "KsPbs_0" => issued: 1685, batches: 142, by_timeout: 0, usage: 0.9891165172855315
     "LdSt_0" => issued: 3394, batches: 3394, by_timeout: 0, usage: 1
     "Lin_0" => issued: 1840, batches: 1840, by_timeout: 0, usage: 1

除了实际延迟之外，你可以从本报告中获得的最重要信息是 PBS 批次的数量（在本例中为 142）和 PBS 单元使用率。这将指示批次已满的时间百分比，指示你的 IOp 使用 PBS 单元的效率。by_timeout 变量也很重要，因为它指示有多少批次未完全调度满，并且由于无法调度更多 PBS 而超时启动。此超时功能主要是一个安全功能，设置为与批次延迟相当的非常大的值。你的 IOps 应始终指示如果该批次是后续批次的依赖项，则是否刷新该批次。

如果你不明白为什么你的 PBS 单元使用率很低，你将必须检查指令调度器跟踪。在同一目录（示例中的 mockup.rpt）中，你将找到每个执行的 IOp 类型的 json 文件。这包含指令调度器事件的跟踪，你可以从中访问调度过程的几乎所有详细信息。此跟踪是为了模拟真实的硬件跟踪而制作的，因此以下技术也将有助于使用真实硬件进行调试。

使用 HPU 调试性能

在我们深入了解如何使用跟踪调试你的 IOp 的细节之前，你需要更多地了解指令调度器。

指令调度器

HPU 中的指令调度器负责将指令调度到组成 HPU 的多个处理单元。目前只有三个：加载存储单元、线性 FHE 操作单元和 PBS 单元。所有三个单元都可以并行运行，PBS 单元实际上可以并行运行许多引导程序。为了最大化效率，指令调度器会查看 DOp 流并重新排序操作（同时尊重它们的依赖关系），以使所有三个单元尽可能地忙碌。在执行此操作时，它会记录用于做出决策的所有事件，例如将 DOps 排队、将 DOps 调度到处理元素、执行、清除 DOp 的依赖关系等。此事件流将发送到 HBM 内存中的缓冲区，该缓冲区稍后可以通过 PCIe 检索。

mockup 捕获的跟踪与硬件捕获的跟踪之间的主要区别在于，在硬件中，指令调度器实际上并不知道哪个 IOp 正在执行。因此，所有事件都只是按它们被看到的顺序排队到同一内存中，而 mockup 实际上按 IOp 分隔事件。这意味着在调试硬件跟踪之前，你必须找出你的 IOp 在事件流中的位置。这并不难，因为所有 DOp 流都带有同步 ID，该 ID 可用于分隔来自多个 IOps 的事件，因此你只需在许多 DOp 组中搜索你的 IOp 即可。尽管如此，这仍然很麻烦，如果 mockup 重现了 HPU 性能，那么你最好使用它，因为它记录的信息比硬件多。同样，所有这些都是动态目标，我们可能会在将来的迭代中将这些信息添加到跟踪中。

检索硬件跟踪

无论如何，在你使用了你的 HPU 之后，你可以通过编译和执行一个小型的 rust 程序——hputil 来检索跟踪：

cargo build --release --features hpu,utils,hw-v80 --bin hputil
./target/release/hputil trace-dump -f trace.json

这会将所有事件保存到一个 json 文件中。HBM 跟踪缓冲区很小，在编写时约为 32MB，但是将所有这些信息解压缩到 json 文件会导致文件大小超过 GB。我们计划更改输出格式或允许使用多种输出格式，但是目前不支持。

一旦你有了你的跟踪文件，请妥善保存它，因为它可能是弄清楚你的 IOp 发生了什么的关键。

[!NOTE] 此程序对于从 HPU 提取更多信息很有用，例如转储调试寄存器。它是供内部使用的，如果你清楚地了解每个寄存器包含的内容，那么它的其余功能才有用。尽管如此，大多数寄存器都有一个暗示性的名称，因此你可以阅读 --help 输出以了解更多信息。

使用指令调度器跟踪进行调试

一旦你有了想要查看的跟踪文件，无论它是硬件跟踪还是 mockup 跟踪，你都可以使用专门为此目的编写的 python 库。你可以在 TFHE-rs 代码库中找到它。该库的主要目的是将跟踪分成来自不同 IOps 的独立跟踪，并通过筛选不同类型的事件来帮助你分析跟踪，同时收集有关这些事件的统计信息。首先，你导入该库：

from isctrace.analysis import Trace, Refilled, Retired

iops = Trace.from_hw("trace.json") # Or Trace.from_mockup, for mockup traces
retired = Retired(iops[x])          # x 是你想要查看的 IOp 索引

你可以将它们视为 pandas DataFrame：

retired.to_df()

Retired 类不仅仅是收集退休事件。实际上，它将发布事件与退休事件配对以获得 DOp 延迟。

你可以从 Retired 类获得的另一个非常重要的信息是我们所说的 PBS 延迟表，它也是一个 DataFrame：

retired.pbs_latency_table(freq_mhz=freq_mhz)

显然，如果此信息不足以弄清楚发生了什么，你可以对 Trace 类中记录的信息执行任何你想要的操作。

我们现在已经介绍了我们自己实际使用的所有工具和技巧，以调试和改进我们自己的 IOps。尽管如此，这里的大部分魔力在于知道如何为 HPU 正确编写程序，因此我们将以一个性能改进示例结束。

一个例子

假设你想编写一个以同态方式比较两个密文的 IOp[^2]。天真地，并假设你已经了解 HPU 指令集，你可以尝试执行以下操作：

其中灰色菱形表示 PBS，如果输入不为零，则输出 1，否则输出零，除非它是负数，在这种情况下它实际上会输出 -1，因为 PBS 是 nega-cyclic 的。从现在开始，我们将此 PBS 称为“符号 PBS”。如果你将 1 添加到此结果，你将获得一个顺序值：0 表示小于，1 表示等于，2 表示大于。

黄色菱形是“顺序合并 PBS”，我们将从现在开始这样称呼它。它查看打包到一个密文中的两个顺序消息。如果最重要的顺序值等于，则 PBS 选择最不重要的顺序，否则选择最重要的顺序。打包操作是隐式的，但它映射到 a*4 + b，可以使用单个 MAC 操作由 HPU 完成，这非常便宜。

粉色菱形是最终比较 PBS，或“比较 PBS”，现在将顺序值转换为一个布尔值，这取决于你尝试执行的比较类型。如果你想要进行小于比较，则仅当输入是大于值 (2) 时，你才会输出 0。

图中的所有操作都直接映射到指令集中的 DOp。然后，我们可以尝试通过简单地减去每对密文的每一位数字，在结果上运行 符号 PBS，加 1 以获得每个数字的顺序值，并使用 顺序合并 PBS 从最高有效位到最低有效位以递归方式合并顺序值来执行比较。最终结果将是通过 比较 PBS (粉色) 将最终顺序值转换为布尔值的结果。请注意，TFHE-rs 和我们自己的 IOps 进行了一些进一步的简化，并使用更多的 FHE 技巧来尝试减少使用的 PBS 数量，但为了简单起见，我们将在此处不使用它们。另外，请注意，此示例的最终结果将最终可能与实际实现相媲美，但我将保留理解作为读者的练习。

从上面的图直接翻译成 rust 固件代码实际上非常简单。即使本文的目的不是解释如何为 HPU 编写固件，为了完整起见，我将在此处粘贴它：

pub fn cmp_gt(prog: &mut Program) {
    // Create Input/Output template entry points to be linked at execution time.
    // 创建在执行时链接的输入/输出模板入口点。
    let mut dst = prog.iop_template_var(OperandKind::Dst, 0);
    let src_a = prog.iop_template_var(OperandKind::Src, 0);
    let src_b = prog.iop_template_var(OperandKind::Src, 1);

    // Get the index of the required PBSs
    // 获取所需 PBS 的索引
    let sgn_pbs = new_pbs!(prog, "CmpSign");   // gray   diamond // 灰色   菱形
    let red_pbs = new_pbs!(prog, "CmpReduce"); // yellow diamond // 黄色 菱形
    let gt_pbs = new_pbs!(prog, "CmpGt");      // pink   diamond // 粉色   菱形

    dst[0] &lt;&lt;= std::iter::zip(src_a, src_b)
        .rev()
        .fold(prog.new_imm(pbs_macro::CMP_EQUAL), |acc, (a, b)| {
            (&(&a - &b).pbs(&sgn_pbs, false) + &prog.new_imm(1))
                .pack_carry(&acc)
                .pbs(&red_pbs, false)
        })
        .pbs(&gt_pbs, false);
}

[!NOTE] 请注意，本例中使用的所有代码都可以在 here 找到。这是一个额外的固件实现，仅用于演示目的。

正如我们所了解的那样，理解此 IOp 性能的第一部分是对其进行基准测试。以下是由 mockup 提供的 64 位操作的上述操作的延迟报告：

> cargo run --profile devo --features hpu --example hpu_bench -- \
    --fw Demo --integer-w 64 --iop CMP_GT --src 1 --src 0
> cat mockup.rpt/CMP_GT*.rpt
Report for IOp: CMP_GT   &lt;I2 I64> &lt;I2@0x40> &lt;I64@0x00 I64@0x20>
TimeRpt { cycle: 13166040, duration: 43.886ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 96, Pbs: 65, Sync: 1}
Processing element statistics:
     "KsPbs_0" => issued: 65, batches: 34, by_timeout: 34, usage: 0.17379679144385018
     "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
     "Lin_0" => issued: 96, batches: 96, by_timeout: 0, usage: 1
 >

在这个例子中，一个批处理大约需要 1 毫秒，超时设置为 300 微秒。首先弹出的是使用率或 PBS 单元效率为 17%。此外，IOp 需要的 PBS 数量为 65。我们知道 HPU 可以并行运行许多 PBS，在这个例子中是 10 个。这意味着那些 65 个 PBS 可能会在 65/10 * 1ms=6.5ms 上运行，而我们现在为 43ms！你知道你不能信任 HPU 团队，但在你发出一些噪音之前，让我们收集更多信息。

为了能够进行调查，你可以读取 mockup 跟踪并打印退休指令和批处理延迟报告，如前几节所示。以下是 8 位比较的结果，为了使事情简单：

           latency   delta  reltime opcode             args
timestamp
503482162      422     422      422     LD          R0 @0x3
503482447      681     285      707     LD          R1 @0x7
503482729      807     282      989     LD          R7 @0x2
503483160     1212     431     1420     LD          R8 @0x6
503483458     1354     298     1718     LD         R14 @0x1
503483742     1612     284     2002     LD         R15 @0x5
503484040     1722     298     2300     LD         R21 @0x0
503484485     2141     445     2745     LD         R22 @0x4
503484622     2149     137     2882    SUB         R2 R0 R1
503486697     3530    2075     4957    SUB         R9 R7 R8
503488779     5030    2082     7039    SUB      R16 R14 R15
503490861     6369    2082     9121    SUB      R23 R21 R22
503872701   388072  381840   390961    PBS        R3 R2 @10
503872776   386072      75   391036    PBS       R10 R9 @10
503872858   384072      82   391118    PBS      R17 R16 @10
503872940   382072      82   391200    PBS      R24 R23 @10
503874855     2147    1915   393115   ADDS          R4 R3 1
503876931     4148    2076   395191   ADDS        R11 R10 1
503879014     6149    2083   397274   ADDS        R18 R17 1
503881097     8150    2083   399357   ADDS        R25 R24 1
503883173     8311    2076   401433   ADDS          R5 R4 4
504270837   387657  387664   789097    PBS        R6 R5 @11
504272990     2146    2153   791250    MAC   R12 R6 R11 X4
504660668   387671  387678  1178928    PBS      R13 R12 @11
504662821     2146    2153  1181081    MAC  R19 R13 R18 X4
505050499   387671  387678  1568759    PBS      R20 R19 @11
505052652     2146    2153  1570912    MAC  R26 R20 R25 X4
505440337   387678  387685  1958597    PBS      R27 R26 @11
505828029   387685  387692  2346289    PBS      R28 R27 @12
505828481      445     452  2346741     ST         @0x8 R28

                    min          avg          max          sum  count
batch size
1           1292.306667  1303.392667  1326.323333  6516.963333      5
4           1304.000000  1304.000000  1304.000000  1304.000000      1

你可能注意到的第一件事是我们主要有两种不同的批处理大小，一个批处理大小为 4，五个批处理大小为 1 PBS。尽管我们没有以任何并行方式描述 IOp，但指令调度程序正确地识别出 符号 PBS (灰色) 可以全部并行运行，因为它们没有共享依赖关系。对于 8 位，我们使用 4 个密文和 4 个 符号 PBS，因此调度程序创建了一个由 4 个 PBS 组成的批处理。对于 64 位，它实际上可以启动 3 批 12 个 [^3]。那么，为什么它也不能将 顺序合并 PBS 打包到批处理中呢？原因很简单，因为这个算法是递归的 —— 一个 顺序合并 PBS 依赖于先前的合并。换句话说，在上一个 顺序合并 PBS 完成之前，一个 顺序合并 PBS 无法启动。对于硬件工程师来说，递归性一直困扰着他们，他们试图并行化操作数十年，最近，随着多核 CPU 和大规模并行 GPU 的出现，也困扰着软件工程师。这对于许多算法来说都很常见，包括基本算法，如加法、除法和更具体的算法，如 ECC 码、排序、IIR 滤波器以及无数其他算法。

并行化递归算法的一种常用方法是找到问题的不同公式，你可以将其分解为两个可以合并的并行计算。如果这可行，那么你可以对两个并行计算递归地执行相同的过程，以获得四个并行计算，依此类推，直到你无法进一步减少它为止。这被称为递归加倍，并广泛用于现在著名的，令人难以置信的丰富且大部分被遗忘的 kogge-stone adder 的推导中[^4]。几乎所有递归算法的突破递归都以某种方式或另一种方式使用递归加倍，并且它也可以用于我们简单的比较中。如果你意识到你可以将整数分成两部分，计算最高有效部分的所有数字的顺序，以及最低有效部分的所有数字的顺序，并通过单个合并来合并生成的两个顺序，那么我们已经公式化的比较可以分解为两个使用完全相同的操作的并行问题。如果你递归地不断分割各个部分，你将得到一棵合并树，而不是一个递归的合并流。如果你有足够的 “线程” 或计算元素，树的最终延迟将与 log(N) 乘以合并延迟成正比，而不是与 N 成正比。有人说一张图片胜过千言万语：

请注意，计算现在分阶段完成，每个阶段都带有前一个阶段一半的并行工作。它并非一直完全并行直到结束，但仍然比原来的递归公式要好得多。

让我们对这个新公式 (demo.rs 中的 cmp_gte()) 进行基准测试：

IOp 报告: CMP_GTE  &lt;I2 I64> &lt;I2@0x40> &lt;I64@0x00 I64@0x20>
TimeRpt { cycle: 3699192, duration: 12.33ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 95, Pbs: 64, Sync: 1}
Processing element statistics:
     "KsPbs_0" => issued: 64, batches: 10, by_timeout: 7, usage: 0.5636363636363636
     "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
     "Lin_0" => issued: 95, batches: 95, by_timeout: 0, usage: 1

我们极大地改善了延迟。请注意，我们现在只做了十批次，而不是三十四个。PBS 单元的使用率虽然不完美，但大幅提高。请注意，我们仍然有未满的批次，特别是对于树的最后阶段。如果不向调度器提供应该刷新这些批次的信息，它只会在超时后启动批次。通过在每个阶段结束时正确刷新批次，我们可以得到这个 (demo.rs 中的 cmp_lt()):

Report for IOp: CMP_LT   &lt;I2 I64> &lt;I2@0x40> &lt;I64@0x00 I64@0x20>
TimeRpt { cycle: 3176268, duration: 10.587ms }
InstructionKind {MemLd: 64, MemSt: 1, Arith: 95, Pbs: 63, Sync: 1}
Processing element statistics:
     "KsPbs_0" => issued: 63, batches: 10, by_timeout: 2, usage: 0.5545454545454545
     "LdSt_0" => issued: 65, batches: 65, by_timeout: 0, usage: 1
     "Lin_0" => issued: 95, batches: 95, by_timeout: 0, usage: 1

这几乎是百分之二十的改进。现在，仍然有两个批次超时。你可以读取追踪数据并读取批次延迟报告，以了解这些批次的位置。在这个特殊情况下，发生的情况是两个批次之间的线性运算花费了超过 300us 才能完成。仍然可以隐藏这种延迟，但这需要重新排序 IOp 以避免这种情况。我们正在开发一种新的固件框架，它通过在操作依赖图上运行模拟并尝试以最佳方式调度操作来解决这些细节。你唯一的工作是弄清楚如何并行化操作并将这些操作依赖项编写为图。你可以阅读当前的 llt IOp 实现来学习如何做到这一点，但它尚未被认为是广泛使用的稳定版本。

结束语

希望本文档能够启发你了解可用于调试 HPU IOps 的工具。在尝试编写甚至调试 IOps 之前，请确保你还阅读了其他与向 HPU 编写固件相关的文档。

除此之外，祝你同态加密愉快！

[^2]: 我们已经有可以做到这一点的 IOps，但它们实际上是关于如何显着提高 IOp 性能的一个非常好的例子，或者从另一个角度来看，如何使 HPU 看起来很糟糕。 [^3]: 尽管在此示例中，典型的最小批量大小为十个 PBS，但是 HPU 运行十二个 PBS 比分别运行两批十个和两个 PBS 效率更高。一批十二个的延迟是单个一批十个的延迟的 12/10，而两批十个和两个的延迟是两倍。这是因为作为 PBS 的一部分要完成的工作量可以分解为许多较小的部分，并且有效延迟变为那些较小的工作块的延迟之和。这表明我们可能会用来自单个 PBS 的工作填充所有十个槽，并使 PBS 延迟降低十倍。但是，我们无法做到这一点，因为获取引导密钥的带宽受到限制，迫使我们在多个 PBS 中共享单个旋转的密钥，从而保持最大的 PBS 吞吐量。 [^4]: 我们都站在巨人的肩膀上，即使有点老，也应该承认巨人。Kogge, Peter M., and Harold S. Stone. "A parallel algorithm for the efficient solution of a general class of recurrence equations." IEEE transactions on computers 100.8 (1973): 786-793.



>- 原文链接： [github.com/zama-ai/hpu_f...](https://github.com/zama-ai/hpu_fpga/blob/main/docs/debug.md)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

密码学 - 调试IOps - Zama-Ai

常规调试选项

HPU mockup

调试正确性

使用 mockup 调试性能

使用 HPU 调试性能

指令调度器

检索硬件跟踪

使用指令调度器跟踪进行调试

一个例子

结束语

0 条评论

文章目录