首先,摆脱所有不必要的依赖关系。#pragma omp critical(assignment)
不是必需的,因为每个索引(*newData)
每个循环仅写入一次,因此不存在竞争条件。
您的代码现在可能如下所示:
#pragma omp parallel for
for (int i = 0; i < range; i++)
(*newData)[i] = ((*data)[i-1] + (*data)[i] + (*data)[i+1]) / 3.0;
现在我们正在寻找瓶颈。我提出的潜在候选人名单如下:
- 慢速分裂
- 缓存颠簸
- ILP(指令级并行)
- 内存带宽限制
- 隐藏的依赖项
那么让我们进一步分析它们。
慢速除法:有些 CPU 需要永远计算 double/double。要了解您的 CPU 的运行时间和吞吐量,您必须查看其规格。也许更换/3.0
with *0.3333..
可能有帮助,但也许你的编译器已经这样做了。使用扩展指令集(如 SSE/AVX),您可以一次安排多个除法/乘法。
缓存抖动:由于您的 CPU 必须一次加载/存储一个缓存行,因此可能会发生冲突。想象一下,如果线程 1 尝试写入 (*newdata)[1],线程 2 尝试写入 (*newdata)[2],并且它们位于同一缓存行上。现在他们中的一个必须等待另一个。你可以用以下方法解决这个问题#pragma omp parallel for schedule(static, 64)
.
ILP:如果操作是独立的,CPU 可以将多个操作调度到管道中。为此,您必须展开循环。这可能看起来像这样:
assert(range % 4 == 0);
#pragma omp parallel for
for (int i = 0; i < range/4; i++) {
(*newData)[i*4+0] = ((*data)[i*4-1] + (*data)[i*4+0] + (*data)[i*4+1]) / 3.0;
(*newData)[i*4+1] = ((*data)[i*4+0] + (*data)[i*4+1] + (*data)[i*4+2]) / 3.0;
(*newData)[i*4+2] = ((*data)[i*4+1] + (*data)[i*4+2] + (*data)[i*4+3]) / 3.0;
(*newData)[i*4+3] = ((*data)[i*4+2] + (*data)[i*4+3] + (*data)[i*4+4]) / 3.0;
}
内存带宽限制:对于您非常简单的循环,请考虑这一点。您需要加载多少内存以及您的 CPU 将忙于处理它多长时间。您正在加载大约 1 个缓存行并计算一些取消引用、一些指针加法、两次加法和一次除法。您达到的限制取决于您的 CPU 规格。
现在考虑缓存局部性。您可以修改代码以更好地利用缓存吗?如果一个线程在一次循环迭代中获得 i=3,而在下一次循环迭代中获得 i=7,则必须重新加载 3 (*data)。但如果从 i=3 到 i=4,您可能不需要加载任何内容,因为 (*data)[i+1] 位于先前加载的缓存行中。您可以节省一些 RAM 带宽。要利用它,请展开循环。使用 float 而不是 double 也可以增加这种机会。
隐藏的依赖项:我个人觉得这部分非常棘手。有时您的编译器不确定它是否可以重用某些数据,因为它不知道它没有更改。使用const
帮助编译器。但有时你需要一个restrict
给编译器正确的提示。但我不太明白这一点,无法解释它。
所以这就是我要尝试的:
const double ONETHIRD = 1.0 / 3.0;
assert(range % 4 == 0);
#pragma omp parallel for schedule(static, 1024)
for (int i = 0; i < range/4; i++) {
(*newData)[i*4+0] = ((*data)[i*4-1] + (*data)[i*4+0] + (*data)[i*4+1]) * ONETHIRD;
(*newData)[i*4+1] = ((*data)[i*4+0] + (*data)[i*4+1] + (*data)[i*4+2]) * ONETHIRD;
(*newData)[i*4+2] = ((*data)[i*4+1] + (*data)[i*4+2] + (*data)[i*4+3]) * ONETHIRD;
(*newData)[i*4+3] = ((*data)[i*4+2] + (*data)[i*4+3] + (*data)[i*4+4]) * ONETHIRD;
}
然后进行基准测试。进行更多基准测试,再进行更多基准测试。只有基准测试才能告诉您哪些技巧有帮助。
PS:还有一件事需要考虑。如果您发现您的程序严重占用内存带宽。您会考虑更改算法。也许将两个步骤合二为一。就像从b[i] := (a[i-1] + a[i] + a[i+1]) / 3.0
to
d[i] := (n[i-1] + n[i] + n[i+1]) / 3.0 = (a[i-2] + 2.0 * a[i-1] + 3.0 * a[i] + 2.0 * a[i+1] + a[i+1]) / 3.0
。我想这其中的原因你自己就会找到的。
享受优化的乐趣;-)