0

我在这里相对较新，但我想如果有人可以提供帮助，那就是这里的人。

我们正在做一个非常大规模的原子晶格模拟程序，这个非常简单的函数被使用了很多次，以至于它显着减慢了这个过程。

它只是检查周期性格子中一个站点的 8 个邻居（我们在 BCC 中）的类型（称为格子的结构的 3d 向量的一部分，包括表示原子类型的整数 t）。

我意识到可能无法进一步简化它，但如果有人有任何灵感，请告诉我，谢谢！

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
//cout << "neighbour" << endl;
int n = 0;

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k+1].t)
{
    n++;
}
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j][k-1].t)
{
    n++;
}

return n;
}
4

2 回答 2

2

首先，使用中的格子环绕解决方案 ( (i+1) & (LATTICE_SIZE-1)) 仅当 LATTICE_SIZE 是 2 的幂时才能正常工作。例如，如果LATTICE_SIZE == 100和i == 99, (i+1)&(LATTICE_SIZE-1) == 100 & 99 == 0x64 & 0x63 == 0x60 == 96，而预期值为 0。

鉴于此，我建议您检查多维数组索引在您的编译器和平台上的工作方式。当 LATTICE_SIZE 等于 2 的幂时，第 n 个索引的乘法可以有效地用左移代替，这在某些架构上明显更快。VC++11 会自动进行这种优化，但是我不知道你的编译器是什么，也不能假设它也这样做。

想到的另一个改进是尽量避免从高阶索引重新计算偏移量。如果我们将相同的高阶索引组合在一起，优化器可以帮助实现这一目标。我只是通过对表达式进行排序来实现这一点：

if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i+1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k+1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][j                       ][k-1].t)  n++;
if (V != lattice[(i-1) & (LATTICE_SIZE-1)][(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;

我的优化器利用了这一点，结果加速只有 4%。但是，对于您的系统，它可能会归结为不同的值。

此外，大部分优化实际上取决于函数的使用。例如，我写了一个这样的简单测试：

volatile int n = 0;
for ( int i = 0; i != LATTICE_SIZE; ++i )
    for ( int j = 0; j != LATTICE_SIZE; ++j )
        for ( int k = 0; k != LATTICE_SIZE; ++k )
            n += neighbour ( i, j, k );

我的测量显示每个 neighbour() 调用大约 12 ns。之后我注意到邻居只在两个高阶飞机上检查。我重构了函数以向优化器提供更明确的提示：

int neighbour_in_plane ( elem_t l[LATTICE_SIZE][LATTICE_SIZE], int j, int k )
{
    int n = 0;
    if (V != l[(j-1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    if (V != l[j                       ][k-1].t)  n++;
    if (V != l[j                       ][k+1].t)  n++;
    if (V != l[(j+1) & (LATTICE_SIZE-1)][k  ].t)  n++;
    return n;
}

//calculates number of neighbours that aren't vacancies
int neighbour(int i, int j, int k)
{
    return neighbour_in_plane ( lattice[(i-1) & (LATTICE_SIZE-1)], i, j ) +
           neighbour_in_plane ( lattice[(i+1) & (LATTICE_SIZE-1)], i, j );
}

令人惊讶的是，每次调用只有 4 ns。我检查了编译器输出，发现这一次它已将两个函数内联到调用循环中，并为我做了一些优化。Eq 它有效地将两个内部循环移动到 neighbour_in_plane() 函数中，从而避免了数千次重新计算 lattice[(i-+1) & (LATTICE_SIZE-1)]表达式。

底线是你必须在你的代码+编译器+平台环境中使用这个函数才能最大限度地利用它。

于 2013-08-13T08:35:26.413 回答
1

我假设 LATTICE_SIZE 是 2 的幂。否则，& (LATTICE_SIZE-1)不会按照您的意愿进行环绕。此外，我注意到“k”维度没有换行。这是故意的吗？

然后，在 C++ 中，该代码的执行时间将在很大程度上取决于您的“格”是什么类型的“数组”，以及比较 V != lattice[i][i][k].t 是多么昂贵或便宜。通常，嵌套的 std::vector 或 boost::multi_array 可能比传统的“C”数组慢得多： Lattice lattice[LATTICE_SIZE][LATTICE_SIZE][LATTICE_SIZE]

如果您有能力在所有三个维度上留下一个空边框（基本上是一个空表面），那么这可能有助于提高效率，因为您可以用& (LATTICE_SIZE-1). 如果你有一个编译时常量 LATTICE_SIZE，那么计算像 lattice[i-1][j][k+1] 这样的精确索引会快很多，因为编译器可以确定各种数组访问之间的常量偏移量.

最后但同样重要的是，我建议您查看为该函数生成的汇编程序输出（只需使用 -S 开关编译并查看生成的 .s 文件）。如果编译器将“if”转换为围绕“n++”（转换为inc %reg）的条件跳转，那么这就为进一步优化留下了空间，因为条件跳转往往会被 CPU 错误预测，然后导致大量额外的时钟周期. 如果使用 cmov，或者如果“if”的结果通过条件集指令（如 setc 或 setg）转换为寄存器，则代码可能已经更接近最优。为了帮助编译器有效地使用 Intel x86 上的 setxx 操作，您可以尝试将结果计数“n”转换为“unsigned char”。

于 2013-08-13T07:30:08.670 回答