c - 划分位图以进行并行处理

Question

如何将位图划分为多个片段并用于并行处理？我已经有了位图的高度和宽度，但是从这里开始。我已阅读使用 MPI_Cart_shift() 和 MPI_Sendrecv()。但是，我不确定如何使用它们。

  width = BMP_GetWidth (bmp);  
  height = BMP_GetHeight (bmp);
  new_bmp = BMP_Create(width, height, 24); // BMP_Create(UINT width, UINT height, USHORT depth)

Answer 1

我如何将位图划分为用于并行处理的片段取决于正在进行的处理类型。

您的标签(但不是您的问题)提到高斯模糊，所以这可能是一个很好的起点。

对于高斯模糊，每个输出像素都依赖于大量输入像素，仅此而已。如果每个处理器都有所有输入像素的(只读)副本，那么您可以根据需要分割工作，但“ strip ”效果最好。具体来说，如果有 N 个处理器，第一个处理器将找到第一组“total_pixels/N”输出像素(可能是图像顶部的像素带)，第二个处理器将执行第二组“total_pixels/N”输出像素(可能是第一个带下方的像素带)等。完成所有处理器后，您只需按正确的顺序附加每个处理器的输出像素即可获得整个输出位图。

请注意(由于舍入)某些处理器可能需要执行不同数量的像素 - 例如如果位图有 10000 个像素，并且您有 64 个处理器，则“10000/64 = 156.25”，但处理器无法处理四分之一像素，因此最终会得到 48 个处理器处理 156 个像素，而 16 个处理器处理 157 个像素( “48*156 + 16*157 = 10000”)。

此外，如果处理器可能具有不同的速度和/或不同的延迟，您可能希望将工作拆分为更多部分(例如，如果有 64 个处理器，则将工作拆分为 128 部分，其中较慢的处理器可能只执行 1 部分，而较慢的处理器可能只执行 1 部分)更快的处理器可能可以处理 4 件)。

如果处理器还没有所有输入像素的副本(并且没有共享内存)，那么您可以向每个处理器发送所有像素的一部分。例如，如果您有一个 7 行高的高斯矩阵(输出位置上方 3 行，输出位置上方 1 行，输出位置下方 3 行)，并且如果每个处理器输出 100 行像素的带，则您将向每个处理器发送一个“3+100+3 = 106”的输入像素带进行处理(处理第一个带和最后一个带的处理器除外，它们只会得到“3+100”或“100+” 3"行输入像素)。

对于像(例如)Floyd-Steinberg 抖动这样的东西，事情会变得更加复杂，因为一个输出像素取决于所有先前的输出像素(除了输入像素之外)。在这种情况下，您可以将“3 色”位图拆分为三个单独的单色位图(每个处理器一个，最多 3 个处理器)，每个处理器可以抖动其单色位图，然后您可以将三个生成的单色位图合并在一起获得单个“3 色”输出位图；但实际上不可能使用超过 3 个处理器(在不更改为更适合并行化的不同抖动算法的情况下)。

为了绘制一个圆或一个椭圆，您可以让每个处理器绘制一条圆弧并将这些圆弧组合起来；为了绘制 1234 个形状，您可以将图像分割成一个网格，并让每个处理器在网格内绘制一个图 block 。