Loading article…
通信回避アルゴリズムは、メモリ階層内でのデータの移動を最小限に抑えることで、実行時間とエネルギー消費を改善します。これらのアルゴリズムは、演算と通信という2つのコスト（時間とエネルギーの観点から）の合計を最小限に抑えます。この文脈における通信とは、メモリレベル間、またはネットワークを介した複数のプロセッサ間でデータを移動することを指します。これは演算よりもはるかにコストがかかります。[ 1 ]
通信回避アルゴリズムの解析においてよく用いられる計算モデルの一つに、2段階メモリモデルがある。
[ 2 ]系6.2:
定理—与えられた行列サイズの、 それからコミュニケーションの複雑さがある。
この下限値は、タイル行列乗算によって達成可能です。
その他の数値線形代数演算に関するより一般的な結果は、[ 3 ]に記載されています。以下の証明は[ 4 ]からのものです。
計算グラフを描くことができます格子点の立方体として、各点は次の形式である。。 以来コンピューティングプロセッサが立方体内の各点に少なくとも一度はアクセスする必要がある。したがって、問題は、最小限の通信量で格子点を構成する。
もしが大きい場合は、単純にすべてをロードできますエントリを書きますエントリー。これは面白くない。
もしが小さい場合、最小通信アルゴリズムを個別のセグメントに分割できます。各セグメントでは、正確に次の処理を実行します。キャッシュへの読み込み、およびキャッシュからの任意の数の書き込み。
各セグメント中、プロセッサは最大で異なるポイントから。
させてこの区間でカバーされる格子点の集合をとする。すると、ルーミス・ホイットニーの不等式により、
制約付き。
算術平均と幾何平均の不等式により、極値は、。
したがって、算術強度は以下によって上限が定められる。どこしたがって、通信は以下によって制限される。。
直接計算により、タイル行列乗算アルゴリズムが下限値に到達することが検証される。
次の実行時間モデルを考えてみましょう: [ 5 ]
⇒ 総実行時間 = γ·( FLOPs数) + β·(ワード数)
時間とエネルギーで測定した場合、β >> γであることから、通信コストが計算コストを支配していることがわかります。技術動向[ 6 ]によると、クラウドコンピューティングからスーパーコンピュータ、モバイルデバイスまで、さまざまなプラットフォームで通信の相対コストが増加しています。また、このレポートでは、プロセッサと DRAM の電力使用量のバランスを取るために、今後 10 年間でDRAMアクセス時間と FLOPsの間のギャップが 100 倍に拡大すると予測しています。[ 1 ]
メモリ階層の上位に行くほど、エネルギー消費量は桁違いに増加する。[ 7 ]
アメリカ合衆国大統領バラク・オバマは、 2012会計年度のエネルギー省予算要求で、通信回避アルゴリズムを議会に提出した。[ 1 ]
新アルゴリズムにより、超大規模コンピューティングシステムにおける性能と精度が向上。現代のコンピュータアーキテクチャでは、プロセッサ間の通信に、特定のプロセッサによる浮動小数点演算の処理時間よりも長い時間がかかります。ASCRの研究者らは、一般的に使用されている線形代数手法を基に、アルゴリズム内で指定される通信パターンを再定式化することで、プロセッサとメモリ階層間の通信を最小限に抑える新しい手法を開発しました。この手法は、世界中の研究者が大規模で複雑なマルチフィジックス問題を解決するための機能を提供する、高く評価されているソフトウェアスイートであるTRILINOSフレームワークに実装されています。
通信回避アルゴリズムは、以下の目的で設計されています。
次の簡単な例[ 1 ]は、これらがどのように実現されるかを示しています。
A、B、Cをn × nの正方行列とする。以下の単純なアルゴリズムは、C = C + A * B を実現する。
i = 1 から n まで j = 1 から n まで k = 1 から n まで C(i,j) = C(i,j) + A(i,k) * B(k,j)
算術コスト（時間計算量）：nが十分に大きい場合はn 2（2 n − 1）またはO（n 3）。
各ステップで通信コストを明記して、このアルゴリズムを書き直す
![{\displaystyle D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cac33af611126fc1c4c482c88ffc62682d5cc2a)
i = 1 から n まで {Aのi行目を高速メモリに読み込む} - n 2回の読み込み j = 1 から n まで {C(i,j)を高速メモリに読み込む} - n 2回の読み込み {Bのj列目を高速メモリに読み込む} - n 3回の読み込み k = 1 から n まで C(i,j) = C(i,j) + A(i,k) * B(k,j) {C(i,j)を低速メモリに書き戻す} - n 2回の書き込み高速メモリは、サイズMのローカルプロセッサメモリ（CPUキャッシュ）と定義でき、低速メモリはDRAMと定義できる。
通信コスト（読み取り/書き込み）：n 3 + 3 n 2または O( n 3 )
総実行時間 = γ ·O( n 3 ) + β ·O( n 3 )であり、 β >> γであるため、通信コストが支配的になります。ブロック化（タイル化）行列乗算アルゴリズム[ 1 ]は、この支配的な項を削減します。
A、B、Cは、 b × bのサブブロックからなるn / b × n / b行列であると考える。ここでbはブロックサイズと呼ばれる。高速メモリには3つのb × bブロックが収まると仮定する。
i = 1 から n/b まで j = 1 から n/b まで {ブロック C(i,j) を高速メモリに読み込む} - b 2 × (n/b) 2 = n 2回読み込み k = 1 から n/b まで {ブロック A(i,k) を高速メモリに読み込む} - b 2 × (n/b) 3 = n 3 /b 回の読み込み {ブロック B(k,j) を高速メモリに読み込む} - b 2 × (n/b) 3 = n 3 /b 回の読み込み C(i,j) = C(i,j) + A(i,k) * B(k,j) - {ブロックに対して行列乗算を実行する} {ブロック C(i,j) を低速メモリに書き戻す} - b 2 × (n/b) 2 = n 2 回の書き込み通信コスト：2 n 3 / b + 2 n 2 回の読み書き << 2 n 3 回の算術コスト
bをできるだけ大きくする：
我々は以下の通信下限値を達成した。
この問題に対処するために過去に調査されたアプローチのほとんどは、通信と計算をオーバーラップさせることを目的としたスケジューリングまたはチューニング技術に依存しています。しかし、このアプローチでは最大でも 2 倍の改善しか得られません。ゴースティングは通信を削減するための別の技術で、プロセッサが将来の計算のために隣接するプロセッサからのデータを冗長に保存して計算します。キャッシュ非依存アルゴリズムは、1999 年に高速フーリエ変換用に導入された別のアプローチであり、[ 8 ]その後、グラフアルゴリズム、動的計画法などに拡張されました。これらは、密な LU および QR 分解として線形代数のいくつかの演算にも適用されました[ 9 ] [ 10 ] [ 11 ]。アーキテクチャ固有のアルゴリズムの設計は、並列アルゴリズムの通信を削減するために使用できるもう 1 つのアプローチであり、文献には、特定の通信トポロジに適応したアルゴリズムの例が多数あります。[ 12 ]