a1
、、、がヒープメモリを指していると仮定し、数値コードb1
には次のコアループがあります。c1
d1
const int n = 100000;
for (int j = 0; j < n; j++) {
a1[j] += b1[j];
c1[j] += d1[j];
}
このループは別の外側のループを介して 10,000 回実行されますfor
。速度を上げるために、コードを次のように変更しました。
for (int j = 0; j < n; j++) {
a1[j] += b1[j];
}
for (int j = 0; j < n; j++) {
c1[j] += d1[j];
}
コンパイル日マイクロソフト Visual C++ 10.0完全な最適化とSSE232ビット対応インテル コア 2Duo (x64) では、最初の例では 5.5 秒かかり、ダブルループの例では 1.9 秒しかかかりません。
最初のループの逆アセンブリは基本的に次のようになります (このブロックは完全なプログラム内で約 5 回繰り返されます)。
movsd xmm0,mmword ptr [edx+18h]
addsd xmm0,mmword ptr [ecx+20h]
movsd mmword ptr [ecx+20h],xmm0
movsd xmm0,mmword ptr [esi+10h]
addsd xmm0,mmword ptr [eax+30h]
movsd mmword ptr [eax+30h],xmm0
movsd xmm0,mmword ptr [edx+20h]
addsd xmm0,mmword ptr [ecx+28h]
movsd mmword ptr [ecx+28h],xmm0
movsd xmm0,mmword ptr [esi+18h]
addsd xmm0,mmword ptr [eax+38h]
二重ループの例の各ループでは、次のコードが生成されます (次のブロックは約 3 回繰り返されます)。
addsd xmm0,mmword ptr [eax+28h]
movsd mmword ptr [eax+28h],xmm0
movsd xmm0,mmword ptr [ecx+20h]
addsd xmm0,mmword ptr [eax+30h]
movsd mmword ptr [eax+30h],xmm0
movsd xmm0,mmword ptr [ecx+28h]
addsd xmm0,mmword ptr [eax+38h]
movsd mmword ptr [eax+38h],xmm0
movsd xmm0,mmword ptr [ecx+30h]
addsd xmm0,mmword ptr [eax+40h]
movsd mmword ptr [eax+40h],xmm0
動作は配列のサイズ (n) と CPU キャッシュに大きく依存するため、この質問は無関係であることが判明しました。したがって、さらに興味がある場合は、質問を言い換えます。
次のグラフの 5 つの領域で示されるさまざまなキャッシュ動作につながる詳細について、確かな洞察を提供していただけますか?
これらの CPU に同様のグラフを提供して、CPU/キャッシュ アーキテクチャ間の違いを指摘するのも興味深いかもしれません。
完全なコードはこちらです。未定 Tick_Count
より高解像度のタイミングの場合は、マクロを定義しないことで無効にできますTBB_TIMING
。
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
//#define TBB_TIMING
#ifdef TBB_TIMING
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif
using namespace std;
//#define preallocate_memory new_cont
enum { new_cont, new_sep };
double *a1, *b1, *c1, *d1;
void allo(int cont, int n)
{
switch(cont) {
case new_cont:
a1 = new double[n*4];
b1 = a1 + n;
c1 = b1 + n;
d1 = c1 + n;
break;
case new_sep:
a1 = new double[n];
b1 = new double[n];
c1 = new double[n];
d1 = new double[n];
break;
}
for (int i = 0; i < n; i++) {
a1[i] = 1.0;
d1[i] = 1.0;
c1[i] = 1.0;
b1[i] = 1.0;
}
}
void ff(int cont)
{
switch(cont){
case new_sep:
delete[] b1;
delete[] c1;
delete[] d1;
case new_cont:
delete[] a1;
}
}
double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
allo(cont,n);
#endif
#ifdef TBB_TIMING
tick_count t0 = tick_count::now();
#else
clock_t start = clock();
#endif
if (loops == 1) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
}
} else {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a1[j] += b1[j];
}
for (int j = 0; j < n; j++) {
c1[j] += d1[j];
}
}
}
double ret;
#ifdef TBB_TIMING
tick_count t1 = tick_count::now();
ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
clock_t end = clock();
ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif
#ifndef preallocate_memory
ff(cont);
#endif
return ret;
}
void main()
{
freopen("C:\\test.csv", "w", stdout);
char *s = " ";
string na[2] ={"new_cont", "new_sep"};
cout << "n";
for (int j = 0; j < 2; j++)
for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
cout << s << i << "_loops_" << na[preallocate_memory];
#else
cout << s << i << "_loops_" << na[j];
#endif
cout << endl;
long long nmax = 1000000;
#ifdef preallocate_memory
allo(preallocate_memory, nmax);
#endif
for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
{
const long long m = 10000000/n;
cout << n;
for (int j = 0; j < 2; j++)
for (int i = 1; i <= 2; i++)
cout << s << plain(n, m, j, i);
cout << endl;
}
}
さまざまな値に対する FLOPS を表示しますn
。
ベストアンサー1
これをさらに分析すると、これは (少なくとも部分的には) 4 つのポインターのデータ配置によって発生していると考えられます。これにより、ある程度のキャッシュ バンク/ウェイの競合が発生します。
配列の割り当て方法を正しく推測すると、配列はページ行に揃えられる可能性があります。
これは、各ループのすべてのアクセスが同じキャッシュ ウェイに配置されることを意味します。ただし、Intel プロセッサは以前から 8 ウェイ L1 キャッシュ アソシエティビティを備えています。しかし、実際にはパフォーマンスは完全に均一ではありません。4 ウェイのアクセスは、2 ウェイのアクセスよりも依然として低速です。
編集: 実際には、すべての配列を別々に割り当てているように見えます。通常、このような大規模な割り当てが要求されると、アロケータは OS に新しいページを要求します。したがって、大規模な割り当てがページ境界からの同じオフセットに表示される可能性が高くなります。
テストコードは次のとおりです。
int main(){
const int n = 100000;
#ifdef ALLOCATE_SEPERATE
double *a1 = (double*)malloc(n * sizeof(double));
double *b1 = (double*)malloc(n * sizeof(double));
double *c1 = (double*)malloc(n * sizeof(double));
double *d1 = (double*)malloc(n * sizeof(double));
#else
double *a1 = (double*)malloc(n * sizeof(double) * 4);
double *b1 = a1 + n;
double *c1 = b1 + n;
double *d1 = c1 + n;
#endif
// Zero the data to prevent any chance of denormals.
memset(a1,0,n * sizeof(double));
memset(b1,0,n * sizeof(double));
memset(c1,0,n * sizeof(double));
memset(d1,0,n * sizeof(double));
// Print the addresses
cout << a1 << endl;
cout << b1 << endl;
cout << c1 << endl;
cout << d1 << endl;
clock_t start = clock();
int c = 0;
while (c++ < 10000){
#if ONE_LOOP
for(int j=0;j<n;j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
#else
for(int j=0;j<n;j++){
a1[j] += b1[j];
}
for(int j=0;j<n;j++){
c1[j] += d1[j];
}
#endif
}
clock_t end = clock();
cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;
system("pause");
return 0;
}
ベンチマーク結果:
編集:実際のCore 2 アーキテクチャ マシンでの結果:
2 x Intel Xeon X5482 Harpertown @ 3.2 GHz:
#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206
#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116
//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894
//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993
観察:
1 ループで6.206 秒、2 ループで2.116 秒。これは OP の結果を正確に再現します。
最初の 2 つのテストでは、配列は別々に割り当てられます。ページに対してすべての配列が同じ配置になっていることがわかります。
2 番目の 2 つのテストでは、配列が一緒にパックされて、そのアラインメントが解除されます。ここでは、両方のループが高速になっていることがわかります。さらに、通常予想されるとおり、2 番目の (二重) ループの方が低速になっています。
@Stephen Cannon がコメントで指摘しているように、このアラインメントによってロード/ストア ユニットまたはキャッシュで誤ったエイリアシングが発生する可能性が非常に高いです。これについて Google で検索したところ、Intel には部分的なアドレス エイリアシングストール用のハードウェア カウンターがあることが分かりました。
5つの地域 - 説明
地域1:
これは簡単です。データセットが非常に小さいため、パフォーマンスはループや分岐などのオーバーヘッドによって左右されます。
地域2:
ここで、データ サイズが増加すると、相対的なオーバーヘッドの量が減り、パフォーマンスが「飽和」します。ここで、2 つのループは、ループと分岐のオーバーヘッドが 2 倍になるため、遅くなります。
ここで何が起こっているのか正確にはわかりません...アグナー・フォグが言うように、アラインメントはまだ影響を与える可能性がありますキャッシュバンクの競合(このリンクは Sandy Bridge に関するものですが、その考え方は Core 2 にも当てはまるはずです。)
地域3:
この時点で、データは L1 キャッシュに収まらなくなります。そのため、パフォーマンスは L1 <-> L2 キャッシュ帯域幅によって制限されます。
地域4:
私たちが観察しているのは、単一ループでのパフォーマンスの低下です。そして、前述したように、これはアラインメントによるもので、プロセッサのロード/ストア ユニットで誤ったエイリアシングストールを引き起こす可能性が最も高いです。
ただし、誤ったエイリアシングが発生するには、データセット間に十分な間隔が必要です。これが、領域 3 でこれが見られない理由です。
地域5:
この時点では、キャッシュに収まるものは何もありません。そのため、メモリ帯域幅に制限されます。