11

行列乗算のパフォーマンスを比較するためだけに、Java で 2 つの行列クラスを作成しました。1 つのクラス (Mat1)には、行列のdouble[][] A行が であるメンバーが格納されます。もう一方のクラス (Mat2) には、 が格納され、は の転置です。iA[i]ATTA

正方行列 M があり、 の積が欲しいとしましょうM.mult(M)。製品を呼び出しますP。

M が Mat1 インスタンスの場合、使用されるアルゴリズムは単純なものでした。

P[i][j] += M.A[i][k] * M.A[k][j]
    for k in range(0, M.A.length)

M が私が使用した Mat2 の場合:

P[i][j] += M.A[i][k] * M.T[j][k]

これは同じアルゴリズムですT[j][k]==A[k][j]。1000x1000 行列では、2 番目のアルゴリズムは私のマシンで約 1.2 秒かかりますが、最初のアルゴリズムは少なくとも 25 秒かかります。2番目の方が速いと思っていましたが、それほどではありません。問題は、なぜこれほど高速なのかということです。

私の唯一の推測は、データが 1 ワードよりも大きなチャンクでキャッシュに取り込まれるため、2 番目のアルゴリズムが CPU キャッシュをより有効に利用できるということです。すぐ下の行に移動してキャッシュします（配列は行の優先順で格納されるため、メモリ内には約 1000 ワードです）。キャッシュされるデータはありません。

誰かに尋ねたところ、メモリ アクセス パターンがより使いやすいためだと彼は考えていました (つまり、2 番目のバージョンでは TLB のソフト フォールトが少なくなるからです)。私はこれについてまったく考えていませんでしたが、TLB フォールトがどのように減少するかを見ることができます。

それで、それはどれですか？または、パフォーマンスの違いには他の理由がありますか?

4

4 に答える 4

5

これは、データの局所性によるものです。

RAMでは、マトリックスは、あなたの観点からは2次元ですが、もちろん、連続したバイト配列として格納されます。1D配列との唯一の違いは、使用する両方のインデックスを補間することによってオフセットが計算されることです。

これは、位置x,yにある要素にアクセスすると計算x*row_length + yされ、指定された位置にある要素を参照するために使用されるオフセットになることを意味します。

何が起こるかというと、大きなマトリックスはメモリのページだけに保存​​されないため（これは、OSがRAMをチャンクに分割して管理する方法です）、アクセスしようとすると、CPUキャッシュ内に正しいページをロードする必要があります。まだ存在していない要素。

乗算を連続して実行する限り、問題は発生しません。主にページのすべての係数を使用してから次の係数に切り替えるためですが、インデックスを反転すると、すべての要素がに含まれる可能性があります。異なるメモリページなので、RAMに別のページを要求する必要があるたびに、これはほとんどすべての乗算に対して、違いが非常にきれいである理由です。

（私は説明全体をかなり単純化しました、それはあなたにこの問題に関する基本的な考えを与えるためだけです）

いずれにせよ、これはJVM自体が原因ではないと思います。これは、OSがJavaプロセスのメモリを管理する方法に関連している可能性があります。

于 2010-10-27T00:53:57.653 に答える
0

キャッシュとTLBの仮説はどちらも妥当ですが、擬似コードスニペットだけでなく、ベンチマークの完全なコードを確認したいと思います。

もう1つの可能性は、転置を使用したバージョンのデータ配列にアプリケーションが50％多くのメモリを使用した結果としてパフォーマンスが異なることです。JVMのヒープサイズが小さい場合、これが原因でGCが頻繁に実行されている可能性があります。これは、デフォルトのヒープサイズを使用した結果である可能性があります。（3ロットの1000 x 1000 x 8バイトは約24Mbです）

初期ヒープサイズと最大ヒープサイズを（たとえば）現在の最大サイズの2倍に設定してみてください。それでも違いがない場合、これは単純なヒープサイズの問題ではありません。

于 2010-10-27T00:51:52.977 に答える
0

この一連の結果を踏まえて、JDK6 と OpenJDK7 のパフォーマンスを比較してみてください...

于 2010-10-27T05:53:31.947 に答える
0

問題が局所性である可能性を推測するのは簡単ですが、それは推測にすぎません。

推測する必要はありません。シングル ステップとランダムな一時停止という 2 つの手法で答えが得られる可能性があります。

遅いコードを 1 ステップ実行すると、夢にも思わなかった多くのことを実行していることに気付くかもしれません。など、あなたは尋ねますか？試してみてください。機械語レベルで見るべきことは、無駄な動きをせずに内側のループを効率的にステップスルーすることです。

実際に無駄な動きがなく内側のループを通過している場合は、ランダムに一時停止すると情報が得られます。遅いものは速いものよりも 20 倍の時間がかかるため、95% の時間は必要のないことを行っていることを意味します。それで、それが何であるかを見てください。一時停止するたびに、95% の確率で、それが何なのか、なぜなのかがわかります。

低速の場合に、実行中の命令が高速の場合と同様に効率的であると思われる場合、キャッシュの局所性は低速の理由の合理的な推測です。進行している可能性のある他の愚かさを排除したら、そのキャッシュの局所性が支配的になると確信しています。

于 2010-10-27T01:47:28.887 に答える