キャッシュがマルチスレッドアプリケーションに与える影響

理論上のコンポーネント。



多くのコンピューターのボトルネックはRAMです-プロセッサーインターフェースです。 これは、メモリへのリクエストを形成するのにかかる時間が非常に長く、メモリの周波数がプロセッサの周波数よりも低いためです。 一般的な場合、メモリからデータを受信して​​いる間、プログラムの実行は停止します。 状況を改善するために、専用の高速メモリ（キャッシュ）が使用されます。



キャッシュがある場合、プロセッサがRAMの特定のバイトにアクセスする必要がある場合、このバイトを含むメモリ領域（領域のサイズはプロセッサによって異なります）がキャッシュで選択され、プロセッサはキャッシュからデータを読み取ります。 プロセッサがメモリにデータを書き込む場合、まずキャッシュに行き、次にRAMに行きます。



マルチコアおよびマルチプロセッサシステムでは、各コアまたはプロセッサに独自の個人用キャッシュがあります。 キャッシュ内のデータが1つのプロセッサによって変更された場合、変更は、重複するアドレススペースを使用する他のプロセッサと同期する必要があります。

変更が頻繁に発生し、データ領域が重複すると、生産性が低下します。



どれだけ悪いことがあるのか​​疑問があります。 また、データの長さがどのように影響するかを見るのも興味深いものでした。





実験。

検証のために、ワークスペースの交差の2つのケースに対して2つのマルチスレッドC ++プログラムを作成しました。

• エリアはオーバーラップせず、各スレッドのスタック上にあります。
• スレッドのワークスペースは一般的です。1、4、および8バイトのワードの配列で、合計長は1024バイトです。各スレッドはワードを変更します（たとえば、偶数または奇数のみ）。

2つの作業スレッドがあり、それぞれが単語を変更し、配列全体を通過し、境界に到達すると、先頭に戻ります。 各スレッドは1億の変更を行います。



UPD CPUの名前のタイプミスをありがとうございました。

テストには、HP xw4600ワークステーション、CPU Core 2 Quad（Q9300）、OS Linux Slamd64 12.1、カーネル2.6.24.5、およびgcc 4.2.3コンパイラーを使用しました。 結果は64ビットプログラムであったため、1.4および8バイト長のワードの算術演算は1クロックサイクルで実行されました。



実行時間はtime（1）コマンドによって測定され、5回の実験で平均されました。



最初は、単純に単語をインクリメントして戻すプログラムが作成されましたが、スタック上の配列の場合、-O2最適化は下品なことをすることがわかりました。 そのため、データでより複雑な処理を行う2つ目のプログラムが作成されました。



結果

UPD： APIチャートのmt_およびGoogleチャートをリマークするためのThnx。 結果はグラフィカル形式です。

数字を見たい人はさらにスクロールできます。



y軸では、プログラムの実際の実行時間（秒単位）。 X軸では、語長（ペア）。



プログラム1。







プログラム2。







プログラム2 +最適化-O2。







結論

明らかに重複していない領域の場合、より速く、大幅に動作することを確かに言うことができます。 最適化は何らかの形で影響しますが、傾向は継続しています。



しかし、単語の長さへの依存は、どういうわけかそれほど顕著ではありません。



この作品のアイデアは、 www.ddj.com / architect / 208200273の記事から着想を得ています。



UPDパーフェクトコードをブログに投稿しようとしていますが、これは適切な場所であるように思えます。



結果は表形式です。

結果は数秒で表示されます。



プログラム1（共有メモリ）。

語長	64	32	8
リアルタイム	1,297	1,532	0.846
ユーザー時間 政権	2,461	3,049	1,664

プログラム1（スタック）

語長	64	32	8
リアルタイム	0.453	0.431	0.441
ユーザー時間 政権	0.851	0.842	0.866

プログラム2（共有メモリ）。

語長	64	32	8
リアルタイム	9,191	9,033	8,921
ユーザー時間 政権	18,365	18,039	17,824

プログラム2（スタック）

語長	64	32	8
リアルタイム	8,432	8,412	8,808
ユーザー時間 モードc	16,843	16,796	17,548

プログラム2 +最適化-O2（共有メモリ）。

語長	64	32	8
リアルタイム	4,247	4,380	3,473
ユーザー時間 政権	8,415	8,960	6,781

プログラム2 +最適化-O2（スタック）

