0

我目前正在开发一个解决红/蓝计算的程序；程序是用 C 编写的。

问题描述在这里：http ://www.cs.utah.edu/~mhall/cs4961f10/CS4961-L9.pdf

tl; dr你有一个颜色网格（红色/蓝色/白色），首先红色单元格根据某些规则向右移动，然后蓝色单元格根据其他规则向下移动。

我已经让我的程序正常工作并提供正确的输出，我现在正在尝试看看我是否根本无法加快它的速度。

使用 Intel 的 VTune Amplifier（这是一个并行编程课程，我们正在集成并行工作室的 Visual Studio 中进行 pthreads），我发现我的代码中最大的热点是移动蓝色单元格时。

实现细节：grid存储为动态分配的int**，这样设置

globalBoard = malloc(sizeof(int *) * size);
    for (i = 0; i < size; i++)
    {
        globalBoard[i] = malloc(sizeof(int) * size);
        for (j = 0; j < size; j++)
            globalBoard[i][j] = rand() % 3;
    }

经过一些研究，我相信热点的原因（几乎是移动红细胞的 4 倍 CPU 时间）是逐列遍历时缓存未命中。

我知道在后台，这个网格将存储为一维数组，所以当我将红色单元格向右移动并逐行移动时，我最常检查连续值，因此 CPU 不需要加载新值经常进入缓存，而逐列会导致在数组中跳跃的数量只会随着板的大小而增加。

话虽如此，我希望这个特定的部分更快。这是现在的代码：

void blueStep(int col)
{
    int i;
    int local[size];
    for (i = 0; i < size; local[i] = globalBoard[i++][col]);

    for (i = 0; i < size; i++)
    {
        if (i < size - 1)
        {
            if (globalBoard[i][col] == 2 && globalBoard[i + 1][col] == 0)
            {
                local[i++] = 0;
                local[i] = 2;
            }
        }
        else
        {
            if (globalBoard[i][col] == 2 && globalBoard[0][col] == 0)
            {
                local[i++] = 0;
                local[0] = 2;
            }
        }
    }
    for (i = 0; i < size; i++)
        globalBoard[i][col] = local[i];

}

在这里，col 是要处理的列，size 是网格的大小（它总是正方形）。

我在想我也许可以做一些花哨的指针运算来加快速度，并且正在阅读：http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/pointer。 .html _

看着它，我觉得我可能需要更改声明网格的方式以利用二维数组指针算法，但我仍然不确定如何使用该方法遍历列。

欢迎提供任何帮助，或任何其他快速浏览专栏的建议。

更新：经过更多的研究和讨论，我的假设似乎是不正确的。事实证明，由于错误共享，实际上将结果写回全局数组所需的时间几乎是循环列的两倍。也就是说，我仍然有点好奇是否有更好的方法来进行列遍历。

4

1 回答 1

0

我认为答案是在瓷砖中处理网格。您可以在 16x16 或 32x32 的瓷砖中快速向下或向右移动瓷砖。这两个动作实际上是相同的，并以相同的速度运行：将所有值读入 XMM 寄存器、处理、写入。您可能想在此处调查 MASKMOVDQU 指令。如果我了解问题的性质，您可以将图块重叠一行/列，如果您以通常的（扫描）顺序处理它们，这将可以正常工作。如果没有，您必须单独处理拼接瓷砖。

在 C 代码中没有真正快速的方法可以做到这一点。但是，您可以尝试 (1) 将板类型更改为 unit8_t，(2) 用算术替换所有 if .. 语句，如下所示： value = (mask & value) | (^mask & newvalue)，以及 (3) 在编译器选项中打开最大循环展开和自动矢量化。这会给你一个很好的加速 - 特别是避免条件。

编辑除了可以放入寄存器的切片之外，您还可以进行第二级切片的大小以适合您的缓存。我认为该组合将大致以您的内存带宽运行。

编辑或者，使您的板类型为两位：将四个单元打包成一个字节。很适合用算术思想替换 if 语句:)

于 2013-10-29T07:44:16.143 回答