并行化归并排序的加速比计算及代码优化技术咨询

问题1：Y远小于m时的加速比推导与图表趋势 #

加速比推导 #

用Work-Span并行计算模型分析更适配分治算法（比Amdahl定律更直观）：

• 工作量（总操作数，即串行时间）：(W(m) = O(m \log m))
• 跨度（并行执行的最长串行路径时间）：经典归并排序的合并阶段是串行链式操作，总跨度 (S(m) = O(m))（合并操作总时间为 (m + m/2 + m/4 + ... + 1 = O(m))）

根据模型，并行时间 (T_p = \max\left(\frac{W}{Y}, S\right))，加速比 (S_{speed} = \frac{W}{T_p})，结合Y远小于m的条件，分两种场景：

1. 当 (Y \ll \log m)（核心数远小于递归树深度）：
   核心足够处理所有并行子任务，(T_p \approx \frac{W}{Y} = \frac{m \log m}{Y})，加速比 (S_{speed} \approx Y)，接近线性加速。
2. 当 (\log m \leq Y \ll m)（核心数超过递归树深度但远小于元素数）：
   受限于串行合并的跨度，(T_p \approx S = O(m))，加速比 (S_{speed} \approx \frac{m \log m}{m} = \log m)，达到上限后不再增长。

图表趋势 #

• 横轴：核心数Y；纵轴：加速比
• 当Y从1增长到(\log m)时，加速比呈线性上升，斜率接近1
• 当Y超过(\log m)后，加速比趋于平稳，维持在(\log m)附近

问题2：Y=m时的变化与最优加速比实现 #

Y=m时的结论 #

经典归并排序的跨度是(O(m))，此时并行时间(T_p \approx O(m))，加速比仅为(\log m)，远低于强缩放要求的线性加速，核心资源严重浪费。

代码修改方案（实现强缩放） #

要实现最优加速比，需将跨度从(O(m))降至(O((\log m)^2))，核心是并行化合并阶段并优化任务分配：

修改后的伪代码

ParallelMergesort(m, core_count)
    if length(m) <= 1
        return m
    if core_count == 1
        # 退化为串行归并排序
        return SerialMergesort(m)
    
    middle = length(m) // 2
    left = m[0:middle]
    right = m[middle:]
    
    # 并行执行左右子排序，均分核心
    [left_sorted, right_sorted] = parallel_run(
        lambda: ParallelMergesort(left, core_count//2),
        lambda: ParallelMergesort(right, core_count - core_count//2)
    )
    
    # 并行合并两个有序列表
    return ParallelMerge(left_sorted, right_sorted, core_count)

ParallelMerge(left, right, core_count)
    if not left or not right:
        return left + right
    if core_count == 1:
        return SerialMerge(left, right)
    
    # 二分分割两个列表，递归并行合并
    mid_left = length(left) // 2
    split_pos = binary_search(right, left[mid_left])
    [part1, part2] = parallel_run(
        lambda: ParallelMerge(left[:mid_left+1], right[:split_pos], core_count//2),
        lambda: ParallelMerge(left[mid_left+1:], right[split_pos:], core_count - core_count//2)
    )
    return part1 + part2

# 原串行归并排序与合并函数
SerialMergesort(m)
    # 与题目中Mergesort逻辑一致
SerialMerge(left, right)
    # 与题目中Merge逻辑一致

修改说明

1. 递归任务并行化：将左右子排序任务分配给不同核心，最大化并行度
2. 并行合并：通过二分查找分割两个有序列表，将合并任务拆分为子任务并行执行，把合并阶段的跨度从(O(m))降至(O(\log m))，总算法跨度变为(O((\log m)^2))
3. 动态核心分配：根据剩余核心数调整子任务的核心分配，避免核心闲置

修改后，当Y=m时，并行时间(T_p \approx O((\log m)^2))，加速比(S_{speed} \approx \frac{m \log m}{(\log m)^2} = \frac{m}{\log m})，接近强缩放效果。

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