計算機アーキテクチャ特論 A 2017 年 11 6 枝廣 計算機アーキテクチャ特論 A 並列アーキテクチャの基本 ( 枝廣 ) 10/2, 10/16, 10/23, 10/30, 11/6, 11/13, (11/20( 予備 )) 内容 ( 変更の可能性あり ) 序論 ( マルチコア= 並列アーキテクチャ概論 ) キャッシュ コヒーレンシ メモリ コンシステンシ 並列プログラミングモデル 語 並列に関する法則 同期 並列アルゴリズム 並列化の課題 資料置場 : http://www.pdsl.jp/class/ Page 1
同期のためのハードウェアとソフトウェアとの協調 同期の必要性 ( 排他制御 ) 排他制御のための基本ソフトウェア関数と仕組み ミューテックス ( ロックとアンロック ) セマフォ 基本ソフトウェア関数の実現 必須のハードウェア機構 : アトミック命令 アトミック命令の例とロックの実現 スワップ ロードリンクト ストアコンディショナル Page 2
排他制御 問 : 下図のような銀 預 システムにおいて つのスレッドから同時に読み書き可能な場合 問題が起こることがある どのような場合か説明せよ スレッド 1: 10 万円預ける スレッド 2: 10 万円下ろす 何らかの同期を とることが必要 1 2 3 4 預金残高 100 万円
Page 4 同期のためのハードウェアとソフトウェアとの協調 同期の必要性 ( 排他制御 ) 排他制御のための基本ソフトウェア関数と仕組み ミューテックス ( ロックとアンロック ) Mutex (Mutual Exclusion): 相互排他 セマフォ 基本ソフトウェア関数の実現 必須のハードウェア機構 : アトミック命令 アトミック命令の例とロックの実現 スワップ ロードリンクト ストアコンディショナル
Mutex (Lock Unlock) を いた排他制御の実現 その他の処理 Thread 1 Thread 2 時間 預金残高の変更 ( クリティカルセクション ) Lock Thread 1 は実行可能 STOP Unlock されるまでWait Unlock その他の処理
排他制御の例 Mutex (= Mutual Exclusion) ある変数の Lock/Unlock セマフォ リソースが複数ある場合に利 利 可能なリソース数を保持し リソースが残っている限りプログラムはクリティカルセクションに れる Mutexはリソース数が つの特殊ケースと考えられる 6
pthread, POSIX セマフォ pthread mutex pthread_mutex_init ロック変数の初期化 pthread_mutex_lock, pthread_mutex_unlock pthread_destroy POSIX セマフォ sem_init sem_wait, sem_post sem_destroy 7
Windows Thread API クリティカルセクション InitializeCriticalSection EnterCriticalSection, LeaveCriticalSection DeleteCriticalSection セマフォ CreateSemaphore WaitForSingleObject, ReleaseSemaphore CloseHandle 8
Example2 : Calculate Primes and count # of Primes /* Check */ for (i = 0; i < DATA_NUM; i++) { #include <stdio.h> #include <math.h> #define DATA_NUM 100 int main() { BOOL primes[data_num]; int I, j, count; primes[i] = TRUE; limit = (int)sqrt((double)i); for (j = 2; j <= limit; j++) if (primes[j] && i % j == 0) { primes[i] = FALSE; break; } if (j > limit) count++; } } /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); } printf(" n"); return 0; 9
Pthread (1/2) #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <math.h> #include <pthread.h> #define THREAD_NUM 3 #define DATA_NUM 100 typedef struct _thread_arg { int id; bool *primes; pthread_mutex_t *mutex; } thread_arg_t; int count; Calc Primes void thread_func(void *arg) { thread_arg_t* targ = (thread_arg_t *)arg; int c_start, c_end, range, limit; int i, j; } /* Determine Range of Values to be Checked */ range = (DATA_NUM - 2) / THREAD_NUM + 1; c_start = 2 + targ->id *range; c_end = 2 + (targ->id+1) *range; if (c_end > DATA_NUM) c_end = DATA_NUM; /* Check */ for (i = c_start; i < c_end; i++) { limit = (int)sqrt((double) i); for (j = 2; j <= limit; j++) if (targ->primes[j] && i % j == 0) { targ->primes[i] = false; break; } if(j > limit) { pthread_mutex_lock(targ->mutex); count++; pthread_mutex_unlock(targ->mutex); } } return; 10
int main() { pthread_t handle[thread_num]; thread_arg_t targ[thread_num]; bool primes[data_num]; int i; pthread_mutex_t mutex; /* Initialize */ for (i = 0; i < DATA_NUM; i++) primes[i] = true; /* Initialize mutex variable */ pthread_mutex_init(&mutex, NULL); /* Start */ for (i = 0; i < THREAD_NUM; i++) { targ[i].id = i; targ[i].primes = primes; targ[i].mutex = &mutex; pthread_create(&handle[i], NULL, (void*)thread_func, (void*)&targ[i]); } /* Wait for All Threads */ for (i = 0; i < THREAD_NUM; i++) pthread_join(handle[i], NULL); /* Destroy Mutex Variable */ pthread_mutex_destroy(&mutex); /* Output */ for (i = 2; i < DATA_NUM; i++) if (primes[i]) printf("%d ", i); printf(" n"); return 0; Pthread (2/2) 11
Windows thread (1/2) #include <stdio.h> #include <windows.h> #include <math.h> #define THREAD_NUM 3 #define DATA_NUM 100 typedef struct _thread_arg { int id; BOOL *primes; CRITICAL_SECTION *cs; } thread_arg_t; int count; Calc Primes void thread_func(void *arg) { thread_arg_t* targ = (thread_arg_t *)arg; int c_start, c_end, range, limit; int i, j; } /* Determine Range of Values to be Checked */ range = (DATA_NUM - 2) / THREAD_NUM + 1; c_start = 2 + targ->id * range; c_end = 2 + (targ->id + 1) * range; if (c_end > DATA_NUM) c_end = DATA_NUM; /* Check */ for (i = c_start; i < c_end; i++) { limit = (int)sqrt((double)i); for (j = 2; j <= limit; j++) if (targ->primes[j] && i % j == 0) { targ->primes[i] = FALSE; break; } if(j > limit) { EnterCriticalSection(targ->cs); count++; LeaveCriticalSection(targ->cs); } } return; 12
int main() { HANDLE handle[thread_num]; thread_arg_t targ[thread_num]; BOOL primes[data_num]; int i; CRITICAL_SECTION cs; for (i = 0; i < DATA_NUM; i++) { primes[i] = TRUE; } /* Initialize critical section variable */ InitializeCriticalSection(&cs); for (i = 0; i < THREAD_NUM; i++) { targ[i].id = i; targ[i].primes = primes; targ[i].mutex = &cs; handle[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)thread_ func, (void *)&targ[i], 0, NULL); } WaitForMultipleObjects(THREAD_NUM, handle, TRUE, INFINITE); } /* Destroy critical section Variable */ DeleteCriticalSection(&cs); /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); } printf(" n"); return 0; Windows thread (2/2) 13
OpenMP Clause 付加情報 private, shared ( 変数 ) reduction ( 演算 ) #pragma omp critical #pragma omp atomic ある に対するクリティカルセクション 14
Reduction Thread 1 Thread 2 Thread 3 Thread 4 counting counting counting counting Count Final Result 15
OpenMP #include <stdio.h> #include <math.h> #include <omp.h> #define DATA_NUM 100 int main() { BOOL primes[data_num]; int I, j, count; /* Check */ #pragma omp parallel for reduction(+;count) private(limit, j) for (i = 0; i < DATA_NUM; i++) { limit = (int)sqrt((double)i); for (j = 2; j <= limit; j++) if (primes[j] && i % j == 0) { primes[i] = FALSE; break; } if (j > limit) count++; } /* Initialize */ #pragma omp parallel for for (i = 0; i < DATA_NUM; i++) primes[i] = TRUE; Calc Primes } /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); } printf(" n"); return 0; 16
Mutex (Lock/Unlock) の仕組み 共有資源 ( 今の場合預金残高やカウンタ あるいはクリティカルセクション ) ごとに変数 ( ロック変数とよぶ ) を持つ ロック変数が未使用 使用中のフラグとなり 未使用 を読むことができたスレッドはロック変数を 使用中 に書き換えて先に進む ( ロック取得 ) 共有資源の利用が終われば 未使用 に戻す (unlock) ただし ロック変数を同時に読み書きできると同じ問題が起こる ロック変数をロックする??? プロセッサにはアトミックなメモリアクセスを支援するハードウェア機構が存在することが普通であり それを使う アトミックなメモリアクセス : メモリへの 読み と 書き の処理が他のプロセッサからの処理に割り込まれずに行われること Page 17
Mutex (Lock/Unlock) の仕組み ( スピンロック ) 開始 スピンウェイトまたはビジーウェイト ロック変数を読み, 1 を書き込む操作をアトミックに実行 No 読んだ値 =0? クリティカルセクションに入る Yes ( ロック成功 ) クリティカルセクションから出る ロック変数を 0 に ( ロック解除 ) 終了 Page 18
Page 19 スピンロック
セマフォ Mutex (Lock/Unlock) は つの共有資源に対する相互排他 セマフォ : 複数共有資源の管理 P 操作 : 資源を取得するときの操作 V 操作 : 資源を開放するときの操作 P(i) V(i) Si Si -1 Si Si+1 Si <0? Yes Si 0? Yes No P(i) を発行したプロセスを続行 P(i) を発行したプロセスを資源 i に対する待ち行列 Q(i) に入れて待機状態にする (a) 資源 i に対する P 操作 No 終了 資源 i に対する待ち行列 Q(i) からプロセスを取り出し実行 (b) 資源 i に対する V 操作 Page 20
Page 21 セマフォ (1)
Page 22 セマフォ (2)
Page 23 セマフォ (3)
Page 24 セマフォを使った待ち合わせ
同期のためのハードウェアとソフトウェアとの協調 同期の必要性 ( 排他制御 ) 排他制御のための基本ソフトウェア関数と仕組み ミューテックス ( ロックとアンロック ) セマフォ 基本ソフトウェア関数の実現 必須のハードウェア機構 : アトミック命令 アトミック命令の例とロックの実現 スワップ ロードリンクト ストアコンディショナル Page 25
使用中アトミックなメモリアクセスとは アトミックなメモリアクセスとは : メモリへの 読み と 書き の処理が他のプロセッサからの処理に割り込まれずに われること 右図で 共有リソースの使 権を得るために 未使 を つだけ準備し これを読んだ CPU が使 権を得るとする ( 使 権を得たならば 使 中 と書き換え 終了後 未使 に戻す ) 1 2 3 4 の順で処理が われれば CPU1 が使 権を得て CPU2 は使 中を読むので問題は起こらない もしも 1 2 の間に 3 の処理が割り込むと CPU1,2 の両 が使 権を得る このようなことが起こらないようなハードウェアサポートが重要であり プロセッサは アトミックなメモリアクセス を うための命令を持つ CPU1 CPU2 2 1 未使用使用中3 共有リソース 4 26
アトミック命令の例 (ARM の SWAP) SWAP reg, [Addr] レジスタ値 (reg) とメモリ値 ([Addr]) とのアトミックな交換 Lock Example ([0x60] = 0: Not Use, 1: Used) L1: mov r1,#1 swap r1,[0x60] jeq r1,#1,l1 Used Unlock Example mov r1,#0 st r1,[0x60] Not Use HW 0x60 CPU1 DSP Mem Used 27
Lock --- Example 1 L1: mov r1,#1 CPU r1=1 HW Mem [0x60]=0 Unlock DSP 28
Lock --- Example 1 swap r1,[0x60] CPU r1=1 0 Get Lock! HW Mem [0x60]=0 1 Lock! DSP 29
Lock --- Example 1 jeq r1,#1,l1 CPU r1=0 Go Ahead! HW Mem [0x60]=1 Lock! DSP 30
Lock --- Example 2 L1: mov r1,#1 CPU r1=1 HW Mem [0x60]=1 Lock DSP 31
Lock --- Example 2 swap r1,[0x60] CPU r1=1 1 HW [0x60]=1 1 Lock DSP Mem 32
Lock --- Example 2 jeq r1,#1,l1 CPU HW r1=1 Cannot Get Lock, Return to L1 (Loop Until CPU Gets Lock.) Mem [0x60]=1 Still Locked DSP 33
Unlock --- Example mov r1,#0 CPU r1=0 HW Mem [0x60]=1 Lock DSP 34
Unlock --- Example st r1,[0x60] CPU 0 r1=0 HW [0x60]=1 Unlock 0 DSP Mem Store to [0x60] 35
Swap --- Why Swap? swap r1,[0x60] CPU r1=1 0 HW [0x60]=0 1 Unlock DSP Mem 36
Swap --- Whatʼs Swap? swap r1,[0x60] Load from [0x60] 0 HW [0x60]=0 Unlock 1 CPU 1 r1=1 DSP 0 Mem Store to [0x60] 37
Resource Conflict (3) Why is SWAP necessary? If LD/ST instructions are used instead of SWAP, Case: P1 and P2 require a resource at the same time (P1) LD r1,[0x60] ; P1 loads value 0 (P2) LD r1,[0x60] ; P2 loads value 0 as well Both Processors get the right! Case: P1 s Lock and P2 s Unlock happens at the same time (P1) LD r1,[0x60] ; P1 loads value 1 (P2) ST r1,[0x60] ; P2 stores value 0 (P1) ST r1,[0x60] ; P1 stores value 1 P1 overwrites the unlock by P2. The resource cannot be locked any more! 38
Swap --- Case 1 r1=1 0Get Lock! (P1) Load from [0x60] 0 HW [0x60]=0 Unlock CPU DSP Mem (P2)Load from [0x60] 0 Get Lock! 39
Swap --- Case 1 (P1) Load from [0x60] 0 HW [0x60]=0 Unlock Lock! 1 CPU 1 r1=1 DSP 0Go Ahead! Mem Store to [0x60] (P2)Load from [0x60] 0 Go Ahead! 40
Swap --- Case 2 CPU r1=0 Trying to Get Lock HW Mem [0x60]=1 Lock P2 Has Lock. DSP 41
Swap --- Case 2 r1=1 Cannot Get Lock! (P1) Load from [0x60] HW [0x60]=1 Lock 1 CPU DSP Mem P2 Has Lock! 42
Swap --- Case 2 r1=1 Cannot Get Lock! (P1) Load from [0x60] 1 HW [0x60]=1 0 Lock Unlock! CPU DSP Mem (P2)Store to [0x60] 0 P2 Releases Lock! 43
Swap --- Case 2 (P1) Load from [0x60] 1 HW [0x60]=1 0 1 Lock Unlock! Lock! 1 CPU r1=1 DSP Cannot Get Lock! Mem (P2) Store to [0x60] (P2)Store to [0x60] Loop INFINITELY! 0 P2 Doesn t have Lock. Nobody can lock ANYMORE! 44
Page 45 アトミック命令を実現するためのハードウェア CPU1 上のSW1がメモリの値を読んで (1) 書き終わる (2) までCPU2はメモリアクセスできない メモリシステムのロック 用用中CPU2 ( ( 1 未使 CPUはバスに対して ロックアクセス を うことができ そ の間他のCPUはバスにアクセスできない きな負荷となる 中CPU1 SW1 SW2 1 3 CPU1 CPU2 2 キャッシュ 1 4 ) ) 使使共有リソース 0 用( )
ロードリンクト ストアコンディショナル (LLSC) LLbit 特殊なハードウェア機構 address で されたメモリ領域の排他状態を保持する LLbitはLL 命令において排他状態に設定され,SC 命令においてこれを いて同じプロセッサからの同じ共有変数に対するSC 命令のみが成功するように動作する. ハードウェアのロックがない Page 46
Page 47 ロードリンクト ストアコンディショナル (LLSC)
Page 48 LLSC を いたスピンロックの実現