Enter your search text in the box above

Select a result to preview

Merge 基礎與 Co-rank 概念 (Sequential Merge & Parallelization)

#parallel-pattern #ordered-merge #co-rank-function #stable-sort #dynamic-input-identification

重點總覽 (Overview)

項目 內容 關鍵點
問題定義 兩個已排序陣列 A (m el(個)) + B (n el(個)) → 一個已排序陣列 C (m+n el(個)) |C| = m + n
Stability (穩定性) 相等 key 維持原輸入順序；A 元素優先於相等的 B 元素 tie 時取 A[i] <= B[j]
Sequential 演算法 雙指標 (i,j) 掃描 + 收尾複製 複雜度 O(m+n)
平行化挑戰 每個 thread 的輸入範圍 無法由 index 算式直接得到(資料相依) dynamic input data identification
平行化策略 切分 output,再用 co-rank function 反推各 thread 的 input 子範圍 output-centric 分解
Co-rank 概念 output rank k → 唯一 co-ranks (i, j),滿足 k = i + j i,j 唯一 (Siebert & Träff 2012)
Co-rank 實作 對已排序輸入做 binary search O(log N), N=max(m,n)
Important

Merge 與本書先前所有 pattern 的根本差異:每個 thread 要讀取的 input 範圍取決於實際輸入數值,而非單純的 thread index 計算。這正是「dynamic input data identification」這一章的核心主題,也是 set intersection / set union / map-reduce 等運算的共通難點。

有序合併與穩定性 (Ordered Merge & Stability)

Ordered merge:給定依排序關係 ≤ 排序的 A (m 個) 與 B (n 個),產生包含全部 m+n 個元素、且仍依 ≤ 排序的 C。元素帶有 key,排序關係定義在 key 上(最簡單情況下元素本身即 key)。

A (m=5): [ 1 , 7 , 8 , 9 , 10 ]
B (n=4): [ 7 , 10 , 10 , 12 ]

           A0  A1  B0  A2  A3  A4  B1  B2  B3
            |   |   |   |   |   |   |   |   |
            v   v   v   v   v   v   v   v   v
C (m+n=9):[ 1 , 7 , 7 , 8 , 9 , 10 , 10 , 10 , 12 ]
                  ^A  ^B           ^A   ^B   ^B
              tie:A先  within-B 保序  across+within 保序

Stability (穩定排序):key 相等的元素在輸出中保持其輸入中的相對順序。Merge 需展現兩種穩定性:

穩定性類型 範例(上圖) 規則
Within a list (同一清單內) B 的兩個 10 (B[1], B[2]) 在 C 中維持原順序 同陣列指標單調遞增即自動成立
Across lists (跨清單) A 的 7 排在 B 的 7 之前 tie 時 A 優先 → 用 A[i] <= B[j]
Tip

Stability 的價值:可保留先前依其他 key 排序的成果。例如資料先依次要 key 排好,再依主要 key 做 stable merge,則同主要 key 內仍保有次要 key 的順序。這是 merge sort 能逐層保持正確性的基礎。

Warning

「A 優先」是設計慣例,不是數學必然。若改成 A[i] < B[j](嚴格小於),tie 時會取 B,變成「B 優先」——仍是合法排序,但不再 stable across lists。穩定性要求決定了比較運算子要用 <=。

用途:merge 是 merge sort 的核心(見 13-Sorting/03-Parallel-Merge-Sort-and-Other-Methods),也是 map-reduce 框架(如 Hadoop)在 reduction tree 中組合排序結果的基礎運算。

循序合併演算法 (A Sequential Merge Algorithm)

兩段式結構:(1) while-loop 同時掃描 A、B,每次迭代填一個 C 位置;(2) 收尾複製尚未耗盡那一方的剩餘元素。

void merge_sequential(int *A, int m, int *B, int n, int *C) {
    int i = 0;   // index into A
    int j = 0;   // index into B
    int k = 0;   // index into C
    // --- Part 1: 兩陣列都還有元素時,逐位置挑選 ---
    while ((i < m) && (j < n)) {
        if (A[i] <= B[j]) {        // tie 取 A => 維持 stability
            C[k++] = A[i++];
        } else {
            C[k++] = B[j++];
        }
    }
    // --- Part 2: 複製剩餘元素(只會進入其中一個 while)---
    if (i == m) {                  // A 已耗盡 → 複製剩下的 B
        while (j < n) { C[k++] = B[j++]; }
    } else {                       // 否則 B 已耗盡 → 複製剩下的 A
        while (i < m) { C[k++] = A[i++]; }
    }
}
Tip

第二部分的 if-else 對正確性而言不是必要的:可直接寫兩個連續 while-loop,依 A/B 何者先耗盡只會有一個被執行。書中保留 if-else 純粹為了可讀性。

複雜度:A、B 每個元素各被讀一次、C 每個位置各被寫一次。

量 值
Work m + n 次比較/搬移
Time complexity O(m + n)(與總元素數線性)

平行化策略 (A Parallelization Approach)

Siebert & Träff (2012) 的策略,output-centric 分解:

   Step 1  切分 OUTPUT:每個 thread 認領 C 的一段(output range)
   Step 2  co-rank function:由 output range 反推它要讀的 A、B input ranges
   Step 3  各 thread 對自己的 (A 子陣列, B 子陣列) 獨立呼叫 merge_sequential

