Enter your search text in the box above

Select a result to preview

Thread Coarsening 與本章總結 (Summary)

#parallel-pattern #thread-coarsening #ordered-merge #binary-search #dynamic-input-identification

重點總覽 (Overview)

項目 說明 重點
Merge 的平行化代價 每個 thread 都要自己做 binary search 找出 co-rank 多出來的是 search 成本，不是計算成本
Thread Coarsening 手段 減少 launch 的 thread 數 = 每個 thread 負責多個輸出元素 降低 binary search 總次數
Coarsening factor T 每個 thread 產生的 C 元素個數 本章所有 kernel 都已套用 (T > 1)
未 coarsen 的下場 T = 1，每個輸出元素都要做一次 binary search 成本 prohibitive（無法接受）
co-rank 呼叫數 每個 thread 呼叫 co-rank 2 次 (k_curr、k_next) search 成本 2·log N 攤提到 T 個元素
本章主題 Dynamic input data identification（動態輸入範圍） 輸入範圍 data-dependent → 需 co-rank、tiling、circular buffer
Important

Thread coarsening 在 merge 裡的角色與前面章節不同。在 reduction/scan/histogram 裡 coarsening 主要省的是 同步 / 重複載入 / atomic 成本；在 merge 裡，coarsening 攤提的是每個 thread 專屬的 binary search 成本。這是 merge 特有的「動態輸入辨識」開銷。

為 Merge 做 Thread Coarsening (Thread Coarsening for Merge)

核心觀察

平行化 merge 的主要代價在於：每個 thread 必須執行自己的 binary-search co-rank 運算，才能知道它要讀哪一段 A 與 B（輸入範圍是 data-dependent，不能用單純的 index 計算決定）。

Tip

Coarsening 是 merge 的 必需品 (essential)，不只是優化選項。沒有它，binary search 的成本會主宰整個 kernel 的執行時間。

Thread → Data 映射對照

Uncoarsened (T = 1)：每個輸出元素都要一次 binary search
 thread:   t0    t1    t2    t3    t4    t5    t6    t7   ...
 output:  C[0]  C[1]  C[2]  C[3]  C[4]  C[5]  C[6]  C[7]
 search:  [BS]  [BS]  [BS]  [BS]  [BS]  [BS]  [BS]  [BS]   <- (m+n) 次 search!

Coarsened (T = 3)：binary search 成本攤提到多個元素
 thread:    t0            t1            t2
 output:  C[0..2]       C[3..5]       C[6..8]
 search:  [BS×2]        [BS×2]        [BS×2]              <- 只有 (m+n)/T 個 thread
          k_curr,k_next  k_curr,k_next k_curr,k_next
            |               |             |
            v               v             v
        sequential merge T 個元素 (O(T)，無需 search)

每個 thread 只在兩端各做一次 co-rank（k_curr 決定起點、k_next 決定終點），中間 T 個元素用便宜的 merge_sequential（O(T)）填滿。

成本攤提 (Cost Amortization)

設兩輸入陣列大小 m、n，N = max(m, n)，coarsening factor T（每 thread 輸出元素數）：

量 公式
Thread 總數 numThreads = (m + n) / T
每 thread co-rank 呼叫 2（k_curr + k_next）
單次 binary search 成本 O(log N)
binary search 總成本 (m+n)/T × 2 × O(log N) ← 隨 T 變大而下降
每 thread sequential merge O(T)
merge 總成本 (m+n)/T × O(T) = O(m + n) ← 與 T 無關
每個輸出元素攤到的 search 成本 2·log N / T ← T↑ 則攤提成本 ↓ 
// 本章所有 kernel 的 coarsening 骨架（thread-level）：T = elements per thread
int k_curr = tid * elementsPerThread;                    // 本 thread 輸出起點 rank
int k_next = min((tid + 1) * elementsPerThread, m + n);  // 下一 thread 輸出起點 rank

int i_curr = co_rank(k_curr, A, m, B, n);   // binary search #1  O(log N)
int i_next = co_rank(k_next, A, m, B, n);   // binary search #2  O(log N)
int j_curr = k_curr - i_curr;
int j_next = k_next - i_next;

// 攤提：以下 merge 一次處理 (k_next - k_curr) = T 個元素，無需再 search
merge_sequential(&A[i_curr], i_next - i_curr,
                 &B[j_curr], j_next - j_curr,
                 &C[k_curr]);                // O(T)
Warning

Coarsening 不是免費：T 太大會減少 thread / block 數，降低 occupancy 與平行度，使部分 SM 閒置。需在「攤提 search 成本」與「保有足夠平行度隱藏延遲」之間取捨。最佳 T 與硬體相關，需 profiling。

