logo标签列表

C++ 优化嵌套循环的向量化

c++vectorizationnested-loops
5

我有一个处理多层嵌套循环的程序，操作的是一个三维域：

unsigned int sX(m_sizeZ*m_sizeY);
unsigned int b(sX+m_sizeZ);
for(unsigned int i(1);i<m_sizeX-1;i++){
    for(unsigned int j(1);j<m_sizeY-1;j++){     
        for(unsigned int k(1);k<m_sizeZ-1;k++){
            m_r[b+k]=m_func[b+k]-m_cX*(m_data[b+k-sX]+m_data[b+k+sX]-2.0*m_data[b+k])
                        -m_cY*(m_data[b+k-m_sizeZ]+m_data[b+k+m_sizeZ]-2.0*m_data[b+k])
                        -m_cZ*(m_data[b+k-1]+m_data[b+k+1]-2.0*m_data[b+k]);
        }
        b+=m_sizeZ;
    }
    b+=2*m_sizeZ;
}

我的数组大小是m_sizeX * m_sizeY * m_sizeZ的两倍。

我这样迭代是因为我不想触及域的边界。

当使用（g++）-msse2 -ftree-vectorizer-verbose = 2编译时，我当然会得到多个嵌套循环的提示。

有没有什么方法可以使用单个循环而不需要（更多或更少）复杂的检查操作？

谢谢！

1
你可以将所有3个坐标编码成一个数字，然后使用模数解码它。就像你可以将2D数组映射到单个内存块中，反之亦然。但是我不建议这种方法。循环非常简单，因此编译器应该没有任何问题自行转换它。 - luk32
1
"多重嵌套循环注意事项。你总是这么含糊吗？这有趣吗？" - Lightness Races in Orbit
抱歉如果我看起来含糊不清。我收到的完整信息是： PoissonSolverCG.cpp:93: 注意：未向量化：多个嵌套循环。 PoissonSolverCG.cpp:93: 注意：循环形式不佳。 分析PoissonSolverCG.cpp:94处的循环。 - repptilia
4个回答
2

如果你的目标是获得良好的向量化效果，那么最好的方法可能就是对边缘点应用与内部点相同的计算方式，只有在计算完成所有点之后才将其重置。可以使用以下类似代码：

unsigned int sX(m_sizeZ*m_sizeY);
unsigned int start = (1*m_sizeY + 1)*m_sizeZ + 1;
unsigned int end = ((m_sizeX - 1)*m_sizeY - 1)*m_sizeZ - 1;
//Do calculation for everything, including the edges.
for(unsigned int i = start; i < end; i++) {
    m_r[i]=m_func[i]-m_cX*(m_data[i-sX]+m_data[i+sX]-2.0*m_data[i])
                -m_cY*(m_data[i-m_sizeZ]+m_data[i+m_sizeZ]-2.0*m_data[i])
                -m_cZ*(m_data[i-1]+m_data[i+1]-2.0*m_data[i]);
}
//Reset the edges.
for(unsigned x = 0; x < m_sizeX; x++) {
    for(unsigned y = 0; y < m_sizeY; y++) {
        m_r[x*sX + y*m_sizeZ] = m_data[x*sX + y*m_sizeZ];
        m_r[x*sX + y*m_sizeZ + m_sizeZ-1] = m_data[x*sX + y*m_sizeZ + m_sizeZ-1];
    }
}
for(unsigned x = 0; x < m_sizeX; x++) {
    for(unsigned z = 0; z < m_sizeZ; z++) {
        m_r[x*sX + z] = m_data[x*sX + z];
        m_r[x*sX + (m_sizeY-1)*m_sizeZ + z] = m_data[x*sX + (m_sizeY-1)*m_sizeZ + z];
    }
}

这是额外的计算，但它有两个积极的影响：

  1. 现在，您的编译器可以非常容易地对第一个循环进行矢量化（这需要大部分时间）。

  2. 这种方法几乎消除了由固定矢量大小导致的边缘问题：由于您的矢量单元可以处理一次多个对齐的循环迭代，因此计算中的每个边缘都会导致需要完成两个特殊迭代。一次是在运行开始时用来对齐矢量循环，另一次是在结尾处处理矢量循环的剩余部分。

