稀疏矩陣與基礎儲存格式 (COO 與 CSR)

重點總覽 (Overview)

背景與 SpMV (Background & SpMV)

• Sparse matrix (稀疏矩陣)：絕大多數元素為 0。儲存/處理這些 0 會浪費 記憶體容量、頻寬、時間、能量。
• 來源：科學/工程/金融的線性方程組。每個 row = 一條方程式，每個 column = 一個變數的係數。方程式間 稀疏耦合 (每條方程式只牽涉少數變數)。
• 解線性系統 A·X + Y = 0：
  • 直接法 (求反矩陣，如 Gaussian elimination) 對大型稀疏矩陣不切實際 → 反矩陣會產生大量 fill-ins (額外 nonzero)，比原矩陣還大。
  • 迭代法 (iterative)：若 A 為 positive-definite，可用 conjugate gradient。每次迭代猜 X、算 A·X + Y、看是否接近 0，再用梯度修正。與第 8 章 Stencil 的迭代解法相關。
• 迭代法最耗時的核心 = SpMV (Sparse Matrix-Vector multiplication and accumulation)：計算 A·X + Y，其中 A 稀疏、X 與 Y 為 dense vector。因重要性而有標準函式庫介面 SpMV。

五大設計考量 (The Five Design Considerations)

範例稀疏矩陣 (Fig. 14.1)：

        x0  x1  x2  x3
 eq0 [   1   7   .   . ]
 eq1 [   5   .   3   9 ]
 eq2 [   .   2   8   . ]
 eq3 [   .   .   .   6 ]
        ( . 代表 0 )

COO 格式與 SpMV (Coordinate List Format)

COO 把每個 nonzero 連同它的 row index 與 column index 各存一份，三個陣列同位置對應。

 index :  0   1   2   3   4   5   6   7
 value : [1   7   5   3   9   2   8   6]
 colIdx: [0   1   0   2   3   1   2   3]
 rowIdx: [0   0   1   1   1   2   2   3]
          \__r0_/ \___r1___/ \_r2_/ r3

• COO 完全移除所有 0 元素，但引入 colIdx、rowIdx 的 儲存負擔 (overhead)。
• 小矩陣時 overhead 可能 > 省下的空間；但 真正稀疏時 (如 1% nonzero)，COO 總量 ≈ 原始的 3%。

平行 SpMV/COO：一個 thread 處理一個 nonzero

__global__ void spmv_coo_kernel(COOMatrix cooMatrix, float* x, float* y) {
    unsigned int i = blockIdx.x * blockDim.x + threadIdx.x;   // 02 該 thread 的 nonzero 索引
    if (i < cooMatrix.numNonzeros) {                          // 03 邊界檢查
        unsigned int row = cooMatrix.rowIdx[i];               // 04
        unsigned int col = cooMatrix.colIdx[i];               // 05
        float value = cooMatrix.value[i];                     // 06
        atomicAdd(&y[row], x[col] * value);                   // 07 必須用 atomic!
    }
}

Thread → 資料映射 (注意 row 0 由 t0、t1 兩個 thread 共同貢獻)：

 thread:  t0  t1  t2  t3  t4  t5  t6  t7
 value :   1   7   5   3   9   2   8   6
 row   :   0   0   1   1   1   2   2   3
            \  /    \  |  /    \  /    |
   atomicAdd: y[0]    y[1]      y[2]  y[3]
   ^^^^^^^ t0,t1 同寫 y[0] → race → 需要 atomic

COO 在五大考量下：

CSR 格式與 SpMV (Compressed Sparse Row Format)

CSR 與 COO 一樣存 value 與 colIdx，但 nonzero 依 row 分組 (grouped by row)，並用 rowPtrs[] 取代 rowIdx[]：rowPtrs[r] = 第 r 個 row 的 nonzero 在 value/colIdx 中的起始 offset。

 index :  0   1   2   3   4   5   6   7
 value : [1   7 | 5   3   9 | 2   8 | 6]
 colIdx: [0   1 | 0   2   3 | 1   2 | 3]
 rowPtrs:[0       2           5       7   8]
          r0      r1          r2      r3  (end / 不存在的 row4)

• rowPtrs[r] 起始、rowPtrs[r+1] 結束 (exclusive)。例如 row1 = value[2..4]。
• rowPtrs[numRows] (此例 = 8) 多存一個「不存在 row 4」的起點 = 總 nonzero 數，方便界定最後一個 row 的結尾。
• row 內若依 colIdx 遞增排序，value 等同「去除所有 0 後的 row-major layout」(排序非必要，kernel 仍正確)。

平行 SpMV/CSR：一個 thread 處理一個 row

__global__ void spmv_csr_kernel(CSRMatrix csrMatrix, float* x, float* y) {
    unsigned int row = blockIdx.x * blockDim.x + threadIdx.x;   // 02 該 thread 負責的 row
    if (row < csrMatrix.numRows) {                              // 03 邊界檢查
        float sum = 0.0f;                                       // 04
        for (unsigned int i = csrMatrix.rowPtrs[row];           // 05 起點
                       i < csrMatrix.rowPtrs[row + 1]; ++i) {   // 06 終點 = 下一 row 起點
            unsigned int col = csrMatrix.colIdx[i];             // 07
            float value = csrMatrix.value[i];                   // 08
            sum += x[col] * value;                              // 09 區域累加
        }
        y[row] += sum;                                          // 11 無 atomic!
    }
}

Thread → row 映射 (每 thread 寫入 不同 y[row] → 不需 atomic)：

 t0 → row0: value[0..1]  →  y[0]
 t1 → row1: value[2..4]  →  y[1]
 t2 → row2: value[5..6]  →  y[2]
 t3 → row3: value[7]     →  y[3]   (各自獨立 → 無 race)

為何 CSR 非 coalesced？(strided access)

連續 thread 在同一迭代讀取的是「各 row 的起點」，彼此 相距很遠：

 iter 0:  t0→value[0]  t1→value[2]  t2→value[5]  t3→value[7]   (跳躍/strided)
 iter 1:  t0→value[1]  t1→value[3]  t2→value[6]  t3→ (已結束)
 iter 2:  t0→ done     t1→value[4]  t2→ done     t3→ done       ← divergence

對比 COO 同一迭代是 t0→value[0], t1→value[1], ... 連續 → coalesced。

CSR 在五大考量下：

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

Related Notes

• 14-Sparse-Matrix-Computation/02-Regularized-Formats-ELL-Hybrid-JDS
• 09-Parallel-Histogram/01-Atomic-Operations-and-Basic-Histogram
• 06-Performance-Considerations/01-Memory-Coalescing
• 04-Compute-Architecture-And-Scheduling/02-Warps-SIMD-and-Control-Divergence
• 11-Prefix-Sum-Scan/01-Scan-Foundations-and-Kogge-Stone
• 19-Parallel-Programming-And-Computational-Thinking/03-Problem-Decomposition-Output-vs-Input-Centric