優化清單與效能瓶頸 (Optimization Checklist & Bottlenecks)

#memory-and-performance #optimization-checklist #performance-bottleneck #occupancy #thread-coarsening

重點總覽 (Overview)

本節將本書第一部分(Ch.2–6)學到的優化手法整合成一張清單 (checklist),並強調一個核心原則:所有優化本質上都是「用一種資源換另一種資源」,因此必須先找出限制效能的瓶頸資源 (bottleneck),否則優化可能無效甚至有害。

項目	重點
清單包含幾項優化	6 項通用優化(非窮舉)
優化的本質	增加 resource A 的使用量,以減輕 resource B 的壓力
何時有益	被緩解的資源是「瓶頸」,且被加重的資源不會反過來限制平行執行
優化失敗的情形	沒打中瓶頸 → 無效;加重了真正的瓶頸 → 反而變慢
找瓶頸的工具	profiling tools(如 NVIDIA Nsight / profiler)
瓶頸的特性	hardware-specific,同一程式在不同 GPU 上瓶頸可能不同

Important

沒有先理解瓶頸就調效能,等於是猜測 (guesswork)。合理的策略「可能」有效也「可能」無效。

六大優化清單 (A Checklist of Optimizations)

每一項優化都從兩個角度帶來好處:對運算核心 (compute cores) 與對記憶體 (memory);並各自有對應的施作策略 (strategies)。

#	優化	對 compute cores 的好處	對 memory 的好處	主要策略	詳見章節
1	Maximizing occupancy	更多 work 可隱藏 pipeline latency	更多平行記憶體存取可隱藏 DRAM latency	調 threads/block、shared mem/block、registers/thread	Ch.4 / Ch.5
2	Coalesced global memory accesses	較少因等待 global memory 而 pipeline stall	減少 global memory traffic、善用 bursts / cache lines	corner turning;重排 thread→data 映射;重排 data layout	Ch.6 / Ch.12 / Ch.13 / Ch.14
3	Minimizing control divergence	高 SIMD efficiency(SIMD 執行時閒置核心更少)	—	重排 work/data 分配,使同 warp 工作量相近	Ch.10 / Ch.11 / Ch.15 / Ch.14
4	Tiling of reused data	較少因等待 global memory 而 pipeline stall	減少 global memory traffic	把 block 內重複用的資料放進 shared memory / registers,只搬一次	Ch.5 / Ch.7 / Ch.8
5	Privatization	較少因等待 atomic update 而 pipeline stall	減少 atomic update 的爭用與序列化	對私有副本做局部更新,結束時再合併回公用副本	Ch.9 / Ch.15
6	Thread coarsening	減少多餘的 work / divergence / synchronization	減少多餘的 global memory traffic	一個 thread 負責多個 work 單元,降低「平行的代價」	Ch.6 / Ch.8 / Ch.9 / Ch.10–13

Tip

這六項是跨應用通用的優化,程式設計師應「優先考慮」。但清單不是窮舉;特定 pattern 還有專屬手法,例如 Ch.7 的 constant memory、Ch.10 的 double-buffering。

各項優化的「策略細節」速記

Coalescing(不規則存取時)三策略:
1. 先以 coalesced 方式把資料搬進 shared memory,再在 shared memory 做不規則存取(例:corner turning,以及 Ch.12 Merge 的協作 binary search)。
2. 重排 thread→data 的映射(例:Ch.10 Reduction)。
3. 重排 data 本身的 layout(例:Ch.14 的 ELL / JDS 格式)。
Tiling 進階觀察:tile 不一定放 shared memory,也可放 registers(Ch.8 Stencil 的 register tiling);input/output tile 維度不同時 tiling 會更難(Ch.7/Ch.8);output 也可被 tile,不限 input。
Thread coarsening 的「代價」因 pattern 而異:Ch.6 減少重複載入 input tile;Ch.9 減少 private copy 的 commit 次數;Ch.10/11 減少 synchronization 與 divergence;Ch.11 額外減少 work 冗餘;Ch.12 減少 binary search 次數;Ch.13 改善 coalescing。

Warning

Privatization 在本章僅「為完整性提及」,正式介紹在 Ch.9 Parallel Histogram。Thread coarsening 不是萬靈丹:若沒有「平行的代價」(如 vector add、RGB→grayscale)就施作,不會有明顯效益(見 sibling note 03)。

