マルチコアを使うのは難しい

計算機システムⅠ
５章マルチコアとキャッシュコヒーレンス制御
http://arch.naist.jp/htdocs-arch0/ppt/lect05/lect05.pdf
Copyright © 2015 奈良先端大中島康彦
1
主記憶空間の数が「複数」か「1つ」か
ただしプログラムは容易
2
マルチスレッドによる並列処理
3
キャッシュコヒーレンス制御の必要性
 データは共有メモリに配置
 なるべくキャッシュを利用すればプロセッサは高速動作可能
 矛盾が生じないためにどうすればよいか
 CPU１がアドレスAにXを格納
 同時にCPU２がYを格納
Ｘ
CPU1とCPU２が常時相互監視すればよい
しかし、同時実行の効果が出ない
CPU数が増えると指数関数的に手間が増える
4
Ｙ
キャッシュコヒーレンス制御とは
要するに、メモリ内容を更新したら、他のキャッシュを無効化すればよい
ライトバックキャッシュでのライトインバリデートプロトコル（MSI プロトコルの場合）
1) 有効なデータが載っていないライン
2) 複数プロセッサが共有の可能性があるライン
3) あるプロセッサが修正した可能性があるライン
5
… 無効状態(Invalid)
… 共有状態(Shared)
… 修正状態(Modified)
ＭＳＩプロトコル
6
排他制御の必要性
 複数スレッドが同一変数を更新
 矛盾が生じないためにどうすればよいか
【スレッド１】
：
A = A + 1;
：
【命令列１】
load A,r1
add
r1,#1,r1
store A,r1
アドレスA
２
３
４
２
３
３
【スレッド２】
：
：
A = A + 1;
【命令列２】
load A,r2
add
r2,#1,r2
：
store A,r2
「キャッシュコヒーレンス制御」は正しく動作しても、値は矛盾
解決には「排他制御」が必要
7
排他制御とは
 Intelでは、cmpxchg reg, mem を使用 … アトミック命令
%eaxレジスタの値 = memのロード値なら、regの値をストア
%eaxレジスタの値 != memのロード値なら、ロード値をregに格納
【スレッド１】
mov #1,r0
Loop: mov #255,%eax
lock cmpxchg r0, X
brc
r0!=255
load A,r1
add
r1,#1,r1
store A,r1
mov #255,X
アドレスX
255
255
255
1
1
1
1
255
【スレッド2】
mov #1,r0
Loop: mov #255,%eax
lock cmpxchg r0, X
brc
r0!=255
load A,r1
add
r1,#1,r1
store A,r1
mov #255,X
クリティカルセクションと呼ぶ
8
排他制御とは
 ARMでは、ldrexおよびstrexの組み合わせにより、cmpxchgを実現
ldrex r0, X … アドレスXをロックしr0に読み出す
--この間、ロックが外される可能性有り-strex r0, X … アドレスXがロックされていればr0をストアする
 キャッシュのModify状態との相性が良く、バスロック不要
 cmpxchg (X, _old, _new) Xの値=_oldの値なら、_newをXにストア
9
cmpxchg: ldrex r3, X
… アドレスXをロード
mov #0, r4
… r4に0を代入
test r3, _old
… r3と_oldを比較
strexeq r4, _new, X … 同じ場合、
ロックOKならXに_newをストアしr4に0を代入
失敗ならr4に1を代入
brc
r4!=0
… 失敗ならやり直し
return
… 成功なら復帰
演習問題
●以下のスレッド(tid=0,1,…,31)を３２個同時実行する場合の
速度差の原因は？
#define SIZE 32768
double A[SIZE];
void *parallel(tid) int tid;
{
int j, k;
for (k=0; k<SIZE; k++) {
for (j=0; j<SIZE; j++)
A[tid*8] += k;
}
}
４．３秒
10
#define SIZE 32768
double A[SIZE];
void *parallel(tid) int tid;
{
int j, k;
for (k=0; k<SIZE; k++) {
for (j=0; j<SIZE; j++)
A[tid] += k;
}
}
１０８秒
12

Download Report