高性能計算基盤 第 7 回 CA1003: 主記憶共有型システム http://arch.naist.jp/htdocs-arch3/ppt/ca1003/ca1003j.pdf Copyright 2019 奈良先端大中島康彦 1
2
3
4 マルチスレッディングとマルチコア
5
6
7
主記憶空間の数が 複数 か 1 つ か 8 ただしプログラムは容易
9 1 つの主記憶空間を共有する場合
10 マルチスレッドによる並列処理
キャッシュコヒーレンス制御の必要性 データは共有メモリに配置 なるべくキャッシュを利用すればプロセッサは高速動作可能 矛盾が生じないためにどうすればよいか CPU1 がアドレス A に X を格納 同時に CPU2 が Y を格納 X Y CPU1 と CPU2 が常時相互監視すればよいしかし 同時実行の効果が出ない CPU 数が増えると指数関数的に手間が増える 11
キャッシュコヒーレンス制御とは 要するに メモリ内容を更新したら 他のキャッシュを無効化すればよい ライトバックキャッシュでのライトインバリデートプロトコル (MSI プロトコルの場合 ) 1) 有効なデータが載っていないライン 無効状態 (Invalid) 2) 複数プロセッサが共有の可能性があるライン 共有状態 (Shared) 3) あるプロセッサが修正した可能性があるライン 修正状態 (Modified) 12
13 MSI プロトコル
14
15
An Example (looks like Intel MIC) CORE#0 CORE#58 CORE#59 Th#0 Int Th#1 Th#2 Float I1$ 32KB/8way Th#3 4threads/core Fmul 4/1 Fadd 4/1 Fdiv 20/20 Fsqrt 20/20 Miss:15cycle Th#0 Int Th#1 Th#2 Float I1$ 32KB/8way Th#3 Th#0 Int Th#1 Th#2 Float I1$ 32KB/8way Th#3 O1$ 32KB/8way inclusive Miss:15cycle O1$ 32KB/8way inclusive O1$ 32KB/8way inclusive L2$ 512KB/8way MOESI Miss->otherL2:15cycle Miss->Memory:200cycle L2$ 512KB/8way MOESI L2$ 512KB/8way MOESI L2RQ L2CC L2RQ L2CC L2RQ L2CC L2DIR #0 L2DIR #1 L2DIR #2 L2DIR #3 L2DIR #4 L2DIR #5 L2DIR L2DIR #62 L2DIR #63 2013/11/11 16 MMCC MMCC MMCC MMCC MainMem MainMem MainMem MainMem #0 #1 #2 #3
Sim_core.c Th#0 Th#1 Th#2 Th#3 I1$ is shared among thread and provides 1 instr./cycle (not 4 instr./cycle) Int Float I1$ 32KB/8way D1$ 32KB/8way inclusive L2$ 512KB/8way MOESI D1$ and L2$ have Valid, Dirty, Shared bits/line V0 invalid -> miss D0,S0 load hit, store miss(update L2dir) D1,S0 load hit, store hit D1,S1 load hit, store miss(invalidate other$) D0,S1 load hit, store miss(invalidate other$) L2RQ L2CC L1$ miss Select L1$ LRU- way to replace & extract line Writeback to L2$ (inclusive never miss) Request L2$ for load/store L2$ miss Select L2$ LRU-way to replace & extract line Req L2dir Writeback to MM Request L2dir to get line L2CC MMCC Wait for Ack L1$ fill Get line for L2$ Ack 2013/11/11 17
Sim_mreq.c L2RQ L2CC L2RQ L2CC L2RQ L2CC L2DIR #0 L2dir has V,D,S/line for each Core (hash is used in the real hardware) V0 Invalid, D0,S0 Exclusive, D0,S1 Shared D1,S0 Modified, D1,S1 Owned MMCC MMCC MMCC MMCC L2$ Invalidate Req: Others: Exclusive/Shared > Invalid Local: > Modified MM Writeback Req: Others: Exclusive/Shared > Invalid Local: > Invalid Read Req for load: Home: > Owned Others: no-change Local: > Shared If no HOME, data should be loaded from MM (Shared can be invalidated anytime) Read Req for store: Home: Copyback > Invalid Others: > Invalid Local: > Modified If no HOME, data should be loaded from MM (Shared can be invalidated anytime) L1$ miss Select L1$ LRU- way to replace & extract line 2013/11/11 18 Writeback to L2$ (inclusive never miss) Request L2$ for load/store L2$ miss Select L2$ LRU-way to replace & extract line Req L2dir Writeback to MM Request L2dir to get line L2CC MMCC Wait for Ack L1$ fill Get line for L2$ Ack
Sim_cluster.c MMCC MainMem #0 Simply gets the request from L2dir and sends ack to L2dir L1$ miss Select L1$ LRU- way to replace & extract line Writeback to L2$ (inclusive never miss) Request L2$ for load/store L2$ miss Select L2$ LRU-way to replace & extract line Req L2dir Writeback to MM Request L2dir to get line L2CC MMCC Wait for Ack L1$ fill Get line for L2$ Ack 2013/11/11 19
排他制御の必要性 複数スレッドが同一変数を更新 矛盾が生じないためにどうすればよいか スレッド 1 : A = A + 1; : 命令列 1 load A,r1 add r1,#1,r1 store A,r1 アドレス A 2 3 4 2 3 3 スレッド 2 : : A = A + 1; 命令列 2 load A,r2 add r2,#1,r2 : store A,r2 20 キャッシュコヒーレンス制御 は正しく動作しても 値は矛盾解決には 排他制御 が必要
排他制御とは Intel では cmpxchg reg, mem を使用 アトミック命令 %eax レジスタの値 = mem のロード値なら reg の値をストア %eax レジスタの値!= mem のロード値なら ロード値を reg に格納 Loop: スレッド1 mov #1,r0 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 Loop: スレッド2 mov #1,r0 mov #255,%eax lock cmpxchg r0, X brc r0!=255 load A,r1 add r1,#1,r1 store A,r1 mov #255,X クリティカルセクションと呼ぶ 21
排他制御とは ARM では ldrex および strex の組み合わせにより cmpxchg を実現 ldrex r0, X アドレス X をロックし r0 に読み出す -- この間 ロックが外される可能性有り -- strex r0, X アドレス X がロックされていれば r0 をストアする キャッシュの Modify 状態との相性が良く バスロック不要 cmpxchg (X, _old, _new) X の値 =_old の値なら _new を X にストア 22 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) を 32 個同時実行する場合の速度差の原因は? #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; } } #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; } } 4.3 秒 108 秒 23
演習問題 以下の 2 つのスレッドを同時実行する場合の実行時間は? #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[i*8] += k; } } 8 バイト 8=64 バイト異なるキャッシュラインに対応 #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[i] += k; } } 同一キャッシュラインに対応 A[0] A[0] A[1] A[2] A[3] A[1] 24