（様式 20）成果報告書

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

利用課題名 高性能と高生産性を両立する並列分散ランタイムシステム
英文：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 つのベンチマークプログラムについて良好な負荷分散性能が得られることを確認した。
英文抄録（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 task-parallel library for distributed
memory machines, and performance evaluation on the TSUBAME supercomputer. As a result, weconfirmed that MassiveThreads/DM achieved good scalability in three task-parallel benchmark
programs (Binary Task Creation, Unbalanced Tree Search, NQueens).

Keywords: Task parallelism; lightweight multithreading; thread migration; distributed work
stealing; remote direct memory access

背景と目的なタスク並列処理系は、共有メモリ並列計算機では軽

近年、並列計算機の複雑化が進んでいる。特に分散量 マ ル チ ス レ ッ ド 処 理 系 (Cilk, Java fork/join

メモリ並列計算機は、単に構成する計算ノードの数がframework など)という形で実現され、広く使われるよう増えているだけでなく、計算ノード内に複数の CPU を持になってきている。

ち、さらに CPU 内にプロセッサコアを複数持つような複当研究グループでは、その一環として、次の二つの雑な構成も珍しくなくなっている。このような並列計算機システムから構成される分散メモリ並列計算機向けタの性能を最大限引き出すためには、複数のメモリ・ネッ

ス ク 並 列 処 理 系 MassiveThreads/DM を 提 案 す る 。

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

MassiveThreads/DM は以下の要素技術で構成される:列プログラムを記述しなければならない。

1. 分散メモリ並列計算機において、ノード間負荷分散

当研究グループでは、この問題を解決するために、を実現するタスク並列ライブラリ：(1)分割統治形式による通信効率の良い並列アルゴリ

従来のタスク並列ライブラリの多くは共有メモリ計

ズム(cache-oblivious アルゴリズム)を設計し、(2)そ算機向けであり、ノード内での動的な負荷分散機のアルゴリズムによって再帰的に分解されるタスク・デ能を提供する一方で、ノード間で負荷分散を行うータを、各メモリ・ネットワーク階層に適切に配置するよ機能を提供しているものは数少ない。また、ノードうなタスク並列処理系の実現を目指している。このよう間負荷分散機能を提供している処理系についても、

（様式 20）成果報告書
コード変換を用いてタスクのマイグレーションを実開発を実施した。今年度は主に軽量マルチスレッド機装しており、利用するためには専用のコンパイラを能の高性能化に取り組んだ。

使う必要があるなど、利便性の点で問題がある。

MassiveThreads/DM の軽量マルチスレッド機能は、この問題に対して、提案するタスク並列ライブラ

生成した軽量スレッドをノード間で移動させることによっ

リでは、タスクのもつスタックをノード間で転送するて、動的な負荷分散(ワークスティーリング)を行っていことにより、コード変換を用いない C ライブラリとしる。これまでの軽量マルチスレッド実装は、既存のスレての実装を実現する。

ッ ド マ イ グ レ ー シ ョ ン 手 法 で あ る iso-address 法

2. タスク並列処理系からの利用に特化した大域アドレ[Antoniu et al.,1999] を 用 い て 実 装 し て い た が 、ス空間ライブラリ：

iso-address 法には負荷分散のスケーラビリティに関しタスク並列モデルと大域アドレス空間モデルを組て次の二つの制約が存在する:

み合わせるにあたっては、タスク並列モデルの「計(1) スレッドのスタック領域を割り当てるために、プ算機のもつ並列性と比べて非常に多くのタスクがロセッサ数に比例した仮想アドレス空間を1ノー生成される」という特徴が問題となる。既存の大域ドごとに予約しておく必要がある。例えば、300

アドレス空間モデルにおいては、大域メモリにアク万並列の環境で、1ワーカ上で同時に存在しうセスする際に、アクセスするメモリ領域の実体が存るスレッド数を8192個、スレッドスタックのサイ在するノードとの通信が発生する。これは、前述のズを16KBとすると、必要な仮想アドレス空間のタスク並列モデルの性質と組み合わせたときに、サイズは222+13+14 バイトとなる。これは現在の大量に生成されたタスクがそれぞれ通信を行うこ

