並列プログラミングの問題と解決
インテル® Cilk™ Plus によるソリューション

インテル株式会社
ソフトウェア&サービス統括部
April 22’ 2011

Intel、インテル、 Intel ロゴ、「Intel.さあ、その先へ。」ロゴ、Intel Core、Itanium、MMX、Pentium、Xeon 、VTune、Cilk は、アメリカ合衆国およびその他の国における Intel Corporation またはその子会社の商標または登録商標です。
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

内容
•

•

ソフトウェア開発のトレンド-

ソフトウェア開発における 6 のトレンド
ソフトウェア全体に与える影響の比較
並行プログラミングにおける 3 の原理

並列プログラミングにおける問題とインテル® Cilk™ Plus によるソリューション

-並列指向
並列プログラミングにおける問題の分離決定性の問題2© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

内容
•

•

ソフトウェア開発のトレンド-

ソフトウェア開発における 6 のトレンド
ソフトウェア全体に与える影響の比較
並行プログラミングにおける 3 の原理

並列プログラミングにおける問題とインテル® Cilk™ Plus によるソリューション

-並列指向
並列プログラミングにおける問題の分離決定性の問題3© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

ソフトウェア開発における 6 つのトレンドそれぞれ 1958 年から 1973 年の間に誕生し、1990 年代/2000 年代に台頭し始めて、5 年強をかけて成熟したツール/言語/フレームワーク/ランタ
イム体系が構築されたGUI

オブジェクト GC

ジェネリックNet

並列化

大きな相違点: 並行化時代の到来は察知できていた1990 1992 1994 1996 1998 2000 2002 2004 2006 2008 2010 20124
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

ソフトウェア全体に与える影響の比較
GUI

オブジェクトGC

ジェネリックWeb

並行化

アプリケーション・
プログラミング・
モデル













ライブラリーとフレームワーク











言語とコンパイラー

ランタイムと OS

ツール (設計、測定、テスト)























影響の範囲と重要性 = 多少。1 つの主要な製品リリース
 = 重要。1 つ以上の製品リリース
 = 新しい考え方が必須。複数の主要リリース

5© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並行プログラミングにおける 3 つの原理
I. 非同期エージェントによる隔離

II. 並行収集によるスケーラ
ビリティーIII. 安全な共有リソースによ
る一貫性

タグライン

ブロッキングの回避

フリーランチの復活

共有状態問題の回避

要約

個別にタスクを実行し、メッ
セージにより通信することで応答性を維持複数のコアを使用し、グルー
プ単位で処理を実行すること
でより素早く結果を取得。
データ/アルゴリズムの構造を並列化

共有リソース （特に、共有メモ
リーの可変オブジェクト） へのアクセスを同期させることで競合を回避

例

GUI、Web サービス、バッ
クグラウンド印刷/コンパイ
ル

ツリー、クイックソード、コンパイル

メモリーにある可変共有オブジ
ェクト、データベース・テーブル

主要な目的

応答性

スループット、
スケーラビリティー

競合なし、デッドロックなし

条件

隔離、個別

低オーバーヘッド、副作用なし

結合可能、直列化可能

現在の抽象概念

スレッド、メッセージキュー

スレッドプール、OpenMP*

明示的ロック、ロックフリー・ライブラリー、トランザクション

可能な抽象概念

アクティブ・オブジェクト、
FutureChore、Future、Parallel
STL、PLINQ、Cilk Plus

トランザクション・メモリー、改善されたロック、ArBB

6© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

内容
•

•

ソフトウェア開発のトレンド-

ソフトウェア開発における 6 のトレンド
ソフトウェア全体に与える影響の比較
並行プログラミングにおける 3 の原理

並列プログラミングにおける問題とインテル® Cilk™ Plus によるソリューション

-並列指向
並列プログラミングにおける問題の分離決定性の問題7© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列指向
並列指向とは、そしてアルゴリズムにおける並列性とは?
多くの技術者はそれを知らないまま過ごしてきた
アプリケーションのアルゴリズムに並列性を実装するため、並列ア
ルゴリズムのパターンを知らなければならない

