（様式 20）成果報告書

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

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

邦文抄録（300 字程度）
当研究グループでは、大規模並列計算機において高性能な並列プログラムを容易に開発できるようにすることを目的として、タスク並列プログラミングモデルに関する研究を行っている。本研究課題では、昨年度から引き続いて、当研究グループで開発している分散メモリ並列計算機向けタスク並列処理系 MassiveThreads/DMの性能改善・機能追加を実施し、TSUBAME 上での動作確認と性能評価を行った。結果として、二分木上再帰タスク生成、Unbalanced Tree Search、N クイーン問題の 3 つのベンチマークプログラムについて、171 ノード
2048 コア使用時に良好な負荷分散性能が得られることを確認した。
英文抄録（100 words 程度）
Our group has studied task-parallel programming models to improve productivity in developing
high performance parallel programs on large-scale distributed memory machines. In this project, we
conducted performance improvement for MassiveThreads/DM, a library providing task-parallelism
on distributed memory machines, and performance evaluation on the TSUBAME supercomputer. As
a result, we confirmed that MassiveThreads/DM achieved good scalability in three benchmark
programs (Binary Task Creation, Unbalanced Tree Search, NQueens) with 2048 processors.

Keywords:Parallel programming, task-parallelism, global work stealing, global address space

背景と目的
近年、並列計算機の複雑化が進んでいる。特に分散framework など)という形で実現され、広く使われるようになってきている。

メモリ並列計算機は、単に構成する計算ノードの数が当研究グループでは、その一環として、次の二つの増えているだけでなく、計算ノード内に複数の CPU を持システムから構成される分散メモリ並列計算機向けタ

ち、さらに CPU 内にプロセッサコアを複数持つような複スク並列処理系 MassiveThreads/DM を提案する。

雑な構成も珍しくなくなっている。このような並列計算機

1. 分散メモリ並列計算機において、ノード間負荷分散の性能を最大限引き出すためには、複数のメモリ・ネッを実現するタスク並列ライブラリ：

トワーク階層について熟知し、その知識に基づいて並

従来のタスク並列ライブラリの多くは共有メモリ計列プログラムを記述しなければならない。

算機向けであり、ノード内での動的な負荷分散機

当研究グループでは、この問題を解決するために、能を提供する一方で、ノード間で負荷分散を行う(1)分割統治形式による通信効率の良い並列アルゴリ機能を提供しているものは数少ない。また、ノードズム(cache-oblivious アルゴリズム)を設計し、(2)そ間負荷分散機能を提供している処理系についても、のアルゴリズムによって再帰的に分解されるタスク・デコード変換を用いてタスクのマイグレーションを実ータを、各メモリ・ネットワーク階層に適切に配置するよ装しており、利用するためには専用のコンパイラをうなタスク並列処理系の実現を目指している。このよう使う必要があるなど、利便性の点で問題がある。

なタスク並列処理系は、共有メモリ並列計算機では軽この問題に対して、提案するタスク並列ライブラ

