（様式 20）成果報告書

TSUBAME 共同利用 平成 24 年度 学術利用 成果報告書

高性能と高生産性を両立する並列分散ランタイムシステム
Parallel and Distributed Runtime System Realizing High Performance and High Productivity
田浦 健次朗Kenjiro Taura
東京大学 情報理工学系研究科
Graduate School of Information Science and Technology, The University of Tokyo

当研究グループでは、大規模並列計算機において高性能な並列プログラムを容易に開発できるようにすることを目的として、タスク並列プログラミングモデルに関する研究を行っている。本研究課題では、その一環として、分散メモリ並列計算機においてノード間負荷分散を自動化するタスク並列ライブラリと、タスク並列処理系からの利用に特化した大域アドレス空間ライブラリを設計・実装し、TSUBAME 上での動作確認と性能評価を実施する。結果として、タスク並列・大域アドレス空間の両方を使用する基礎的なベンチマークプログラムにおいて、良好な台数効果が得られることを確認した。
Our group studies task-parallel programming models to improve productivity in developing highperformance parallel programs. In this project, as part of this effort, we design and implement atask-parallel library supporting automatic load balancing in distributed memory machines and a
global address space library specialized for task parallelism. As a result, our system could achieve goodspeedup in a benchmark program using both task parallelism and global address space.

Keywords: parallel programming, task parallelism, load balancing, global address space

１

背景と目的
近年、並列計算機の複雑化が進んでいる。特に分散1. 分散メモリ並列計算機において、ノード間負荷分散を実現するタスク並列ライブラリ：

メモリ並列計算機は、構成する計算ノードが増加してい従来のタスク並列ライブラリの多くは共有メモリ計ることに加えて、計算ノード内に複数の CPU を持ち、さら算機向けであり、ノード内での動的な負荷分散機に CPU 内にプロセッサコアを複数持つような階層的な構能を提供する一方で、ノード間で負荷分散を行う成などを採用するものも珍しくなくなっている。このよう機能を提供しているものは数少ない。また、ノードな並列計算機の性能を最大限引き出すためには、複間負荷分散機能を提供している処理系についても、数のメモリ・ネットワーク階層について熟知し、その知識コード変換を用いてタスクのマイグレーションを実に基づいて並列プログラムを記述しなければならず、こ装しており、利用するためには専用のコンパイラをのことが高性能な並列プログラムの開発を難しいもの使う必要があるなど、利便性の点で問題がある。としている。

この問題に対して、提案するタスク並列ライブラ

当研究グループでは、この問題に対して、(1)分割統リでは、タスクのもつスタックをノード間で転送する治形式で通信効率の良い並列アルゴリズムを設計し、ことにより、コード変換を用いない C ライブラリとし(2)そのアルゴリズムによって再帰的に生成されるタスての実装を実現する。

クを、各メモリ階層に適切に配置するようなタスク並列

2. タスク並列処理系からの利用に特化した大域アドレ処理系を実現することによって、解決することを試みてス空間ライブラリ：いる。

タスク並列モデルと大域アドレス空間モデルを組

本利用課題では、その一環として次の二つのシステ

み合わせるにあたっては、タスク並列モデルの「計ムを設計・実装し、TSUBAME 上で動作確認と性能評価を算機のもつ並列性と比べて非常に多くのタスクが行うことを目的とする。

生成される」という特徴が問題となる。既存の大域

（様式 20）成果報告書
アドレス空間モデルにおいては、大域メモリにアクページマイグレーションを導入するにあたっては 、大セスする際に、アクセスするメモリ領域の実体が存域メモリをページと呼ぶ単位で分割し、各ページについ在するノードとの通信が発生する。これは、前述のてホームプロセスと呼ぶプロセスを割り当てる。ホーム

タスク並列モデルの性質と組み合わせたときに、プロセスは、ページがどのプロセス上に存在するかを大量に生成されたタスクがそれぞれ通信を行うこ管理するプロセスで、大域メモリにアクセスする際には、ととなり、(1)通信の準備にかかるオーバーヘッド

まずアクセスするページのホームプロセスにデータのがタスクの数だけ発生し、また(2)データ量の少な所在を問い合わせてから、データの転送を行う。

い通信によって通信帯域を活用できないといったタスク並列ライブラリに関しては、共有メモリ計算機点で、計算機のもつ性能を最大限活用する上での向け軽量マルチスレッドライブラリである障害となる。

MassiveThreads をベースとして、ノード間負荷分散機提案する大域アドレス空間ライブラリでは、この能を実装する。MassiveThreads をノード間負荷分散に問題を解決するため、既存の大域アドレス空間モ対応させるにあたっては、MassiveThreads の提供するデルに対して、次の二つの機能を新たに導入する軽量スレッドをノード間で移動させる必要がある。提案[1]。

ライブラリでは、コード変換を用いない実装手法として、(a) キャッシュ機能： タスク間で共有されるキャスレッドのスタックを全プロセスで一意な仮想アドレス上ッシュ領域を提供する。この機能を利用することにに割り当て、移動先プロセスにおいて移動元と同じアド

よって、あるタスクがまとめてデータを読み込み、レスにスタックを配置することによって、スレッドのノード他のタスクは通信なしでキャッシュからデータを読間移動を実現する。

