Vertex-centric 與 Edge-centric 的 BFS 平行化 (Push, Pull, Edge-Centric)

重點總覽 (Overview)

每一層 (level) 都呼叫一次 kernel：先把 root 標為 level 0，逐層 (level-by-level) 把上一層鄰居標為當層，直到沒有新頂點被造訪。本筆記比較三種把工作映射到 thread 的策略。

Vertex-centric Push（top-down / CSR）

• 每個 thread 負責一個 vertex，先檢查自己是否屬於 上一層 currLevel-1；若是，沿 出邊 (outgoing edges) 把未造訪鄰居標為當層。
• 需要快速取得「某 source 頂點的出邊」→ 即 adjacency matrix 某一列 (row) 的非零元素 → CSR（srcPtrs + dst）。
• Push 語意：每個 active 頂點把自己的 depth「推 (push)」給所有鄰居。建 BFS tree 時等於「父找子」(top-down)。

// Fig. 15.6  Vertex-centric PUSH (top-down), uses CSR (srcPtrs, dst)
__global__ void bfs_push_kernel(CSRGraph csr, unsigned int *level,
                                unsigned int *newVertexVisited,
                                unsigned int currLevel) {
    unsigned int vertex = blockIdx.x * blockDim.x + threadIdx.x;     // 03
    if (vertex < csr.numVertices) {                                  // 04
        if (level[vertex] == currLevel - 1) {                        // 05 在上一層才工作
            for (unsigned int e = csr.srcPtrs[vertex];               // 06
                 e < csr.srcPtrs[vertex + 1]; ++e) {                 // 07 走出邊
                unsigned int neighbor = csr.dst[e];                  // 08
                if (level[neighbor] == UINT_MAX) {                   // 09 未造訪?
                    level[neighbor] = currLevel;                     // 10 標當層
                    *newVertexVisited = 1;                           // 11 idempotent 旗標
                }
            }
        }
    }
}

Push: thread = vertex, 沿 row 掃出邊 (CSR)
  level[]  0  1  1  X  X  X  X  X  X     (X = UINT_MAX 未造訪)
            v1 active ──srcPtrs[1..2]──► dst: 3,4   ⇒ level[3]=level[4]=2
            v2 active ──srcPtrs[2..3]──► dst: 5,6,7 ⇒ level[5..7]=2
  只有「上一層」的 thread (v1,v2) 真正迭代鄰居，其餘 thread 立即退出

Vertex-centric Pull（bottom-up / CSC）

• 每個 thread 負責一個 vertex，先檢查自己是否 尚未造訪；若是，沿 入邊 (incoming edges) 找是否有任何鄰居在 上一層；找到一個即把自己標為當層並 break。
• 需要快速取得「某 destination 頂點的入邊」→ adjacency matrix 某一行 (column) 的非零元素 → CSC（dstPtrs + src）。
• Pull 語意：每個未造訪頂點「拉 (pull)」回前驅的 active 狀態。建 BFS tree 時等於「子找父」(bottom-up)。

// Fig. 15.8  Vertex-centric PULL (bottom-up), uses CSC (dstPtrs, src)
__global__ void bfs_pull_kernel(CSCGraph csc, unsigned int *level,
                                unsigned int *newVertexVisited,
                                unsigned int currLevel) {
    unsigned int vertex = blockIdx.x * blockDim.x + threadIdx.x;     // 03
    if (vertex < csc.numVertices) {                                  // 04
        if (level[vertex] == UINT_MAX) {                             // 05 只處理未造訪頂點
            for (unsigned int e = csc.dstPtrs[vertex];               // 06
                 e < csc.dstPtrs[vertex + 1]; ++e) {                 // 07 走入邊
                unsigned int neighbor = csc.src[e];                  // 08
                if (level[neighbor] == currLevel - 1) {              // 09 前驅在上一層?
                    level[vertex] = currLevel;                       // 10 標自己
                    *newVertexVisited = 1;                           // 11
                    break;                                           // 12 找到一個就夠
                }
            }
        }
    }
}