谢谢！这看起来确实是一个不错的解决方案。 - repptilia
1
你可以在单个循环中迭代，从1到m_sizeX*m_sizeY*m_sizeZ（计数器为C），并按以下方式计算i，j，k：
i = C / (m_sizeY*m_sizeZ)
j = (C % (m_sizeY*m_sizeZ)) / m_sizeZ
k = (C % (m_sizeY*m_sizeZ)) % m_sizeZ

这种方法的限制在于你必须注意 m_sizeX*m_sizeY*m_sizeZ 在不溢出的情况下保持在 C 范围内。 编辑 为了控制边界而不使用 if-else 语句，你可以创建一个函数。
size_t nextToCalculate(size_t previous)
{
    return previous+1+!condition;
}

并在您的循环中使用它：

for(int C = 0; C < m_sizeX*m_sizeY*m_sizeZ; C = nextToCalculate(C))
{
  int z = (C % (m_sizeY*m_sizeZ)) % m_sizeZ;
  int y = (C % (m_sizeY*m_sizeZ)) / m_sizeZ;
  int x = C / (m_sizeY*m_sizeZ);
  ...
  ...
  ...
}

甚至可以在行内包含其实现：

Or even include its implementation in line:

for(int C = 0; C < m_sizeX*m_sizeY*m_sizeZ; C = C+1+!CONDITION(C+1))
{
  int z = (C % (m_sizeY*m_sizeZ)) % m_sizeZ;
  int y = (C % (m_sizeY*m_sizeZ)) / m_sizeZ;
  int x = C / (m_sizeY*m_sizeZ);
  ...
  ...
  ...
}
@luk32 我认为这是显而易见的，但你是对的，我会添加上去。 - Pablo Francisco Pérez Hidalgo
只要 m_sizeX*m_sizeY*m_sizeZ 在 C 范围内，您不应该遇到任何问题，也不会有性能问题。如果该值太大，则可以使用相同的策略仅展开两个级别，映射 m_sizeX*m_sizeY 或 m_sizeY*m_sizeZ。 - Pablo Francisco Pérez Hidalgo
我收到了提示：未向量化：锁存器块不为空。 - repptilia
1
@PabloFranciscoPérezHidalgo 不管你使用哪个逻辑运算符，所有的逻辑运算符都会编译成一个比较加一个条件分支。这适用于 ==、<=、!、&& 等等。CPU 对这些都不喜欢。 - cmaster - reinstate monica
@cmaster 我不知道，我会记住的。谢谢你提供的信息。 - Pablo Francisco Pérez Hidalgo
显示剩余8条评论
0
你可以试试这个（单循环，如你所要求的）：
unsigned int sX(m_sizeZ*m_sizeY);
unsigned int b(sX+m_sizeZ);
unsigned int i, j, k;
for (i = 1, j = 1, k = 1;
     i < m_sizeX-1 && j < m_sizeY - 1 && k < m_sizeZ - 1;
     k++) {
    m_r[b+k]=m_func[b+k]-m_cX*(m_data[b+k-sX]+m_data[b+k+sX]-2.0*m_data[b+k])
             -m_cY*(m_data[b+k-m_sizeZ]+m_data[b+k+m_sizeZ]-2.0*m_data[b+k])
             -m_cZ*(m_data[b+k-1]+m_data[b+k+1]-2.0*m_data[b+k]);
    if (k == (m_sizeZ - 2)) {
      if (j == (m_sizeY - 2)) {
         b+=2*m_sizeZ;
         j = 0;
         i++;
     }
     k = 0;
     b+=m_sizeZ;
     j++;
    }
}
看起来好像更好了，因为我没有收到坏的循环形式消息，但是我收到了这个消息：未向量化：基本块中的数据引用不足。 - repptilia
这可能不是一个好主意，因为你在内部循环中引入了额外的 if() 语句。CPU 不喜欢那些。 - cmaster - reinstate monica
0

将代码作为整个可编译的函数。首先看一下：

  • 使用 const int m_sizeX_1 = m_sizeX-1 并在 for 循环中使用它
  • 为 b+k 使用临时变量
  • 甚至为 m_data+b+k 使用临时变量
  • 通常向量化建议 - 通过提取变量简化代码，然后您将更容易看到下一步该做什么
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接