python - 使用 MPI 提高性能

Question

我测试了对前 N 整数求和的(几乎)“令人尴尬的并行”(即完全可并行化)算法并行化的性能增益:

串行算法很简单:

N = 100000000
print sum(range(N))

在我的双核笔记本电脑 (Lenovo X200) 上的执行时间:0m21.111s。

并行化(使用 mpi4py)版本使用 3 个节点；节点 0 计算整数下半部分的和，节点 1 计算上半部分的和。两者都将它们的结果(通过 comm.send)发送到节点 2，节点 2 将两个数字相加并打印结果:

from mpi4py import MPI

comm = MPI.COMM_WORLD
rank = comm.Get_rank()

N = 100000000

if rank == 0: 
  s = sum(range(N/2))
  comm.send(s,dest=2,tag=11)
elif rank == 1:
  s = sum(range(N/2+1,N))
  comm.send(s,dest=2,tag=11)
elif rank == 2:
  s1 = comm.recv(source=0, tag=11)
  s2 = comm.recv(source=1, tag=11)
  print s1+s2

我的双核笔记本电脑的两个核心都被充分利用了；现在的执行时间:15.746 秒。

我的问题:至少理论上，执行时间应该减半。哪个开销吃掉了丢失的 4 秒？ (肯定不是 s1+s2)。那些发送/接收命令有那么耗时吗？？

编辑: 阅读答案并重新思考问题后，我认为 4 秒(在某些运行中甚至更多)被生成两个列表引起的高内存流量所占用长度 50000000；我笔记本电脑的两个内核共享一个公共(public)内存(至少是主内存；我认为它们有独立的二级缓存)而这正是瓶颈:所以，两个内核经常想同时访问内存(为了获得下一个列表元素)，其中一个必须等​​待...

如果我使用 xrange 而不是 range，下一个列表元素将延迟生成并且分配的内存很少。我对其进行了测试，使用 xrange 运行与上述相同的程序仅需 11 秒!

Answer 1

你是怎么安排时间的，你的笔记本电脑是什么？

如果您从 shell 进行计时，您可能会(如 BiggAl 所建议的那样)在启动 python 时遇到延迟。这是真正的开销，值得了解，但可能不是您的当务之急。我很难想象这会导致 4 秒的开销...[编辑添加:尽管 BiggAl 认为在 Windows 下它确实可能是]

我认为更可能的问题是内存带宽限制。虽然您将在此设置中充分利用两个内核，但您只有那么多的内存带宽，这可能最终成为这里的限制。每个核心都试图写入大量数据(范围(N/2))，然后将其读入(总和)以进行相当适度的计算(一个整数)，所以我怀疑计算不是瓶颈。

我在 Nehalem 盒子上使用 timeit 运行了相同的设置，每个内核的内存带宽都非常好，并且确实获得了预期的加速:

from mpi4py import MPI
import timeit

comm = MPI.COMM_WORLD
rank = comm.Get_rank()

N = 10000000

def parSum():
    if rank == 0:
        ...etc

def serSum():
    s = sum(range(N))

if rank == 0:
    print 'Parallel time:'
    tp = timeit.Timer("parSum()","from __main__ import parSum")
    print tp.timeit(number=10)

    print 'Serial time:'
    ts = timeit.Timer("serSum()","from __main__ import serSum")
    print ts.timeit(number=10)

我从中得到的

$ mpirun -np 3 python ./sum.py
Parallel time:
1.91955494881
Serial time:
3.84715008736

如果你认为这是一个内存带宽问题，你可以通过计算来测试人为计算量大；说使用 numpy 并对范围的更复杂的函数求和:sum(numpy.sin(range(N/2+1,N)))，比如说。这应该使平衡从内存访问倾斜到计算。