5

我正在为我的大学进行一项与医疗用途图像重建算法相关的研究。

我被困在长达 3 周的时间里，我需要提高以下代码的性能：

for (lor=lor0[mypid]; lor <= lor1[mypid]; lor++)
{
  LOR_X = P.symmLOR[lor].x;
  LOR_Y = P.symmLOR[lor].y;
  LOR_XY = P.symmLOR[lor].xy;
  lor_z = P.symmLOR[lor].z;
  LOR_Z_X = P.symmLOR[lor_z].x;
  LOR_Z_Y = P.symmLOR[lor_z].y;
  LOR_Z_XY = P.symmLOR[lor_z].xy;  

  s0 = P.a2r[lor];
  s1 = P.a2r[lor+1];

  for (s=s0; s < s1; s++)
  {
    pixel     = P.a2b[s];
    v         = P.a2p[s]; 

    b[lor]    += v * x[pixel];

    p          = P.symm_Xpixel[pixel];
    b[LOR_X]  += v * x[p];

    p          = P.symm_Ypixel[pixel];
    b[LOR_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel];
    b[LOR_XY] += v * x[p];


    // do Z symmetry.
    pixel_z    = P.symm_Zpixel[pixel];
    b[lor_z]  += v * x[pixel_z];


    p          = P.symm_Xpixel[pixel_z];
    b[LOR_Z_X]  += v * x[p];


    p          = P.symm_Ypixel[pixel_z];
    b[LOR_Z_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel_z];
    b[LOR_Z_XY] += v * x[p];

   }

}

对于任何想知道的人，该代码实现了 MLEM 转发功能，所有变量都是 FLOAT。

经过几次测试，我注意到这部分代码出现了很大的延迟。（你知道，90 - 10 规则）。

后来，我使用 Papi (http://cl.cs.utk.edu/papi/) 来测量 L1D 缓存未命中。正如我所想，Papi 确认性能下降是由于更多的未命中，特别是对于随机访问 b 向量（巨大的大小）。

阅读互联网上的信息到目前为止，我只知道两种提高性能的选择：提高数据局部性或减少数据污染。

为了进行第一个改进，我将尝试将代码更改为可感知缓存，就像 Ulrich Drepper 在每个程序员都应该了解的内存(www.akkadia.org/drepper/cpumemory.pdf)中提出的那样。 1 矩阵乘法。

我相信阻止 SpMV（稀疏矩阵向量乘法）会提高性能。

另一方面，每次程序尝试访问 b 向量时，我们都会遇到所谓的缓存污染。

有没有办法在不使用缓存的情况下使用 SIMD 指令从 b 向量中加载一个值？

此外，可以使用 void _mm_stream_ps(float * p , __m128 a) 之类的函数在向量 b 上存储一个浮点值而不污染缓存？

我不能使用 _mm_stream_ps 因为总是存储 4 个浮点数，但对 b 向量的访问显然是随机的。

我希望清楚我的困境。

更多信息：v 是具有 CRS 格式的稀疏矩阵存储的列值。我意识到如果我尝试将 CRS 格式更改为其他格式，则可以进行其他优化，但是，就像我之前所说的，我已经做了几个月的测试，我知道性能下降与向量 b 上的随机访问有关。从 400.000.000 L1D Misses 当我不存储在向量 b 中时，我可以转到 100~ Misses。

谢谢。

4

4 回答 4

2

减少对向量 b 的随机访问的一个简单优化是永远不要在内部 for 循环中写入向量 b。

而是将向量 B 所需的所有值加载到临时变量中，在更新这些临时变量时执行整个内部 for 循环，然后将临时变量写回向量 B。

临时变量最坏的情况是位于相同的缓存行上，这取决于您的编译器和环境，您可能还会提示编译器为这些变量使用寄存器。

于 2011-01-18T21:52:27.160 回答
2

我什至不会假装我知道代码在做什么 :) 但是导致一些额外内存访问的一个可能原因是别名：如果编译器不能确定b,x和各种P.symm数组不重叠，则写入tob将影响如何安排读取x和P.symm's。如果编译器特别悲观，它甚至可能会强制P从内存中重新获取 的字段。所有这些都将导致您看到的缓存未命中。改善这一点的两种简单方法是：

  1. 在 上使用 __restrict b。这保证b不会与其他数组重叠，因此对其的写入不会影响来自其他数组的读取（或写入）。

  2. 重新排序，以便P.symm首先从 's 读取所有内容，然后是从 读取x，最后是对 的所有写入b。这应该会分解读取中的一些依赖关系，并且编译器会安排从P.symm's 并行读取，然后并行读取x，并希望b明智地进行写入。

另一件风格上的事情（这将有助于第 2 点）是不要p过多地重用变量。没有理由不能拥有例如p_x, p_y,p_xy等，这将使重新排序代码更容易。

一旦一切就绪，您就可以__builtin_prefetch在已知的缓存未命中之前开始散布预取指令（即在 gcc 上）。

希望有帮助。

于 2011-01-18T22:13:54.063 回答
2

我会说，首先尝试帮助您的编译器。

  • 像在循环之前一样声明外循环的边界const。
  • 将您可能（所有LOR_..）声明为局部变量的所有变量，例如： float LOR_X = P.symmLOR[lor].x;或 size_t s0 = P.a2r[lor];
  • 如果您碰巧有现代的、符合 C99 的编译器，这也特别适用于循环变量：for (size_t s=s0; s < s1; s++)
  • b 为您的向量单独加载和存储。您在那里访问的项目的位置不依赖于s. 因此，创建一个局部变量来保存您在内循环之前处理的所有不同情况的实际值， 在内循环内更新这些局部变量，并在内循环之后存储结果。
  • 也许将您的内部循环分成几个。索引计算相对便宜，然后您的系统可能会更好地识别对某些向量的流式访问。
  • 查看编译器生成的汇编器并确定内部循环的代码。尝试将尽可能多的“远”负载和存储移出该循环。

编辑：在重新阅读 gravitron 的答案和您的评论之后，这里重要的事情实际上是尽可能地声明变量是本地的，并检查编译器是否成功地将缓存丢失加载和存储在内循环之外。

于 2011-01-19T09:12:09.347 回答
0

这些都是很好的答案，我会问为什么这么多索引？通过在本地变化不大的索引值？

此外，它不会杀死你做一些随机的停顿，看看它通常在哪里。

于 2011-01-18T22:24:46.707 回答