4

我正在进行分子动力学模拟，我一直在努力并行实现它，虽然我成功地完全加载了我的 4 线程处理器，但并行计算时间大于计算时间串行模式。

研究每个线程开始和结束循环迭代的时间点，我注意到了一种模式：就好像不同的线程在相互等待。就在那时，我将注意力转向了我的程序结构。我有一个类，它的一个实例代表我的粒子系统，包含有关粒子的所有信息以及一些使用这些信息的函数。我还有一个类实例，它代表我的原子间势，包含势函数的参数以及一些函数（其中一个函数计算两个给定粒子之间的力）。

所以在我的程序中存在两个不同类的实例，它们相互交互：一个类的某些函数引用另一个类的实例。我试图并行实现的块如下所示：

      void Run_simulation(Class_system &system, Class_potential &potential, some other arguments){
          #pragma omp parallel for
              for(…) 
      }

for(...) 是实际的计算，使用来自类实例的数据和来自system类实例的一些Class_system函数。potentialClass_potential

我说得对吗，正是这种结构才是我麻烦的根源？

你能建议我在这种情况下应该做什么吗？我必须以完全不同的方式重写我的程序吗？我应该使用一些不同的工具来并行实现我的程序吗？

4

1 回答 1

5

如果没有关于您的模拟类型的更多详细信息，我只能推测，所以这是我的推测。

您是否研究过负载平衡的问题？我猜这个循环会在线程之间分配粒子，但如果你有某种受限的范围潜力，那么在模拟体积的不同区域中，计算时间可能会因粒子而异，具体取决于空间密度。这是分子动力学中一个非常常见的问题，并且在分布式内存（大多数情况下为 MPI）代码中很难正确解决。幸运的是，使用 OpenMP，您可以直接访问每个计算元素上的所有粒子，因此负载平衡更容易实现。它不仅更容易，而且是内置的，可以这么说 - 只需使用子句更改for指令的调度，其中schedule(dynamic,chunk)chunk是一个很小的数字，其最佳值可能因模拟而异。您可以将chunk部分输入数据添加到程序中，或者您可以改为编写schedule(runtime)，然后通过将OMP_SCHEDULE环境变量设置为"static"、"dynamic,1"、"dynamic,10"、等值来使用不同的调度类"guided"。

另一个可能导致性能下降的来源是虚假共享和真实共享。当您的数据结构不适合并发修改时，就会发生错误共享。例如，如果您为每个粒子保留 3D 位置和速度信息（假设您使用速度 Verlet 积分器），给定 IEEE 754 双精度，每个坐标/速度三元组占用 24 个字节。这意味着一个 64 字节的高速缓存行可容纳 2 个完整的三元组和另一个的 2/3。这样做的结果是，无论您如何在线程之间分配粒子，总是至少有两个线程必须共享一个缓存行。假设这些线程在不同的物理内核上运行。如果一个线程写入它的缓存行副本（例如它更新一个粒子的位置），将涉及缓存一致性协议，它将使另一个线程中的缓存行无效，然后必须从较慢的缓存甚至主内存中重新读取它。当第二个线程更新其粒子时，这将使第一个内核中的缓存行无效。这个问题的解决方案是适当的填充和适当的块大小选择，这样没有两个线程会共享一个缓存行。例如，如果你添加一个表面的第 4 维（你可以用它来存储粒子在位置向量第 4 元素中的势能和在速度向量第 4 元素中的动能）那么每个位置/速度四元组将占用 32 个字节，并且恰好两个粒子的信息将适合单个高速缓存行。如果您随后在每个线程中分配偶数个粒子，

当线程同时访问相同的数据结构并且结构的各个部分之间存在重叠并由不同的线程修改时，就会发生真正的共享。在分子动力学模拟中，这种情况非常频繁地发生，因为我们想利用牛顿第三定律，以便在处理成对相互作用势时将计算时间减半。当一个线程计算作用在粒子上的力时i，在枚举其邻居j时，计算j施加在的力会i自动为您提供施加在的力，i以便j可以将贡献添加到总力上j。但j可能属于另一个可能同时修改它的线程，因此必须对两个更新都使用原子操作（两者，因为另一个线程可能会更新i如果它恰好与它自己的多个粒子中的一个相邻）。x86 上的原子更新是通过锁定指令实现的。这并不像经常出现的那样慢得可怕，但仍然比常规更新慢。它还包括与虚假共享相同的缓存行失效效果。为了解决这个问题，以增加内存使用为代价，可以使用本地数组来存储部分力贡献，然后在最后执行减少。缩减本身必须与锁定指令串行或并行执行，因此可能会证明使用这种方法不仅没有任何好处，而且可能会更慢。适当的粒子分类和处理元件之间的巧妙分布以最小化界面区域可用于解决这个问题。

我想谈的另一件事是内存带宽。根据您的算法，获取的数据元素数量与循环的每次迭代执行的浮点运算数量之间存在一定的比率。每个处理器只有有限的带宽可用于内存获取，如果您的数据恰好不能完全放入 CPU 缓存中，那么内存总线可能无法提供足够的数据来支持在单个处理器上执行的这么多线程插座。您的 Core i3-2370M 只有 3 MiB 的 L3 缓存，因此如果您明确保留每个粒子的位置、速度和力，您只能在 L3 缓存中存储大约 43000 个粒子，在 L2 缓存中存储大约 3600 个粒子（或大约 1800 个）每个超线程的粒子数）。

最后一个是超线程。正如高性能标记已经指出的那样，超线程共享大量核心机器。例如，只有一个 AVX 矢量 FPU 引擎在两个超线程之间共享。如果您的代码未矢量化，您将失去处理器中可用的大量计算能力。如果您的代码是矢量化的，那么两个超线程将在争夺对 AVX 引擎的控制权时相互进入。只有当超线程能够通过将计算（在一个超线程中）与内存负载（在另一个超线程中）重叠来隐藏内存延迟时，超线程才有用。使用密集的数字代码在执行内存加载/存储之前执行许多寄存器操作，超线程没有任何好处，你' d 最好以一半的线程数运行并将它们显式绑定到不同的内核，以防止操作系统调度程序将它们作为超线程运行。Windows 上的调度程序在这方面特别愚蠢，请参阅这里以咆哮为例。英特尔的 OpenMP 实现支持通过环境变量控制的各种绑定策略。GNU 的 OpenMP 实现也是如此。我不知道在 Microsoft 的 OpenMP 实现中控制线程绑定（又名关联掩码）的任何方法。

于 2012-12-20T10:43:59.080 回答