时间戳

首页 > 解决方案 > 如何在矩阵乘法的工作进程中处理 n 而不是倍数 p？

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

问题描述

我正在研究一个关于使用工作进程进行矩阵乘法的伪代码的问题。w 是工人的数量，p 是处理器的数量，n 是进程的数量。伪代码通过将 i 行划分为每条 n/P 行的 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 整除的情况下经常发生？

标签： multithreadingmatrixconcurrencyparallel-processingpseudocode

解决方案

最简单的解决方案是给最后一个工人所有剩余的行（它们不会超过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 行)

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

推荐阅读