针对任何大整数优化 MPI 代码

Question

我正在尝试使用 Monte Carlo 方法计算 pi 的估计值。我用的方法是圆内切成正方形。

这是我解决问题的简单代码：

#define _XOPEN_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>

#define SEED time(NULL)

void pi_mpi_version(void) {

  unsigned int seed;
  long long int all_point;
  double x, y, start, end;
  int rank, size;
  long long int i, points = 0, all_intern;

  MPI_Init(NULL, NULL);
  start = MPI_Wtime();

  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MPI_Comm_size(MPI_COMM_WORLD, &size);

  seed = SEED + rank;

  for ( i = 0; i < 1000000000; i++ ) {
    x = (double) rand_r(&seed) / RAND_MAX;
    y = (double) rand_r(&seed) / RAND_MAX;

    if ( x * x + y * y <= 1.0 ) points++;
  }

  MPI_Reduce(&points, &all_intern, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
  all_point = 1000000000 * size;

  MPI_Barrier(MPI_COMM_WORLD);
  end = MPI_Wtime();

  if ( rank == 0 ) {
    printf("All intern: %lld\n", all_intern);
    printf("All points: %lld\n", all_point);
    printf("\u03C0 \u2248 %Lf\n", (long double) all_intern / all_point * 4.0);
    printf("Time elapsed: %.4f\n", end - start);
  }

  MPI_Finalize();
}

我尝试将所有变量设置为 long long int 但输入 1000000000 就像在代码中一样， return 是一个负数。输入高达 100000000 似乎有效。

Answer 1

这实际上是一个比您想象的更有趣的问题。您的结果是两个问题的组合：溢出和类型混淆。

首先是溢出部分：大于 2147483647 的数字无法使用带符号的 32 位整数表示，这是许多 C++ 编译器中 int 的默认大小以及 MPI 用于 MPI_INT 的内部表示的大小。因此，一旦您拥有超过 2-3 个 MPI 等级，1000000000 * pi / 4 大小的部分计数仍然可以表示为 int，但它们的总和不能 - 结果溢出并且变为负数。

行也是如此

1000000000 * size

没有任何后缀，size和1000000000都是int类型，它们的乘积也是。因此，该计算将溢出，然后才将结果存储在较大的 long long int all_points 变量中。简单修复：将计算替换为

1000000000LL * size

这会强制第一个整数为 long long int 类型，因此整个计算不会溢出。

但是您的代码还有第二个更严重的问题：类型混淆。

MPI_Reduce 期望其发送和接收缓冲区的值为 void*，这意味着您可以使用任何指针作为参数。现在的类型混淆是 MPI_Reduce 期望你传递一个指向 int 的指针，因为你传递了 MPI_INT 作为类型参数。但是你传递的指针指向一个long long int。您需要使用的是 MPI_LONG_LONG_INT，它对应于 long long int 类型。

如果您想知道为什么您的代码仍然适用于较小的迭代次数，您可以阅读整数的二进制表示，尤其是 Little/Big Endian。

针对任何大整数优化 MPI 代码

Optimize MPI code for any big integer number

c

mpi