マルチコアマシンでの並列アルゴリズムのパフォーマンスに取り組んでいます。ループ並べ替え (ikj) 手法を使用した行列乗算の実験を行いました。
シリアル実行の結果は下の画像のようになります。nXn 行列のすべてのサイズのループ順序 ikj と kij の L1 データ キャッシュ ヒットはほぼ 100% であり (画像 1 ボックス番号 1 & 2)、サイズ 2048 のループ順序 ikj を見ることができます。 4096 L2 データ キャッシュ ヒットが突然 %50 減少 (画像 2 ボックス番号 1 & 2) L2 命令キャッシュ ヒットでも同じことが当てはまります。これら 2 つのサイズの L1 データ キャッシュ ヒットが他のサイズ (256、512、1024) の場合、約 100% です。命令キャッシュ ヒットとデータ キャッシュ ヒットの両方で、この勾配の正当な理由を見つけることができませんでした。理由を見つける方法について、誰かが私に手がかりを与えることができますか？
L2 統合キャッシュが問題を悪化させる効果があると思いますか? それでも、この減少の原因は何なのか、理由を見つけるために、アルゴリズムとパフォーマンスのどの特性をプロファイリングする必要がありますか。
実験マシンはIntel e4500で、2Mb L2キャッシュ、キャッシュライン64、OSはfedora 17 x64、gcc 4.7 -oコンパイラ最適化なし
要約された完全な質問?
my problem is that why sudden decrease of about 50% in both L2 data and instruction cache happens in only ikj & kij algorithm as it's boxed and numbered 1 & 2 in images, but not in other loop variation?
*Image 1*
*Image 2*
*Image 3*
*Image 4*
*Image 5*
前述の問題にもかかわらず、ikj&kij アルゴリズムのタイミングは増加しません。しかし、他のものよりも高速です。
ikj および kij アルゴリズムは、ループ並べ替え手法の 2 つのバリエーションです/
kij アルゴリズム
For (k=0;k<n;k++)
For(i=0;i<n;i++){
r=A[i][k];
For (j=0;j<n;j++)
C[i][j]+=r*B[k][j]
}
ikjアルゴリズム
For (i=0;i<n;i++)
For(k=0;k<n;k++){
r=A[i][k];
For (j=0;j<n;j++)
C[i][j]+=r*B[k][j]
}
ありがとう