x86-64プロセッサの仮想アドレス空間の上限ととなり、(1)通信の準備にかかるオーバーヘッドである248バイトを越えており、このような環境でがタスクの数だけ発生し、また(2)データ量の少なはiso-address法を適用することができない。

い通信によって通信帯域を活用できないといった点で、計算機のもつ性能を最大限活用する上での障害となる。
提案する大域アドレス空間ライブラリでは、この問題を解決するため、既存の大域アドレス空間モデルに対して、次の二つの機能を新たに導入する。
(a) キャッシュ機能： タスク間で共有されるキャッシュ領域を提供する。この機能を利用することによって、あるタスクがまとめてデータを読み込み、他のタスクは通信なしでキャッシュからデータを読むだけで済むようにすることが可能になる。
(b)大域メモリの配置を動的に変更する機能(ページマイグレーション): タスクがプロセス間を移動した際に、タスクのアクセスする大域メモリも同時に移動させることができる。

(2)

スケーラブルなワークスティーリングを実現するためには、Remote Direct Memory Access(RDMA) を用いた片側タスクスティーリングが重要である [Dinan et al., 2009]。RDMA を用いてスレッドマイグレーションを実装するためには、各スレッドのもつスタック領域を物理メモリに固定する必要があるが、iso-address 法によるスレッドマイグレーションでは、スレッドのスタック領域が広大な仮想アドレス空間のどこかに割り当てられるようになっているため、スレッドスタックとして使われる領域をすべて物理メモリに固定することは不可能である。

我々は、これらの問題を解決し、スケーラブルな負荷分散を実現するため、仮想メモリ使用量を逐次実行時と同程度にまで削減するスレッドマイグレーション方式
uni-address 法を新しく提案した。Uni-address 法は、

概要
本利用課題では、昨年度から引き続いてTSUBAME を用いた MassiveThreads/DM の設計・

iso-address 法が「すべてのスレッドが常に正しい仮想アドレス上に配置されている」という仮定を保つように設計されているのに対して、「すべてのスレッドが少なくと（様式 20）成果報告書

図 1. Uni-address 法におけるコンテキストスイッチの動作も実行中に正しい仮想アドレス上に配置されていればUni-address threads (server)

125 cycles

よい」という考えに基づいてスレッドマイグレーションをUni-address threads (polling)

286 cycles実現している。

MassiveThreads

125 cycles

以下、uni-address 法の基本動作を説明する。まず、スタックを配置する領域を uni-address 領域と RDMA

図 2. スレッド生成オーバーヘッド領域の二つに分ける。 Uni-address 領域は実行中スレッドを配置する領域で全ノードで同じ仮想アドレスを割り当てておく。RDMA 領域は停止中のスレッドのスタックを退避するための領域で、任意の仮想アドレスを割り当ててよいものとする。Uni-address 法では、すべてのスレッドの仮想アドレスを uni-address 領域の仮想アドレス上に割り当てる。そして、あるスレッドにコンテキストスイッチする際には、実行中スレッドのスタック領域を RDMA 領域に退避したのち、実行したいスレッドの図 3. ワークスティーリングにかかる時間の内訳

スタック領域を uni-address 領域にロードした上でスレッドのコンテキストを復元する (図 1)。ノードをまたがってスレッドを移動させる際には、移動元ノードの RDMA回数を N としたとき O(N)回にまで削減できる。

領域から移動先の uni-address 領域へスレッドスタック

我々は、uni-address 法を用いたスレッドマイグレーを RDMA 転送したのち、そのスレッドのコンテキストをションを提供する軽量マルチスレッドライブラリ復元すればよい。このようにスレッドを管理することで、

uni-address threads を TSUBAME 上に実装した。

