加速弗里德曼检验表计算：GPU并行计算的高效解决方案

### 加速弗里德曼检验表计算：GPU 并行计算的高效解决方案 #### 1. 随机数生成与 CPU 实现 在加速弗里德曼检验表计算的过程中，随机数的生成是关键的一步。BigCrush 是 TestU01 库中要求最严格的测试集，常用于测试随机数的质量，它包含 106 个测试，使用近 238 个随机数。 Philox 4x32 10 生成器能够产生 264 个周期为 2128 的伪随机数子序列，这个周期大于实验所需的最大数量（15 × 400 × 108）。为了在 CPU 上生成算法所需的随机数，我们使用 Random123 库，因为它提供了 Philox 4x32 10 生成器的 CPU 实现。 对于计算弗里德曼检验表值的其他三个相关操作的 CPU 实现，我们简要说明如下： - **矩阵行排序**：由于 CPU 实现使用 C++ 编码，我们使用 C++ 标准模板库（STL）中的 sort 函数对矩阵的每一行进行排序。该函数用于计算随机数的有序索引。 - **列求和与向量求和**：在 CPU 上实现列求和和向量求和是直接的，每个独立元素通过迭代处理。 #### 2. GPU 计算弗里德曼检验表值 为了进一步加速计算，我们将给定对 (k, N) 的事件计算卸载到 GPU 上。算法在 GPU 上为每个事件计算  R2 j 和  r2 ij，然后将整个结果传输到 CPU。在 CPU 接收到结果后，进行后处理（本文未详细说明），调整值以获得公式 3 的分子和分母，最终用于构建 (k, N) 对的直方图。 我们的算法核心思想是使用单个线程块网格并行计算给定对 (k, N) 的多个事件。由于事件数量约为 108，这种方法能够充分利用 GPU 的大规模并行架构。 以下是主机端的伪代码： ```plaintext 1 transfer seed for random numbers to GPU 2 call initCurandState kernel 3 events = 0 4 while events < maxEvents do 5 call generateAndOrderNumbers kernel 6 call sumColumns kernel 7 call sumVectors kernel 8 events = events + e 9 end 10 transfer results from GPU to CPU ``` #### 3. GPU 数据组织 我们的方案使用了几种存储在 GPU 不同内存空间的数据结构： - **状态矩阵**：用于存储每个随机数生成器的状态，维度为 N × k，存储在 GPU 的全局内存中。 - **随机数向量**：为了计算表值，每行的随机数只需临时存储，因为真正重要的数据是排名。因此，在 GPU 的共享内存中分配一个 k 元素的向量来存储随机数，用于加速算法第 5 步的排名计算。 - **主矩阵**：用于存储 e 次行排序后的结果索引，矩阵有 N2 × e 行和 k2 列，其中 N2 和 k2 是大于或等于 N 和 k 的最小 2 的幂次方。这样的维度选择是为了使归约计算更高效。 - **部分和向量**：用于存储矩阵列求和的部分结果，是一个 k 元素的双精度浮点数向量，存储在 GPU 的共享内存中，用于加速平方和计算时的内存访问。 - ** R2 j 最终结果向量**：用于存储每个事件的平方和最终结果，有 e 个双精度浮点数元素，即同时执行的独立事件数量。 - ** r2 ij 结果向量**：用于存储矩阵所有元素的平方和结果，也有 e 个双精度浮点数元素。 #### 4. GPU 内核操作 - **initCurandState 内核**：初始化随机数生成器的状态。该内核以 N 个块启动，每个块有 k 个线程，每个线程使用实验种子和通过块 ID 和线程 ID 计算的单调递增数独立初始化一个状态，从而确定 N × k 个不同的随机子序列。 - **generateAndOrderNumbers 内核**：为每行生成随机数并进行排序。同样以 N 个块和每个块 k 个线程启动，每个块计算不同的行。每个线程从状态矩阵读取其状态，然后重复 e 次以下任务： 1. 生成一个 1 到 k 之间的随机数，并存储在随机数向量的相应位置。 2. 计算随机数的排名。我们使用两个辅助计数器变量，一个用于存储索引（初始化为 1），一个用于存储平局数量（初始化为 0）。通过将每个线程的随机数与向量中的其他元素进行比较，为小于该数的元素的索引变量加 1，为等于该数的元素的平局变量加 1。排名计算为索引变量和平局变量的一半之和。 3. 将排名值存储在全局内存的主矩阵中，矩阵位置由重复次数、块 ID 和线程 ID 确定。由于主矩阵按行存储，所有写入操作都是合并的。最后，将生成器的状态存储在状态矩阵中，以便下次调用内核时使用。 - **sumColumns 内核**：对主矩阵中存储的排名进行列求和。这涉及应用著名的归约模式和多次调用内核。每次调用内核时，为了保持对全局内存的合并访问，每个块读取两行的所有元素，并对同一列的值进行求和。内核调用 log2(N2/2) 次，第一次以 e×N2/2 个块和每个块 k 个线程启动，每次调用时块数减半。最终调用以 e 个块启动，每个 e 个独立事件的列求和结果存储在主矩阵中每个 e 个子矩阵的第一行。需要注意的是，输入矩阵可能有比 N 更多的行，因此剩余行需要用零填充，以正确计算归约而不影响最终求和结果。在第一次调用 sumColumns 内核时，由于读取了矩阵的所有元素，内核还计算矩阵所有元素的平方和。该计算也涉及沿列的归约模式，以及使用 atomicAdd 操作对不同块计算的值进行求和，以避免竞争条件。结果存储在全局内存中  r2 ij 结果向量的相应位置。 - **sumVectors 内核**：计算前一个内核产生的向量元素的平方，然后对结果值进行求和。该内核以 e 个块（每行一个块）和每个块 k2 个线程启动。首先，内核将行的值从全局内存复制到共享内存并计算数字的平方。然后，使用归约模式计算平方和，执行 log2(k2) 次迭代，将数字对相加。最后，将最终结果从共享内存复制到全局内存中  R2 j 最终结果向量的相应位置。 #### 5. 实验设置 为了评估 GPU 实现的算法性能，我们进行了实验。我们分别在 CPU 和 GPU 上实现了该算法（不包括直方图计算）。CPU 实现使用 C++ 编码，GPU 实现使用 CUDA 并使用 CUDA Toolkit 版本 9.2。 实验平台如下： - **CPU 平台**：一台配备 Quad Core Intel i7 - 6700 处理器（3.40 GHz）和 64 GB RAM 的 PC，运行 CentOS Linux 7.0 操作系统，CPU 实现作为单线程应用程序执行。 - **GPU 平台**：Nvidia 的 GeForce GTX 980 Ti（2816 个 CUDA 核心，1000 MHz，Maxwell 架构），连接到用于