日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

依存関係をもった並列タスクのための動的グループバ
リア同期とその効率的な実装
夏 澄彦

佐藤 芳樹

千葉 滋

依存関係をもった並列タスクを記述するにはバリア同期がよく用いられる．バリア同期とは，並列に動作するプログ
ラムの実行を待ち合わせるために用いられ，プログラミング言語や並列分散ライブラリによって提供される．しかし，エージェントシミュレーションのような不均一な並列タスクを持つアプリケーションでは，タスク数の増加に伴い待機状態のスレッドが増加し，CPU の実行効率が低下するばかりでなく，待機スレッドの占有するメモリ量も増大する．そのため，スケーラブルな並列プログラムを実装するには，バリア同期による待ち時間を最小化するよう細心の注意が必要となる．我々はバリア対象のスレッドを実行時に指定し，さらにスレッドプログラムを分割することにより，軽量なバリア同期機構を開発した．本論文では，開発した動的グループバリア同期機構と，歩行者シミュレーションのアプリケーションに適用した結果について報告する．

了するまで続きの処理が待機させされる．素朴なバリ

1 はじめにア同期の実装では，全てのタスクが同期を待ち合わせ

マルチエージェントシミュレーションのような現実るため，並列タスク数の増加に伴い待機スレッド数も世界の自律的な行動主体をモデリングするようなソ増加し，その結果，スレッドによって占有されるメモ

フトウェアは，他の多くの科学技術計算とは異なり，リ量が増大する．また，タスク間の実行時間が不均一

オブジェクト指向のような抽象度の高い設計と親和なアプリケーションの場合，全てのスレッドで同期を性が高い．一方，一般にエージェントを実装したプロ行うと，CPU の実行効率が低下し，プログラムのパグラムは，計算粒度が大きく，他のエージェントや外フォーマンスも悪化してしまう．

部システムとの協調が必要となり，依存関係が複雑に我々は，エージェントプログラムのモジュラリティなる傾向がある．このようなエージェント間の処理のを保ったまま，バリア同期対象のタスクを動的に指定

依存関係は，大規模シミュレーションのためのソフトできる機構を開発した．プログラマによってバリア対ウェアの並列分散化の障壁となっている．

象のタスクを実行時に指定することで，同期に参加

大規模エージェントシミュレーションを科学技術計するスレッドを最小限に抑え，待機スレッドの増加を算プログラムでよく利用されるバリア同期のような抑制することが可能となる．さらに，待機スレッド数タスク制御機構を用いて効率良く実行することは難を削減するために，エージェントを実装するスレッド

しい．バリア同期とは，依存関係のある並列タスクをコードを分割し，ノンブロッキングな形式の同期を行記述するためのシンプルな機構である．バリア制御のうことが可能なプリミティブも提供する．

対象とされた並列タスクは，全てのタスクの実行が終Sumihiko Natsu， Shigeru Chiba, 東京大学大学院情報理工学系研究科創造情報学専攻, Dept. of Creative
Informatics Graduate School of Information Scienceand Technology， The University of Tokyo.
Yoshiki Sato, 東京大学情報基盤センター, Information
Technology Center， The University of Tokyo.

以下，1 章では不均一な並列タスクに対してバリア同期を用いた場合の問題点を述べる．2 章で開発した実行時のグループバリア同期機構について説明し，3
章では更にスレッド分割を行った場合の同期機構について説明する．4 章では，開発したバリア同期機構を歩行者シミュレーションに対して適用した実験を報告

図1

図2

OpenMP の barrier 指示文

CrowdWalk#pragma omp parallel
{
3A();
4
#pragma omp barrier
5B();
6 }
12する．5 章で関連研究について論じ，6 章で本論文をまとめて，今後の課題を述べる．

2 不均一な並列タスクのバリア同期計算に依存関係のある並列タスクを記述するには
図3

バリア同期が有用である．バリア同期とは，並列に動歩行者エージェント全体の処理を簡略化したプログ
ラム