量 マ ル チ ス レ ッ ド 処 理 系 (Cilk, Java fork/join

リでは、タスクのもつスタックをノード間で転送する

（様式 20）成果報告書ことにより、コード変換を用いない C ライブラリとし[Saraswat et al. 2011]による動的負荷分散を実装し、ての実装を実現する。

比較評価を実施した。ライフライン方式は、プロセッサ

2. タスク並列処理系からの利用に特化した大域アドレ間のタスク分散の流れをあらかじめライフライングラフ

ス空間ライブラリ：と呼ばれるグラフで表現しておき、ワークスティーリング

タスク並列モデルと大域アドレス空間モデルを組が失敗したときにライフライングラフにより規定されるタみ合わせるにあたっては、タスク並列モデルの「計スクの流れに基づいてタスクを受け渡すことにより、タ算機のもつ並列性と比べて非常に多くのタスクがスクを分散させていく負荷分散方式である。ライフライ生成される」という特徴が問題となる。既存の大域ン方式を用いることによって、ワークスティーリングによアドレス空間モデルにおいては、大域メモリにアクる通信処理コストを低減させることができる。

セスする際に、アクセスするメモリ領域の実体が存

また、大域アドレス空間機構については、従来は分在するノードとの通信が発生する。これは、前述の散配列の各プロセッサへの分散方式は 1 次元分散のタスク並列モデルの性質と組み合わせたときに、みであったところを、二次元分散を指定可能とするなど、大量に生成されたタスクがそれぞれ通信を行うこ

プログラマによる性能チューニングのための機構を新ととなり、(1)通信の準備にかかるオーバーヘッドたに実装した。

がタスクの数だけ発生し、また(2)データ量の少ない通信によって通信帯域を活用できないといった点で、計算機のもつ性能を最大限活用する上での障害となる。

結果および考察

MassiveThreads/DM の細粒度スレッド機構に関して、TSUBAME 上で動作確認をするとともに処理提案する大域アドレス空間ライブラリでは、この系の性能を評価するため、TSUBAME の 171 ノード問題を解決するため、既存の大域アドレス空間モ2048 プロセッサを用いた構成で評価実験を実施しデルに対して、次の二つの機能を新たに導入すた。

る。
(a) キャッシュ機能： タスク間で共有されるキャッシュ領域を提供する。この機能を利用することに動作確認と性能評価にあたっては、次の 3 つのベンチマークプログラムを用いて、そのタスク生成性能(1 秒間あたりのタスク生成数)を計測した。

よって、あるタスクがまとめてデータを読み込み、他のタスクは通信なしでキャッシュからデータを読むだけで済むようにすることが可能になる。

1. 二分木状再帰タスク生成: 指定した再帰レベル
まで、各タスクが二つの子タスクを再帰的に生成(b)大域メモリの配置を動的に変更する機能(ペするベンチマークである。比較的負荷分散が容ージマイグレーション): タスクがプロセス間を移易なベンチマークであり、処理系の基礎的な負動した際に、タスクのアクセスする大域メモリも同荷分散性能を評価するために用いる。

時に移動させることができる。

2. Unbalanced Tree Search: 乱数を用いて不規則な状態空間を再帰的に探索するベンチマーク

概要
本利用課題では、昨年度から引き続いて、である。このベンチマークは、負荷分散性能の評価を目的として作られたもので、タスク並列処理

TSUBAME を用いた MassiveThreads/DM の設計・系の評価に広く用いられているものである。

開発を実施した。今年度は主に軽量タスク機構につい3. N クイーン問題: N クイーン問題を解くベンチマて、実装方法の見直しによって、タスク生成コストを低ークプログラムであり、BOTS ベンチマークスイ減するとともに、負荷分散性能の改善に取り組んだ。まートから MassiveThreads/DM 上に移植した。

た、これまで用いてきたワークスティーリングによる動

このベンチマークもタスク並列処理系の評価に的負荷分散に加えて、新たにライフライン方式広く用いられているものである。

各ベンチマークの評価結果を図 1、図 2、図 3 に示す。グラフ凡例中の lifeline は、ライフライン方式による負荷分散を示し、random backoff は、単純なワークスティーリングによる負荷分散に加えて、ワークスティーリング失敗時にワークスティーリングにかかった時間に基づいたバックオフを設けたものを示す。random backoff によるバックオフ時間は、前回Performance (millions of tasks generated)（様式 20）成果報告書
Binary Tree Creation Performance(tree depth=36)
7000
6000
5000
4000
3000
2000
1000
00256ィーリングにかかった時間を Tsteal として、rand(0, 1)
×2Nfail× Tsteal という式を用いて決定される。

Performance(millions of tasks generated)

exponential backoff は、random backoff におけで失敗した回数を Nfail (≦32) 、前回のワークステ

1024 1280 1536 1792 2048
# of cores
random backoff
ideal

図 1. 二分木状タスク生成のタスク生成性能て 、 rand(0, 1) × Tsteal で 決 定 さ れ る 。 ま た 、

そのバックオフ時間は、ワークスティーリングに連続

768

lifelinerandom backoffのワークスティーリングにかかった時間を Tsteal としるバックオフ時間の上限を指数的に増やしたもので、

512

Unbalanced Tree Search Performance(tree depth=17)
2500
2000
1500
1000
500
00256

512

結果として、各ベンチマークについて、2048 プロセッサ構成までの動作を確認し、良好な台数効果が得

768 1024 1280 1536 1792 2048
# of cores
lifelinerandom backoff
exponential backoff
ideal

られていることがわかった。また、どのベンチマークプログラムについても、ライフライン方式を用いるより

図 2. Unbalanced Tree Search のも通常のワークスティーリングにバックオフを加えたタスク生成性能ものの方が良好な性能が得られていることがわかる。
は、アルゴリズムの性質上、従来のワークスティーリングと比較して 1 度に盗まれる(潜在的な)タスクの数が小さくなりがちで、結果としてプロセッサ間のタスクの受け渡し回数が増加してしまうことによると推測している。
まとめ、今後の課題
本利用課題では、昨年度から引き続き、分散メモリ

NQueens (N=17) Performance
Performance(millions of tasks generated)

この原因は現在調査中であるが、ライフライン方式

250200150
1005000256

512768 1024 1280 1536 1792 2048
# of cores
lifelinerandom backoff
exponential backoff
ideal

図 3. N クイーン問題のタスク生成性能並列計算機における並列プログラミングの生産性を改善することを目的として、分散メモリ並列計算機向けタムバックオフを加えたものについて、ライフライン方式よスク並列ライブラリ MassiveThreads/DM の設計・開りも良好な性能を得られることを確認した。

発を実施した。TSUBAME 上での性能評価の結果、今後は、今回実験を行わなかった、大域メモリへの二分木状タスク生成、Unbalanced Tree Search、N ク

アクセスがボトルネックとなるようなアプリケーションにイーン問題の 3 つのベンチマークプログラムについて、ついて、性能評価を進めるとともに、通信回数を抑える

171 ノード 2048 プロセッサ構成で良好な台数効果が得ようなタスクスケジューリング手法の導入や、効率的なられていることを確認した。また、単純なワークスティー大域メモリの配置手法を検討していく予定である。

リングに加えて、ライフライン方式による負荷分散の性能評価を実施し、単純なワークスティーリングにランダ