并行编程 - 将 MPI 应用于素数筛

Question

我之前写了一个来计算Eratosthenes筛法的变体。我正在尝试调整这个程序，以便它可以通过 MPI 在并行编程环境中工作。我正在与其他人一起完成这项任务，看来我们已经成功地并行化了部分代码。我不确定我们写的是不是并行化的。

Scott Ridgway 在 Parallel Scientific Computing 中描述了埃拉托色尼筛法的变体。在第一章中，他描述了所谓的素数筛法。修改后的筛法不是寻找 k 以内的素数，而是搜索 k <= n <= k^2 之间的素数。我通过以下代码完成了此操作。为了并行化此代码，我在 Python 中编写了以下程序（为了运行该程序，我在安装了 MPI 的 Jupyter Notebooks 中测试了 Windows）：

import numpy as np
import platform
import sys
from mpi4py import MPI

comm = MPI.COMM_WORLD

id = comm.Get_rank ( )

p = comm.Get_size ( )

# k : Find the primes between 1 and k. k is set as a default value.
k=10
# define the list S_k of the primes between 2 and k
S_k=[]
# define the list S_k2[] of the primes between k and k**2
S_k2=[]

for i in range ( 2 + id, k + 1, p ):
  flag=0
  for j in range ( 2, i ):
    if ( i % j ) == 0:
      break
  else:
     flag=flag+1

  if (flag==i-2):
      S_k.append(i)

b=int(k**2-k)/p

for n in range(int(k+id*b),int(k+(id+1)*b)):

    flag=0
    for i in range(len(S_k)):

        if (n % S_k[i]) == 0:
            break
        else:
            flag=flag+1


    if (flag==len(S_k)):
        S_k2.append(n)

print (S_k2)

节目returns

[10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47, 49, 50, 52, 53, 55, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 97, 98]

看来我们已经成功地创建了一个程序，通过 MPI 并行计算素数筛。我们如何验证我们编写的代码是否已成功并行化？有没有办法让我们验证不同的处理器正在拆分上面代码中的工作？

Answer 1

使用 MPI 处理日志记录的一种方法是使用提供的名称 which identifies each node uniquely。在这种情况下，只需添加一个 print 语句：

print(MPI.Get_processor_name(),'is running')

会告诉你是不是运行不同的物理节点。

并行编程 - 将 MPI 应用于素数筛

Parallel Programing - Applying MPI to Prime Number Sieve

python-3.x

mpi

primes