通过避免或消除人为依赖来暴露并行性
许多应用程序和算法包含串行优化，这些优化会无意中引入数据依赖并抑制并行性。通常可以通过简单的转换来消除此类依赖，甚至可以通过域分解或分块等技术完全避免它们。
摘要
许多应用程序和算法包含串行优化，这些优化会无意中引入数据依赖并抑制并行性。通常可以通过简单的转换来消除此类依赖，甚至可以通过域分解或分块等技术完全避免它们。
本文是大型系列“Intel 多线程应用程序开发指南”的一部分，该系列为 Intel® 平台上的高效多线程应用程序开发提供了指导方针。
背景
虽然用于并行化的多线程是性能的重要来源，但确保每个线程高效运行同样重要。虽然优化编译器完成了大部分这项工作，但程序员通过利用数据重用和选择有利于机器优势的指令来提高性能，这种情况并不少见。不幸的是，提高串行性能的技术也可能无意中引入数据依赖，从而难以通过多线程获得更高的性能。
一个例子是重用中间结果以避免重复计算。例如，通过模糊来平滑图像可以通过用其邻域（包括其自身）中的像素的加权平均值替换每个图像像素来实现。以下伪代码描述了一个 3x3 模糊模板
for each pixel in (imageIn)
sum = value of pixel
// compute the average of 9 pixels from imageIn
for each neighbor of (pixel)
sum += value of neighbor
// store the resulting value in imageOut
pixelOut = sum / 9
每个像素值都参与多个计算这一事实使人们可以利用数据重用来提高性能。在以下伪代码中，中间结果被计算并使用了三次，从而提高了串行性能
subroutine BlurLine (lineIn, lineOut)
for each pixel j in (lineIn)
// compute the average of 3 pixels from line
// and store the resulting value in lineout
pixelOut = (pixel j-1 + pixel j + pixel j+1) / 3
declare lineCache[3]
lineCache[0] = 0
BlurLine (line 1 of imageIn, lineCache[1])
for each line i in (imageIn)
BlurLine (line i+1 of imageIn, lineCache[i mod 3])
lineSums = lineCache[0] + lineCache[1] + lineCache[2]
lineOut = lineSums / 3
此优化会在输出图像的相邻行计算之间引入依赖。如果尝试并行计算此循环的迭代，则依赖关系会导致不正确的结果。
另一个常见的例子是循环内的指针偏移
ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr);
ptr++;
}
通过递增 ptr，代码可能利用了寄存器递增的快速操作，并避免了为每次迭代计算 someArray[i] 的算术运算。虽然每次调用 compute 可能与其他调用无关，但指针成为显式依赖；其在每次迭代中的值取决于前一次迭代中的值。
最后，算法经常会促进并行性，但数据结构的设计目的是为了其他目的，却无意中阻碍了并行性。稀疏矩阵算法就是其中一个例子。由于大多数矩阵元素为零，因此通常用“打包”形式替换常规矩阵表示，该形式包含元素值和相对偏移量，用于跳过零值条目。
本文介绍了在这些具有挑战性的情况下有效引入并行性的策略。
通知
当然，最好找到无需移除现有优化或进行大量源代码更改即可利用并行性的方法。在移除任何串行优化以暴露并行性之前，请考虑是否可以通过将现有内核应用于问题的一个子集来保留该优化。通常，如果原始算法包含并行性，则还可以将子集定义为独立单元并并行计算它们。
为了高效地对模糊操作进行多线程处理，请考虑将图像细分为固定大小的子图像或块。模糊算法允许数据块独立计算。以下伪代码说明了图像分块的使用
// One time operation:
// Decompose the image into non-overlapping blocks.
blockList = Decompose (image, xRes, yRes)
foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}
用于模糊整个图像的现有代码可以在 BlurBlock 的实现中重用。使用 OpenMP 或显式线程来并行处理多个块可以获得多线程的优势，并保留原始的优化内核。
在其他情况下，现有串行优化带来的好处与每次迭代的总成本相比很小，这使得分块变得不必要。当迭代粒度足够粗，可以从并行化中预期到加速时，通常就是这种情况。指针递增的例子就是这种情况。感应变量可以很容易地被显式索引替换，从而消除依赖关系并允许循环的简单并行化。
ptr = &someArray[0]
for (i = 0; i < N; i++)
{
Compute (ptr[i]);
}
请注意，原始优化虽然很小，但不一定丢失。编译器通常通过利用递增或其他快速操作来积极优化索引计算，从而实现串行和并行性能的优势。
其他情况，例如涉及打包稀疏矩阵的代码，可能更难进行多线程处理。通常，解包数据结构不切实际，但通常可以将矩阵细分为块，存储指向每个块开头的指针。当这些矩阵与适当的基于块的算法配对时，可以同时实现打包表示和并行化的优势。
上面描述的分块技术是一种更通用的技术，称为“域分解”。分解后，每个线程独立处理一个或多个域。在某些情况下，算法和数据的性质决定了每个域的工作量几乎是恒定的。在其他情况下，工作量可能因域而异。在这种情况下，如果域的数量等于线程的数量，则并行性能可能会受到负载不平衡的限制。总的来说，最好确保域的数量相对于线程的数量足够大。这将允许动态调度等技术在线程之间平衡负载。
使用指南
一些串行优化可以带来巨大的性能提升。考虑目标处理器数量，以确保并行性带来的加速将超过因移除优化而造成的性能损失。
引入分块算法有时会阻碍编译器区分别名数据和非别名数据的能力。如果分块后，编译器无法再确定数据是非别名数据，性能可能会受到影响。考虑使用 restrict 关键字明确禁止别名。启用过程间优化也有助于编译器检测非别名数据。