LCR2000報告

Survey: Flexible Control Structure
for Parallelism in OpenMP
田中義純
[email protected]
その前に、
非常に簡単にLCR2000の報告
５月２５日～２７日
 Rochester Univ. in NY

– NYの田舎町
– 「古き良きヨーロッパ」ｂｙ田浦さん
22／？件採択
 参加者数４０～５０人

全体的な印象

SDSMの話が多かった
– クラスタ
– OpenMP

興味のある方は田中まで
– Proceedings をお貸しします
閑話休題
以降の構成
既存の仕様の制限
 The Workqueuing Model
 実験結果
 まとめ
 Reference

Worksharing Construct

Parallel construct で生成されたスレッド
チームが仕事を分配して実行する
#pragma omp for
for (i=0; i<n; i++)
process( data[i] );
#pragma omp sections
{
#pragma omp section
process( a );
#pragma omp section
process( b );
}
For Construct の制限
ループの実行前に、下限・上限・増減が決まっ
ていなくてはならず、途中で変更も出来ない
 全てのイテレーションは独立でないといけない

nodeptr list, p;
…
#pragma omp for
for (p=list; p!=NULL; p=p->next)
process( p->data );
コンパイル時エラー
それでも並列化するためには
nodeptr list, p;
…
for (p=list; p!=NULL; p=p->next)
process( p->data );
この部分を標準化すればよい
それでも並列化するためには
nodeptr list, p;
…
int n = 0;
for (p=list; p!=NULL; p=p->next) n++;
nodeptr *q = new nodeptr[n];
int i = 0;
for (p=list; p!=NULL; p=p->next) q[i++];
#pragma omp parallel for
for (int i=0; i<n; i++) process( q[i] );
Sections Construct の制限

section は sections のトップレベルに書かな
くてはならない
#pragma omp sections
{
if ( node.left_leaf )
#pragma omp section
process( node.left_leaf );
else if ( node.right_leaf )
#pragma omp section
process( node.right_leaf );
}
現在の仕様の限界

Worksharing construct に入る前に、仕事の
絶対量が決まっていなくてはならない
– for: ループの初めに決まる
– sections: コンパイル時に決まる
新しいプラグマの提案

The workqueuing model
– #pragma omp taskq
 空のqueueを生成する
– #pragma omp task
 queueに仕事を挿入する
Workqueuing Model の例
tree list, p;
…
#pragma omp parallel taskq
for (p=list; p!=NULL; p=p->next) {
if ( p->left )
#pragma omp task
traverse( p->left );
else if ( p->right )
#pragma omp task
traverse( p->right );
}
Workqueuing pragma の特徴

#pragma omp taskq
– 他の taskq、task の内側に書くことが出来る
入れ子並列をサポート

#pragma omp task
– taskq の内側のどのレベルにも書くことが出来る
queue
task
queue
task
task
task
queue
task
task
task
task
task
Workqueuing Model の Target

Hierarchical Linked Lists

Recursive Control/Data Structure
e.g. Tree traversal
Semantics

#pragma omp taskq
– Normal case: 複数のスレッドが遭遇
 一台のスレッドが内部を実行し、残りのスレッドは
入り口で待っている
– Nested case: 一台のスレッドが遭遇
 遭遇したスレッドが実行する

#pragma omp task
– 対応するqueueに仕事を挿入する
Syntax (1)

#pragma omp taskq [ clause [ clause ] … ]
–
–
–
–
–
–
–
–
–
private (list)
firstprivate (list)
lastprivate (list)
reduction (operator:list)
ordered
nowait
If
qdepth ( d )
maxqs ( n )
Syntax (2)

#pragma omp task [ clause [ clause ] … ]
– private (list)
– firstprivate (list)
Work Stealing

いつ起こるか？
– 今実行している taskq の仕事がなくなった時

起こり得る状況は？
– taskq が入れ子状になっている時
– nowait clause が付いた時
現在の実装上の問題点
Taskq の実装
 Threadprivate 変数の扱い

実験結果
４台での台数効果
4.5
4
3.5
3
IBM
Compaq
SGI
SUN(ours)
2.5
2
1.5
1
0.5
0
Straseen
FFT
Queens
Mutisort
まとめ

OpenMPに新たなプラグマを導入
 今まで扱えなかった並列性を抽出
 標準のAPIになるように働きかけている
感想

概念的には面白い
– 我々の実装に取り入れることは可能であろう

４台以上のプロセッサでの性能の比較をし
てみたい
– 彼らの実装がどのくらい有効か知りたい
Reference

Sanjiv Shah, Grant Haab, Paul Petersen, and Joe Throop.
Flexible Control Structures for Parallelism in OpenMP. In
the Proceedings of First European Workshop on OpenMP
EWOMP99, pages 60-70, Lund, Sweden, September 1999.

Download Report