計算機アーキテクチャ特論 2013 年 10 28 枝廣 前半 ( 並列アーキテクチャの基本 枝廣 ) 10/7, 10/21, 10/28, 11/11, 11/18, (12/2)( 程は予定 ) 内容 ( 変更の可能性あり ) 序論 ( マルチコア= 並列アーキテクチャ概論 ) キャッシュ コヒーレンシ メモリ コンシステンシ 並列アーキテクチャモデル OSモデル 並列プログラミングモデル 語 スケーラビリティに関する法則 講義のWWWサイト http://www.pdsl.jp/class/ から計算機アーキテクチャ特論のページに る資料配布をしないので 事前にダウンロードして必要ならば印刷してくるように 資料は前 にはアップロードする予定 Page 1
スヌープキャッシュの状態遷移 MESI M(Exclusive Modified: モディファイド ) データが書き変わっている状態 ( 主記憶と 致せず 分だけがデータを持っている ) E(Exclusive Clean: イクスクルーシブ ) 主記憶と 致し 分だけが持っている S(Shared Clean: シェアード ) 主記憶と 致し 他のコアも同じデータを持っている I(Invalid: インバリッド ) 無効状態 Page 2
初期状態 PE1 PE2 PE3 I I I Page 3
PE1 においてアドレス A への書き込み PE1 PE2 PE3 ライトミス I M I I Page 4
PE2 においてアドレス A への読み込み PE1 PE2 PE3 リードミス M S I S I メモリへの書き込み Page 5
PE2 においてアドレス A への書き込み PE1 PE2 PE3 ライトヒット S I S M I インバリデート Page 6
PE3 においてアドレス A への書き込み PE1 PE2 PE3 ライトミス I M I I M インバリデート Page 7
次 スレッドプログラミング Page 8
重要な用語 : プロセス タスク スレッド 処理単位のことであるが OS 等により用語が異なる それぞれの違いに関して正確な定義はない プロセス Linux や Windows などの高機能 OS 上の処理単位など 個々に異なるアドレス空間を持つような最も疎な関係の処理単位 タスクプロセスよりは密 ( 同じアドレス空間など ) な関係の処理単位で RTOS 上の処理単位などで使われる用語 マルチタスク処理 = 並行実行可能な複数タスクを含む処理 スレッドプロセス タスクよりは密な関係の処理単位で 一つの処理を複数プロセッサで実行するために分割した処理単位などで使われる用語 マルチスレッド処理 = 並行実行可能な複数スレッドを含む処理 一般に プロセス > タスク > スレッドの順にオーバーヘッドが大きく 右に行くほど個々の処理単位の処理量を小さくすることができる 9
AMP 型と SMP 型のプログラムモデル AMP 型はプロセッサごとの ( 別々の OS 上の ) プログラムとなり プログラム間の同期 通信を記載する CPU へのタスク ( スレッド ) 割り当てはプログラム時に静的に われる SMP 型は SMP OS 上の つのプログラムとなり 同期 通信も含め 並列化 援 語 API として記載する SMP OS が負荷分散を考慮しながら動的にスレッド ( タスク ) をプロセッサに割り当てる CPU1 向けプログラム CPU2 向けプログラム CPU3 向けプログラム 並列化プログラム タスク 1 タスク 4 タスク 6 タスク 2 タスク 7 タスク 3 タスク 5 スレッド1 スレッド2 スレッド4 スレッド 3 スレッド 5 スレッド 7 スレッド 6 OS OS OS SMP OS CPU1 CPU2 CPU3 CPU1 CPU2 CPU3 AMP 型 SMP 型 10
プログラムが並列 並 実 可能に記述 AMP 型のプログラム 同期 通信以外は通常のソフトウェア SMP 型のプログラム スレッド プログラミング 11
SMP 型マルチコア向けスレッド化プログラミング OS が提供するスレッドライブラリ pthread IEEE の POSIX Section 1003.1c 規格 Linux などで標準的にサポート POSIX: Portable Operating System Interface Windows API Windows でサポート 語仕様内 語拡張のスレッドライブラリ Java Thread Java 語の中に標準で定義 OpenMP C/C++/FORTRAN を並列プログラム可能にするために 国コンパイラベンダグループによって作られた指 パソコン向けの開発環境などで標準的にサポート TBB Intel 社が開発した 語 C/C++ で使える 動的な負荷分散などをランタイムで う TPL Microsoft 社の 語.NET に含まれており C#, VB で使える Cilk MIT で開発された 語 ANSI C で使える Intel などがサポートしはじめている 12
OS スレッドライブラリ pthread IEEE POSIX Section 1003.1c POSIX: Portable Operating System Interface Nichols, Buttlar, and Farrell: Pthreads Programming, OʼREILLY, 1998. Linux などで標準 pthread_create, pthread_join Windows Thread API CreateThread, WaitForMultipleObjects 13
Example2: Calculate Primes #include <stdio.h> #include <math.h> #define DATA_NUM 100 int main() { BOOL primes[data_num]; int i; If primes[i] is TRUE (j is a prime), and (i % j == 0) ( i is multiple number of j), i is an prime. If j is not a prime, we don t have to check if I is multiple number of j. Why? /* Check */ for (i = 0; i < DATA_NUM; i++) { primes[i] = TRUE; limit = (int)sqrt((double)i); for (j = 2; j <= limit; j++) if (primes[j] && i % j == 0) { primes[i] = FALSE; break; /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); printf(" n"); return 0; 14
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 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; typedef struct _thread_arg { int id; bool *primes; thread_arg_t; Calc Primes マルチコア CPU のための並列プログラミング ( 秀和システムズ ) より /* 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; return; 15
int main() { pthread_t handle[thread_num]; thread_arg_t targ[thread_num]; bool primes[data_num]; int i; /* Initialize */ for (i = 0; i < DATA_NUM; i++) primes[i] = true; /* Start */ for (i = 0; i < THREAD_NUM; i++) { targ[i].id = i; targ[i].primes = primes; 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); /* Output */ for (i = 2; i < DATA_NUM; i++) if (primes[i]) printf("%d ", i); printf(" n"); return 0; Pthread (2/2) 16
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; thread_arg_t; Calc Primes マルチコア CPU のための並列プログラミング ( 秀和システムズ ) より 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; return; 17
int main() { HANDLE handle[thread_num]; thread_arg_t targ[thread_num]; BOOL primes[data_num]; int i; for (i = 0; i < DATA_NUM; i++) { primes[i] = TRUE; for (i = 0; i < THREAD_NUM; i++) { targ[i].id = i; targ[i].primes = primes; handle[i] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)thread _func, (void *)&targ[i], 0, NULL); WaitForMultipleObjects(THREAD_NUM, handle, TRUE, INFINITE); /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); printf(" n"); return 0; Windows thread (2/2) 18
OpenMP OS スレッドライブラリは低レベル プログラマはアーキテクチャを考慮し 粒度や負荷分散を考えながら 分でプログラムを切って記載する必要がある OpenMP C/C++/FORTRAN の指 として並列を記載 US のコンパイラベンダが集まって開発 PC 向けの開発環境などでサポートされている http://www.openmp.org/ Fork-Join Model 粒度はランタイムによって決められる 19
OpenMP #include <stdio.h> #include <math.h> #include <omp.h> #define DATA_NUM 100 int main() { BOOL primes[data_num]; int i; /* Initialize */ #pragma omp parallel for for (i = 0; i < DATA_NUM; i++) primes[i] = TRUE; Calc Primes /* Check */ #pragma omp parallel for for (i = 0; i < DATA_NUM; i++) { primes[i] = TRUE; limit = (int)sqrt((double)i); for (j = 2; j <= limit; j++) if (primes[j] && i % j == 0) { primes[i] = FALSE; break; /* Output */ for (i = 2; i < DATA_NUM; i++) { if (primes[i] == 1) printf("%d ", i); printf(" n"); return 0; 20
Software for SMP (OpenMP) Example of OpenMP (Banking) Execute section s in Parallel within sections block #pragma omp parallel sections { #pragma omp section main(); #pragma omp section withdraw(); #pragma omp section deposit(); #pragma omp section balance(); Customer Requests sections ブロックの ʻ で同期 ( すべての section は ʼʼ で同期 ) 21 Banking main() Main thread withdraw() thread deposit() thread balance() thread
Software for SMP (OpenMP) Example of OpenMP (Video Decode) for-loop with for Directive is executed in Parallel #pragma omp parallel for for(i=1; i<=n; i++) Decode#i; Decod e#1 Video Decode Decod e#2 Decod e#3 Decod e#4 その他の指 総和 バリア アトミック Decod e#5 Decod e#8 Decod e#7 Decod e#5 22
排他制御に関する 語 クリティカルセクション 度に つのプロセスまたはスレッドのみが実 可能なプログラムの部分 例 : グローバル変数の書換 ( 素数の数のカウント ) 共有リソース メモリ 周辺デバイスなど 23
排他制御 その他の処理 時間 クリティカルセクション 一度に一つのプロセス ( スレッド ) のみが実行可能例 : グローバル変数の書換共有リソースの利用 その他の処理 24
Lock - Unlock 時間 その他の処理 クリティカルセクション ロック変数 v を宣言 Thread A Lock v Thread A は実行可能 Thread B STOP vがunlock されるまでWait その他の処理 Unlock v 25
排他制御の例 Mutex (= Mutual Exclusion) ある変数の Lock/Unlock セマフォ リソースが複数ある場合に利 利 可能なリソース数を保持し リソースが残っている限りプログラムはクリティカルセクションに れる Mutexはリソース数が つの特殊ケースと考えられる 26
pthread, POSIX セマフォ pthread mutex pthread_mutex_init ロック変数の初期化 pthread_mutex_lock, pthread_mutex_unlock pthread_destroy POSIX セマフォ sem_init sem_wait, sem_post sem_destroy 27
Windows Thread API クリティカルセクション InitializeCriticalSection EnterCriticalSection, LeaveCriticalSection DeleteCriticalSection セマフォ CreateSemaphore WaitForSingleObject, ReleaseSemaphore CloseHandle 28
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, 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; 29
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; 30
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) 31
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; 32
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) 33
OpenMP Clause 付加情報 private, shared ( 変数 ) reduction ( 演算 ) #pragma omp critical #pragma omp atomic ある に対するクリティカルセクション 34
Reduction Thread 1 Thread 2 Thread 3 Thread 4 counting counting counting counting Count Final Result 35
OpenMP #include <stdio.h> #include <math.h> #include <omp.h> #define DATA_NUM 100 int main() { BOOL primes[data_num]; int I, 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; 36