執行策略 (Execution Policies)

Overview Table

10.1 C++17 平行化標準庫演算法總覽

C++17 為標準庫加入平行演算法:並非新演算法,而是對既有演算法(如 std::find、std::transform、std::reduce)的重載。簽名與單執行緒版本相同,只在參數列表最前面新增一個執行策略參數:

std::vector<int> my_data;
std::sortpar, my_data.begin(), my_data.end();

• std::execution::par 表示允許以多執行緒執行;實作仍可以串行方式執行(策略是許可,不是保證)。
• 指定執行策略後,演算法的複雜度要求比串行版寬鬆:平行演算法為了利用平行性通常會做更多總工作量——若能分攤到 100 個處理器,即使總工作量是原來的 2 倍,仍可獲得約 50 倍加速。

10.2 三種標準執行策略(比較表)

三個策略類別定義在 <execution> 標頭檔,並各自對應一個可直接傳入演算法的策略物件:

seq       : T0: [op1]──[op2]──[op3]──[op4]        單執行緒、不交錯、順序未指定
par       : T0: [op1]──[op3]    T1: [op2]──[op4]  多執行緒;單一操作不跨執行緒
par_unseq : T0: [op1a op2a op1b ...]  T1: [op2b ...]
            操作可交錯、可在執行緒間遷移

10.2.1 執行策略對演算法行為的三大影響

影響一:演算法複雜度

• 除了平行管理的排程開銷外,核心操作(交換、比較、使用者提供的函式物件)可能被執行更多次,以換取總執行時間縮短。
• 帶策略重載的操作次數可能是無策略版本的數倍;倍數取決於庫實作與平台,而非傳入的資料。

影響二:異常時的行為

• 執行期間若有異常未被捕獲而逃逸,所有標準執行策略都會呼叫 std::terminate,直接終止程式。
• 使用標準策略時演算法唯一會拋出的異常是 std::bad_alloc——當標準庫無法為內部操作取得足夠資源時。
• 對比:無執行策略的版本會正常傳播異常。

std::for_each(v.begin(), v.end(),
  [](auto x){ throw my_exception(); });   // 異常向外傳播
std::for_eachseq, v.begin(), v.end(,
  [](auto x){ throw my_exception(); });   // std::terminate!

影響三:執行的位置與時間

• 這是各標準策略間根本的差異:策略指定用哪些代理 (agent) 執行演算法——普通執行緒、向量流、GPU 執行緒等。
• 策略也約束演算法步驟的安排:是否按特定順序、步驟間能否交錯、能否彼此平行。

10.2.2 順序策略的陷阱:順序仍未指定

seq 強制所有操作在同一執行緒上、不交錯地執行,但造訪元素的具體順序未指定,且不同呼叫間可能不同:

std::vector<int> v(1000);
int count = 0;
std::for_eachseq, v.begin(), v.end(,
  [&](int& x){ x = ++count; });   // 不保證 v 是 1..1000 依序排列!

Exam/Test Patterns

Related Notes

• 10-Parallel-Algorithms/02-Using-Parallel-Algorithms
• 10-Parallel-Algorithms/Practice-Parallel-Algorithms
• 08-Designing-Concurrent-Code/05-Parallel-Algorithm-Case-Studies
• 03-Sharing-Data/01-Race-Conditions-and-Mutexes
• 05-Memory-Model-and-Atomics/02-Atomic-Types-and-Operations