高度な並列指向の例：
問題（処理）を細かく分割して並列に処理し、結果を結合する 「分割統治」に基づくアルゴリズム。 多くの場合 「分割統治」 を再帰呼び出しで実装
される

8© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

どのように並列アプリケーションを作成するか：
タスクへ分解する

もとのシリアル処理

タスクは共有データとローカルデータを持つ

並列プログラム
環境をコード化

実行のユニット化 + 依存性を解決するための新たな共有データ
9© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

Program SPMD_Emb_Par (){Program SPMD_Emb_Par
()
TYPE
*tmp,
{*func();Program
SPMD_Emb_Par()
global_array
Data(TYPE);
TYPE *tmp,{*func();Program
SPMD_Emb_Par()
global_arrayglobal_array
Data(TYPE);*tmp,*func();{ TYPE Res(TYPE);
int Nglobal_array=global_array
get_num_procs();
Res(TYPE);
Data(TYPE);
TYPE
*tmp,
*func();
int==get_proc_id();
intidNglobal_array
get_num_procs();
Res(TYPE);
Data(TYPE);
ifN(id==0)
int
id==get_proc_id();int
get_num_procs();
global_array
Res(TYPE);
setup_problem(N,DATA);if (id==0)
int Num
id==
get_proc_id();int
get_num_procs();for (int I= 0;
setup_problem(N,DATA);(id==0)int id =ifget_proc_id();
I<N;I=I+Num){for (int I= 0;
setup_problem(N,DATA);
if(id==0)setup_problem(N, Data);
tmp=
func(I);
I<N;I=I+Num){for (int I= 0;
forI<N;I=I+Num){(int I=
ID;tmp);
I<N;I=I+Num){
Res.accumulate(tmp= func(I);tmp= func(I,Data);}tmp
Res.accumulate(tmp);= func(I);Res.accumulate(
tmp);
} }
Res.accumulate(
tmp);
}
} }
}
}

ソースコードに実装
インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

主要な並列アルゴリズム
演算はどのように構成されているか?

データで編成データの流れで編成

タスクで編成

リニア?

再帰?

リニア?

再帰?

規則的?

幾何学分解

再帰
データ

タスク
並列

分割統治

パイプ
ライン

利用例

ゲーム
物理学

レイトレーシング

10© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

分子動力学

規則性
なし?

イベントを
基に調整

離散時間
シミュレーションインテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

参考文献
並列アルゴリズム設計におけるパターン言語について解説
MPI、OpenMP そして Java による例題を提示

プログラマーがどのように並列プログラミングについて考えるのか、著者の仮説を述べている

Patterns for Parallel Programming, Timothy G.
Mattson, Beverly A. Sanders, Berna L. Massingill,
Addison-Wesley, 2005, ISBN 0321228111

11© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列指向の備わったアルゴリズムの例
void qsort(int * begin, int * end) {if (begin != end) {--end;// 最後にピボットを除く
int * middle = std::partition(begin, end, // パーティションテンプレートで
std::bind2nd(std::less<int>(),*end)); // 分割する}

std::swap(*end,*middle);
qsort(begin, middle);
qsort(++middle, ++end);}// ピボットを中間へ移動// ピボットを除く

2 つの呼び出しは、異なるデータ領域を処理
つまり、同時に実行することができる
QuickSort のアルゴリズムに並列性が備わっていることを、誰も教えてくれなかった
12© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

高度な並列指向をサポートする OpenMP* とインテル® Cilk™ Plus
void qsort(int * begin, int * end) {if (begin != end) {--end;// 最後にピボットを除く
int * middle = std::partition(begin, end, // パーティションテンプレートで
std::bind2nd(std::less<int>(),*end)); // 分割する}

std::swap(*end,*middle);
qsort(begin, middle);
qsort(++middle, ++end);}// ピボットを中間へ移動// ピボットを除く
OpenMP*

Cilk™ Plus

このアルゴリズムを簡単に、効率よく並列化するには？
OpenMP* とインテル® Cilk™ Plus を比較してみる
01Sample_1¥sample1.cpp
13© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

高度な並列指向をサポートする
OpenMP* では
void qsort(int * begin, int * end) {if (begin != end) {--end;// 最後にピボットを除く
int * middle = std::partition(begin, end, // パーティションテンプレートで
std::bind2nd(std::less<int>(),*end)); // 分割する
#pragma omp parallel{#pragma omp single{
OpenMP では並列領域の定義の#pragma omp task
仕方によって大きく性能が異なる
qsort(begin, middle);#pragma omp task
qsort(++middle, ++end);#pragma omp taskwait} // end single} // end parallel
01Sample_1¥sample1omp.cpp} // end if
01Sample_1¥sample1omp2.cpp
インテル® ソフトウェア開発製品
14 }© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

高度な並列指向をサポートする
インテル® Cilk™ Plus
void qsort(int * begin, int * end) {if (begin != end) {--end;// 最後にピボットを除く
int * middle = std::partition(begin, end, // パーティションテンプレートで
std::bind2nd(std::less<int>(),*end)); // 分割する}

std::swap(*end,*middle);
qsort(begin,qsort(begin,
middle);cilk_spawn
middle);qsort(++middle, ++end);}// ピボットを中間へ移動// ピボットを除く

このアルゴリズムを簡単に、効率よく並列化するには？
OpenMP* と比較してみる
01Sample_1¥sample1cilk.cpp
15© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

cilk_spawn qsort(begin, middle);
qsort(++middle, ++end);継続

スポーン
begin – middle
スポーン(middle+1) – (end+1)
スポーン

継続

(middle/2)middle

begin –
(middle/2)
begin –
(middle/2)/2

継続(middle/2)/2 –(middle/2)

begin –
(middle/..)/../..

0

1

2

3

16
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

…………………………….

n-1

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

n高度な並列指向の例
レガシー処理を分割統治ベースのアルゴリズムに変更
for(int i = 0; i < ii; ++i)for (int k = 0; k < kk; ++k)for(int j = 0; j < jj; ++j)C[i * jj + j] += A[i * kk + k] * B[k * jj + j];

この例では、3 階層のループの入れ子の最外と最内のループが依存性なく並列化できるfor ループをデータ分割するのがベストな方法か？
02Matmul¥sample4[a,b].cpp
1-17© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

内容
•

•

ソフトウェア開発のトレンド-

ソフトウェア開発における 6 のトレンド
ソフトウェア全体に与える影響の比較
並行プログラミングにおける 3 の原理

並列プログラミングにおける問題とインテル® Cilk™ Plus によるソリューション

-並列指向
並列プログラミングにおける問題の分離決定性の問題18© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離
並列プログラミングを容易にするため、様々な抽象化技術が開発されてきた：ネイティブ・スレッド
OpenMP*
インテル® Cilk™ Plus

19
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

アプリケーションを並列実行する上で、本来アプリケーシ
ョン自身に関わる以外のことを開発者に求めてはいけない

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離の例
static long num_steps = 100000;
double step;
void main () {int i;
double x, pi, sum = 0.0;
step = 1.0/(double) num_steps;}for (i=1;i<= num_steps; i++){x = (i-0.5)*step;sum = sum + 4.0/(1.0+x*x);}
pi = step * sum;20
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Win32 API によるネイティブ・スレッドの実装#include <windows.h>#define NUM_THREADS 2HANDLE thread_handles[NUM_THREADS];CRITICAL_SECTION hUpdateMutex;
static long num_steps = 100000;
double step;
double global_sum = 0.0;

マルチ・スレッドのサポートを設定

void main (){double pi; int i;
DWORD threadID;
int threadArg[NUM_THREADS];

スレッドを生成する準備と生成

for(i=0; i<NUM_THREADS; i++)

InitializeCriticalSection(&hUpdateMutex);

void Pi (void *arg){
int i, start;
double x, sum = 0.0;

for (i=0; i<NUM_THREADS; i++){thread_handles[i] = CreateThread(0, 0,(LPTHREAD_START_ROUTINE) Pi,&threadArg[i], 0, &threadID);}

各スレッドに分割する作業を定義し、それらを関数に切り分ける
start = *(int *) arg;
step = 1.0/(double) num_steps;for (i=start;i<= num_steps;
i=i+NUM_THREADS){
x = (i-0.5)*step;sum = sum + 4.0/(1.0+x*x);}EnterCriticalSection(&hUpdateMutex);
global_sum += sum;
LeaveCriticalSection(&hUpdateMutex);

WaitForMultipleObjects(NUM_THREADS,
thread_handles, TRUE,INFINITE);

すべてのスレッドの完了を待つ

演算結果を１つのスレッドが安全に生成できるように同期}

21© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

threadArg[i] = i+1;

pi = global_sum * step;}

printf(" pi is %f ¥n",pi);

答えを表示インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* による PI のプログラム：
リダクションによる並列処理#include <omp.h>
static long num_steps = 100000;
double step;#define NUM_THREADS 2
void main (){int i; double x, pi, sum = 0.0;
step = 1.0/(double) num_steps;
omp_set_num_threads(NUM_THREADS);#pragma omp parallel for reduction(+:sum) private(x)for (i=1;i<= num_steps; i++){x = (i-0.5)*step;sum = sum + 4.0/(1.0+x*x);}
pi = step * sum;}22
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

これで十分ですか？

23© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離素数を求めるサンプルコード：
void FindPrimes(int start, int end){#pragma omp parallel for reduction(+:gPrimes))for( int i = start; i <= end; i+=2 ){if( TestForPrime(i) )gPrimes++;}}

このループはどのように並列処理されるか?
• どのように負荷は分散されるか?
• スレッドはどのコアで実行されるか?
OpenMP ではプロセッサーコアへのスレッドの割り当ては OS 依存
24© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離を解決する
インテル® Cilk™ Plus と OpenMP*
void FindPrimes(int start, int end){#pragma omp parallel for reduction(+:gPrimes))for( int i = start; i <= end; i+=2 ){if( TestForPrime(i) )gPrimes++;}}void FindPrimes(int start, int end){
cilk::reducer_opadd<int> Primes;
Primes.set_value(gPrimes);
cilk_for( int i = start; i <= end; i+=2 ){if( TestForPrime(i) )gPrimes++;}
gPrimes = Primes.get_value();}25© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

この2つの違いは?

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離を解決する
OpenMP* の実装
bool TestForPrime(int val){
void FindPrimes(int start, int end){
int limit, factor = 3;
#pragma omp parallel for reduction(+:gPrimes))for( int i = start; i <= end; i+=2 ){ limit = (long)(sqrtf((float)val)+0.5f);
if( TestForPrime(i) )while( (factor <= limit) && (val % factor))
gPrimes++;factor ++;}}return (factor > limit);
end =10000000}

4 コア・システムの場合

1 –2500000

2500001 –
5000000

5000001 –
7500000

7500001 –10000000
03Sample_2¥sample2b.cpp

26© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離を解決する
OpenMP* での解決 ….
void FindPrimes(int start, int end){#pragma omp parallel for reduction(+:gPrimes)) schedule(static, 1)for( int i = start; i <= end; i+=2 ){if( TestForPrime(i) )gPrimes++;}}end =10000000

4 コア・システムの場合

1 += 4

3 += 4

5 += 4

7 += 403Sample_2¥sample2b.cpp
27© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

並列プログラミングにおける問題の分離を解決する
インテル® Cilk™ Plus の実装と解決
void FindPrimes(int start, int end){
cilk::reducer_opadd<int> Primes;
Primes.set_value(gPrimes);
cilk_for( int i = start; i <= end; i+=2 ){if( TestForPrime(i) )gPrimes++;}
gPrimes = Primes.get_value();}

Cilk Plus ランタイムが最小粒度を判断し、粒度に達するまで分割を繰り返す
ランタイムは分割されたタスクをワーカーへ割り当てる
ワーカーはランタイムによってプロセッサーコアに配置される
03Sample_2¥sample2c.cpp
28© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

インテル® Cilk™ Plus ランタイム・システム
インテルコンパイラーは並列化技術が効果的にプロセッサーのリソース（キャッシュやメモリー帯域）を利用できるよう、リソースマネージャーレイアー（RML）を実装している
ワーカーA

ワーカーB

ワーカーC

ワーカーD

…

ワーカーZ

Cilk Plus ランタイム
リソースマネージャーレイアー（RML）

不公正
な割り
当て

OS
コア1

コア2

29
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

コア3

コア４

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

内容
•

•

ソフトウェア開発のトレンド-

ソフトウェア開発における 6 のトレンド
ソフトウェア全体に与える影響の比較
並行プログラミングにおける 3 の原理

並列プログラミングにおける問題とインテル® Cilk™ Plus によるソリューション

-並列指向
並列プログラミングにおける問題の分離決定性の問題30© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

決定性の問題
並列に実行されることで結果が変わらないか?
int result += input[i];int result *= input[i];std::list<char> result = ‘A’ + i;

その処理は可換可能か?

31© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

決定性の問題の例
std::list<char> result;#pragma omp parallel forfor (std::size_t i = 'A'; i < 'Z'+1; ++i){lock();
result.push_back((char)i);
unlock();}

このコードを実行すると、シリアルプログラムと結果が異なる

32© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

決定性の問題を解決する
インテル® Cilk™ Plus
Mutex などのロックは決定性を損ねる
std::list<char>cilk::reducer_list_append<char>result;result;#pragma omp parallel for orderedcilk_for(std::size_t
i =i 'A';
i < 'Z'+1;
++i){
for
(std::size_t
i = 'A';< 'Z'+1;++i){
result.push_back((char)i);lock();}#pragmaresult.push_back((char)i);
omp ordered
unlock();result.push_back((char)i);}
unlock();}reducer_list_append で定義された result には、並列操作
における決定性が保証される
04Sample_3¥sample3[a-c].cpp
33© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

まとめ
並列指向
並列プログラミングにおける問題の分離決定性の問題34© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

バックアップ35© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

インテル® Cilk™ Plus 概要

1-36© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

インテル® Cilk™ Plus 概要
インテル® Cilk™ Plus は、共有メモリー・マルチコア・システム向けの C/C++
ベース言語拡張• Cilk™ Plus は、3 のキーワードを定義する• cilk_spawn は、関数呼び出しを並列実行することを許可する• cilk_sync は、スポーンされたすべての子関数が終了するまで指定された位置で待機することを指示する• cilk_for は、ループ反復を並列に実行することを許可する• Cilk™ Plus のハイパーオブジェクトは、結合可能な操作を行う場合に一般的なリダクションやユーザー定義リダクションを可能にする• Cilk™ Plus は、ベクトル化を容易にするため並列配列表記（array
notation ）を提供する• Cilk™ Plus は、要素関数によるベクトル化を提供する• Cilk™ Plus のタスク・スケジューラーは、自身の作業デックが空の場合、他のワーカーの作業をスチールすることを許す• Cilk™ Plus では、#pragma simd を利用してユーザーの強制によるループのベクトル化が可能
37© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

フィボナッチ数列の例• フィボナッチ数列は、 <0,1,1,2,3,5,8,13,21,34,...> のように、自身の2つ前の数を足した値になるような数列• 再起的な関係:
F0 = 0,F1 = 1,
Fn = Fn-1 + Fn-2 for n > 1• 数列は、 Leonardo di Pisa (1170-1250 AD.) にちなんで命名された。 フィボナッチ filius Bonaccii の構造 - 「Bonnaccio の息子」 として知られている。それ以前にインドの数学者によって発見されていたが、フィボナッチの 1202 の書籍の Liber Abaci は、西洋の数学者に数列を紹介した

注意：この再帰プログラムは、n 番目のフィボナッチ数列を計算する
最適な方法ではないが、これは良い教訓となる
38© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

フィボナッチの実行
Fib(4)
Fib(2)

Fib(3)
Fib(2)
Fib(1)

Fib(1)

Fib(1)

Fib(0)

並列化のための考察
fib(n-1) と fib(n-2) の計算は、干渉なしに同時に実行することができる

39© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

Fib(0)
int fib(int n){
if (n<2) return n;else {
int x = fib(n-1);
int y = fib(n-2);
return x+y;}}

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

シリアル版のフィボナッチ
int fib(int n){
if (n<2) return n;else {
int x = fib(n-1);
int y = fib(n-2);
return x+y;}}40
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

ネスト並列版のフィボナッチ
int fib(int n){
if (n<2) return n;

スポーンされる子関数は、呼び出した親と並列に実行される

else {
int x = cilk_spawn fib(n-1);
この同期ポイント以前にスポーン
int y = fib(n-2);
cilk_sync;

されたすべての子関数が終了するまで、このポイントで待機する

return x+y;}}

Cilk™ Plus キーワードは、並列実行の許可を与える
もので、並列実行を強制するものではない

41© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Cilk_for によるマトリクス演算の例
ここから…
for(unsigned int i = 0; i < n; ++i) {int itn = i * n;for (unsigned int k = 0; k < n; ++k) {for (unsigned int j = 0; j < n; ++j) {int ktn = k * n;A[itn + j] += B[itn + k] * C[ktn + j];
}
}
}

42
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Cilk_for によるマトリクス演算の例#include <cilk/cilk.h>…
cilk_for (unsigned int i = 0; i < n; ++i) {// このプログラムで利用される唯一の Cilk™ Plus キーワード
int itn = i * n;for (unsigned int k = 0; k < n; ++k) {for (unsigned int j = 0; j < n; ++j) {int ktn = k * n;A[itn + j] += B[itn + k] * C[ktn + j];
}
}
}

43
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

ここへ

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

実験 – マンデルブロー集合の並列版
目的: 並列版のマンデルブローを作成する。ソースに Cilk™ Plus の
cilk_for キーワードを追加し、並列にマンデルブロー集合の計算を行う

44© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

レデューサー・ハイパーオブジェクト
レデューサー・ハイパーオブジェクト•変数 x は、加算、乗算、論理AND、リストの連結のような結合操作が可能な
レデューサーとして定義できる•ストランドは、x を通常の非局所変数のようにアップデートできるが、実際は
x 異なったビューの収集として保持される•Cilk™ Plus ランタイム・システムは、ビューを操作し必要とされる時にそれらを結合する•x の 1 のビューだけが残っていれば、保持される値は安定しており、引用できる
総和
レデューサーの例

X:23

45© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

X:15

X:37

75
インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Cilk™ Plus レデューサーの例

Parallel Studio のサンプルにある、Nqueens の場合
cilk::reducer_opadd<unsigned int>
total;…
total.set_value(g_nSolutions);
cilk_for (int i=0; i<g_nsize; i++) {…
nqSetQueen(pNQ, 0, i);…
}
g_nSolutions = total.get_value();

総和を行うレデューサー
オブジェクトを total として宣言する
g_nSolutions 変数の値をレデューサー total の初期値として設定する
各 cilk_for セクションの終端には、暗黙の同期がある
各ストランドが持つローカル
な total の値を結合して、
g_nSolutions に読み出す46© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Cilk™ Plus 配列表記
インテル® Cilk™ Plus は、プログラマーがアルゴリズムのループ中で配列要
素をインデックスで操作する代わりに、配列を簡単に操作する言語構造を提供する
コンパイラーは、並列を操作するため SIMD 命令を利用したベクトル・コードを生成する– 例: 配列表記なしの操作

for (int i = 0; i < length; ++i) {res[i] = elemental_func(a[i],b[i]);}– 例: 配列表記を利用すると、ループを排除できる
res[:] = elemental_func(a[:] , b[:]);

括弧中の数字の意味は?
– r[0:N] = src1[0:N] + src2[0:N];– [0:N] は、要素 0 から始まり、N 個の要素を操作することを意味する– [0:N:2]は、0 から N 個の要素を、2 ずつスキップする47© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Cilk™ Plus 要素関数
要素関数は、スカラー引数や配列要素で並列に呼び出すことができる正規関数
コンパイラーにショートベクトル・バージョンの関数を生成することを指示するには、__declspec (vector) アノテーションを利用する• 関数宣言に vector 宣言子を追加する• __declspec(vector) float elemental_func(float, float);
例: マルチコアとベクトル化に対応する
cilk_for (i = 0; i < length; ++i) {res[i] = elemental_func(a[i],b[i]);}例: 配列表記を利用してベクトル化する
res[:] = elemental_func(a[:] , b[:]);

48© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

戻る
インテル® ソフトウェア開発製品

Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* の概要

49© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* とは?
• 移植性の高い、共有メモリー型スレッド API– Fortran, C, and C++– 複数のコンパイラーベンダーが、Linux と Windows をサポート• 標準化されたタスクとループ・レベルの並列性• 粗い粒度の並列性をサポート• 1 のソースコードで、シリアル版と並列版に対応• 20 年以上にわたる、コンパイラーによるスレッド化の経験
http://www.openmp.org
現在の仕様は、 OpenMP 3.0 （C/C++ と Fortran の仕様を統合）
OpenMP 3.1 仕様を策定中
50© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* プログラミング・モデル
Fork-Join 型並列：
• マスタースレッド が、指示された場所でスレッドのチームを構成• 並列性はインクリメンタルに追加される: シリアル・プログラムが、
並列プログラムに発展する

マスター
スレッド
並列領域
51
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

開始するにあたっていくつかの構文の詳細
OpenMP* における大部分の構造は、コンパイラー指示文かプラグマ
C と C++ では、プラグマで始まる:#pragma omp 指示句 [指示節 [指示節]…]

ヘッダーファイル
#include “omp.h”

52© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* 並列領域と構造化ブロック （C/C++）
ほとんどの OpenMP 構文は、構造化ブロックで適用される– 構造化ブロック: 入口が 1 で、出口が 1 の実行ブロック– C/C++ で許される分岐の例外は、exit() 文のみ
構造化ブロック#pragma omp parallel{
int id = omp_get_thread_num();
more: res[id] = do_big_job (id);if (conv (res[id]) goto more;}printf (“All done¥n”);

53© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

非構造化ブロックif (go_now()) goto more;#pragma omp parallel{
int id = omp_get_thread_num();
more: res[id] = do_big_job(id);if (conv (res[id]) goto done;
goto more;}
done: if (!really_done()) goto more;printf (“All done¥n”);

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

OpenMP* ワークシェア
ワークシェアは、スレッドに処理を分散する OpenMP で利用される一般的な技術
OpenMP における 3 のワークシェアの例:– omp for 指示句– omp section 指示句– omp task 指示句– omp single 指示句

作業を自動的にスレッドに分割する
54© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

omp for 指示句// N=12 と想定#pragma omp parallel#pragma omp for
for(i = 1, i < N+1, i++)c[i] = a[i] + b[i];スレッドには独立したループが割り当てられるスレッドはワークシェア領域の終
わりで待機する

55© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

#pragma omp parallel#pragma omp for
i=1

i=5

i=9

i=2

i=6

i = 10i=3

i=7i = 11i=4

i=8i = 12

暗黙のバリアインテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

指示句の組み合わせ
下記の 2 の記述は等価#pragma omp parallel{#pragma omp forfor (i=0;i< MAX; i++) {res[i] = huge();}}#pragma omp parallel forfor (i=0;i< MAX; i++) {res[i] = huge();}56© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

Private 指示句
各タスクに変数を複製する– 変数は初期化されない; C++ オブジェクトはデフォルトのコンストラクタ– 並列領域外の変数はすべて未定義

void* work(float* c, int N) {float x, y; int i;#pragma omp parallel for private(x,y)
for(i=0; i<N; i++) {x = a[i]; y = b[i];c[i] = x + y;}}57
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

実験 – マンデルブロー集合の並列版
目的: 並列版のマンデルブローを作成する。ソースに OpenMP ワー
クシェア指示句を追加し、並列にマンデルブロー集合の計算を行う

58© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

スケジュール指示節
スケジュール指示節 は、ループ反復がどのようにスレッドに割り当てられるかに影響する
schedule(static [,chunk])– “chunk” で指定される回数のループ反復ブロックをスレッドに割り当て– ラウンドロビン形式の分散– 低いオーバーヘッドのため、ロードインバランスになり易い

schedule(dynamic[,chunk])– スレッドが “chunk” サイズの反復を要求– スレッドが反復を処理し終えると、次を要求– 高いオーバーヘッド、ロードインバランスを軽減

schedule(guided[,chunk])– 開始時は大きなブロックをダイナミックにスケジュール– 終わりに近づくとブロックサイズを小さくする; “chunk” より大きい59© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

スケジュール節の例#pragma omp parallel for schedule (static, 8)for( int i = start; i <= end; i += 2 ){if ( TestForPrime(i)) gPrimesFound++;}

反復は 8 回のチャンクに分割される
start = 3 なら、最初のチャンクは、
i={3,5,7,9,11,13,15,17}// 8回の反復60© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

実験 –マンデルブロー集合のスケジューリング
目的: 並列版のマンデルブロー集
合を作成し、OpenMP のスケジ
ュール指示節でダイナミックにスケジュールする

61© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスク分解a = 一郎();b = 次郎();s = お母さん(a, b);c = 次郎();printf (“%6.2f¥n”,
おばあさん(s,c));

次郎

一郎

お母
さん

一郎、次郎、そして三郎は同時に演算できる62© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

三郎
おばあ
さん

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスク
不規則な処理の並列化を可能にする– 限りないループ– 再帰アルゴリズム– 生産と消費アルゴリズム

63© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスクとは?
タスクは作業の独立した単位
スレッドには、各タスクの作業が割り当てられる
タスクは据え置かれる

タスクは即座に実行、もしくは延期される
ランタイム・システムは、以下のいずれかを行うか決定する
タスクは以下で構成される:
実行するコード
data 環境
内部制御変数（ICV）
64© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

シリアル

並列

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

簡単なタスクの例#pragma omp parallel// 8 スレッドと過程{#pragma omp single private(p){…
while (p) {#pragma omp task{
processwork(p);}p = p->next;
}
}
}