語長	64	32	8
リアルタイム	3,282	3,718	3,308
ユーザー時間 政権	6,550	7,384	5,565

ソースコード。



プログラム1。



#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int8_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

array[index] = array[index] + 1;

#else

array1[index] = array1[index] + 1;

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .







#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int8_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

array[index] = array[index] + 1;

#else

array1[index] = array1[index] + 1;

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .







#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int8_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

array[index] = array[index] + 1;

#else

array1[index] = array1[index] + 1;

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .













プログラム2。



#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int64_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

//#define DOIT 100000000 * (sizeof(u_int64_t) / sizeof(MTYPE))

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



template<typename RTYPE, int TLEN>

RTYPE scramble(u_int16_t *seed, RTYPE a){

int d;

//

for ( d = 0; d < 8; ++d){

u_int16_t mask;

//

mask = (*seed & 0x1) ^ ( (*seed >> 1) &0x1);

mask = mask & 0x1;

*seed = (mask << 15) | (*seed >> 1);

//

a = a ^ ((RTYPE)mask << d);

}

//

return a;

};



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

u_int16_t seed = 0x4a80;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

MTYPE data;

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

data = array[index];

array[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#else

data = array1[index];

array1[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .







#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int64_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

//#define DOIT 100000000 * (sizeof(u_int64_t) / sizeof(MTYPE))

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



template<typename RTYPE, int TLEN>

RTYPE scramble(u_int16_t *seed, RTYPE a){

int d;

//

for ( d = 0; d < 8; ++d){

u_int16_t mask;

//

mask = (*seed & 0x1) ^ ( (*seed >> 1) &0x1);

mask = mask & 0x1;

*seed = (mask << 15) | (*seed >> 1);

//

a = a ^ ((RTYPE)mask << d);

}

//

return a;

};



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

u_int16_t seed = 0x4a80;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

MTYPE data;

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

data = array[index];

array[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#else

data = array1[index];

array1[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .







#include <sys/types.h>



#include <stdio.h>

#include <stdlib.h>



#include <pthread.h>



#define TBYTES 1024

//

#define TOTAL 2

// u_int8_t u_int32_t u_int64_t

#define MTYPE u_int64_t

//

#define MAXAR TBYTES/ sizeof (MTYPE)

//#define DOIT 100000000 * (sizeof(u_int64_t) / sizeof(MTYPE))

#define DOIT 100000000



MTYPE *array;



pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int workers = 2;



template<typename RTYPE, int TLEN>

RTYPE scramble(u_int16_t *seed, RTYPE a){

int d;

//

for ( d = 0; d < 8; ++d){

u_int16_t mask;

//

mask = (*seed & 0x1) ^ ( (*seed >> 1) &0x1);

mask = mask & 0x1;

*seed = (mask << 15) | (*seed >> 1);

//

a = a ^ ((RTYPE)mask << d);

}

//

return a;

};



//

//#define SHARED 1



void *

runner( void * args){

unsigned int which = *(unsigned int *)args; delete (unsigned int *)args;

unsigned int index = which;

u_int16_t seed = 0x4a80;

MTYPE array1[MAXAR];

//

for ( unsigned int i = 0; i < DOIT; ++i){

MTYPE data;

if ( index >= MAXAR)

index = which;

//

#if defined(SHARED)

data = array[index];

array[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#else

data = array1[index];

array1[index] = scramble<MTYPE, 8* sizeof (MTYPE)>(&seed, data);

#endif

//

index += TOTAL;

}

//

pthread_mutex_lock(&mux);

-- workers;

pthread_mutex_unlock(&mux);

pthread_cond_broadcast(&cond);

//

return 0;

};



int

main() {

//

array = (MTYPE*)calloc(MAXAR, sizeof (MTYPE));

//

unsigned int *which;

pthread_t t1;

pthread_attr_t attr;

//

pthread_attr_init(&attr);

pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

//

which = new unsigned int (0);

pthread_create(&t1, &attr, runner, ( void *)which);

//

which = new unsigned int (1);

pthread_create(&t1, &attr, runner, ( void *)which);

//

pthread_mutex_lock(&mux);

while (!pthread_cond_wait(&cond, &mux)){

if ( !workers)

break ;

};

pthread_mutex_unlock(&mux);

//

return 0;

};

//



* This source code was highlighted with Source Code Highlighter .