如何在矩阵乘法的工作进程中处理 n 而不是倍数 p？

Question

我正在研究一个关于使用工作进程进行矩阵乘法的伪代码的问题。 w 是工人的数量，p 是处理器的数量，n 是进程的数量。伪代码通过将 i 行分成 P 条，每条 n/P 行来计算矩阵结果。

process worker[w = 1 to P]
 int first = (w-1) * n/P;
 int last = first + n/P - 1;
 for [i = first to last] {

  for [j = 0 to n-1] {

    c[i,j] = 0.0;
    for[k = 0 to n-1]
     c[i,j] = c[i,j] + a[i,k]*b[k,j];
    }
   }
 }

我的问题是，如果 n 不是 P 处理器的倍数，我将如何处理，这在 n 不能被 p 整除的情况下经常发生？

Answer 1

最简单的解决方案是给最后一个工人所有剩余的行（它们不会超过 P-1）：

if w == P {
  last += n mod P
}

n mod P 是 n 除以 P 的余数。

或者像这样更改 first 和 last 的计算：

int first = ((w-1) * n)/P
int last = (w * n)/P - 1

这会自动处理 n 不能被 P 整除的情况。在 * 和 / 具有相同优先级并且是左结合的大多数语言中，括号并不是真正必需的。关键是 n 的乘法应该发生在 P.

除法之前

示例：n = 11、P = 3：

w = 1：first = 0，last = 2（3 行）
w = 2: first = 3, last = 6 (4 行)
w = 3: first = 7, last = 10 (4 行)

这是一个更好的解决方案，因为它将分配的剩余部分平均分配给了工人。

如何在矩阵乘法的工作进程中处理 n 而不是倍数 p？

How to handle n not a multiple p in worker processes in matrix multiplication?

parallel-processing

concurrency

multithreading

pseudocode

matrix