Enter your search text in the box above

Select a result to preview

Parallel Merge Sort 與其他平行排序方法 (Merge Sort & Other Parallel Sorts)

#parallel-pattern #merge-sort #sorting-networks #sample-sort #algorithm-selection

重點總覽 (Overview)

方法 (Method) 類別 (Class) 複雜度 (Work) 平行化重點 適用場景
Merge sort comparison-based, bottom-up O(N·logN) merge tree:跨 merge 平行 + merge 內平行 (co-rank) 通用 key、複雜比較運算子
Radix sort (LSD) noncomparison-based, bottom-up < O(N·logN) one-thread-per-key + exclusive scan(見 sibling) 整數 / lexicographic key
Odd-even transposition sort comparison-based, network-like O(N²) 固定 even/odd pair 比較,不重疊 小序列、簡單實作
Sorting networks (bitonic / odd-even merge) comparison-based, fixed pattern O(N·log²N) 固定比較序列,天生平行 小序列最快
Sample sort comparison-based, top-down O(N·logN) 重點在 partition,合併僅 concatenate 超大序列 / 多 GPU 跨記憶體
MSD radix sort noncomparison-based, top-down < O(N·logN) 由 MSD 切桶,後續操作越來越 local 超大序列(避免 global shuffle)
Important

本章主體是 radix sort(見兩個 sibling notes)。本筆記聚焦 comparison-based 的 merge sort 平行化策略,以及其他平行排序法的概覽與全章總結。實務上多數人會直接用 Thrust 等函式庫而非自行實作。

為何需要 Comparison-Based Sort (Why Comparison-Based?)

Radix sort 雖然複雜度低於 O(N·logN),但有侷限。何時改用 merge sort 這類 comparison-based 演算法:

考量 Radix sort (noncomparison) Merge sort (comparison)
key 類型 僅限整數等可拆 digit 的 key 任意型別(只要能定義比較)
排序準則 限 lexicographic order 可用複雜 comparison operator
適配新 key 型別 常需另寫不同版本 只改 comparison operator 即可
複雜度 < O(N·logN)(優勢) O(N·logN)(下界,較高)
Tip

Comparison-based sort 的根本限制:任何 comparison-based 演算法不可能優於 O(N·logN),因為它必須執行足夠多次的兩兩比較。Radix sort 能更快,是因為它不靠比較,而是靠 digit 分桶。

平行 Merge Sort (Parallel Merge Sort)

核心思路:divide → sort segments → ordered merge,反覆合併直到全部成為單一 segment。

初始: 將 input 切成多個小 segment,各自獨立用任意高效演算法排序
之後: 每兩個 sorted segment → ordered merge 成一個 → 重複到剩一個 segment

Merge tree(自底向上 bottom-up)

 Sorted segments (leaves)
  s0  s1   s2  s3   s4  s5   s6  s7        8 segments
   \  /     \  /     \  /     \  /
   m(01)    m(23)    m(45)    m(67)   ← Stage 1: 4 independent merges (each small)
     \        /         \        /
      m(0123)            m(4567)        ← Stage 2: 2 merges (each 2x keys)
          \                /
           m(01234567)                  ← Stage 3: 1 merge (all keys)

每個 internal node 是一次 ordered merge(第 12 章 Merge 的平行 merge pattern)。

兩層平行性 (Two levels of parallelism)

merge sort 在每個 stage 都有平行機會,但平行來源隨 stage 改變:

Stage 階段 獨立 merge 數 每次 merge 的 key 數 主要平行來源 thread block 分配(8 blocks 範例)
早期 (early) 多 少 跨 merge 平行(many independent merges) 4 merges → 每 merge 配 2 blocks
中期 中 中 兩者兼有 2 merges → 每 merge 配 4 blocks
晚期 (late) 少 多 merge 內平行(co-rank 切分) 1 merge → 8 blocks 全投入
Tip

總平行度大致守恆:早期靠「很多小 merge」填滿 GPU,晚期靠「單一大 merge 內部用 co-rank function 切成許多獨立段」填滿 GPU。兩端都能讓所有 thread block 有事做。