Warning

各 kernel 做 binary search 的位置不同（影響 coalescing）：

  • Basic kernel：每個 thread 都對 global memory 做 co-rank（不規則、uncoalesced）。
  • Tiled / Circular：每 block 只有一個 thread 對 global memory 做 block-level co-rank；各 thread 的 thread-level co-rank 改在 shared memory 上做。

本章總結：Dynamic Input Data Identification (Chapter Summary)

與先前 pattern 的根本差異

merge 與本書先前所有 pattern 的關鍵不同：每個 thread 要讀的輸入範圍無法用簡單 index 計算得知，而是 data-dependent（取決於實際的輸入數值）。這就是本章主題 dynamic input data identification，同樣概念也適用於 set intersection、set union 等運算。

一般 pattern：  thread t → 固定輸入 A[t]            （index 算得出來）
merge pattern： thread t → A[i_t .. i_{t+1}-1]      （i_t 由 co-rank「搜尋」決定）
                          B[j_t .. j_{t+1}-1]        （範圍大小隨資料浮動）

四個 Kernel 的演進（同一問題、逐步優化記憶體效率）

Kernel (節) global mem co-rank shared mem co-rank Coalescing Shared mem 利用率 程式複雜度
Basic (12.5) 每 thread × 2 無 差 (uncoalesced) 不使用 低
Tiled (12.6) 每 block 1 thread × 2 每 thread × 2 載入 coalesced 50% 浪費（每次只用一半） 中
Circular Buffer (12.7) 每 block 1 thread × 2 每 thread × 2 載入 coalesced 100% 使用 高
Coarsening (12.8) （已套用於以上全部） （已套用於以上全部） — — —
Note

Coarsening 是橫切於以上三者的維度：三個 kernel 本來就都是 coarsened（每 thread 多元素），因為若不 coarsen，binary search 成本會壓垮一切。

解決方案鏈

挑戰 解法 對應節
輸入範圍 data-dependent，無法靠 index 算出 co-rank function（binary search，O(log N)） 12.4
每 thread 自己 search 成本高 thread coarsening（攤提 search 到多元素） 12.8
co-rank / merge 對 global memory 存取不規則、uncoalesced shared-memory tiling（block-level 載入後在 shared mem 上 search） 12.6
tiled 版每輪只用掉一半載入的資料，浪費頻寬 circular buffer（保留上輪剩餘元素，wrap-around 重用） 12.7
circular buffer 讓 index 計算（wrap-around）變複雜 simplified buffer access model（對外呈現連續 buffer，wrap 只在實際存取時處理） 12.7
Tip

設計哲學重點：把複雜資料結構（circular buffer）的繁瑣處理封裝進 library 函式（co_rank_circular、merge_sequential_circular），讓使用端 (user code) 幾乎不變。良好的介面設計能把複雜度的衝擊降到最低。

Important

merge 是 memory-bandwidth bound：運算與 register 資源通常閒置。因此「多用 registers / 多算 address 來省記憶體頻寬」（如 circular buffer 的額外 bookkeeping）是合理取捨，即使會略降 occupancy。

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

情境 / 關鍵字 答案 / 技巧
「merge 平行化的主要代價是什麼？」 每個 thread 都要做自己的 binary-search co-rank（輸入範圍 data-dependent）
「為何 merge 一定要 thread coarsening？」 攤提 binary search 成本；T=1 時每個元素一次 search，prohibitively expensive
「coarsening 在 merge vs reduction 省的是什麼？」 merge 省 binary search 次數；reduction/scan 省 同步 / 重複載入
「每個 thread 呼叫幾次 co-rank？」 2 次：k_curr（起點）與 k_next（終點），中間用 merge_sequential
「binary search 總成本公式」 (m+n)/T × 2 × O(log N)，N = max(m,n)；T↑ → 成本 ↓
Ex.4 基本 kernel：幾個 thread 對 global mem 做 binary search？ (m+n)/T 個 thread 全部：(1,030,400+608,000)/8 = 204,800
Ex.4 tiled kernel：幾個 thread 對 global mem 做 binary search？ 每 block 只 1 個 → blocks 數 = 204,800/1024 = 200
Ex.4 tiled kernel：幾個 thread 對 shared mem 做 binary search？ 全部 thread：204,800
「本章核心主題一句話」 Dynamic input data identification：輸入範圍隨資料動態決定
「circular buffer 解決什麼？」 tiled 版每輪浪費一半載入資料；circular buffer 讓 shared mem 100% 使用
「coarsening 的 downside？」 thread/block 數變少 → occupancy / 平行度下降，但 memory-bound 下可接受