使用MPI获得性能提升

Question

我测试了并行化(几乎)"令人难以置信的并行"(即完全可并行化)算法的性能增益,该算法总结了第一个N整数:

串行算法很简单:

N = 100000000
print sum(range(N))

我的双核笔记本电脑(联想X200)的执行时间:0m21.111s.

并行化(带mpi4py)版本使用3个节点; 节点0计算整数的下半部分之和,节点1计算上半部分的总和.两者都将结果(via 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.746s.

我的问题:至少在理论上,执行时间几乎应该减半.哪个开销吃了4秒？(当然不是s1 + s2).那些发送/接收命令是否耗时？

编辑:在阅读了答案并重新思考问题之后,我认为4秒(在某些运行中甚至更多)被生成两个长度为50000000的列表所导致的高内存流量所吞噬; 我的笔记本电脑的两个核心共享一个公共内存(至少是主内存;我认为它们有独立的L2缓存),这正是瓶颈:因此,两个内核通常都希望同时访问内存(以获取内存)下一个列表元素),其中一个必须等​​待...

如果我使用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)))比如说.这应该倾斜从内存访问到计算的平衡.