実行中のスレッドについて常に正しい仮想アドレス上に実 装 に あ た っ て は 、 RDMA 通 信 ラ イ ブ ラ リ で あ る配置することができる。

GASNet を 用 い て 行 っ た 。 GASNet は RDMA

Uni-address 法では、コンテキストスイッチのたびにREAD/WRITE をサポートしている一方で、ワークステRDMA 領域へのスタックの退避が必要で、従来の軽ィ ー リ ン グ キ ュ ー の 実 装 に 必 要 な RDMA

量スレッド実装と比較してスレッド操作のオーバーヘッ

fetch-and-add などのアトミック命令をサポートしていドが大きくなる。そこで我々は、典型的なワークスティーない。そこで我々は、RDMA fetch-and-add を 2 つのリングスケジューラについて、uni-address 領域に複数方法を用いてソフトウェア実装した。一つは 1 計算コアのスレッドを同時に配置できるようにすることで RDMAごとに 1 通信コアを割り当て、通信コアに領域への退避を削減する手法を開発した。この手法をfetch-and-add を処理させる方法で、RDMA のもつ、用いると、スタックコピーの回数をワークスティーリング

通信相手との同期を必要としない通信方式を再現する

（様式 20）成果報告書ものである(server ベース実装)。もう一つは、計算の最中に定期的に fetch-and-add リクエストが到着しているかどうか確認し、fetch-and-add 処理を実行する方式である(polling ベース実装)。こちらは通信用のコアを用意する必要がなく、すべてのコアを計算に用いることができる。

結果および考察
本利用課題では、uni-address threads の性能評価を行った。具体的には、スレッド生成オーバーヘッドの評価、1 回のワークスティーリングにかかる時間の評価、3 つの負荷分散ベンチマークによる仮想メモリ使用量と負荷分散性能の評価を行った。
スレッド生成にかかるオーバーヘッドを図 1 に示す。
図 2 を見ると、提案手法のスレッド生成オーバーヘッド
は 125 cycles と十分小さく、既存の共有メモリ環境向け軽量マルチスレッドライブラリである MassiveThreadsと同等のオーバーヘッドとなっている。polling ベース実装 の ス レ ッ ド 生 成 オ ー バ ー ヘ ッ ド が 285 cycles とserver ベース実装に対し て大きくなっているのは、
fetch-and-add リ ク エ ス ト の 到 着 確 認 の コ ス ト(gasnet_AMPoll 関数の呼び出し) が原因である。
図 3 に示すのは 1 回のワークスティーリングにかかる時間の内訳である。図中の suspend と resume がuni-address 法によるオーバーヘッドを示しており、ワークスティーリング全体にかかる時間に占める割合は十分小さいことが確認できる。
Binary Task Creation、Unbalanced Tree Search、

図 4. 各負荷分散ベンチマークのスケーラビリティ
まとめ、今後の課題

NQueens ソルバの 3 つの負荷分散ベンチマークを実

本利用課題では、分散メモリ環境向けタスク並列ライ行したときの uni-address threads の並列性能を図 4ブラリ MassiveThreads/DM の設計・実装を進めた。に示す。どのベンチマークについても、RDMA ワークス

本年度は、特に軽量マルチスレッド機能の負荷分散性ティーリングを再現している server ベース実装につい能の改善に取り組んだ。従来のスレッドマイグレーショては良好なスケーラビリティが得られている。一方で、ン手法に基づくワークスティーリング実装では RDMAワークスティーリング時に計算コア間で同期が必要なを用いた片側タスクスティーリングを実現できないため、polling ベース実装では一部スケーラビリティの低下を負荷分散性能に課題があった。我々は、RDMA 通信確認した。

でスレッドを転送できる新しいスレッドマイグレーション

これらのベンチマークは、スタック領域の仮想メモリ手法である uni-address 法を新しく開発し、RDMA を使用量が 104KB 以下で動作することを確認している。

用いたスケーラブルなワークスティーリングを実現した。
今後は、より多くのコアを用いた実験を行い、高並列時の性能評価を進める予定である。