Warning

merge 內如何切分(co-rank function、tiled merge、circular buffer、thread coarsening)本筆記不重複,全部在第 12 章 Merge。Merge sort 只是把那些 merge kernel 組織成一棵 merge tree 反覆呼叫。書中將完整實作留作習題。

其他平行排序方法 (Other Parallel Sort Methods)

Odd-Even Transposition Sort

最簡單的平行排序之一,類似平行版 bubble sort:

索引:  0   1   2   3   4   5   6   7
Phase A (even pairs): (0,1) (2,3) (4,5) (6,7)   ← 並行比較,逆序則 swap
Phase B (odd  pairs):    (1,2) (3,4) (5,6)      ← 並行比較,逆序則 swap
... 交替 A/B,直到某輪兩 phase 都無 swap 為止

Sorting Networks(固定比較模式)

Warning

漸進複雜度差,不代表實務慢。因為實作簡單、比較模式固定(無 data-dependent 分支),sorting networks 在小序列上往往是最快的選擇。這是「asymptotic worse but practically best on small inputs」的典型案例。

兩大策略:Bottom-Up vs Top-Down

非 sorting-network 的 comparison-based 平行排序可分為兩類,差別在「工作量集中在哪裡」:

策略 代表 做法 工作集中處 combine 步驟
Bottom-up Merge sort 切 tile → 各自排序 → merge tree 合併 合併 (merge tree) 昂貴(主要工作)
Top-down Sample sort partition 成有序桶 → 各桶獨立排序 切分 (partition) trivial(直接 concatenate)

Sample Sort(quicksort 的 p-way 推廣)

1. 從 input 選 p-1 個 splitter key(例如隨機取樣),排序之
2. 用 splitters 把 input 切成 p 個 bucket:
   bucket k 的所有 key  >  bucket j (j<k) 的所有 key
                        <  bucket j (j>k) 的所有 key
3. 每個 bucket 獨立排序
4. 依序 concatenate 各 bucket 即為結果(無需 merge)

MSD vs LSD Radix Sort

Radix sort 同樣有 bottom-up / top-down 兩種策略:

LSD radix sort(本章描述的) MSD radix sort
起點 digit least significant digit most significant digit
方向 LSD → MSD MSD → LSD
切分性質 每步需 global shuffle(全域重排) 每步操作於逐漸 localized 的區域
適用 一般 超大序列(類似 sample sort)
Tip

對映關係:merge sort=bottom-up、sample sort=top-down;同理 LSD radix=bottom-up、MSD radix=top-down。Top-down(sample sort / MSD radix)因為後續工作越來越 local、不需全域搬移,對超大序列更有利。

全章總結 (Chapter Summary)

考試/面試重點 (Exam / Test Patterns)

情境 / 關鍵字 答案 / 技巧
key 是複雜型別或需自訂比較 用 comparison-based(merge sort),只改 comparison operator;radix 需另寫版本
comparison-based 排序複雜度下界 O(N·logN)(必須做足夠比較,無法更快)
merge sort 早期 stage 平行來源 跨 merge 平行(很多獨立 merge,每個 key 少)
merge sort 晚期 stage 平行來源 merge 內平行(少數大 merge,用 co-rank 切分)
odd-even transposition sort 複雜度 O(N²),類平行 bubble sort,大序列差
sorting networks 代表 / 複雜度 bitonic sort、odd-even merge sort;O(N·log²N)
為何 sorting network 漸進較差卻常用 實作簡單、比較固定 → 小序列實務最快
bottom-up vs top-down 代表 merge sort=bottom-up(工作在 merge);sample sort=top-down(工作在 partition)
sample sort 步驟 選 p-1 splitter → 排序 → 切 p 桶 → 各桶獨立排序 → concatenate
sample sort 適用 / oversampling 超大序列 / 多 GPU 跨記憶體;oversample 取得平衡 partition
LSD vs MSD radix LSD 每步 global shuffle;MSD 操作越來越 local,適合超大序列
實務排序首選 用 Thrust 等函式庫,而非手寫 kernel