むだけで済むようにすることが可能になる。
(b)大域メモリの配置を動的に変更する機能(ペ３

結果および考察ージマイグレーション): タスクがプロセス間を移提案する大域アドレス空間ライブラリとタスク並列ラ動した際に、タスクのアクセスする大域メモリも同イブラリの有効性を調査するために、評価実験を行っ時に移動させることができる。

た。まず、開発した大域アドレス空間ライブラリの基本性能を調査するため、2 つのノードを用いてデータサイ２

概要ズを変化させながら、通信にかかった時間を計測した。

提案システムを実装するにあたっては、まず大域アドその結果を図 1 に示す。 local は大域メモリの実体がレス空間ライブラリを実装し、その後、大域アドレス空自ノードに存在する場合、remote は大域メモリの実体間ライブラリの機能を用いてタスク並列ライブラリを実が他ノードに存在する場合を示している。図 1 を見ると、装する。なお、大域アドレス空間ライブラリを実装する

GASNet の GET 操作には 2-3 マイクロ秒程度かかる

にあたっては、下位通信ライブラリとして GASNet を用のに対し、提案システムの通信遅延は 10 マイクロ秒程いる。

度であった。一方自ノードに大域メモリの実体が存在す提案する大域アドレス空間ライブラリは、る場合については、GASNet では 10 ナノ秒程度である

Partitioned Global Address Space (PGAS)をベースのに対し、1 マイクロ秒程度かかっている。これは、大として、キャッシュ機能とページマイグレーションを提供

域メモリを管理するページテーブルの操作が複雑であする。大域メモリに対するキャッシュ機能を導入するにることと、実装の最適化が進んでいないことが一つの原あたっては、キャッシュの一貫性の保証をプログラマの因と考えている。また、すでにキャッシュされたデータへ責任とするようなプログラミングモデルを採用することのアクセスにかかる時間を計測した結果、70 ナノ秒程によって、高いスケーラビリティを実現する。

度でアクセス可能であることがわかっている。

（様式 20）成果報告書
データサイズ (bytes)

1.00E+00
1.00E-01て、ワークスティールが多発するフェーズにおける通信local
remotegasnet_getv local
gasnet_getv remotememcpy1.00E-02
通信時間 (sec)に関しては、ランダムなバックオフを設定することによっ

1.00E-03
1.00E-04の衝突が緩和されたことが確認できている。
４

まとめ、今後の課題
本利用課題では、分散メモリ並列計算機における並1.00E-05

列プログラミングについて、生産性と性能を両立するタ

1.00E-06

スク並列プログラミングシステムを設計・実装し、その1.00E-07性能評価を行った。結果として、フィボナッチ数など基1.00E-08

本的なベンチマークプログラムについて良好な台数効

1.00E-09

果が得られた。

図 1. 大域メモリに対する GET 操作の実行時間

価や、行列積など大域的な配列を用いる必要のあるベ

9e+06

fib (J=0, B=0)
fib (J=1, B=0)
fib (J=1, B=1)
fib (J=1, B=2)
ideal

8e+06
7e+06
6e+06
Tasks/sec

今後は、より多くのプロセッサを用いた場合の性能評ンチマークを用いて性能評価を実施していく予定である。
また、当研究グループでは、本利用課題と並行して、共有メモリ並列計算機での Adaptive Mesh Refinement

5e+06

や Fast Multipole Method といった数値計算手法の4e+06

タスク並列実装[2,3]を行っており、これらの手法につい3e+06て、提案ライブラリを用いて並列化し、その性能を評価2e+06したいと考えている。

1e+06
0244872
96 120# of processes

144

168192

図 2. フィボナッチ数計算におけるタスク生成性能(1 秒間あたりタスク生成数)
さらに、開発したタスク並列ライブラリの基本性能を調査するため、フィボナッチ数列を再帰的に計算するベンチマークプログラムを用いて、タスク生成のコストとスケーラビリティを計測した。その結果を図 2 に示す。図中の J はタスク間同期処理の際に、タスクを生成したプ
ロセスにタスクを移動させた後に同期処理を行ったかどうかを示し、B はワークスティール失敗時に次のワークスティールを試行するまでのバックオフ時間を設定するか(B=1)、ランダムなバックオフ時間を設定するか(B=2)、バックオフ時間を設定しないか(B=0)を示している。結果として、J=0 から J=1 とした場合には、発生する通信の数は減少したものの、性能はほとんど改善しなかった。また、バックオフ時間に関しては、ランダムでないバックオフ時間を設定した場合では若干の性能向上が見られたが、実行ごとに性能の揺れが激しくなっている。さらに、バックオフ時間にランダム性をもたせた場合には、良好なスケーラビリティが得られている。これ

参考文献
[1]

秋山茂樹，田浦健次朗．軽量マルチスレッディン

グ向け大域アドレス空間ライブラリ．並列／分散／協調処理に関するサマー・ワークショップ(SWoPP2012)．鳥取．2012 年 8 月．
[2]

Kenjiro Taura, Jun Nakashima, Rio Yokota,

and Naoya Maruyama. A Task Parallelism Meets
Fast Multipole Methods. Workshop on Latest
Advances in Scalable Algorithms for Large-Scale
Systems (ScalA). Nov 2012.
[3]

河野 瑛，田浦健次朗．タスク並列モデルを用いた Tree-based AMR の評価．並列／分散／協調処理に関するサマー・ワークショップ(SWoPP2012)．鳥取．
2012 年 8 月．