使用MPI的性能提升

2 投票

7 回答

2658 浏览

提问于 2025-04-16 13:53

我测试了一个几乎可以完全并行化的算法，这个算法是用来计算前 N 个整数的总和。这个算法的串行版本非常简单：

N = 100000000
print sum(range(N))

在我的双核笔记本电脑（联想 X200）上运行这个串行算法的时间是：0分21.111秒。

而并行化的版本（使用 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的列表导致的高内存流量。我的笔记本的两个核心共享一块公共内存（至少是主内存；我想它们有各自的L2缓存），而这正是瓶颈所在：所以，两个核心经常想同时访问内存（获取下一个列表元素），结果其中一个就得等着...

如果我用 xrange 代替 range，下一个列表元素会懒惰地生成，分配的内存也会少很多。我测试了一下，使用 xrange 运行同样的程序只需要11秒！

性能优化内存管理数据传输并行计算负载均衡算法复杂度多核处理 mpi

7 个回答

我的问题是：理论上来说，执行时间应该差不多减半。那到底是什么原因让少了4秒呢？

一些想法：

你是在用Python 2吗？如果是的话，建议用 xrange，因为它会创建一个生成器/迭代器对象。这样可以节省一些毫秒，因为 range 会创建一个完整的字典并不断添加，而 xrange 不会。如果你用的是Python 3，range 默认就会创建一个迭代器。实际上，这样的改变可能不会节省太多时间或内存，但Python的开发者显然认为把所有东西都实现为生成器是值得的，因为这正是Python 3的一个重要特性。
理论上来说，算法的部分应该快2倍。但实际上，这比想象中要复杂。算法开始时设置线程或进程是有成本的，这会增加你的运行时间；最后，在结果同步时（等待线程结束）也会有成本。所以你永远无法真正实现2倍的速度提升。对于小规模的算法，大家都知道串行算法的表现会比多线程的好；只有当你处理的数据量大到线程创建的成本可以忽略不计时，才能感受到显著的速度提升。
工作负载的平衡可能会是个问题。在32位系统中，寄存器能容纳的最大数字是4294967296（2^32）。而你的总和在大值时是4999999950000000。大数相加的复杂度是O(n)，也就是你需要的数组元素数量，所以一旦开始使用大数，就会出现性能下降，而不是使用单个内存地址能处理的数字。
```
y = 0
for x in xrange(1, 100000000):
    if (x+y) > 2**32:
        print "X is " + str(x)
        print "y is " + str(y)
        break
    else:
        y += x
```
这段代码可以告诉你在什么情况下，数字相加的成本开始变高。我建议你先测一下到那个值的总和，再测一下从那里到N的总和，然后调整你的工作队列，以便在合适的时机进行分割。

当然，在64位系统上你应该不会遇到这个问题，因为2^64比你的总和要大，除非 Python内部没有使用 uint64_t。我本以为它会使用。

回答于 2025-04-16 由 Python大师

分享举报

你是怎么测时间的？你的笔记本电脑是什么型号？

如果你是通过命令行来测时间，可能会像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)))。这样应该会把重点从内存访问转移到计算上。

回答于 2025-04-16 由 Python大师

分享举报

接下来，我假设你在使用Python 2.x。

根据你笔记本电脑的硬件配置，进程0和进程1之间可能会有很大的内存竞争。

range(100000000/2) 这个命令会在我的电脑上创建一个占用1.5GB内存的列表，所以这两个进程加起来大约需要3GB的内存。使用两个核心来处理这两个列表，可能会导致内存带宽的问题（或者说是交换内存）。这很可能是导致并行处理不完美的原因。

如果用 xrange 替代 range，就不会生成完整的列表，这样可以更好地利用并行处理，因为计算会更依赖CPU。

顺便提一下，你的代码里有个错误：第二个 (x)range 应该从 N/2 开始，而不是 N/2+1。

回答于 2025-04-16 由 Python大师

分享举报

使用MPI的性能提升

7 个回答

撰写回答