Microsoft PowerPoint ppt [互換モード]

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

•

前半（並列アーキテクチャの基本、枝廣）

–

10/3, 10/17,

10/24

, 10/31, 11/7, 11/14（⽇程は予定）

–

内容（変更の可能性あり）

• 序論（マルチコア＝並列アーキテクチャ概論） • キャッシュ・コヒーレンシ、メモリ・コンシステンシ • 並列プログラミングモデル、⾔語 • スケーラビリティに関する法則 • 同期 • 並列アルゴリズム、並列化の課題

–

資料置場︓

http://www.pdsl.jp/class/

•

後半（先端トピックス、本⽥）

–

11/21〜

–

内容（変更の可能性あり）

２０１６年１０⽉２４⽇ 枝廣

プログラムモデルに関する⽤語

(分類ではない)

•

データ並列 (= SIMD)

•

Fork-Join

•

ワークシェアリング

•

⽣産者－消費者

•

パイプライン

START

JOB1 JOB2

_・・・

JOBn

FORK

END

JOIN

main()

withdraw()

deposit()

balance()

Work Share

Data-Base

Producer

Consumer

1 2 3

Time

Pipelining

Proc. 1 Proc. 2 Proc. 3 1 2 3

Example 1

•

for (i=0; i<10000; i++) {

proc1(i);

proc2(i);

proc3(i);

proc4(i);

}

Example 1

•

for (i=0; i<10000; i++) {

proc1(i);

proc2(i);

proc3(i);

proc4(i);

}

proc1()

proc2()

proc3()

proc4()

START

i=1 – 1000 1001-2000 9001-10000

・・・

FORK

END

JOIN

Time

Pipelining

Proc. 1 Proc. 2 Proc. 3 Proc. 4 1 2 3 4 1 2 3 4 (i=0) (i=1)

並列プログラム設計

•

今⽇のトピック

–

Fosterによる設計⽅法論

–

参考⽂献:

M. Quinn: Parallel Programming in C with

MPI and OpenMP, McGraw-Hill, 2003.

