使用 omp parallel for in 乘法算法（BigInt 乘法）

Question

出于教育目的，我正在开发用于处理表示为字符向量 (vector<char>) 的大量数字的 C++ 库。

这是我用于乘法的算法：

string multiplicationInner(CharVector a, CharVector b) {
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());

  IntVector stack(a.size() + b.size() + 1);

  int i, j;
  for (i = 0; i < a.size(); i++)
    for (j = 0; j < b.size(); j++)
      stack[i + j] += charToInt(a[i]) * charToInt(b[j]);
 

  for (int i = 0; i < stack.size(); i++) {
    int num = stack[i] % 10;
    int move = stack[i] / 10;
    stack[i] = num;

    if (stack[i + 1])
      stack[i + 1] += move;
    else if (move)
      stack[i + 1] = move;
  }

  CharVector stackChar = intVectorToCharVector(&stack);
  deleteZerosAtEnd(&stackChar);
  reverse(stackChar.begin(), stackChar.end());

  return charVectorToString(&stackChar);
};

这个函数在我的程序中被调用了十亿次，所以我想在里面实现#pragma omp parallel for。

我的问题是：如何并行化第一个周期？

这是我试过的：

int i, j;
  #pragma omp parallel for
  for (i = 0; i < a.size(); i++) {
    for (j = 0; j < b.size(); j++)
      stack[i + j] += charToInt(a[i]) * charToInt(b[j]);
  }

算法停止正常工作。需要建议。

编辑：此变体有效，但（使用 omp parallel for）基准测试显示它比没有它慢 15-20 倍。（CPU：M1 Pro，8 核）

#pragma omp parallel for schedule(dynamic)
  for (int k = 0; k < a.size() + b.size(); k++) { 
    for (int i = 0; i < a.size(); i++) {
      int j = k - i;
      if (j >= 0 && j < b.size()) {
        stack[k] += charToInt(a[i]) * charToInt(b[j]);
      }
    }
  }

这是我程序的一部分，其中最常调用乘法。（米勒-拉宾检验）

BigInt modularExponentiation(BigInt base, BigInt exponent, BigInt mod) {
  BigInt x = B_ONE; // 1
  BigInt y = base;

  while (exponent > B_ZERO) { // while exponent > 0
    if (isOdd(exponent))
      x = (x * y) % mod;
    y = (y * y) % mod;
    exponent /= B_TWO; // exponent /= 2
  }

  return (x % mod);
};

bool isMillerRabinTestOk(BigInt candidate) {
  if (candidate < B_TWO)
    return false;

  if (candidate != B_TWO && isEven(candidate))
    return false;

  BigInt canditateMinusOne = candidate - B_ONE;
  BigInt s = canditateMinusOne;
  while (isEven(s))
    s /= B_TWO;

  for (int i = 0; i < MILLER_RABIN_TEST_ITERATIONS; i++) {
    BigInt a = BigInt(rand()) % canditateMinusOne + B_ONE;
    BigInt temp = s;
    BigInt mod = modularExponentiation(a, temp, candidate);

    while (temp != canditateMinusOne && mod != B_ONE && mod != canditateMinusOne) {
      mod = (mod * mod) % candidate;
      temp *= B_TWO;
    }

    if (mod != canditateMinusOne && isEven(temp))
      return false;
  }

  return true;
};

Answer 1

您的循环没有适合并行化的结构。但是，您可以转换它们：

for (k=0; k<a.size()+b.size(); k++) { 
  for (i=0; i<a.size(); i++) {
    j=k-i;
    stack[k] += a[i] * b[j];
}

现在外循环没有冲突了。将此视为“坐标变换”：您仍在遍历相同的 i/j row/column space，但现在在新坐标中：k/i 代表 diagonal/row.

顺便说一句，这段代码有点隐喻。检查你的循环边界，并使用正确的乘法。我这里只是说明原理。

使用 omp parallel for in 乘法算法（BigInt 乘法）

Using omp parallel for in multiplication algorithm (BigInt multiplication)

c++

parallel-processing

multiplication

openmp

bigint