yohhoyの日記

技術的メモをしていきたい日記

C++1yへの並列アルゴリズムライブラリ提案

C++1yに向けた並列プログラミングモデルについてメモ。(PDF)N3429 A C++ Library Solution to Parallelismにて、いくつか並列アルゴリズムの追加提案がなされている(言語コア機能の拡張提案は含まない)。初期提案のため概要レベル。

2021-03-17追記:Thrustライブラリベースの並列アルゴリズムISO/IEC TS 19570:2015(通称 Parallelism TS)として標準化され、その後P0024R2採択によりC++17標準ライブラリへと統合された。

これら並列アルゴリズム群は Intel TBB(Threading Building Blocks) および Microsoft PPL(Parallel Pattern Library) の共通サブセットから構成されており、それぞれに対応する逐次処理版のアルゴリズムまたは言語コア機能が存在する。

アルゴリズム 並列処理版 逐次処理版
関数呼び出し parallel_invoke (関数呼び出し)
反復/index parallel_for (for文)
反復/iterator parallel_for_each std::for_each
変換操作 parallel_transform std::transform
還元操作*1 parallel_reduce std::accumulate
ソート(unstable) parallel_sort std::sort

この提案(およびTBB、PPL)における並列アルゴリズムの機能設計として、実際にどのように並列処理するかは処理系依存であることに注意*2。従来の逐次アルゴリズムは逐次実行セマンティクスを持つと定義されており、ハードウェア並列性を活用することが出来なかった(Ex.シングルスレッド実行)。一方の並列アルゴリズムは任意に並列実行され得るとセマンティクス定義しておくことで、さまざまなマルチコア環境において高効率な並列処理を実現できる。

メモ:同種のアプローチとしてThrustライブラリベースの(PDF)N3408 Parallelizing The Standard Algorithms Libraryも提案されている。N3429/TBB/PPLは複数CPU上での粗粒度タスク/データ並列を目指しているが、N3408/ThrustはGPGPU上での(超)細粒度データ並列を目指している模様。

関連URL

*1:parallel_reduce 並列アルゴリズムは std::accumelate 逐次アルゴリズムと良く似ているが、一部要件が異なるため parallel_accmulate という名前を避けている。

*2:N3429 Design Decisionsより引用:"One principal design decision is that parallelism is optional. An implementation is free to engage in sequential execution."