GCC は、私のお気に入りの C++17 機能である標準テンプレート ライブラリ (STL) の並列アルゴリズムをサポートしています。私は数日前にこれに気づきました。喜んで記事を書き、熱意を分かち合いたいと思います.
Microsoft コンパイラは、最初から並列アルゴリズムをサポートしていますが、残念ながら GCC も Clang もサポートしていません。 GCC 9以降、並列アルゴリズムを使用できるようになったため、正確に言う必要があります。次回の投稿でパフォーマンスの数値を示す例を紹介する前に、STL の並列アルゴリズムについて書き、必要な情報を提供したいと思います。
標準テンプレート ライブラリの並列アルゴリズム
標準テンプレート ライブラリには、範囲とその要素を検索、カウント、および操作するための 100 を超えるアルゴリズムがあります。 C++17 では、そのうち 69 個が新しいオーバーロードを取得し、新しいオーバーロードが追加されています。オーバーロードされた新しいアルゴリズムは、いわゆる実行ポリシーで呼び出すことができます。実行ポリシーを使用して、アルゴリズムを順次実行するか、並列で実行するか、ベクトル化と並行して実行するかを指定できます。実行ポリシーを使用するには、ヘッダー <execution>
を含める必要があります .
実行ポリシー
C++17 標準では、次の 3 つの実行ポリシーが定義されています。std::execution::sequenced_policy
std::execution::parallel_policy
std::execution::parallel_unsequenced_policy
対応するポリシー タグは、プログラムを順次実行するか、並列で実行するか、ベクトル化と並行して実行するかを指定します。
std::execution::seq
:プログラムを順番に実行します
std::execution::par
:プログラムを複数のスレッドで並行して実行します
std::execution::par_unseq
:プログラムを複数のスレッドで並行して実行し、個々のループのインターリーブを許可します。 SIMD (S イングル私 指示 M 複数 D アタ)
実行ポリシーの使い方
std::execution::par
または std::execution::par_unseq
アルゴリズムを並列または並列でベクトル化して実行できます。このポリシーは許可であり、要件ではありません。
次のコード スニペットは、すべての実行ポリシーを適用します。
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // standard sequential sort std::sort(v.begin(), v.end()); // (1) // sequential execution std::sort(std::execution::seq, v.begin(), v.end()); // (2) // permitting parallel execution std::sort(std::execution::par, v.begin(), v.end()); // (3) // permitting parallel and vectorized execution std::sort(std::execution::par_unseq, v.begin(), v.end()); // (4)
この例は、
std::sort
の従来のバリアントを引き続き使用できることを示しています。 (4)。さらに、C++17 では、順次 (2)、並列 (3)、または並列およびベクトル化 (4) バージョンを使用するかどうかを明示的に指定できます。 並列およびベクトル化された実行
アルゴリズムが並列でベクトル化された方法で実行されるかどうかは、多くの要因に依存します。たとえば、CPU とオペレーティング システムが SIMD 命令をサポートしているかどうかによって異なります。さらに、コードの変換に使用したコンパイラと最適化レベルにも依存します。次の例は、ベクトルを埋める単純なループを示しています。
const int SIZE = 8; int vec[] = {1, 2, 3, 4, 5, 6, 7, 8}; int res[] = {0, 0, 0, 0, 0, 0, 0, 0}; int main() { for (int i = 0; i < SIZE; ++i) { res[i] = vec[i]+5; } }
式 res[i] = vec[i] + 5
この小さな例の重要な行です。 Compiler Explorer のおかげで、clang 3.6 によって生成されたアセンブラー命令を詳しく調べることができます。
最適化なし
アセンブラの説明はこちら。各追加は順番に行われます。
最大最適化あり
最高の最適化レベル -O3、xmm0
などの特殊レジスターを使用する 128 ビットまたは 4 つの整数を保持できるものが使用されます。この特別なレジスタは、加算がベクトルの 4 つの要素で並列に行われることを意味します。
実行ポリシーのないアルゴリズムのオーバーロードと、逐次実行ポリシーのアルゴリズムのオーバーロード std::execution::seq
例外という 1 つの側面で異なります。
例外
実行ポリシーのあるアルゴリズムの使用中に例外が発生した場合、std::terminate
std::terminate
が呼び出されます。 インストールされたstd::terminate_handler
を呼び出します .その結果、デフォルトの std::abort
ごとに が呼び出され、プログラムが異常終了します。例外の処理は、実行ポリシーのないアルゴリズムの呼び出しと、シーケンシャルな std::execution::seq
を持つアルゴリズムの違いです。 実行ポリシー。実行ポリシーなしでアルゴリズムを呼び出すと、例外が伝播されるため、例外を処理できます。
C++17 では、69 の STL アルゴリズムが新しいオーバーロードを取得し、新しいアルゴリズムが追加されました。
アルゴリズム
並列化されたバージョンの 69 のアルゴリズムは次のとおりです。
新しいアルゴリズム
並列実行用に設計された C++17 の新しいアルゴリズムは、std
にあります。 名前空間であり、ヘッダー <numeric>
が必要です .
std::exclusive_scan:
範囲の i 番目 (排他的) 要素まで、呼び出し可能なバイナリを左から適用します。 callable の左の引数は前の結果です。中間結果を保存します。std::inclusive_scan
:左から範囲の i 番目 (両端を含む) の要素までバイナリ呼び出し可能を適用します。 callable の左の引数は前の結果です。中間結果を保存します。std::transform_exclusive_scan
:最初に単項 callable を範囲に適用し、次にstd::exclusive_scan
を適用します .std::transform_inclusive_scan
:最初に単項 callable を範囲に適用し、次にstd::inclusive_scan
を適用します .std::reduce
:バイナリ callable を範囲に適用します。std::transform_reduce
:最初に単項呼び出し可能オブジェクトを 1 つに適用するか、バイナリ呼び出し可能オブジェクトを 2 つの範囲に適用し、次にstd::reduce
を適用します。 結果の範囲に。
確かに、この説明は簡単には理解できませんが、すでに std::accumulat
を知っているなら e と std::partial_sum
、reduce と scan のバリエーションはよく知られているはずです。 std::reduce
std::accumulate への並列ペンダントであり、並列ペンダントを partial_sum にスキャンします。並列実行が std::reduce
の理由です 連想的で交換可能な callable が必要です。対応するステートメントは、partial_sum のバリエーションとは対照的に、スキャンのバリエーションに当てはまります。詳細については、cppreferenc.com/algorithm にアクセスしてください。
なぜ std::reduce
が必要なのか不思議に思うかもしれません すでに std::accumulate
があるため、並列実行用 .その理由は std::accumulate
並列化できない順序で要素を処理します。
std::accumulate
対 std::reduce
while std::accumulate
その要素を左から右に処理します std::reduce
任意の順序で行います。 std::accumulate
を使用した小さなコード スニペットから始めましょう。 と std::reduce
. callable はラムダ関数 [](int a, int b){ return a * b; }
です .
std::vector<int> v{1, 2, 3, 4}; std::accumulate(v.begin(), v.end(), 1, [](int a, int b){ return a * b; }); std::reduce(std::execution::par, v.begin(), v.end(), 1 , [](int a, int b){ return a * b; });
次の 2 つのグラフは、 std::accumulate
のさまざまな処理戦略を示しています。 と std::reduce
.
std::accumulate
左から開始し、二項演算子を連続して適用します。
- 逆に
std::reduce
二項演算子を非決定的な方法で適用します。
callable の連想性により、 std::reduce
要素の任意の隣接ペアに縮小ステップを適用するアルゴリズム。可換性のおかげで、中間結果は任意の順序で計算できます。
次は?
約束どおり、次回の投稿では STL の並列アルゴリズムを使用し、Microsoft コンパイラと GCC のパフォーマンス数値を提供します。
Stephan Roth の書籍「Clean C++20」が当たるクーポン 5 枚
Stephan Roth の書籍「Clean C++20」の発行者 Apress が後援する 5 枚のバウチャーを差し上げます。入手方法はこちら:https://bit.ly/StephanRoth.