Enter your search text in the box above

Select a result to preview

執行緒間劃分工作 (Dividing Work Between Threads)

#cpp-concurrency #concept #concurrent-design #data-partitioning

Overview Table

劃分策略 前提 適用情境 代表範例
塊狀劃分(處理前劃分) 資料量事先已知 元素可獨立處理、操作相同 平行版 std::for_each、parallel_accumulate
遞迴劃分 處理過程中才知道如何分 遞迴演算法、劃分依賴中間結果 平行快速排序(代碼 8.1)
按任務類型劃分 工作性質不同 資料長度未知、事件驅動、多階段處理 管線 (pipeline)、GUI 事件執行緒

處理開始前的資料劃分(塊狀劃分)

最簡單的平行化方式:資料量已知時,開始處理前就把資料切成連續區塊,每個執行緒分得一塊,各自獨立處理、互不溝通,最後由主執行緒合併結果(MPI/OpenMP 的典型結構)。

資料: [ e0 e1 e2 e3 | e4 e5 e6 e7 | e8 e9 e10 e11 | e12 ... ]
          執行緒 1        執行緒 2        執行緒 3       主執行緒
          ↓ 獨立處理      ↓ 獨立處理      ↓ 獨立處理      ↓
          └───────────────┴──── 主執行緒合併結果 ────┴──────┘
適用限制

塊狀劃分要求事先知道資料長度且能整齊切割。若只有處理過資料後才知道怎麼分(如快速排序),或資料是動態產生/外部輸入,此法不適用,需改用遞迴劃分或按任務類型劃分。

遞迴劃分(平行快速排序)

快速排序先以中樞 (pivot) 把資料分成前後兩半,再對兩半遞迴排序——劃分結果依賴前一步的處理,無法事前切塊。但每層遞迴的兩半存取的是不同資料集、完全獨立,天然適合平行:

              [ 全部資料 ]
              /          \
       [ < pivot ]     [ >= pivot ]   ← 劃分後才知道兩半內容
        /      \         /      \
     [...]   [...]    [...]   [...]   ← 每層遞迴皆可併發執行

代碼 8.1 的改良:限制執行緒數量 + 以執行緒安全堆疊 (thread-safe stack) 分派工作:

// sorter<T> 核心思路(節錄)
thread_safe_stack<chunk_to_sort> chunks;   // 待排序資料塊(含 promise)
unsigned const max_thread_count =
    std::thread::hardware_concurrency() - 1;  // 上限:硬體執行緒數
std::atomic<bool> end_of_data;             // 析構時設為 true,結束工作迴圈

// do_sort: 劃分後把「小於 pivot 的一半」推上堆疊,
// 若執行緒未達上限就再開新執行緒;等待結果期間
// 呼叫 try_sort_chunk() 幫忙處理堆疊上的資料塊(不空等)
代價

所有執行緒都存取同一個堆疊,重度爭用會降低效能;工作清單的爭用問題與改良(工作竊取等)見第 9 章。此外此版即使資料已不需要排序,閒置執行緒仍會持續嘗試取工作。

按任務類型劃分

前兩種方式中每個執行緒做相同的事、不同的資料;另一種選擇是讓執行緒專職化——各做不同種類的工作(如同水電工與電工各司其職),即關注點分離 (separation of concerns)。

兩個危險訊號

若劃分後執行緒間共享大量資料或頻繁互相等待,代表交互太密切、關注點沒分乾淨。應檢討:交互都指向同一來源 → 抽成單一執行緒負責;兩個執行緒總在密集交流 → 乾脆合併為一個執行緒。

劃分任務序列:管線 (pipeline)

同一組操作序列要套用到多個獨立資料項、且輸入長度未知(網路串流、掃描檔案系統)時,可為每個階段建一個執行緒,資料處理完丟入佇列交給下一階段:

資料流 → [階段1|執行緒A] →佇列→ [階段2|執行緒B] →佇列→ [階段3|執行緒C] → 輸出
          資料項 i 在階段2 時,階段1 已可同時處理資料項 i+1

塊狀劃分 vs 管線(20 個資料項、4 核、每項 4 步驟 × 每步 3 秒):

方式 全部完成時間 輸出節奏
塊狀劃分(4 執行緒各處理 5 項) 60 秒 每 12 秒一次湧出 4 項(突發)
管線(4 階段各佔 1 核) 69 秒(最末核閒置等待 9 秒才開工) 啟動延遲 12 秒後,每 3 秒穩定產出 1 項
管線的價值在「平滑輸出」

管線總時間反而較長(末端階段有啟動延遲),但輸出均勻穩定。高清影片播放需要穩定 ≥25 幀/秒:能「1 秒解 100 幀然後停 1 秒」的程式毫無用處,觀眾卻能接受片頭延遲——管線正好給出穩定解碼率。

Exam/Test Patterns

情境/關鍵字 答案
「資料量已知、元素獨立、操作相同」 塊狀劃分(處理前切連續區塊,主執行緒合併)
「快速排序如何平行化」 遞迴劃分:pivot 劃分後兩半獨立,可併發;每層可用 std::async
「遞迴劃分執行緒數量爆炸」 以 hardware_concurrency() 限制上限 + 執行緒安全堆疊存放待處理塊;等待時幫忙取塊處理
「代碼 8.1 的 sorter 本質是什麼」 執行緒池雛形:所有執行緒從同一清單取任務(爭用問題見第 9 章)
「輸入長度未知/資料來自網路」 管線 (pipeline) 或按任務類型劃分,不能用塊狀劃分
「需要穩定輸出節奏(如影片 25fps)」 管線:啟動延遲後每階段時間產出一項,輸出平滑
「執行緒間共享大量資料、頻繁互等」 關注點沒分乾淨 → 重新劃分、合併交互密切的執行緒