作するプログラムの実行を待ち合わせるために用いclass Pedestrian implements Comparable<Pedestrian> {2static void main(String args[]) {3Collection<Pedestrian> all = ...;
4for (int i = 0; i < iteration; i++) {5for (Pedestrian pedestrian : all) {6pedestrian.preUpdate();7}
8all.sort();
9for (Pedestrian pedestrian : all) {10pedestrian.moveCommit();11}
12for (Pedestrian pedestrian : all) {13pedestrian.postUpdate();
14}
15}
16}
17 }
1

られ，通常は，MPI や OpenMP といった並列分散向け機能を提供する専用ライブラリによって提供されており，X10 や Chapel のように専用の言語プリミティブを持ったプログラミング言語も数多く登場してきている．OpenMP では，並列化したタスク内で互いに待ち合わせする位置に明示的に同期のための指示文を記述する (図 1)．それぞれのスレッドで，並列にA() が実行された後，お互いに他のスレッドを待ち合わせ，全てのスレッドがこの barrier 指示文に到達してから，スレッドが再開され，並列に B() が実行される．MPI にも同様の同期機構 MPI Barrier(comm) が存在し，指定したコミュニケータ comm 内の全プロら，次に進もうとしている道をシーケンシャルに計セスで同期を取ることが可能となる．

算（preUpdate）する．その後，衝突判定を行うため互いに協調しながら動作するようなエージェントシに，道を移動する順にエージェントを並び替えてかミュレーションも，バリア同期を必要とする並列タス

ら，一つずつ移動を行い（moveCommit），最後に後クの一例に挙げられる．図 3 に，歩行者シミュレー
タ CrowdWalk（図 2）†1 の歩行者エージェントの処処理（postUpdate）を行う．

理を簡略化したプログラム例を示す．シミュレーショのようにエージェント毎にまとめてスレッド化できンでは，各エージェント（歩行者）が単位時間ごとる．しかし，実際には moveCommit のような共有オに，グラフ構造状の道の上を辿り，ゴールに進む．道ブジェクト（道）への書き込みや衝突判定など，他のにはそれぞれ限界容量があるため，進入できるエーエージェントとの依存関係を考慮すべき処理順序がジェントの上限が決められているため，衝突判定を行Java のスレッドスケジューラに依存するという問題う必要がある．単位時間毎の処理は各イテレーションが発生する．エージェント処理のモジュラリティを維で実行され，まずエージェントの現在位置と速度か持したまま，意図した実行順序でスレッドを制御する

依存関係を考慮しなければ，これらの処理を図 4ためには，各エージェントが互いに同期しながら処†1 現在，産業技術総合研究所で開発中理を進めていくようにコードを改変しなければなら図4

依存関係を無視した並列化

class Pedestrian {2void update() {3preUpdate();14// moveCommit は適切な順番で呼ばれる必要がある

5

moveCommit();
postUpdate();

6}

7

図5

3

56

9

public static void main(String args[]) {9for (Pedestrian pedestrian : pedestrians) {10new Thread(-> pedestrian.update()).start(); 11}12}13121314}// CyclicBarrier のコンストラクタの第 2 引数で渡した// Runnable が一度だけ実行される// （sort や全歩行者への moveCommit が実行される）

7811void update() {preUpdate();barrier.await();

4810postUpdate();}public static void main(String args[]) {barrier = new CyclicBarrier(all.size(), -> {all.sort();for (Pedestrian pedestrian : all) {pedestrian.moveCommit();}});
for (Pedestrian pedestrian : pedestrians) {new Thread(-> pedestrian.update()).start();
}
}

1415
16ない．具体的には，moveCommit が呼ばれる順番が， 1718preUpdate の計算結果に依存するため，エージェントは自分の preUpdate が終わった後，moveCommit をバリア同期を用いた並列化

class Pedestrian {2static CyclicBarrier barrier;
1192021

実行する前に，他のエージェントが preUpdate が実22行し終えるまで待たなければならない．

2423}

このような並列タスク間の依存関係は，バリア同期を用いることで簡潔に記述できる．例えば，Javaに対して同期を行うと，最も preUpdate の計算時間

6 の java.util.concurrent で導入された CyclicBarrierが長いエージェントの実行が完了するまで，他のエーを用いて並列化を行うと，図 4 は図 5 のように記述

