Microsoft PowerPoint ppt [互換モード]

(1)

計算機アーキテクチャ特論

• 前半（並列アーキテクチャの基本、枝廣） – 10/7, 10/21, 10/28, 11/11, 11/18, (12/2)（⽇程は予定） – 内容（変更の可能性あり） • 序論（マルチコア＝並列アーキテクチャ概論） • キャッシュ・コヒーレンシ、メモリ・コンシステンシ • 並列アーキテクチャモデル、ＯＳモデル • 並列プログラミングモデル、⾔語 • スケーラビリティに関する法則 – 講義のWWWサイト http://www.pdsl.jp/class/ から計算機アーキテクチャ特論のページに⼊る資料配布をしないので、事前にダウンロードして必要ならば印刷してくるように。資料は前⽇にはアップロードする予定

２０１３年１０⽉２８⽇枝廣

(2)

スヌープキャッシュの状態遷移

• ＭＥＳＩ

–

M（Exclusive Modified：モディファイド）

データが書き変わっている状態（主記憶と⼀致せず、⾃分だけがデータを持っている）

–

E（Exclusive Clean：イクスクルーシブ）

主記憶と⼀致し、⾃分だけが持っている

–

S（Shared Clean：シェアード）

主記憶と⼀致し、他のコアも同じデータを持っている

–

I（Invalid：インバリッド）

_無効状態

(3)

初期状態

I

(4)

PE1においてアドレスAへの書き込み

ライトミス

I→M

I

(5)

PE2においてアドレスAへの読み込み

M→S

リードミス

I→S

I

ＰＥ１ＰＥ２ＰＥ３

メモリへの書き込み

(6)

PE2においてアドレスAへの書き込み

S→I

ライトヒット

S→M

I

インバリデート

(7)

PE3においてアドレスAへの書き込み

I

M→I

ライトミス

I→M

インバリデート

(8)

⽬次

(9)

重要な用語：プロセス、タスク、スレッド

• 処理単位のことであるが、OS等により用語が異なる。それぞれの

違いに関して正確な定義はない

• プロセス

LinuxやWindowsなどの高機能OS上の処理単位など、個々に異なるアドレス空間を持つような最も疎な関係の処理単位

• タスク

プロセスよりは密（同じアドレス空間など）な関係の処理単位で、RTOS上の処理単位などで使われる用語 – マルチタスク処理＝並行実行可能な複数タスクを含む処理

• スレッド

プロセス、タスクよりは密な関係の処理単位で、一つの処理を複数プロセッサで実行するために分割した処理単位などで使われる用語 – マルチスレッド処理＝並行実行可能な複数スレッドを含む処理

• 一般に、プロセス＞タスク＞スレッドの順

に

オーバーヘッドが

大きく

、

右に行くほど

個々の処理単位の処理量を小さくすることができる

(10)

AMP型とSMP型のプログラムモデル

• AMP型はプロセッサごとの（別々のOS上の）プログラムとなり、プログラム間の同期・通信を記載する。CPUへのタスク（スレッド）割り当てはプログラム時に静的に⾏われる • SMP型はSMP OS上の⼀つのプログラムとなり、同期・通信も含め、並列化⽀援⾔語・APIとして記載する。SMP OSが負荷分散を考慮しながら動的にスレッド（タスク）をプロセッサに割り当てるスレッド７スレッド３スレッド５スレッド２スレッド１スレッド４スレッド６タスク７タスク３タスク５タスク２ OS CPU１ OS CPU２ OS CPU３ SMP OS

CPU１ CPU２ CPU３

CPU１向けプログラム CPU２向けプログラム CPU３向けプログラムタスク１タスク４タスク６並列化プログラム

AMP型

SMP型

(11)

プログラムが並列・並⾏実⾏可能に記述

• AMP型のプログラム

–

同期・通信以外は通常のソフトウェア

• SMP型のプログラム

(12)

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などがサポートしはじめている

(13)

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

(14)

#include <stdio.h> #include <math.h> #define DATA_NUM 100 int main() { BOOL primes[DATA_NUM]; int i;

Example2: Calculate Primes

/* 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; }

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?

(15)

#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; } thread_arg_t; マルチコア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;

Pthread (1/2)

Calc Primes

(16)

/* 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; 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]); }

Pthread (2/2)

(17)

#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; マルチコアCPUのための 並列プログラミング

void thread_func(void *arg) {

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;

Windows thread (1/2)

Calc Primes

(18)

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; } 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);

}

(19)

OpenMP

• OS スレッドライブラリは低レベル

–

プログラマはアーキテクチャを考慮し、粒度

や負荷分散を考えながら⾃分でプログラムを

切って記載する必要がある。

• OpenMP

–

C/C++/FORTRANの指⽰⾏として並列を記

載

–

USのコンパイラベンダが集まって開発

–

PC向けの開発環境などでサポートされている

–

http://www.openmp.org/

–

Fork-Join Model

–

粒度はランタイムによって決められる

(20)

#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;

OpenMP

Calc Primes

/* 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 */

(21)

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();

}

–‘sections’

ブロックのʻ}’で同期

(すべてのsectionはʼ}ʼで同期)

Banking

main()

Main thread

withdraw()

thread