(This book refers: I. Foster: Designing

and Building Parallel Programs: Concepts

and Tools for Parallel Software

並列プログラム設計

•

タスク・チャネルモデル

–

タスク: プログラム、内蔵メモリ、⼊出⼒ポ

ート

–

チャネル︓メッセージキュー。あるタスクの

出⼒ポートと別のタスクの⼊⼒ポートを接続

する

–

受信タスク︓ブロック、同期︓タスクは出⼒

タスクからの値が準備できるまで先に進めな

い

–

送信タスク: ⾮ブロック、⾮同期︓タスクは

⼊⼒タスクの受信準備を待たずに先に進める

Fosterによる設計⽅法論

（まずは、プロファイラなどを使ってホットスポット（＝

もっとも時間がかかっていて並列化する価値がある関数な

ど）を⾒つける）

1. Partitioning

2. Communication

3. Agglomeration

4. Mapping

Partitioning

•

可能な限りの並列性を⾒つけ、要素タス

クを抽出する

–

Domain decomposition

1. データを分割する

2. 分割されたデータに計算を関連付ける⽅法を決

める

–

Functional Decomposition

1. 計算を分割する

2. 分割された個々の計算にデータを関連付ける⽅

法を決める

Pipelining

Data

Ti

m

e

Track position of  instrument Track position of  instrument Determine image location Determine image location Display Image Display Image Track position of  instrument Track position of  instrument Determine image location Determine image location Display Image Display Image Track position of  instrument Track position of  instrument Determine image location Determine image location Display Image Display Image Track position of  instrument Track position of  instrument Determine image location Determine image location Display Image Display Image

Fosterによるチェックリスト (Partitioning)

•

少なくとも想定する計算機が持つプロセッサ数よりも

⼀桁多いタスクがあること (この条件が満たされない

場合、後の設計⾃由度が⼤幅に制約を受ける)

•

冗⻑な計算やデータ構造が最⼩化されていること (

この条件が満たされない場合、問題規模が⼤きくなっ

た時に⼗分な性能が得られない場合がある)

•

要素タスクはおおよそ同じサイズであること (もしも

違うならば、プロセッサ間の負荷分散が難しくなる場

合がある)

•

タスク数が問題規模に応じた増加関数であること (も

しも違うならば、より規模の⼤きい問題に対して、よ

り多くのプロセッサを使うことが不可能になる場合が

ある)

Communication

•

局所的通信

–

ある計算実⾏において少数のタスクのみが関与す

る

•

⼤域的通信

–

ある計算実⾏において多くのタスクが関与する

•

⼤域的な通信は局所的通信と⽐べてオーバー

ヘッドが⼤きい

–

アーキテクチャに依存する

–

通信に分散メモリ型を使う場合⼤きなオーバーヘ

ッドとなる

Examples of Many-Core Architecture

CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU CPU Memory CPU CPU CPU CPU Mem CPU CPU CPU CPU Mem CPU CPU CPU CPU Mem CPU CPU CPU CPU Mem

near

_far

クラスタ内は集中メモリ

クラスタ間は分散メモリ

Cf. Tileraは等距離

通信時間

CPU1

ALU1 ALU2 ALU3 ALU4

SMP OS1

CPU2

ALU1 ALU2 ALU3 ALU4

CPU3

ALU1 ALU2 ALU3 ALU4

APP

_APP

_{APP APP}

_APP

_APP

APP

_APP

_APP

CPU4

ALU1 ALU2 ALU3 ALU4

SMP OS2

CPU5

ALU1 ALU2 ALU3 ALU4

CPU6

ALU1 ALU2 ALU3 ALU4

APP

_APP

_{APP APP}

_APP

_APP

APP

_APP

_APP

No Overhead

for Software

(Superscalar,

SIMD)

<10

2

_{Cycles per Variable,}

10

3

_{Cycles per Thread}

> 10

4

_{Cycles per Variable (Packet)}

Fosterによるチェックリスト (Communication)

•

通信はタスク間でバランスされているこ

と

•

各タスクは少数の隣接タスクとのみ通信

していること

•

それぞれのタスクが並⾏して通信処理を

実⾏できること

•

それぞれのタスクが並⾏して計算処理を

実⾏できること

Agglomeration（集塊、凝集）

•

性能やプログラム容易性を向上させるため、

タスクのグループ化を⾏ってより⼤きなタス

クにする処理

–

通信オーバーヘッドの減少

•

局所性の増⼤

•

送信タスクや受信タスクのグループ化

–

並列設計のスケーラビリティの維持

•

例︓(8 x 128 x 256)３次元⾏列演算

•

第⼀次元でagglomerationを⾏うと、

– 4 CPU: 2 x 128 x 256 per CPU – 8 CPU: 1 x 128 x 256 per CPU

Fosterによるチェックリスト (Agglomeration)

•

Agglomerationによって並列アルゴリズムの局所性が

増⼤していること

•

計算の複製によって通信を利⽤するよりも処理時間が

減少していること

•

データの複製は⼗分少なく、アルゴリズムのスケーラ

ビリティを損なっていないこと

•

グループ化後のそれぞれタスクは同様の計算および通

信時間を有していること

•

タスク数は問題規模に応じて増加関数であること

•

タスク数は可能な限り少なく、しかしながら少なくと

も想定計算機のプロセッサ数と同程度であること

•

Agglomerationの選択と既存コード改変コストとのト

計算の複製

Step 1 Step 2 Step 3‐1 Step 3‐2

communication

Step 1 Step 2 Step 3‐1 Step 1 Step 2 Step 3‐2

どちらが高速

_?

データの複製

Step 1 Step 2 Step 3‐1 Step 3‐2 Step 1 Step 2 Step 3‐1 Step 1 Step 2 Step 3‐2 Data1 Data2 Data3‐1

CPU1

_CPU2

_CPU1

_CPU2

Data3‐2 Data1 Data2 Data3‐1 Data3‐2 Data1 Data2

Mapping

•

タスクをプロセスに割り当てる処理

•

分散メモリを仮定

–

集中メモリ型計算機であれば、ＯＳが⾃動的

に割り当てるため

•

プロセッサ利⽤率最⼤化かつプロセッサ

間通信最⼩化

–

プロセッサ利⽤率 --- 現在考えている問題の

解法において実際にプロセッサが動作してい

る時間の割合の平均値

Mapping最適化

•

プロセッサ利⽤率最⼤化とプロセッサ間

通信最⼩化はしばしば競合する.

•

例︓すべてのタスクを⼀つのプロセッサ

に割り付ければ

→ プロセッサ利⽤率は最悪であるが、プ

ロセッサ間通信は最善（０）となる

•

NP-Hard

Fosterによるチェックリスト (Mapping)

•

プロセッサあたり１タスクにする設計と、プ

ロセッサあたり複数タスクにする設計につい

て考慮済であること

•

静的および動的割付について評価済であるこ

と

•

タスクの動的割付を使う場合、管理プログラ

ム（タスクアロケータ）が性能のボトルネッ

クになっていないこと

•

タスクの静的割当を使う場合、タスク数とプ

ロセッサ数の割合が少なくとも10:1はある

こと

Mappingについて

• AMP型では、静的にMappingする

• SMP型では、Mappingを指定することなく（つ

まりMappingの段階がなく）OSに任せる

スレッド７ スレッド３ スレッド５ スレッド２ スレッド１ スレッド４ スレッド６ タスク７ タスク３ タスク５ タスク２ OS OS OS SMP OS CPU１向け プログラム CPU２向け プログラム CPU３向け プログラム タスク１ タスク４ タスク６ 並列化プログラム

•

AMP型のプログラム

–

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

•

SMP型のプログラム

–

スレッド・プログラミング

→本⽇の後半の話題

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

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

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

• プロセス

LinuxやWindowsなどの高機能OS上の処理単位など、個々に異なるアドレス空

間を持つような最も疎な関係の処理単位

• タスク

プロセスよりは密（同じアドレス空間など）な関係の処理単位で、RTOS上の処

理単位などで使われる用語

– マルチタスク処理＝並行実行可能な複数タスクを含む処理

• スレッド

プロセス、タスクよりは密な関係の処理単位で、一つの処理を複数プロセッサで

実行するために分割した処理単位などで使われる用語

– マルチスレッド処理＝並行実行可能な複数スレッドを含む処理

• 一般に、プロセス＞タスク＞スレッドの順にオーバーヘッドが大きく、

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で使える

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

#include <stdio.h>

#include <math.h>

#define DATA_NUM 100

int main() {

BOOL primes[DATA_NUM];

int I,j;

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

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.

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

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

Pthread (1/2)

Calc Primes

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

Pthread (2/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;

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

Windows thread (1/2)

Calc Primes

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

}

OpenMP

•

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

–

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

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

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

•

OpenMP

–

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

載

–

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

–

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

–

http://www.openmp.org/

–

Fork-Join Model

#include <stdio.h>

#include <math.h>

#include <omp.h>

#define DATA_NUM 100

int main() {

BOOL primes[DATA_NUM];

int I,j;

/* Initialize */

#pragma omp parallel for

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

OpenMP

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

}

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’

ブロックのʻ}’で同期

Banking

main()

Main thread

withdraw()

thread

deposit()

thread

balance()

thread

Customer Requests

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