ジェントは待機することになる．それにより，大量のできる．エージェントは各イテレーション（update）待機スレッドが発生する．実際の交通シミュレーショ

内で，preUpdate が終わると，スレッドを待機させ，ンや避難シミュレーションでは，エージェント数は数全てのエージェントに対して同期を行っている．他の十万から数百万にのぼるため，OS のスレッド上限をエージェントが preUpdate を実行し終わると，まず，超える可能性も出てきてしまう．

CyclicBarrier の第２引数で渡した Runnable が実行され，正しい順番で moveCommit がシーケンシャル実

3 実行時のグループバリア同期機構

行された後，スレッドが再開され，postUpdate が並

そこで本研究では，実行中のコンテキストに応じて列実行される．

バリア同期対象のタスクを指定可能なグループバリア

しかし，各タスクの処理内容が不均一である場合，動機機構を API として開発した．既存のバリア同期大規模シミュレーションにおいて，既存のバリア同期とは異なり，同期待ちのタスクグループを限定するたではスケールしなくなるという問題が顕著に出てくめ，待機スレッド数を最小限に止められる．さらに．

る．関係する全スレッドを同期させるような素朴なバ実行時にタスクグループを指定できるため，静的にはリア同期の実装では，全スレッドが最も処理時間の長分からないタスク間の依存関係があるアプリケーショ

いスレッドの計算が終わるまで待機することになり，ンに対しても有効である．

不必要な同期待ちが発生する場合がある．待機状態

例えば，歩行者シミュレーション（図 5）の場合，のタスクの増加は，CPU の実行効率の低下を招くだ

エージェント同士の依存関係が動的に決定可能であけでなく，占有するメモリ量を増大させる．例えば，るため，実行時にどのエージェントと同期すべきかがCrowdWalk の場合，ゴールまでの距離や，周囲の状決定できる．各エージェントは道を移動する際に，衝況によって，各エージェントの preUpdate にかかる時突する可能性のあるエージェントが近傍のみであり，間は不均一である．したがって，全てのエージェント動作している全てのエージェントと同期する必要がな

い．さらに，道を移動しないエージェントはそもそも

図6

衝突しないため，他のエージェントと同期する必要がグループバリアを用いた並列化

class Pedestrian {ない．
2void update(Scheduler<Pedestrian> s) {3
preUpdate();
本研究では，プログラマが柔軟にグループバリア 4s.finished(1);if (goOnSameStreet()) {同期を利用できるように，同期待ち (barrier メソッ 5
6moveCommit();} else {ド) と完了通知 (finished メソッド) のプリミティブを 7
8s.barrier(1, calcNeighborPedestrians());
API として提供する（表 1）．barrier メソッドには， 9s.ordered(2, calcConflictingPedestrians(), -> {moveCommit();バリア同期の対象となるスレッドの集合を引数として 1011});}与えられる．加えて，各スレッド内では，finished メ 12
13postUpdate();ソッドを呼び出すことで，スレッド実行の完了を通知 14 }
1し，バリア同期を明示的に解除できる．

15

static void main() {new ParallelSet<Pedestrian>(all).map((Pedestrian pedestrian,Scheduler<Pedestrian> s) -> {pedestrian.update(scheduler);
return pedestrian;});}16

さらに，指定した複数の並列タスクをシーケンシャ 1718ル実行するためのプリミティブ (ordered メソッド) を提供する．ordered メソッドは内部的には barrier メ

192021

ソッドを使って実装されており，同期待ち対象のス22

レッド集合に対して，同期解除されたタイミングで行

2423}

う処理と，その実行順序が引数として与えられる．
これらのグループバリア同期機構を用いると図 5たスレッドとして扱えるようになる．それによって，のプログラムは図 6 のように記述することができる．

同期待ちスレッドの前処理と後処理は別々のスレッド

各エージェントの preUpdate 処理の後，同じ道へ移に分割されるため，依存関係を持ったタスクの前処理動するエージェントを判別し (goOnSameStreet)，そを待つために，スレッドを中断する必要がなくなる．

