凝集化#
問題
並列処理は細粒度であるため、並列スケジュールや通信のオーバーヘッドが有用なワークを圧迫してしまいます。
コンテキスト
多くのアルゴリズムでは、タスクごとに数命令程度の非常に細粒度の並列処理が可能です。しかし、スレッド間の同期には通常、桁違いに多くのサイクルが必要になります。例えば、2 つの配列要素ごとの加算は完全に並列に実行できますが、各スカラーの加算が個別のタスクとしてスケジュールされている場合、ほとんどの時間は加算ではなく同期の実行に費やされます。
強制
個々の計算は並列に実行できますが、小さくなります。oneAPI スレッディング・ビルディング・ブロック (oneTBB) の実際の使用では、ここでの「小さい」とは 10,000 クロックサイクル未満を意味します。
並列処理はパフォーマンスが目的であり、意味上の理由では必須でありません。
解決方法
計算をブロックにグループ化します。ブロック内の計算を順番に評価します。
ブロックサイズは、並列オーバーヘッドを償却できるように十分大きくする必要があります。ブロックサイズが大きすぎると、ブロック数が少なくなりすぎてプロセッサー間でワークを均等に分散できなくなり、並列処理や負荷分散が制限される可能性があります。
ブロック化のトポロジー選択は、通常、次の 2 つの考慮事項によって決定されます。
ブロック間の同期を最小限に抑えます。
ブロック間のキャッシュ・トラフィックを最小限に抑えます。
計算が完全に独立している場合、ブロックも独立しており、キャッシュ・トラフィックの問題だけを考慮します。
10,000 クロックサイクル未満の「小さい」ループの場合、最適な凝集は単一のブロックになる可能性があるため、並列化は全く実用的ではない可能性があります。
例
range 引数を受け取る oneapi::tbb::parallel_for などの TBB ループ・テンプレートは、自動凝集をサポートします。
凝集するときは、キャッシュ効果を考慮してください。可能であれば、キャッシュラインがグループ間で交差しないようにします。
境界と内部の比率の影響を受ける可能性があります。例えば、計算が 2D グリッドを形成し、最も近い隣接ブロックとのみ通信する場合、ブロックあたりの計算は 2 次的に (ブロックの面積とともに) 増加しますが、ブロック間の通信は線形的に (ブロックの周囲とともに) 増加します。次の図は、8×8 グリッドを集約する 4 つの異なる方法を示しています。このような解析を行う場合、情報がキャッシュライン単位で転送されることを考慮してください。特定の領域では、ブロックが論理グリッドに対して正方形ではなく、基礎となるキャッシュラインのグリッドに対して正方形であると周囲が最小化されることがあります。
8×8 グリッドの 4 つの異なる集合。 
ベクトル化も検討してください。長く連続したデータのサブセットを含むブロックでは、ベクトル化が適切である可能性があります。
再帰計算の場合、ほとんどのワークは末端に対して行われるため、解決策は、次の図に示すように、サブツリーをグループとして扱うことです。
再帰計算の凝集 
多くの場合、このような凝集は、しきい値に達すると、連続的に再帰することで実現されます。例えば、再帰ソートでは、特定のしきい値を超えた場合にのみ部分問題を並列に解くようにします。
リファレンス
Ian Foster 氏は、著書『Designing and Building Parallel Programs』（http://www.mcs.anl.gov/~itf/dbpp）の中で、「凝集」という用語を導入しました。この凝集は、4 段階の PCAM 設計方法の一部です。
パーティショニング (P) - プログラムを可能な限り小さなタスクに分割します。
コミュニケーション (C) - タスク間でどのような通信が必要か把握します。oneTBB では、通信は通常、キャッシュ ライン転送になります。これらは自動で行われますが、タスク間でどのアクションが発生するか理解しておくと、凝集ステップをガイドするのに役立ちます。
凝集 (A) – タスクをより大きなタスクに結合します。Ian Foster 氏の書籍には、一読の価値がある広範の考察リストが掲載されています。
マッピング (M) – タスクをプロセッサーにマップします。oneTBB のタスク・スケジューラーがこのステップを実行します。