關鍵在於:一旦 input/output 範圍確定,各 thread 的子陣列互不重疊、互不相依,可完全平行地各自跑循序 merge。整個平行化的核心就是 co-rank function。

C 被切成 3 段 (3 threads):
C: [ c c c | c c c | c c c ]
     thr0    thr1    thr2
        |       |
        | co-rank 反推
        v       v
A: [ a a a a | a ]     B: [ b | b b | b ]
   thr0:|A|=4 |1         thr0:1  thr1:2  thr2:1
   ── 各 thread 的 A、B 子段大小由「資料數值」決定,不固定 ──
Warning

Output 切得均等(每 thread 同樣數量),但對應的 input 子段大小可變且資料相依:某 thread 可能幾乎全取自 A,另一 thread 幾乎全取自 B。兩個 input 子段大小之和才等於該 thread 的 output 段大小。這種不確定性使後續 tiling 變得困難(見 12-Merge/03-Tiled-and-Circular-Buffer-Merge-Kernels)。

Rank 與 Co-rank 概念 (The Co-Rank Concept)

設 A (m 個)、B (n 個) 已排序,C = merge(A,B) 共 m+n 個。對任一輸出索引 k:

Observation 1:對任意 0 ≤ k < m+n,C[k] 的值非來自 A[i] 即來自 B[j](二選一)。

 Case 1: C[k] 來自 A[i]              Case 2: C[k] 來自 B[j]
   prefix C[0..k-1] =                  prefix C[0..k-1] =
     merge(A[0..i-1], B[0..k-i-1])       merge(A[0..k-j-1], B[0..j-1])
   令 i,再導出 j = k - i               令 j,再導出 i = k - j

Observation 2(統合兩 case):對任意 0 ≤ k < m+n,存在 i、j 使得

            k = i + j        (恆等不變式 / invariant)
   0 ≤ i < m ,  0 ≤ j < n
   C[0..k-1] = merge( A[0..i-1] , B[0..j-1] )

Siebert & Träff 證明這組 i, j 唯一。術語:

術語 符號 意義
Rank k C[k] 在輸出陣列的索引
Co-rank i 對應到 A 的唯一索引(產生 C 前綴所需的 A 元素數)
Co-rank j 對應到 B 的唯一索引,j = k - i

範例(A=[1,7,8,9,10], B=[7,10,10,12], C=[1,7,7,8,9,10,10,10,12]):

C 元素 來源 rank k co-rank i co-rank j 驗證 k=i+j
C[4]=9 A[3] 4 3 1 4 = 3+1 ✓
C[6]=10 B[1] 6 5 1 6 = 5+1 ✓
Important

Co-rank 給出平行化的路徑:把 C 切成多段,每段起點的 rank k 已知;對 thread t 呼叫 co-rank 得 (i_t, j_t),對 thread t+1 得 (i_{t+1}, j_{t+1}),則 thread t 要 merge 的輸入即
A[i_t .. i_{t+1}-1] 與 B[j_t .. j_{t+1}-1]。
兩次 co-rank 呼叫分別界定子範圍的起點與終點。

為何 co-rank 是 search:因為要找的是「使 prefix 為合法 merge」的切點。可形式化為條件 A[i-1] ≤ B[j] 且 B[j-1] < A[i]。由於 A、B 已排序,可用 binary search(或更高 radix)達到 O(log N) 複雜度,N = max(m, n)。搜尋下界可收緊為:

   i_low = max(0, k - n)      // 至少要從 A 取這麼多(因 B 最多只有 n 個)
   j_low = max(0, k - m)      // 對稱地,B 的下界
Warning

Co-rank function 的完整 binary-search 實作、搜尋邊界調整、以及據此寫成的 basic merge kernel,屬於下一篇 12-Merge/02-Co-Rank-Function-and-Basic-Merge-Kernel,本篇只建立概念。

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

情境 / 關鍵字 答案 / 技巧
Sequential merge 複雜度 O(m+n);每元素讀一次、每 C 位置寫一次
為何 tie 用 A[i] <= B[j] 維持 stability across lists(A 優先);用 < 會破壊穩定性
Stability 兩種展現 within-list(同陣列指標單調)、across-list(tie 取 A)
Stability 的價值 保留先前依其他 key 排序的成果(分層排序)
Merge 與其他 pattern 的根本差異 input 範圍資料相依,無法用 index 算式直接得到(dynamic input identification)
Rank vs Co-rank rank = k(C 的索引);co-rank = (i,j)(A、B 的對應索引)
Co-rank 不變式 k = i + j,且 i,j 唯一
給定 C[k] 求 co-rank(如 Exercise 1) 找 (i,j) 使 k=i+j 且 A[i-1]≤B[j]、B[j-1]<A[i]
Co-rank 為何用 binary search / 複雜度 輸入已排序 → search;O(log N), N=max(m,n)
thread t 的 input 子陣列 A[i_t..i_{t+1}-1]、B[j_t..j_{t+1}-1](兩次 co-rank)
平行化的分解方向 output-centric:先切 C,再反推 input
為何每 thread 取 2x 輸入只保證 x 輸出 最壞情況 output 可能全來自單一輸入陣列