并行度提升时运行时长非单调变化的原因探究

测试背景 #

我开展了运行时长测试，以了解并行化的收益及对运行时长的影响（是否线性？）。针对给定整数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')

测试数据（n=45,46,47） #

疑问解答 #

1. 这种现象是否属于预期情况？
   是完全预期的。并行化并非总能带来线性加速，甚至不一定单调递减，因为存在进程调度开销、任务分配不均、资源竞争等现实因素，理想的线性加速只存在于无额外开销的理论场景中。

2. 该现象是否由计算斐波那契数的测试案例导致？
   有直接关联，但不是唯一原因。你使用的递归版斐波那契计算，不同n的计算量差异极大（比如f(47)的计算量远大于f(0)），任务队列里的任务耗时严重不均，会导致进程“忙闲不均”——有的进程早早完成简单任务，有的还在处理大任务，后续调度反而增加额外开销。同时，递归本身的栈开销、重复计算也会放大并行调度的不确定性。

3. 为何运行时长会随并行度提升而增加（如从2到3个并行进程时）？
   主要有两个原因：

• 进程调度开销：新增进程会带来额外的创建、上下文切换、通信开销，当这些开销超过并行计算节省的时间时，总时长就会增加。
• 任务分配策略：multiprocessing.Pool.map按块划分任务，如果任务块集中了大量耗时短的任务，新增进程很快就会闲置，反而占用系统CPU、内存资源，拖慢正在处理大任务的进程。

4. 为何使用6个或16个并行进程时，运行时长无差异？
   这说明系统已达到并行加速的瓶颈：

• CPU核心限制：如果你的物理CPU核心数少于6，超过核心数的进程只能在同一核心上分时调度，无法真正并行，反而增加上下文切换开销，抵消不了收益。
• 任务负载上限：当进程数足够覆盖最耗时的任务时，再增加进程也无法进一步缩短总时长——总时长由耗时最长的任务决定，其他进程完成任务后只能等待，多余进程对总时长没有影响。

内容的提问来源于stack exchange，提问作者clueless