1つの最適化のストーリー

注釈

この記事では、3次行列乗算アルゴリズムの例を使用して、Javaの計算アルゴリズムの高度な最適化の機能を明らかにします。

ステップ0。基準点を設定します！

環境を決定します。

• ハードウェア：1ソケット/ 2コアIntel Core 2 Duo T7300 2GHz、2Gb ram;
• Java：HotSpot（TM）Client VM（ビルド17.0-b17、混合モード、共有）;

最も単純な3次行列乗算アルゴリズムを検討してください。 おそらく、どんな生徒でも、あるいは少年でも彼を知っているでしょう。 さらに、このアルゴリズムの原理は、記事の冒頭のウィキペディアの図を完全に示しているため、その機能については説明しません。

for (int i = 0; i < A.rows(); i++) { for (int j = 0; j < A.columns(); j++) { double summand = 0.0; for (int k = 0; k < B.columns(); k++) { summand += A[i][k] * B[k][j]; } C[i][j] = summand; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ワークロードとして、倍精度の2つの密な正方行列N x N（N = 1000）を使用します。



この場合、単純なキュービックアルゴリズムの実行時間は18.921 sです。 この数値は、後続の最適化の基準点（ベースライン）と見なされます。

ステップ1. 20/80ルールを知る！

80％の時間で20％のコードが機能することが知られています。 開発者のタスクは、これらの合計20％のコードを計算することです。 私たちの場合、すべてが明白です-望ましい20％は内部の計算サイクルに集中しています。 JVMの観点から見ると、このコードはジャストインタイムコンパイルの最も可能性の高い候補です。 オプション-XX：+ PrintCompilation -XX：+ CITimeを使用して、バイトコードがネイティブにコンパイルされているかどうかを確認できます。

 $ java -XX:+PrintCompilation la4j.Demo 1 java.lang.String::hashCode (64 bytes) 2 java.lang.String::charAt (33 bytes) 3 java.lang.String::indexOf (151 bytes) 4 java.lang.String::indexOf (166 bytes) 5 java.util.Random::next (47 bytes) 6 java.util.concurrent.atomic.AtomicLong::get (5 bytes) 7 java.util.concurrent.atomic.AtomicLong::compareAndSet (13 bytes) 8 java.util.Random::nextDouble (24 bytes) 9 la4j.matrix.DenseMatrix::set (10 bytes) 1% la4j.matrix.MatrixFactory::createRandomDenseMatrix @ 30 (68 bytes) 10 la4j.matrix.MatrixFactory::createRandomDenseMatrix (68 bytes) 2% la4j.matrix.DenseMatrix::multiply @ 81 (152 bytes)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リストから、行列乗算メソッド（la4j.matrix.DenseMatrix ::乗算）が正常にコンパイルされたことがわかります。 これにより、さらなるアクションの範囲が与えられます。 最初に、最終変数を活用してみましょう。 ネイティブコードにコンパイルされると、値に直接変換されることが知られています。 理論的には、マトリックスの境界を最終値に置き換えると、メモリアクセスが1000x1000x1000倍減少します。 代わりに、値は直接置き換えられます。 理論を確認してください。

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); for (int i = 0; i < aRows; i++) { for (int j = 0; j < aColumns; j++) { double summand = 0.0; for (int k = 0; k < bColumns; k++) { summand += A[i][k] * B[k][j]; } C[i][j] = summand; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムランタイム ： 16.996秒 ;

パフォーマンスの向上： 〜11％ ;

ステップ2.キャッシュを記憶する！

実際、このような実装は常にゆっくりと動作します。 「k」に対する反復は、列の行列Bの要素を指します。 このような読み取りは、プロセッサがキャッシュからデータを準備するのではなく、毎回メモリからデータをプリフェッチする必要があるため、非常に高価です。



Fortranにこのような問題がないことは注目に値します。 その中の多次元配列は列に格納されます。 したがって、キャッシュは適切に動作し、キュービックアルゴリズムの標準実装は何倍も高速に動作します。



検討中のプラットフォームでは、第1レベル（L1）のキャッシュラインサイズ-64バイト-これは、プロセッサにとって最も安価なメモリです。 私たちのケースでは、64バイトのほぼ空きメモリにより、1つの代わりに最大8つのマトリックスセル（sizeof（double）= 8）を取得し、その後にプリフェッチによるオーバーヘッドが発生する可能性があります。



アルゴリズムの問​​題は、この機能を実際に使用しないことです。 同時に、メモリへのランダムアクセス（列）により、キャッシュラインがリセットされ、各呼び出しでキャッシュラインを更新する手順が初期化されます。



キャッシュを最大限に活用するために、これを修正し、マトリックス要素への順次アクセスを実装してみましょう。 これを行うには、単純に行列Bを転置し、その要素を行ごとに参照します。

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double BT[][] = new double[bColumns][bRows]; for (int i = 0; i < bRows; i++) { for (int j = 0; j < bColumns; j++) { BT[j][i] = B[i][j]; } } for (int i = 0; i < aRows; i++) { for (int j = 0; j < aColumns; j++) { double summand = 0.0; for (int k = 0; k < bColumns; k++) { summand += A[i][k] * BT[j][k]; } C[i][j] = summand; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムランタイム ： 7.334秒 ;

パフォーマンスの向上： 〜232％ ;

ステップ3.考えます！

より多くのコードがありましたが、操作時間はほぼ2.5倍に短縮されました。 悪くない。 ただし、コードを表示すると、明らかな欠陥が明らかになります。 主なものは多くのサイクルです。 1つの計算サイクルで転置演算と乗算演算を組み合わせて、コードの量を減らし、よりエレガントにしようとしましょう。 同時に、行列全体ではなく、必要に応じて列単位で転置が実行されます。

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double thatColumn[] = new double[bRows]; for (int j = 0; j < bColumns; j++) { for (int k = 0; k < aColumns; k++) { thatColumn[k] = B[k][j]; } for (int i = 0; i < aRows; i++) { double thisRow[] = A[i]; double summand = 0; for (int k = 0; k < aColumns; k++) { summand += thisRow[k] * thatColumn[k]; } C[i][j] = summand; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムランタイム ： 3.976秒 。

パフォーマンスの向上： 〜190％ ;

ステップ4.捨てる！

Javaのもう1つの利点である例外を利用します。 マトリックスの境界を越えるチェックをtry {} catch {}ブロックに置き換えてみましょう。 この場合、比較の数が1000に減ります。 実際、常にfalseを返す1000回と1001回がtrueを返すのを比較してください。



一方では-比較の数を減らし、他方では-例外を処理するための追加のオーバーヘッドがあります。 いずれにしても、このアプローチはある程度の成長をもたらします。

 final int aColumns = A.columns(); final int aRows = A.rows(); final int bColumns = B.columns(); final int bRows = B.rows(); double thatColumn[] = new double[bRows]; try { for (int j = 0; ; j++) { for (int k = 0; k < aColumns; k++) { thatColumn[k] = B[k][j]; } for (int i = 0; i < aRows; i++) { double thisRow[] = A[i]; double summand = 0; for (int k = 0; k < aColumns; k++) { summand += thisRow[k] * thatColumn[k]; } C[i][j] = summand; } } } catch (IndexOutOfBoundsException ignored) { }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アルゴリズムランタイム： 3.594秒 。

パフォーマンスの向上： 〜10％ ;

ステップ5.停止しないでください！

この段階で、目標を達成したので、今のところ停止しました。 私の目標は、マトリックスを扱うための最も人気のあるライブラリであるJAMA（Googleの「javaマトリックス」の最初の行）を追い抜くことでした。 現在、私の実装はJAMAよりも約30％高速です。 さらに、比較的小さな最適化により、初期バージョンと比較してほぼ600％の増加が見られました。

結論の代わりに（これは広告ではありません）

レビューしたコードは、オープンソースのlaj4プロジェクトの一部です。 これは、Javaの線形代数の問題を解決するためのライブラリです。 私は、計算数学のコースを研究する過程で、4年目にプロジェクトに取り組み始めました。 現在la4jは優れたパフォーマンスを示し、多くのタスクで対応するものよりも数倍高速に動作します。



誰かが興味を持ち、このように夜を過ごしたい場合-個人的に書いてください:)