Push vs Pull 與 Direction-Optimized

兩者都是 1 thread/vertex，但有兩個影響效能的關鍵差異：

push=scatter（主動把值推給鄰居，寫入分散）   ┐
pull =gather （主動把鄰居值拉進自己，寫入集中）┘  與 Ch.17/18 的 scatter-vs-gather 同源

Edge-centric（COO）

• 每個 thread 負責一條 edge：用 COO src[e] 找源點、若源點在上一層，再用 dst[e] 找目的點、若目的點未造訪則標為當層。
• 需要由「一條邊」直接取得 source 與 destination（即某非零的 row index 與 column index）→ COO（src + dst）。

// Fig. 15.10  Edge-centric, uses COO (src, dst)
__global__ void bfs_edge_kernel(COOGraph coo, unsigned int *level,
                                unsigned int *newVertexVisited,
                                unsigned int currLevel) {
    unsigned int edge = blockIdx.x * blockDim.x + threadIdx.x;       // 03
    if (edge < coo.numEdges) {                                       // 04
        unsigned int vertex = coo.src[edge];                         // 05 邊的源點
        if (level[vertex] == currLevel - 1) {                        // 06 源點在上一層?
            unsigned int neighbor = coo.dst[edge];                   // 07 邊的目的點
            if (level[neighbor] == UINT_MAX) {                       // 08 未造訪?
                level[neighbor] = currLevel;                         // 09 標當層
                *newVertexVisited = 1;                               // 10
            }
        }
    }
}

Edge-centric: thread = edge (每 thread 恰好 1 條邊 → 無 load imbalance)
  edges: (0,1)(0,2)(1,3)(1,4)(2,5)(2,6)(2,7)(3,4)(3,8)...
          ▲              ▲   ▲   ▲   ▲   ▲
          src 在上一層的邊才寫入 dst；其餘 thread 檢查後即退出

優點 vs 缺點

• vertex-centric 的對照：一個頂點 v 無關時，只啟一個 thread 檢查 v 一次即可 跳過全部 n 條邊。

線性代數 / GraphBLAS 形式 (Linear-Algebraic Formulation)

• 上述 kernel 與 Ch.14 的 SpMV (sparse matrix-vector multiplication) 高度相似。稍作改寫，可把「一層 BFS 迭代」整個表達成 SpMV + 少數向量運算，其中 SpMV 是主導運算。
• 更廣義：許多圖計算都能以 adjacency matrix 的稀疏矩陣運算表達 → 稱為圖問題的 linear-algebraic formulation，由 API 規格 GraphBLAS 標準化。

關鍵公式與複雜度 (Key Formulas)

• 滿連通有向圖邊數：E_full = N(N-1)（無自環）；稀疏圖中平均出度 ≪ N-1。
• 每層 launch 的 thread 數：
  • Push / Pull（vertex-centric）：threads = V（全部頂點）
  • Edge-centric：threads = E（全部邊；通常 E ≫ V → 平行度更高）
• 每層實際迭代鄰居的 thread 數：
  • Push：= |前一層頂點集合|（少）
  • Pull：= |未造訪頂點集合|（早期多、後期少）
• 每層工作量：vertex-centric 須掃所有頂點與相關邊 O(V + E)；edge-centric 每層固定掃所有邊 O(E)。
• COO 索引儲存：2·E（src+dst） vs CSR/CSC 的 (V+1) + E。

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

Related Notes

• 15-Graph-Traversal/01-Graph-Representations-and-BFS
• 15-Graph-Traversal/03-Frontiers-Privatization-and-Optimizations
• 14-Sparse-Matrix-Computation/01-Sparse-Matrices-and-Basic-Formats-COO-CSR
• 18-Electrostatic-Potential-Map/01-DCS-Scatter-vs-Gather
• 17-Iterative-MRI-Reconstruction/02-FHD-Kernel-Parallelism-Structure
• 04-Compute-Architecture-And-Scheduling/02-Warps-SIMD-and-Control-Divergence