用一資源換另一資源 (The Resource-Tradeoff Principle)

         優化前                              優化後
   ┌────────────────┐                 ┌────────────────┐
   │ resource A ████ │  ← 瓶頸          │ resource A ██   │  壓力下降 ✔
   │ resource B ██   │                 │ resource B ███  │  使用上升
   └────────────────┘                 └────────────────┘

  規則:只有當「被緩解的 A 是真正瓶頸」
        且「被加重的 B 不會反過來限制平行執行」時,優化才有效。

「以多用一種資源 → 換取少用另一種資源」是所有清單項目的共同模式。
例:shared memory tiling = 多用 shared memory,以減輕 global memory bandwidth 壓力。
- 當瓶頸是 global memory bandwidth 且資料會被重用 → 效果極佳。
- 但若效能其實是被 occupancy 限制,而 occupancy 又已被「用太多 shared memory」卡住 → 再加 tiling 反而更糟。

找出計算的瓶頸 (Knowing Your Computation's Bottleneck)

決定要施作哪一項優化前,必先確認哪個資源在限制效能(= performance bottleneck)。

            ┌─────────────────────────────┐
            │  用 profiler 找出瓶頸資源     │
            └──────────────┬──────────────┘
                           │
        ┌──────────────────┼───────────────────┐
        ▼                  ▼                    ▼
  memory-bound        compute-bound         latency / occupancy
 (bandwidth 飽和)     (SIMD/算力飽和)       (執行緒不足以藏延遲)
        │                  │                    │
  coalescing /        minimize divergence /  maximize occupancy /
  tiling /            algorithm change       coarsening(調 register/
  coarsening                                 shared mem 不傷 occupancy)

判斷 memory-bound 與 compute-bound 可用算術強度 (arithmetic intensity):

Arithmetic Intensity = 計算運算數 / 自 global memory 讀取的位元組數 (OP/B)
與裝置的「算力 ÷ 頻寬」比值(roofline 的 ridge point)比較:OP/B 偏低 → memory-bound;偏高 → compute-bound。
範例(matmul 內層每次:1 mul + 1 add = 2 FLOP,讀 2 個 float = 8 B):
- 無優化 simple kernel:2 / 8 = 0.25 OP/B(嚴重 memory-bound)。
- tile 32×32 的 tiled kernel:資料重用 ~32 倍 → ≈ 0.25 × 32 = 8 OP/B。

Warning

瓶頸是 hardware-specific 的:同一份程式在不同 GPU 上,因算力/頻寬/快取差異,瓶頸可能不同。因此找瓶頸與調效能都需要對 GPU 架構及不同裝置差異有良好理解。

Tip

若施作的優化沒打中瓶頸資源,最好的情況是「沒有效益」,壞的情況是「反而傷害效能」。先 profile,再優化。

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

情境 / 關鍵字	答案 / 技巧
清單上有哪 6 項優化?	maximize occupancy、coalescing、minimize control divergence、tiling、privatization、thread coarsening
哪項優化「對 compute core 沒有列出好處」(只利 memory)?	表中 minimize control divergence 偏 compute(高 SIMD efficiency);純利 memory 的是 coalescing 的 traffic 面向 — 注意「benefit to compute / memory」兩欄要分開記
優化的本質是什麼?	用一種資源換另一種資源;只在「被緩解者是瓶頸」時有效
為何 occupancy 同時藏 pipeline 與 DRAM latency?	夠多 threads → 既有 work 填 pipeline,也產生足量平行記憶體存取填滿 bandwidth
應用不規則存取,如何達成 coalescing?	三策略:搬進 shared mem 再亂存取(corner turning)、重排 thread→data 映射、重排 data layout(ELL/JDS)
shared memory tiling 何時反而變慢?	當瓶頸是 occupancy 且 occupancy 已被 shared memory 用量卡住時
如何分辨 memory-bound vs compute-bound?	算 arithmetic intensity (OP/B),與裝置 compute/bandwidth 比值(roofline ridge)比較
simple matmul 的 OP/B?	0.25 OP/B(2 FLOP / 8 bytes)
找瓶頸用什麼?	profiling tools(NVIDIA profiler / Nsight)
為何同程式在不同 GPU 要重調?	瓶頸是 hardware-specific
privatization 正式在哪章介紹?	Ch.9 Parallel Histogram(本章僅提及)

重點總覽 (Overview)

六大優化清單 (A Checklist of Optimizations)

各項優化的「策略細節」速記

用一資源換另一資源 (The Resource-Tradeoff Principle)

找出計算的瓶頸 (Knowing Your Computation's Bottleneck)

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

Related Notes