NUMA 处理器上的 OpenMP 内存分配

Question

我目前正在尝试在 Maestro 处理器上使用 OpenMP 加速简单的矩阵减法基准测试，该处理器具有 NUMA 架构并基于 Tilera Tile64 处理器。Maestro 主板有 49 个处理器，以 7x7 配置排列成二维阵列。每个核心都有自己的 L1 和 L2 缓存。可以在此处查看电路板的布局：https ://i.stack.imgur.com/RG0fC.png

我对编写“NUMA 感知”应用程序的想法很陌生，但我读到的主要共识是数据局部性是最大化性能的重要组成部分。在核心之间并行化代码时，我应该尽可能将数据保留在执行处理的线程本地使用。

对于这个矩阵减法基准（C[i] = A[i] - B[i]），我认为最好为每个线程分配自己的私有 A、B 和 C 数组，其大小为总大小工作大小除以线程数。例如，如果数组的总大小为 6000*6000，并且我尝试在 20 个线程上并行化它，我将分配大小为 (6000*6000)/20 的私有数组。每个线程都会对其自己的私有数组执行此减法，然后我会将结果收集回总大小为 6000*6000 的最终数组中。例如（无需将每个线程的结果收集到最终数组中）：

int threads = 20;
int size = 6000;
uint8_t *C_final = malloc(sizeof(uint8_t)*(size*size));
#pragma omp parallel num_threads(threads) private(j)
{
     uint8_t *A_priv = malloc(sizeof(uint8_t)*((size*size)/threads));
     uint8_t *B_priv = malloc(sizeof(uint8_t)*((size*size)/threads));
     uint8_t *C_priv = malloc(sizeof(uint8_t)*((size*size)/threads));

     for(j=0; j<((size*size)/threads); j++)
       {
            A_priv[j]=100;
            B_priv[j]=omp_get_thread_num();
            C_priv[j]=0;
       }

     for(j=0; j<((size*size)/threads); j++)
       {
           C_priv[j] = A_priv[j]-B_priv[j];
       }
}

数组的初始值是任意的，我只有 omp_get_thread_num() 在那里，所以我从每个线程的 C_priv 中获得不同的值。我目前正在试验主板上的用户动态网络，它提供了在 CPU 之间路由数据包的硬件，以便将所有单独的线程结果累积到最终的结果数组中。

我已经通过这种方式实现了加速，同时使用 OMP_PROC_BIND=true 固定线程，但我担心将各个结果累积到最终数组中可能会导致开销，从而抵消加速。

这是解决此类问题的正确方法吗？对于使用 OpenMP 的此类问题，我应该采用什么类型的技术来提高 NUMA 架构的速度？

编辑：

为了澄清起见，这是我最初尝试的方法，我注意到执行时间比串行运行代码要慢：

     int threads = 20;
     int size = 6000;
     uint8_t *A_priv = malloc(sizeof(uint8_t)*(size*size));
     uint8_t *B_priv = malloc(sizeof(uint8_t)*(size*size));
     uint8_t *C_priv = malloc(sizeof(uint8_t)*(size*size));

     int i;
     for(i=0; i<(size*size); i++)
     {
       A[i] = 10;
       B[i] = 5;
       C[i] = 0;
     }

     #pragma omp parallel for num_threads(threads)
     for(i=0; i<(size*size); i++)
     {
       C[i] = A[i] - B[i];
     }

在发现使用 OpenMP 时执行时间变慢后，我尝试研究为什么会出现这种情况。数据局部性似乎是问题所在。这个假设是基于我所阅读的有关 NUMA 架构的内容。

我很难找出如何缓解减缓其速度的瓶颈。我找到了一些类似问题的帮助，如下所示：OpenMP：用于调度，它遍历将数据分配给每个线程，以便每个线程处理其本地数据。

我只是觉得像矩阵减法这样简单的事情在使用 OpenMP 时应该不难获得更高的性能。我不知道如何去弄清楚瓶颈到底是什么以及如何缓解它。

Answer 1

通过快速搜索和浏览 TILE64 数据表，您会发现该架构并没有像通过 oprofile、VTune 或 xperf 等工具在 x86 上使用的那样公开性能计数器。如果没有这些，您将不得不自己设计一些实验，以迭代地缩小代码的哪些部分是热门的以及原因 - 在缺乏微架构文档以及工具来指示您的代码如何使用硬件的情况下，有点逆向工程任务。

关于从哪里开始的一些想法：

1. 做一些缩放实验。曲线中是否存在拐点，超过一定的问题大小或线程数量会对整体性能产生重大影响？这个数字是否暗示了与内存层次结构中某个级别的大小、处理器网格的维度或类似的存在某种明确的关系？
2. 记录程序中几个点的执行时间。例如，了解在 malloc 上花费了多少时间、第一个循环与第二个循环上花费的时间可能会很有用。
3. “我通过这种方式实现了加速，同时使用 OMP_PROC_BIND=true 固定线程，但我担心将各个结果累积到最终数组中可能会导致开销，从而抵消加速。” - 这种担心也是可以根据经验进行测试的，特别是如果您正在处理足够大的问题，以至于（2）中的计时器精度对于隔离收集步骤与完全可并行的部分所花费的时间来说不是问题。
4. 尝试不同的操作 - 例如，加法或按元素除法而不是减法，看看是否会改变结果。在许多架构上，不同的算术运算具有不同的延迟和吞吐量。如果您查找并发现 TILE64 就是这种情况，那么进行这样的更改并检测第二个示例的运行时可能会告诉您一些有用的信息，即串行运行它所花费的时间实际上与数据有关局部性问题与启动时间或与 OpenMP 运行时相关的其他开销相比，与实际运行速度较慢的并行实现的正确并行部分相比，与小问题大小的关系可能对总体结果有更多影响。
5. 您可以检查生成的程序集。编译器在您发布的示例中执行基本相同的操作的假设似乎是合理的，但在查看奇怪的性能时不一定像您希望的那样强烈。也许代码大小或布局在使用/不使用 OpenMP 时或从一种并行方法转移到另一种并行方法时会发生变化，例如指令缓存的使用、保留站或 ROB 条目的可用性（如果 TILE64 有这些东西）...？谁知道呢，直到你看到为止。