排序 (Sorting) 練習題 (Practice - Sorting Foundations and Parallel Radix Sort)

兩條件:(1) 輸出為 nondecreasing 或 nonincreasing 順序;(2) 輸出是 input 的 permutation(只重排、不增不減元素)。
Stable sort 在相同 key 時保留原始出現順序;它是 multi-key cascaded sort 的必要條件——先依 secondary key 排,再依 primary key 排,第二次排序會保留第一次建立的順序。

Radix sort 是 noncomparison-based,依 radix(base)把 key 分配到 buckets,逐 digit 重複且每次 iteration 都 stable。N-bit key、1-bit radix 需 N 次 iteration(本章為 LSD:LSB → MSB)。
每個 iteration 都依賴前一個 iteration 的完整結果,故 iteration 之間必須序列;平行的機會在單一 iteration 之內(host 對每個 bit 呼叫一次 kernel)。

落 0 bucket:destination = i − (# ones before)(= 自己之前有幾個 0)。
落 1 bucket:destination = N − (# ones total) + (# ones before)(所有 0 必須排在所有 1 之前,故先跳過全部 # zeros total = N − # ones total,再加上自己之前的 1 的個數)。
唯一非平凡的量是 # ones before。

把每個 key 取出的 bit(0/1)當作輸入做 exclusive scan,結果每格 = 該位置之前所有 bit 的和 = # ones before(正是 destination 公式需要的「不含自己」的前綴和,故用 exclusive 而非 inclusive)。
# ones total 則作為 scan 的副產品取得(例如 bits[N],或最後一格 inclusive 結果)。

因為 scan 過程中 thread 可能要做 barrier synchronization(__syncthreads 或 grid-wide barrier),必須所有 thread 都 active;若把 scan 放在邊界檢查內,被檢查擋掉的 inactive thread 缺席會造成 barrier 死結 / 結果錯誤。
兩種 grid-wide 做法:(1) 用 single-pass / grid-wide scan 技巧維持單一 kernel launch;(2) 拆成 3 個 kernel(scan 前處理 → 獨立 scan → scan 後處理),代價是每個 iteration 變 3 次 grid launch。

Comparison-based 排序不可能優於 O(N·logN),因為必須執行足夠多次的兩兩比較。
Radix sort 能更快(可 < O(N·logN)),是因為它不靠比較,而是靠 digit 分桶;代價是無法泛化到任意 key 類型,通常只適用整數等可拆 digit 的 key。

早期 stage:有很多獨立的 merge 操作(每個 merge 的 key 數少)→ 平行來源是跨 merge 平行(把不同 merge 分給不同 thread block)。
晚期 stage:獨立 merge 數變少、但每個 merge 的 key 數變多 → 平行來源是 merge 內平行(用第 12 章的 co-rank function 把單一大 merge 切成許多獨立段)。兩端都能讓所有 thread block 有事做。

Odd-even transposition sort:交替比較不重疊的 even/odd pair,類平行 bubble sort,O(N²),大序列效率差。
Sorting networks(Batcher's bitonic、odd-even merge sort):固定的比較/交換序列,天生平行,O(N·log²N);漸進雖比 merge sort 差,但小序列上常最快。
Sample sort:top-down,選 p−1 splitter 切成 p 個有序桶,各桶獨立排序後直接 concatenate;適合超大序列 / 多 GPU。
LSD vs MSD:LSD(本章)由低位開始,每步需 global shuffle;MSD 由高位切桶,操作越來越 local,適合超大序列。

exclusive scan(# ones before)= [0, 1, 1, 2, 3, 3, 3, 4],# ones total = 4(共 4 個 1)。
index 2,bit=1:dst = N − total + before = 8 − 4 + 1 = 5。
index 4,bit=0:dst = i − before = 4 − 3 = 1。
(所有 0 桶 key 佔 index 0..3,1 桶 key 佔 index 4..7。)

(a) iteration 數 = ⌈N_bits / r⌉ = ⌈32 / 4⌉ = 8 次。
(b) local bucket 數 = 2^r = 2^4 = 16 個。
(c) r-bit local sort = r = 4 次連續 1-bit local exclusive scan(iteration 間無跨 block 協調)。
(d) global scan 的 table 有 2^r = 16 列(每列對應一個 bucket,欄數 = block 數)。

每個 block 算出各 local bucket 的 key 數,填進一張 row-major bucket-size 表(先放所有 block 的 0-bucket size,再放所有 block 的 1-bucket size):[s00 s01 s02 s03 | s10 s11 s12 s13]。
對這張線性化的表做一次 global exclusive scan,結果即為各 block 各 local bucket 的 global 起始位移。
規則:某 block 的 local 0-bucket 接在所有前面 block 的 0-bucket 之後;local 1-bucket 接在全部 block 的 0-bucket + 前面 block 的 1-bucket 之後。寫回時每個 thread 依 threadIdx 落在哪個 local 桶,取對應位移連續寫回。

基礎(scatter):相鄰 thread 的 key 落在不同 bucket(0/1 交錯),consecutive thread index 不對應 consecutive memory location,一個 warp 內位址跳來跳去 → 需發出多次 memory request(uncoalesced)。
優化:採用 Ch.6 的第 3 法——每個 block 先在 shared memory 做 block-level local sort,把 0/1 桶排成連續段,再讓連續 thread 把整段以 coalesced 方式寫回 global。
成本轉移:把原本 grid-wide 的 scatter 降為 block 內 local exclusive scan(快很多);代價只是多算一張小小的 bucket-size 表的 global exclusive scan(以求各 block local bucket 的全域起始位移)。淨效果是用一次便宜的小 scan 換回大量 coalesced 寫入。

大 radix 的代價:雖然 iteration 數降為 ⌈N_bits/r⌉(grid launch / global 存取 / global scan 次數變少),但 (1) 桶數 = 2^r 變多、每桶 key 變少 → 寫回段變小 → coalescing 惡化;(2) global scan 的 table 大小 ∝ 2^r × #blocks 變大 → scan 開銷上升。故需在「iteration 數」與「coalescing + global scan 開銷」之間取平衡。
Thread coarsening:每個 thread 負責多個 key → block 數變少、每 block key 變多。這同時 (1) 讓 local buckets 變大 → 連續 thread 更可能寫到連續位址(coalescing↑),並 (2) 因 scan table ∝ bucket 數 × block 數,block 數變少 → table 變小 → global scan 開銷↓。
划算前提:當這些 block 本來就會被硬體序列化執行時(此時減少並行度不損失真正的平行收益,卻省下重複付出的 coalescing 與 scan 成本);若 block 真能完全並行,這代價未必該省。