併發設計練習題 (Practice - Designing Concurrent Code)

(1) 塊狀劃分(處理前切連續區塊):資料量事先已知、元素可獨立處理,如平行版 std::for_each;(2) 遞迴劃分:劃分依賴中間結果(如快速排序的 pivot 劃分),每層遞迴獨立可併發;(3) 按任務類型劃分:執行緒專職化(關注點分離),含管線 (pipeline)——適合輸入長度未知或需要穩定輸出節奏的場景。

fetch_add 是「讀-改-寫」操作,每次都要取得最新值:計數器所在的 cache line 所有權在處理器之間反覆搬移(快取乒乓),處理器彼此等待對方更新完成(高爭用)。記憶體順序參數不能消除快取一致性流量。mutex 迴圈同理——mutex 內部資料同樣要在核心間搬移。

不同執行緒存取互不相關的資料,但它們同住一條 cache line,line 所有權仍在處理器間反覆轉移——共享的是 cache line 而非資料,即偽共享。std::hardware_destructive_interference_size:不同執行緒資料的間隔下限hardware_constructive_interference_size:保證同住一條 line 的大小上限(靠攏提升單執行緒快取命中。

P = 1 / (fs + (1 - fs) / N),fs 為串行占比、N 為處理器數。N → ∞ 時 P → 1/fs;fs = 1/3 → 加速上限 3 倍,再多處理器也無濟於事。啟示:縮小串行部分與執行緒等待,或擴大問題規模讓並行部分做更多工作。

漏洞:工作執行緒拋異常無人捕捉 → std::terminate;主執行緒在生成執行緒後、join 前拋異常 → joinable 的 std::thread 解構 → std::terminate。改造:(1) std::packaged_task + std::future 把工作執行緒異常存進 future,get() 時重拋;(2) join_threads RAII 解構時保證全部 join;(3) std::async 遞迴對半劃分——future 解構會等待執行緒、get() 傳播異常,天然異常安全且不超額申請。

用 std::atomic<bool> done flag:每處理一個元素檢查一次;找到者先 promise.set_value() 再設 done flag,其他執行緒看到即返回。值不在範圍內時 promise 永遠不會被設定,get() 會永久等待——必須先 join 全部執行緒、檢查 done flag,未設定則回傳 last。

兩者每執行緒同樣輸出 10,000 個元素。按行劃分(每執行緒 10 整行):讀第二矩陣全部 1,000,000 + 第一矩陣 10 行 10,000 ≈ 1,010,000。按塊劃分(100×100 子矩陣):第一矩陣 100 行 + 第二矩陣 100 列 = 200,000,約 1/5 → 快取缺失大幅減少,選塊狀劃分;塊大小可在執行期依矩陣大小與處理器數調整,並在目標架構上實測。

這是用多執行緒隱藏延遲:掃描受 I/O 限制,多開幾條掃描執行緒用 CPU 空檔處理已載入的檔案;或改用非同步 I/O,等待期間做其他工作。注意執行緒過多會反轉為超額申請(任務切換 + 快取壓力),所以改動前後都要實測效能。

逐段傳播:各塊獨立求和後把前塊末值傳給下塊(先更新末元素、set promise 讓下塊開工,再補其餘元素);每執行緒 ~N/k 運算 + N/k 傳遞,總量 O(N),適合處理器少、元素多;異常經 promise 傳遞,是異常安全的;不能用 std::async(任務中途要互等,必須全部真正並行)。2 的冪距離:stride 每步翻倍,log₂N 步、總量 O(N log N),適合大規模並行(每處理器每步處理一個元素);需要 barrier 全體同步 + 雙緩衝避免競爭;書中版本非異常安全(拋異常即 terminate),需 promise 或 mutex 保護的 exception_ptr 修補。

(a) 不中斷則每條執行緒把自己整塊掃完,可能比串行還慢(串行找到即停);done flag 讓其他執行緒提前返回,代價是每次迭代 load 原子變數。(b) promise = 第一個結果或異常勝出、全部停止,行為最接近 std::find;packaged_task 則各自存異常、其他執行緒繼續找。多執行緒同時 set 是良性競爭,先到者作為「第一個」。(c) 平行版不保證回傳最前面的匹配——可能回傳範圍後段的元素;順序語義是平行化的犧牲品,也印證「元素可獨立處理」是演算法能平行化的必要屬性。