65
© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

8 スレッドのプールがここで作成される
1 つのスレッドのみがwhile ループを実行
while ループ実行される
たびに、ここで processwork()
がタスクとして生成されるインテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスク構造 – 明示的なタスク• omp parallel 指示句でスレッドのチームが生成される• While ループを実行するため
single 指示句を指定する。これをス
レッド “L” と呼ぶことにする• スレッド “L” は、while ループ内でタスクを生成し、次のポインターを割り当てる• スレッド “L” は、新たにスレッドに割り当てるタスクを生成するため omp
task 指示句を実行する• 各タスクは、それぞれのスレッドで実行される• Single 領域の終わりには暗黙のバリアがあり、すべてのタスクはバリア
で実行を完了する

66© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

#pragma omp parallel{#pragma omp single{ // ブロック 1
node * p = head;
while (p) { // ブロック 2#pragma omp task private(p)process(p);p = p->next; // ブロック 3}}}

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

なぜタスクが有効なのか?
不規則なパターンと再帰関数呼び出しを並列化できる可能性がある
スレッド1
スレッド2

Block 1

Block 1
Block 3Block 2
Task 1

Block 3Block 3Block 2
Task 1

アイドル

Block 2
Task 2

アイドル

Block 3

スレッド3
スレッド4

Block 2
Task 2

スレッド化によりセーブ

Block 2
Task 367© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

Block 2
Task 3時間#pragma omp parallel{#pragma omp single{ // ブロック1
node * p = head;
while (p) { // ブロック2#pragma omp task
process(p);p = p->next; // ブロック3
}
}
}

シングル
スレッド

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスクの完了が保障されるのはいつか?
 タスクの完了は次の条件で保障される:

スレッドもしくはタスクのバリア
 #pragma omp barrier が指定される位置
 #pragma omp taskwait が指定される位置

68© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

タスク完了の例#pragma omp parallel{#pragma omp taskfoo();#pragma omp barrier#pragma omp single{#pragma omp taskbar();}}

foo 関数がタスクとして生成される – 各スレッド分のタス
クを生成
すべての foo タスクは、ここで完了する

bar タスクがここで生成される

bar タスクはこの位置で完了することが保障される戻る

69© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

インテル® ソフトウェア開発製品
Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。

インテル® ソフトウェア開発製品© 2011 Intel Corporation. 無断での引用、転載を禁じます。 記載内容は予告なしに変更されることがあります。
＊その他の社名、製品名などは、一般に各社の表示、商標または登録商標です。

Intel、インテル、 Intel ロゴは、アメリカ合衆国およびその他の国における Intel
Corporation またはその子会社の商標または登録商標です。