れら一部のスレッド集合のみを対象にバリア同期をスレッド分割に対応した同期待ち (ibarrier メソッ行っている．その後，実際に衝突するエージェントをド) とシーケンシャル実行 (iordered メソッド）のた計算し，その中で moveCommit をシーケンシャル実めの API を表 2 に示す．プログラマは，barrier や行する．これにより，同期対象のエージェントを最小ordered メソッドの呼び出し後に記述していた後処理化し，また，道を移動しないような場合には，他のを，Runnable クラスのメソッドに切り出し，ibarrier，エージェントと同期しないことが可能となる．

iordered メソッドに渡すことでスレッドを分割できるようになる．これにより，並列タスクは同期待ちをす

4 スレッド分割によるバリア同期の軽量化る必要が無くなり，同期後の処理も単独でスレッド化開発したグループバリア同期機構は，同期待ちにされキューに作成される．したがって，待機スレッドよる待機スレッド数をさらに削減するためにスレッドによる不要な CPU やメモリリソースの消費は避けらプログラムの分割を行う．通常，並列タスク間の依存れる．歩行者シミュレーション（図 5）に適用させる関係を取り除けない場合，待機スレッドが占有すると図 7 のようになる．barrier や ordered をノンブロッ

リソース消費の影響は避けられない．そのような依キングな API である ibarrier や iordered に置き換え存したタスクが増加すれば，並列処理による実行効るため，それらのメソッドの後に実行される処理を率のスケーラビリティは向上できなくなってしまう．

Runnable でラップし，ibarrier や iordered に渡していそこで，本機構では，スレッドプログラムを複数のノる．現時点では，ノンブロッキングのグループバリアンブロッキングなプログラムに分割し，そのシーケ

同期 API は，同期前後でのローカル変数の保存をサンシャルな実行に置き換える．ノンブロッキング化にポートしていないため，プログラマが手動で保存と復よって，スレッドプログラム中の任意の処理は独立し表1

グループバリア同期 API

Scheduler⟨T⟩ API

説明

void barrier(int tag， Set⟨T⟩ set)

set の全ての要素が tag に到達するまでスレッドを停止させる

void finished(int tag)

自身が tag に到達したことを通知し，依存する待機スレッドを再開させる

void ordered(int tag， Set⟨T⟩ set， Runnable seq)

set に対して自然順序付けで seq をシーケンシャル実行する

void ordered(int tag， Set⟨T⟩ set， Comparator⟨T⟩ comp， Runnable seq)

set に対して comp 順で seq をシーケンシャル実行する

表2

ノンブロッキングのグループバリア同期 API

Scheduler⟨T⟩ API

説明

void ibarrier(int tag， Set⟨T⟩ set， Runnable cont)set の全ての要素が tag に到達した後に cont を実行する

void iordered(int tag， Set⟨T⟩ set， Runnable seq， Runnable cont)set に対して自然順序付けで seq をシーケンシャル実行すし，その後 cont を並列実行する

void iordered(int tag， Set⟨T⟩ set， Comparator⟨T⟩ c， Runnable

set に対して comparator 順で seq をシーケンシャル実行し，その後 cont を並列seq， Runnable cont)実行する

図7

ノンブロッキングなグループバリアを用いた並列化

class Pedestrian {2void update(Scheduler<Pedestrian> s) {3preUpdate();4s.finished(1);5if (goOnSameStreet()) {6moveCommit();7
postUpdate();8} else {9s.ibarrier(1, calcNeighborPedestrians(), -> {10s.iordered(11
2, calcConflictingPedestrians(), -> {12moveCommit();13}, -> {14
postUpdate();
15});
16});
17}
18}
19 }

5 予備実験

1

開発したグループバリア同期による実行性能の向上を確認するために予備的な実験を行った．実験では，最低限の歩行者シミューレションの機能を実装したアプリケーションに対して，歩行者数を変化させ，スレッド数，メモリ使用量，CPU 使用率，実行時間の変化を計測した．入力としては，長さが 10mで，収容容量が 2 人の道からなる 500x500 の格子状のマップ与え，移動速度 1m/s の歩行者をランダムに配置した．ゴール数は 25 で，歩行者は最も近いゴールを目指して進み，20 回イテレーション繰り返した結果を測定した．実験環境は Intel(R) Xeon(R)CPU E5-2687W 0 @ 3.10GHz，メモリ 64GB である．
元を行う必要がある．

Java VM は OpenJDK Runtime Environment (rhel-

歩行者シミュレーション（図 6）をスレッド分割

2.3.10.4.el6 4-x86 64) OpenJDK 64-Bit Server VMし、ノンブロッキングなバリア同期を用いる（図 8）(build 23.7-b01， mixed mode) を使い、オプションと図 7 のようになる．図 8 では，まず ordered のは -Xms8g -Xmx8g -Xss512m -XX:+UseG1GC で実行後に行われる postUpdate() を Runnable でラッ実行し，シミュレーション実行時の最大スレッド数，プし、iordered の引数として与えることで，ordered

平均メモリ使用量，平均 CPU 使用率，実行時間につをノンブロッキングな iordered に変換している。続

いて測定を行った．

いて、barrier の実行後に実行される iordered(...) を

図 9 は，歩行者の数を 1,000 から 10,000 まで変化

Runnable でラップし、ibarrier に引数として与えるこさせた時の全エージェントに対してバリア同期を行っとで barrier をノンブロッキングな ibarrier に変換すた場合と近傍のエージェントに対してグループバリアる。この一連の操作によりプログラム全体をノンブ同期を行った場合の結果である．全エージェントを同ロッキング化することが可能となる。

期させる場合，歩行者の増加とともに最大スレッド数は単調増加し，それに伴ってメモリ使用量，CPU 使図8

非同期なグループバリアを用いるためのスレッド分割用率，実行時間のすべてが急激に増加していることがわかる．一方，グループバリア同期では，歩行者を増

6 関連研究加させても最大スレッド数は 100 前後に抑えられる

バリア同期を実現するためアプローチは数多く研ため，急激な性能低下は見られなかった．

究されてきており，様々な並列分散用のライブラリや次に，スレッド分割によるスレッド数削減の効果をプログラミング言語で実現されている．共有メモリ測定するための実験を行った．図 10 はグループバリ型並列計算の標準規格の一つである OpenMP [4] はア同期を利用した上で，スレッド分割の有無を変えbarrier や ordered といった同期構文をサポートしておて比較した結果である．分割により，同時実行スレッり，コメントやディレクティブを用いて宣言的に記述ド数が大幅に増やせるようになったため，歩行者のすることで，短いコード量でバリア同期を行う並列タ数を 10,000 から 160,000 まで変化させた．まず，ススクを記述できる．しかし，OpenMP の barrier は同レッド分割を施すことで，通常のグループバリア同期時に実行されている全てのスレッドに対して同期をに比べても，さらに最大スレッド数が抑えられていとるため，同期スレッドを任意のグループに抑えるこることがわかる．それに伴い，メモリ使用量，CPUとが難しい．分散メモリ型並列計算の標準規格の一使用率，実行時間もシミュレーションの大規模化にあつである MPI [3] でも，同様に MPI barrier というバたっても十分に抑えられていることがわかる．

リア同期機構を備えており，コミュニケータを介して指定したプロセスグループに対する同期を行うことが可能である．言語レベルでバリア同期をサポート

Number of Max Threads

10000

BarrierGroupBarrier

9000
8000
7000
6000
5000
4000
3000
2000
1000

18

Average Memory Usage (GB)

11000

BarrierGroupBarrier

1614121086401000 2000 3000 4000 5000 6000 7000 8000 9000 10000

21000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Pedestrians

Pedestrians(a) 最大スレッド数600

BarrierGroupBarrier

BarrierGroupBarrier

50080

Execution Time (s)Average CPU Use Rate (%)

100(b) メモリ使用量

604020400
300200100

01000 2000 3000 4000 5000 6000 7000 8000 9000 10000

01000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Pedestrians

Pedestrians(c) CPU 使用率
図9(d) 実行時間
グループバリア同期によるスレッド数削減の効果している x10 [6] も Clocks を用いてバリア同期が可的な同期が可能な上，実行中の並列タスクから同期グ能であり，x10 の並列タスクである Activity の処理のループへの動的な登録や解除が可能である．しかし，中で同じ Clock オブジェクトが指定されている他のPhaser では並列タスクを実行する前に同期グループActivity と同期することが可能である．これらのバリが作成されていることを想定しており，本研究のようア同期は同期対象のスレッド集合を動的に指定できるに並列タスク内から動的に同期対象のタスクグルーため，待機スレッドを削減することが可能だが，同期プを作成することは困難である．に関わる並列タスクは全て相互に同期を行うため，一3 章で述べたようなスレッド分割によって変換さ方的な同期は不可能である．Clocks や 2 章で紹介しれたプログラムは一般的に継続渡しスタイル（CPS:た CyclicBarrier に対して，より柔軟なバリア同期をContinuation-Passing-Style）と呼ばれ，これまでに行える機構として Phaser [5] という機能が提案されJava プログラムの継続をサポートするフレームワーており，Java 7 の java.util.concurrent で Java の標

クも数多く実装されている RIFE [2] や Commons

準ライブラリとして導入されている．Phaser を用い

Javaflow [1]．これらの実装技術を用いてスレッド分ると Clocks や CyclicBarrier では不可能であった一方割を施せば，現在本研究でサポートしていない制御文

9.5Blocking
Nonblocking

Average Memory Usage (GB)

Number of Max Threads

1200010000

8000

6000

400020000Blocking
Nonblocking

98.5
87.5
76.5
65.55020000 40000 60000 80000 100000 120000 140000 160000

020000 40000 60000 80000 100000 120000 140000 160000

Pedestrians

Pedestrians(a) 最大スレッド数

1800

Blocking
Nonblocking

Blocking
Nonblocking

1600

80
1400

Execution Time (s)Average CPU Use Rate (%)

100(b) メモリ使用量

604012001000800600400

2020000020000 40000 60000 80000 100000 120000 140000 160000

020000 40000 60000 80000 100000 120000 140000 160000

Pedestrians

Pedestrians(c) CPU 使用率
図 10(d) 実行時間
スレッド分割によるスレッド数削減の効果

内でのバリア同期や，ローカル変数の保存なども可能

み合わせることでスレッド数が削減され，メモリ使用になる．

量の現象やパフォーマンスの改善につながることを，実際の歩行者シミュレーションのサブセットに適用し7 まとめて確認した.

本研究では，エージェントシミュレーションのよう今後は同期機構をさらに拡張し，finished 構文の自な不均一で大規模な並列タスクを持つアプリケーショ動挿入やスレッド分割の自動化などを検討している.

ンに有効な軽量なバリア同期機構を開発した. 並列タ

スレッド分割を自動化を行うことで一般的なバリア同スクが不均一の場合，一般的な全てのスレッドに対す期と同じプログラムを並列タスク数が増加しても効るバリア同期を用いると，タスク数が増加した際，大率よく実行することが可能となる.

量の待機スレッドが発生する. 本研究では待機スレッ

謝辞 本研究を進めるにあたり，産業総合研究所のドの数を削減するため，実行時に対象のタスクを指野田五十樹氏，山下倫央氏には，産総研で開発してい定可能なグループバリア同期機構を開発し，また，スる CrowdWalk のソースコードの提供を始め、様々なレッド分割に対応した API も用意した. これらを組情報や助言をいただきました。深く感謝いたします。

また本研究は JST CREST の支援を受けています。

参 考 文 献[1] Apache Commons. Javaflow. http://commons.
apache.org/sandbox/javaflow/.
[2] RIFE Java web application framework. http://rifers.org/.
[3] MPI A Message-Passing Interface Standard 3.0,
2012.

[4] OpenMP Application Program Interface Version 3.0, May 2008.
http://www.openmp.org/
mp-documents/spec30.pdf.
[5] Shirako, J., Peixotto, D. M., Sarkar, V., andScherer, W. N.: Phasers: A Unified Deadlock-freeConstruct for Collective and Point-to-point Synchronization, Proceedings of the 22Nd Annual International Conference on Supercomputing, ICS ’08,
New York, NY, USA, ACM, 2008, pp. 277–288.
[6] X10 Language Specification version 2.4, May2012.