GCC コンパイラを使用した STL の並列アルゴリズム

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.


No