随着并行化的增加，运行时的非单调演化

Question

我正在运行一些运行时测试，以了解我可以从并行化中获得什么，以及它如何影响运行时(线性地?)。对于给定的整数n，我依次计算n-斐波那契数，并通过允许使用多达16个并行进程来计算{0,1,...,n}中的每个斐波那契数i来改变并行化程度。

import pandas as pd
import time
import multiprocessing as mp

# n-te Fibonacci Zahl
def f(n: int):
if n in {0, 1}:
return n
return f(n - 1) + f(n - 2) 

if __name__ == "__main__":
K = range(1, 16 + 1)
n = 100
N = range(n)

df_dauern = pd.DataFrame(index=K, columns=N)

for _n in N: 
_N = range(_n)
print(f'nn = {_n}')
for k in K:


start = time.time()

pool = mp.Pool(k)
pool.map(f, _N)
pool.close()
pool.join()

ende = time.time()
dauer = ende - start    
m, s = divmod(dauer, 60)
h, m = divmod(m, 60)
h, m, s = round(h), round(m), round(s)

df_dauern.loc[k, _n] = f'{h}:{m}:{s}'

print(f'... k = {k:02d}, Dauer: {h}:{m}:{s}')

df_dauern.to_excel('Dauern.xlsx')

在下面的DataFrame中，我显示{45, 46, 47}中n的持续时间(h:m:s)。

45       46       47
1   0:9:40  0:15:24  0:24:54
2   0:7:24  0:13:23  0:22:59
3    0:5:3   0:9:37   0:19:7
4   0:7:18   0:7:19  0:15:29
5   0:7:21   0:7:17  0:15:35
6   0:3:41   0:9:34   0:9:36
7   0:3:40   0:9:46   0:9:34
8   0:3:41   0:9:33   0:9:33
9   0:3:39   0:9:33   0:9:33
10  0:3:39   0:9:32   0:9:32
11  0:3:39   0:9:34   0:9:45
12  0:3:40    0:6:4   0:9:37
13  0:3:39   0:5:54   0:9:32
14  0:3:39   0:5:55   0:9:32
15  0:3:40   0:5:53   0:9:33
16  0:3:39   0:5:55   0:9:33

在我看来，结果是奇数在两个维度。首先，持续时间不会单调地减少并行化的增加，其次，运行时不会线性减少(即双进程，一半运行时)。

• 这种行为是预期的吗?
• 这种行为是由于所选择的计算斐波那契数的例子?
• 运行时间怎么可能随着并行化的增加而增加(例如，总是从2个并行进程移动到3个并行进程)?
• 为什么我使用6个或16个并行进程没有区别?

Answer 1

这是因为多处理调度算法和任务具有阶乘复杂性的事实，默认情况下，池将选择相对于工人数量的块大小

基本上多处理将工作分成相等的块以减少序列化开销，块大小由。

给出。

chunksize, extra = divmod(len(iterable), len(self._pool) * 4)
chunksize += bool(extra)

4和5的工人,块大小是一样的(3),和99.9%的时间是由过去的3任务,安排在相同的核心(因为他们在1块),所以1核心最终做了99.9%的工作不管核心数,额外的3秒钟最有可能调度开销(更多的工人=更多的调度),你会得到一个加速如果你手动设置chunksize=1pool.map参数,如每一个3任务才会安排不同的核心。

对于worker number大于6,chunksize被计算为2，但是你有一个奇数的task，这意味着你将总是等待最后一个被调度的task，这是最长的一个，整个3:40分钟都在一个函数中，它不能进一步分解，所以不管你是启动6个worker还是100个，你仍然受到最慢的task(或者实际上是最慢的chunk)的限制。