Loading article…
コンピュータサイエンス、特にコンパイラ設計において、ループネスト最適化（LNO）は、ループネストの局所性最適化、並列化、またはその他のループオーバーヘッド削減を目的として、一連のループ変換を適用する最適化手法です。（ネストされたループとは、あるループが別のループの中にある状態を指します。）古典的な用途の一つとして、一般的な線形代数アルゴリズムにおいて、キャッシュの再利用によってメモリアクセス遅延や必要なキャッシュ帯域幅を削減することが挙げられます。
この最適化を実現するために使用される技術は、ループタイリング[ 1 ] 、ループブロッキング[ 2 ]またはストリップマインおよびインターチェンジとも呼ばれます。
ループタイリングは、ループの反復空間をより小さなチャンクまたはブロックに分割することで、ループ内で使用されるデータが再利用されるまでキャッシュに保持されるようにします。ループ反復空間の分割は、大きな配列をより小さなブロックに分割することにつながり、アクセスされる配列要素をキャッシュサイズに収めることができるため、キャッシュの再利用性が向上し、キャッシュサイズの要件が不要になります。
普通のループ
for ( i = 0 ; i < N ; ++ i ) { ... }ブロックサイズ B でブロックできます。
for ( j = 0 ; j < N ; j += B ) { for ( i = j ; i < min ( N , j + B ); ++ i ) { .... } }ここでmin()、 は引数の最小値を返す関数です。
以下は行列とベクトルの乗算の例です。要素数がそれぞれ100の配列が3つあります。このコードでは、配列をより小さなサイズに分割する処理は行っていません。
int i , j , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i ++ ) { c [ i ] = 0 ; for ( j = 0 ; j < n ; j ++ ) { c [ i ] = c [ i ] + a [ i ][ j ] * b [ j ]; } }2×2ブロックを使用してループタイリングを適用すると、コードは次のようになります。
int i , j , x , y , a [ 100 ][ 100 ], b [ 100 ], c [ 100 ]; int n = 100 ; for ( i = 0 ; i < n ; i += 2 ) { c [ i ] = 0 ; c [ i + 1 ] = 0 ; for ( j = 0 ; j < n ; j += 2 ) { for ( x = i ; x < min ( i + 2 , n ); x ++ ) { for ( y = j ; y < min ( j + 2 , n ); y ++ ) { c [ x ] = c [ x ] + a [ x ][ y ] * b [ y ]; } } } }元のループ反復空間はn × nです。配列 a[i, j] のアクセスされるチャンクもn × nです。nが大きすぎてマシンのキャッシュサイズが小さすぎると、1 つのループ反復でアクセスされる配列要素 (たとえば、、i = 1)j = 1 to nがキャッシュラインをまたいでキャッシュミスが発生する可能性があります。
1つのループに対して最適なタイルサイズを決定するのは必ずしも容易ではありません。なぜなら、ループ内でアクセスされる配列領域とターゲットマシンのキャッシュサイズを正確に推定する必要があるからです。ループネストの順序（ループの入れ替え）も、キャッシュパフォーマンスの向上に重要な役割を果たします。明示的なブロッキングでは、これらの要素に基づいてタイルサイズを選択する必要があります。一方、キャッシュ非依存アルゴリズムは、明示的なブロッキングを行わずにキャッシュを効率的に利用するように設計されています。
コンピュータ上で行われる多くの大規模な数学演算では、その時間の大部分が行列乗算に費やされます。その演算は次のとおりです。
ここで、A、B、CはN×N配列です。以下の説明における添え字は、 の形式ですC[row][column]。
基本的なループは次のとおりです。
int i 、j 、k ;for ( i = 0 ; i < N ; ++ i ) { for ( j = 0 ; j < N ; ++ j ) { C [ i ][ j ] = 0 ;for ( k = 0 ; k < N ; ++ k ) C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ]; } }解決すべき問題は3つあります。
元のループは、結果行列のエントリを一度に1つずつ計算します。次のループでは、エントリの小さなブロックを同時に計算することで、ロードされた各値を2回再利用し、内側のループで4回のロードと4回の乗算加算を行うことで、問題2を解決します。4つのアキュムレータを同時に使用することで、このコードはレイテンシ4の単一の浮動小数点加算器をほぼ常に稼働させることができます（問題1）。ただし、このコードは3番目の問題には対処していません。（Nが奇数の場合に必要なクリーンアップ処理にも対処していません。これらの詳細は、以降の説明では省略します。）
for ( i = 0 ; i < N ; i += 2 ) { for ( j = 0 ; j < N ; j += 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; for ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } }このコードでは、iおよびのj反復処理が両方とも2倍の係数でブロックされ、結果として生じる2回の反復処理の内部ループが完全に展開されてしまいました。
このコードは、メインメモリへのメモリ操作ごとに0.8回の乗算加算を処理できるCray Y-MP（1980年代初頭に製造）では十分に快適に動作します。一方、2003年に製造された2.8GHz Pentium 4のようなマシンは、メモリ帯域幅がやや低いものの、浮動小数点演算性能が格段に優れているため、メモリ操作ごとに16.5回の乗算加算を処理できます。結果として、上記のコードは166MHzのY-MPよりも2.8GHz Pentium 4 の方が遅く動作します。
浮動小数点加算のレイテンシが長いマシンや、複数の加算器を備えたマシンでは、並列実行するためにより多くのアキュムレータが必要になります。上記のループを2x2ブロックではなく3x3ブロックを計算するように変更するのは簡単ですが、結果として得られるコードが必ずしも高速になるとは限りません。このループでは、アキュムレータとロードされて再利用されるAとBの値の両方を保持するためのレジスタが必要です。2x2ブロックには7つのレジスタが必要です。3x3ブロックには13のレジスタが必要ですが、ISAに8つの浮動小数点レジスタしかないマシンでは動作しません。CPUに十分なレジスタがない場合、コンパイラはレジスタをスタックスロットにスピルするために追加のロードとストアをスケジュールしますが、これにより、より小さなブロックループよりもループの実行速度が遅くなります。
行列乗算は、他の多くのコードと同様に、メモリ帯域幅によって制限される可能性があり、レジスタを増やすことでコンパイラやプログラマがメモリ帯域幅の必要性を減らすことができます。このようなレジスタの制約があるため、汎用x86や68000 CPUよりも並列性の高いマシンを構築しようとしたRISC CPUのベンダーは、32エントリの浮動小数点レジスタファイルを採用しました。
上記のコードはキャッシュをあまり有効活用していません。C の水平ストライプの結果を計算する際、A の水平ストライプが 1 つロードされ、行列 B 全体がロードされます。計算全体を通して、C は 1 回だけ格納され (これは良い点です)、A は (A のストライプが B のストライプと一緒にキャッシュに収まると仮定して) 1 回キャッシュにロードされますが、B は N/ib 回ロードされます。ここで ib は C 行列のストライプのサイズです。したがって、メインメモリからの合計ロード回数は N 3 /ib 倍になります。上記のコードでは、ibは 2 です。
メモリトラフィックを削減するための次のステップは、ib をできるだけ大きくすることです。これは、ストリームによって報告される「バランス」値よりも大きくする必要があります。この例で使用されている特定の 2.8 GHz Pentium 4 システムの場合、バランス値は 16.5 です。上記の 2 番目のコード例は、アキュムレータレジスタがさらに多く必要になるため、直接拡張することはできません。代わりに、ループはi でブロックされます。（厳密には、これは i がブロックされる 2 回目のケースです。1 回目は係数 2 でした。）
for ( ii = 0 ; ii < N ; ii += ib ) { for ( j = 0 ; j < N ; j += 2 ) { for ( i = ii ; i < ii + ib ; i += 2 ) { acc00 = acc01 = acc10 = acc11 = 0 ; for ( k = 0 ; k < N ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [ k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } }このコードでは、ibを任意の値に設定でき、B行列のロード回数はその値分だけ削減されます。ただし、この自由には代償が伴います。A行列のN×ib個のスライスがキャッシュに保持されるのです。それがシステムに収まる限り、このコードはメモリシステムの制限を受けません。
では、どのくらいのサイズの行列が適合するのでしょうか？例として挙げたシステム、2.8GHz のPentium 4は、16KBのプライマリデータキャッシュを備えています。ib=20の場合、N > 100のとき、このコードにおけるA行列のスライスはプライマリキャッシュよりも大きくなります。これよりも大きな問題の場合は、別の工夫が必要です。
そのトリックは、kループをブロックすることでB行列のストライプのサイズを小さくし、ストライプのサイズをib×kbにすることです。kループをブロックすると、C配列はN/kb回ロードおよび格納され、合計でメモリ転送。Bは依然としてN/ib回転送されます。送金。
マシンのメモリシステムは浮動小数点演算ユニットに追随し、コードは最高のパフォーマンスで実行されます。Pentium 4の16KBキャッシュは十分な大きさではありません。代わりにib=24、kb=64を選択した場合、キャッシュの12KBが使用され、完全に満杯になることは避けられます。これは、C配列とB配列が処理できる余裕を持たせるために望ましいことです。これらの数値は、プロセッサのピーク浮動小数点速度の20%以内に収まります。
ループがブロックされたコードを以下に示しますk。
for ( ii = 0 ; ii < N ; ii += ib ) { for ( kk = 0 ; kk < N ; kk += kb ) { for ( j = 0 ; j < N ; j += 2 ) { for ( i = ii ; i < ii + ib ; i += 2 ) { if ( kk == 0 ) acc00 = acc01 = acc10 = acc11 = 0 ; else { acc00 = C [ i + 0 ][ j + 0 ]; acc01 = C [ i + 0 ][ j + 1 ]; acc10 = C [ i + 1 ][ j + 0 ]; acc11 = C [ i + 1 ][ j + 1 ]; } for ( k = kk ; k < kk + kb ; k ++ ) { acc00 += B [ k ][ j + 0 ] * A [ i + 0 ][ k ]; acc01 += B [ k ][ j + 1 ] * A [ i + 0 ][ k ]; acc10 += B [ k ][ j + 0 ] * A [ i + 1 ][ k ]; acc11 += B [k ][ j + 1 ] * A [ i + 1 ][ k ]; } C [ i + 0 ][ j + 0 ] = acc00 ; C [ i + 0 ][ j + 1 ] = acc01 ; C [ i + 1 ][ j + 0 ] = acc10 ; C [ i + 1 ][ j + 1 ] = acc11 ; } } } }上記のコード例では、ブロッキング係数の倍数ではない N の値の処理の詳細については示されていません。ループネスト最適化を行うコンパイラは、計算の端を整理するコードを生成します。たとえば、ほとんどの LNO コンパイラは、ループから if 文を削除するために、kk == 0 の反復を他の反復から分離するでしょう。このようなコンパイラの利点の 1 つは、この最適化の単純なケースをコーディングするのは簡単である一方、コードが複製および変換される際にすべての詳細を正しく維持することはエラーが発生しやすいプロセスであるということです。kki
上記のループは、16KBのL1キャッシュサイズでブロックされた場合、例のシステムでピーク浮動小数点演算性能の80%しか達成できません。メモリ構成がさらにアンバランスなシステムでは、さらに性能が低下します。幸いなことに、Pentium 4には、レベル1キャッシュに加えて、256KB（モデルによってはそれ以上）の高帯域幅レベル2キャッシュが搭載されています。選択肢はあります。
最初の例のように特定のキャッシュサイズに合わせて調整するのではなく、キャッシュ非依存アルゴリズムは、キャッシュのサイズに関係なく、利用可能なキャッシュを有効活用するように設計されています。これにより、利用可能な場合は、2つ以上のメモリ階層が自動的に活用されます。行列乗算のためのキャッシュ非依存アルゴリズムは既に知られています。