deposit()

thread

balance()

thread

Customer Requests

(22)

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; –その他の指⽰⽂ • 総和 • バリア • アトミック • …

Video Decode

Decod e#1 Decod e#2 Decod e#3 Decod e#5 Decod e#8 Decod e#7 Decod e#4 Decod e#5

(23)

排他制御に関する⽤語

• クリティカルセクション

–

⼀度に⼀つのプロセスまたはスレッドのみが

実⾏可能なプログラムの部分

–

例：グローバル変数の書換

(素数の数のカウント)

• 共有リソース

–

メモリ、周辺デバイスなど

(24)

排他制御

時間

その他の

処理

クリティカル

セクション

その他の

処理

一度に一つのプロセス（スレッド）

のみが実行可能

例：グローバル変数の書換

共有リソースの利用

(25)

Lock - Unlock

時間

その他の

処理

クリティカル

セクション

その他の

処理

「ロック変数」 v を宣言

Thread A

Lock v

Thread A

は実行可能

Unlock v

Thread B

vがUnlock

されるまでWait

STOP

(26)

排他制御の例

• Mutex (= Mutual Exclusion)

–

ある変数のLock/Unlock

• セマフォ

–

リソースが複数ある場合に利⽤

–

利⽤可能なリソース数を保持し、リソースが

残っている限りプログラムはクリティカルセ

クションに⼊れる

–

Mutexはリソース数が⼀つの特殊ケースと考

えられる

(27)

pthread, POSIX セマフォ

• pthread mutex

–

pthread_mutex_init

• ロック変数の初期化

–

pthread_mutex_lock,

pthread_mutex_unlock

–

pthread_destroy

• POSIX セマフォ

–

sem_init

–

sem_wait, sem_post

–

sem_destroy

(28)

Windows Thread API

• クリティカルセクション

–

InitializeCriticalSection

–

EnterCriticalSection, LeaveCriticalSection

–

DeleteCriticalSection

• セマフォ

–

CreateSemaphore

–

WaitForSingleObject, ReleaseSemaphore

–

CloseHandle

(29)

#include <stdio.h> #include <math.h> #define DATA_NUM 100 int main() { BOOL primes[DATA_NUM]; int I, count;

Example2’: Calculate Primes

and count # of Primes

/* 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; } if (j > limit) count++; } /* Output */

printf("¥n"); return 0;

(30)

#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;

void thread_func(void *arg) {

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; }

Pthread (1/2)

Calc Primes

(31)

/* 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; 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]);

Pthread (2/2)

(32)

#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;

void thread_func(void *arg) {

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; }

Windows thread (1/2)

Calc Primes

(33)

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; } 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);

}

(34)

OpenMP

• Clause

–

付加情報

–

private, shared (変数)

–

reduction (演算)

• #pragma omp critical

• #pragma omp atomic

(35)

Reduction

Thread 1

counting

Thread 2

counting

Thread 3

counting

Thread 4

counting

Count

Final Result

(36)

#include <stdio.h> #include <math.h> #include <omp.h> #define DATA_NUM 100 int main() { BOOL primes[DATA_NUM]; int I, count; /* Initialize */

for (i = 0; i < DATA_NUM; i++) primes[i] = TRUE;

OpenMP

Calc Primes

/* 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++; } /* Output */

Microsoft PowerPoint ppt [互換モード]

計算機アーキテクチャ特論

２０１３年１０⽉２８⽇ 枝廣

スヌープキャッシュの状態遷移

•

ＭＥＳＩ

–

M（Exclusive Modified：モディファイド）

–

E（Exclusive Clean：イクスクルーシブ）

–

S（Shared Clean：シェアード）

–

I（Invalid： インバリッド）

初期状態

I

I

I

PE1においてアドレスAへの書き込み

ライトミス

I→M

I

I

PE2においてアドレスAへの読み込み

M→S

リードミス

I→S

I

メモリへの書き込み

PE2においてアドレスAへの書き込み

S→I

ライトヒット

S→M

I

インバリデート

PE3においてアドレスAへの書き込み

I

M→I

ライトミス

I→M

インバリデート

⽬次

重要な用語：プロセス、タスク、スレッド

• 処理単位のことであるが、OS等により用語が異なる。それぞれの

違いに関して正確な定義はない

• プロセス

• タスク

• スレッド

• 一般に、プロセス＞タスク＞スレッドの順

に

オーバーヘッドが

大きく

、

右に行くほど

個々の処理単位の処理量を小さくすることができる

AMP型とSMP型のプログラムモデル

AMP型

SMP型

プログラムが並列・並⾏実⾏可能に記述

•

AMP型のプログラム

–

同期・通信以外は通常のソフトウェア

•

SMP型のプログラム

SMP型マルチコア向けスレッド化プログラミング

•

OSが提供するスレッドライブラリ

•

⾔語仕様内、⾔語拡張のスレッドライブラリ

OS スレッドライブラリ

•

pthread

–

IEEE POSIX Section 1003.1c

POSIX: Portable Operating System

Interface

–

Nichols, Buttlar, and Farrell: Pthreads

Programming, OʼREILLY, 1998.

２０１３年１０⽉２８⽇枝廣

I（Invalid：インバリッド）