专题进阶 · 并行算法推荐总顺序 · 第 109 / 148 课

用双调排序网络观察独立比较交换,计算网络层数并理解它与通用排序的取舍。

先学会这些,再进入本课 归并排序 并行归约
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 并行算法

并行排序Parallel Sort

在并行归并、采样分区或排序网络之间选择,通信和负载平衡同样重要。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用双调排序网络观察独立比较交换,计算网络层数并理解它与通用排序的取舍。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

能否预先决定所有比较位置,让同一轮中的很多比较交换同时进行?

02一步步得到方法

数据无关的比较网络

比较网络固定比较哪两个位置以及升降序方向,不根据数据临时决定下一对。双调排序先形成一段升序、一段降序组成的双调序列,再通过分层比较交换合并成统一方向。

本课实现使用二次幂长度。长度 k 从 2 倍增到 n,在每个 k 内,比较距离 j 从 k/2 不断减半。位置 i 的配对位置为 i XOR j,异或翻转对应的二进制位。

一次只交换每一对中的一个方向

i XOR j 会把配对关系映射回来,因此只在 partner>i 时处理。方向由 i 的 k 位确定:该位为 0 的块做升序,反之降序;在最终 k=n 时所有位置的该位为 0,于是整体升序。

固定 k、j 的一轮中,每个位置只出现在一对比较中,彼此互不冲突。下一轮依赖上一轮结果,仍需要同步。

更多工作换取规则结构

n=2ᵐ 时,总比较轮数为 1+2+…+m=m(m+1)/2,每轮 n/2 个比较器,所以工作 O(n log² n),跨度 O(log² n)。

这比比较排序常见的 O(n log n) 工作更多,但访存和比较结构规则,可能适合某些并行小规模场景。不能据此声称它总比归并或快速排序快;重复值稳定性也未得到保证。

03把一个小例子完全算清楚

n=4,输入 [4,1,3,2]。

步骤计算与状态为什么这样做
k=2、j=1[1,4,3,2]第一对升序,第二对降序
k=4、j=2[1,2,3,4]比较相距 2 的位置
k=4、j=1[1,2,3,4]最终相邻比较完成合并

窄屏可左右滑动表格,阅读完整计算与理由。

3 轮,每轮 2 个比较器,得到升序数组。

04为什么这个方法成立

  1. 双调序列经过相隔半长的比较交换后,较小元素进入前半、较大元素进入后半,两个半段仍具有可递归合并的双调结构。
  2. 逐层减半比较距离,就把一个双调块合并为有序块。
  3. 外层倍增构造更大的相反方向有序块,最终完成整个数组升序;这依赖正确的方向位和配对距离。

05把推导翻译成代码

Python · 双调比较网络的串行模拟

def bitonic_sort(values):
    a = list(values)
    n = len(a)
    if n==0:
        return a
    if n & (n-1):
        raise ValueError("power-of-two length required")
    k = 2
    while k<=n:
        j = k//2
        while j:
            for i in range(n):
                partner = i ^ j
                if partner>i:
                    ascending = (i & k)==0
                    if (ascending and a[i]>a[partner]) or (not ascending and a[i]<a[partner]):
                        a[i],a[partner] = a[partner],a[i]
            j //= 2
        k *= 2
    return a

print(bitonic_sort([4,1,3,2]))

逐个理解关键决定

partner = i ^ j
通过异或确定本轮唯一配对位置。
partner>i
每对只比较一次,避免交换后又被反向处理。
(i & k)==0
同一合并阶段中控制块的升降方向。

06时间、空间与实现范围

工作 O(n log² n),并行跨度 O(log² n);当前 CPU 模拟实际耗时也是 O(n log² n)。

复制输入需 O(n) 空间;网络本身不需要递归栈,不保证稳定排序。

07改变条件,检查哪里会出错

任意长度直接运行

本网络依赖二次幂长度;可补合适哨兵后删除,或选择其他网络。

网络层数就是实际 GPU 延迟

硬件并行度、同步和数据传输仍需测量。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

n=8 总共有几轮?

需要一点提示

log₂8=3。

查看解析与答案

1+2+3=6 轮,共 24 个比较器。

练习 2 · 边界与辨析

i=5、j=2 时 partner 是多少?

需要一点提示

101 XOR 010。

查看解析与答案

7,即二进制 111。

练习 3 · 变式与迁移

为什么同一轮比较可以同时做?

需要一点提示

检查每个索引出现次数。

查看解析与答案

每个位置恰属于一个互不重叠的配对,不共享写入位置。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

NVIDIA · CUDA Best Practices Guide

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。