Comments
Description
Transcript
マルチノードGPU上のコレスキー分解への データドリブン型アルゴリズム
Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report マルチノード GPU 上のコレスキー分解への データドリブン型アルゴリズムの適用 辻田 裕紀1 遠藤 敏夫1,2 概要：重要な数理最適化問題の１つに半正定値計画問題がある。この問題の内部ではコレスキー分解が行 われており、GPU 上で計算することで高速化することができる。しかし、GPU メモリの容量は CPU メ モリに比べて小さく、GPU メモリを越える行列に対応するためにデータの入れ替えを行う必要があるが、 このとき CPU-GPU 間の通信がボトルネックになってしまう。本論文ではマルチノード・マルチ GPU 上 のコレスキー分解に対してデータドリブン型アルゴリズムを適用し、適切にタスクを選択し、GPU メモリ の再利用性を考慮しながらデータを入れ替えることで CPU-GPU 間の通信量を削減することを提案する。 1. はじめに おいて、計算速度に対する相対バンド幅がさらに低下する とカバーしきれなくなると考えられる。 近年、GPU を科学計算などの汎用計算に用いる GPGPU 本論文では上記の問題のさらなる改善のために、マルチ が注目されている。GPU は高い演算能力とバンド幅をも ノード・マルチ GPU 上のコレスキー分解において、デー ち、CPU よりも優れたスループットを持っている。2014 タの再利用性を考慮したデータドリブン型アルゴリズムを 年 6 月の TOP500[1] で世界 2 位となった Titan[2] や東京 適用する。アルゴリズムを概念的にタスクグラフで表し、 工業大学学術国際センターに設置されているスーパーコン 動的タスクスケジューリングを行う。その過程で次に行う ピュータ TSUBAME2.5 [3] は、演算性能の大部分を GPU タスクを適切に選び、GPU メモリの再利用性を考えてデー が寄与しており、高い演算性能および電力性能比をだして タの入れ替えを行うことで CPU-GPU 間の通信量を減ら いる。 すことを提案する。 今日、適用範囲の広さから重要と考えられている数理最適 これにより、PCIe 通信量を 1 ノードのとき最大で 8.6%ま 化問題の 1 つに半正定値計画問題 (SemiDefinite Program) で、4 ノードでは GPU メモリを超えない場合に 9.6%、GPU があり、その高性能大規模ソルバーとして SDPARA[5] が メモリを超える場合でも最大で 30%までの削減を達成し 公開されている。その重要カーネルである密行列に対す た。また計算速度でも 16 ノード、行列サイズ 110592 で るコレスキー分解処理はマルチ GPU 実行対応されており 7263GFlops を達成した。 (以下 SDPARA GPU 版と呼ぶ [4][6])、TSUBAME2.5 の 本論文では第 2 章で研究の背景について説明し、第 3 章 4080GPU を用いて 1.7PFlops の性能を出している。SD- でアルゴリズムの実装概要とタスク選択および GPU メモ PARA GPU 版では、対応可能な問題サイズを拡大するた リの掃出し戦略を示す。第 4 章では実験を行い、アルゴリ めに、行列サイズが容量の限られている GPU メモリを超 ズムの性能評価を行う。そして、第 5 章で関連研究を紹介 える場合に対応している。このような状況で GPU による し、第 6 章でまとめと今後の課題について考察を行う。 計算を行うには、GPU メモリのデータを入れ替えて計算 を繰り返すことが必要である。このとき、CPU メモリは GPU から見て PCI-Express(PCIe) の先にあるメモリであ り、CPU-GPU 間の通信がボトルネックとなってしまう。 2. 背景 2.1 GPGPU GPGPU(General Purpose Graphics Proccessing Unit) これを緩和するために、ブロッキングアルゴリズムにおけ とは、GPU（Graphics Processing Unit）の演算資源を画 るブロックサイズを大きいサイズにチューニングする対応 像処理だけでなく、汎用計算に活用する技術のことである。 などが行われてきた [7]。しかし今後のアーキテクチャに GPU は主に動画やゲームなどに必要な画像処理を行うた 1 2 東京工業大学 東京工業大学学術国際情報センター ⓒ 2014 Information Processing Society of Japan めに特化したプロセッサである。主にビデオカードに搭載 され、PCI Express バスのスロットに装着し、パソコンの 1 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report 拡張ハードウェアとして用いられる。GPU はパソコンに 装着して使用することを前提に作られており、GPU 単体 では動かず、主演算装置の CPU の制御のもとで動作する。 CPU は逐次計算を高速に実行することに重点が置かれた いるのに対し、GPU はスループットを高めることに重点 が置かれている。そのため、GPU は非定型的な処理は不 得意であるが、CPU の数十倍の以上の計算性能をもって いる。GPU を汎用計算に使う方法は、OpenCL を用いる 方法や NVIDIA 社が開発した CUDA などがある。本論文 では NVIDIAGPU 上の CUDA を用いて実装を行ったが、 図 1 ブロックコレスキー分解のスナップショット J. Choi ら [8] の図 5 より転載 ( 2 ) PDTRSM：列パネル L21 を計算するプロセスすべて に L11 が送られ、L21 を計算する。 提案手法は汎用的である。 L21 ←− A21 (Lt11 )−1 2.2 コミュニケーションアボイディング 近年、高性能計算の分野でコミュニケーションアボイ ( 3 ) PDSYRK：列パネル L21 の列がすべてのプロセス列 ディングの必要性が訴えられている。並列ソフトウェアの で行ごとに送られて転置される。このとき、各プロセ 実行時間は計算時間と通信時間の 2 つに分けられるが、計 スは元々の L21 の部分と Lt21 をもつ。それらを使い行 算に比べて通信にかかる時間が長くなりやすく、ボトル 列 A22 の一部分を更新する。 ネックとなってしまうことがある。また年向上率も Flops に比べてバンド幅は低くこの差は年々増え続けている。こ のことはコレスキー分解に置いても例外ではない。 A˜22 ←− A22 − L21 Lt21 図 1 はそのスナップショットを表している。SDPARA GPU 版は ScaLapack を基にして構成されており、各ルー 2.3 データドリブン型を導入するモチベーション チンの構造を保ちつつ、そのルーチンごとに PCIe 通信を コレスキー分解は N × N の対称正定値行列 A を下三角 行っているのが特徴である。これらのルーチンには依存関 行列 L と L の転置行列の積に分解する。つまり A = LLT 係があるが、依存関係はブロックごとに独立しているため、 という形の計算を行う。コレスキー分解を解くアルゴリズ 依存関係のないブロックのルーチン同士は同時に計算を行 ムの１つにブロックコレスキー分解がある。ブロックコレ うことができる。したがって、これらのルーチンをタスク スキー分解はコレスキー分解にブロック分割を行い並列環 とみなすことにより、データドリブン型のアルゴリズムに 境に対応したものである。ブロックサイズを nb とすると、 容易に変換することができる。 k ステップ目では、n × n の行列 A (k) をL (k) とL (k) T に分 解し、式を次のように表す。 ( ) ( )( ) A11 AT21 L11 0 LT11 LT21 = A21 A22 L21 L22 0 LT22 ( ) L11 LT11 L11 LT21 = L21 LT11 L21 LT21 + L22 LT22 ここでブロック A11 は nb × nb 、A21 は (n − nb ) × nb 、A22 は (n − nb ) × (n − nb ) であり、L11 と L22 は下三角行列で 現在の SDPARA GPU 版の実装では、各ルーチンを全 プロセスで同期しながら実行している。しかし、そのルー チンを行うブロックを持たないプロセスはその実行中何も 行わず、計算資源を無駄にすることになってしまう。デー タドリブン型では性質上、各ルーチンをプロセスごとに非 同期で実行することになり、無駄な待ち時間が減ることを 期待できる。MPI 通信においても SDPARA GPU 版では MPI Bcast により実装されていて、本質的に通信と計算の オーバーラップができない部分があるが、データドリブン ある。この式から、A11 の下コレスキー分解要素の L11 が 型のアルゴリズムではポイントツーポイントの非同期通信 既知であると仮定するとブロックコレスキー分解は次のよ を用いることで通信の粒度が細かくなり、通信のオーバー うに帰納的に推論される。 ヘッドは増えるものの、通信と計算のオーバーラップを行 L21 ←− A21 (Lt11 )−1 A˜22 ←− A22 − L21 Lt21 いやすくなる。また SDPARA GPU 版では各ルーチンご = L22 Lt22 ScaLapack ルーチンでは上の分解を次の順番で実行して いる。 ( 1 ) PDPOTF2：対角ブロック A11 を持つプロセスはコレ スキー分解をする。 A11 −→ L11 Lt11 ⓒ 2014 Information Processing Society of Japan とに計算するブロックとその計算に必要なブロックの行列 データ全体を CPU メモリから GPU メモリへ転送し、さら に行列データが GPU メモリの容量を超えるときには分割 して転送することで対応している。そのため GPU メモリ 上にあるデータを把握することが難しく、既に GPU メモ リにある行列のデータでもルーチンごとに再度送らなけれ ばならない。このように冗長な CPU-GPU 間通信が多く 2 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report 発生してしまっているが、データドリブン型では GPU メ モリ上のデータを把握するのが比較的容易にできるため、 GPU メモリ上にあるデータを利用することで、冗長な通 信を減らすことができると考えられる。 3. データドリブン型アルゴリズムの実装と タスク選択および GPU メモリ掃出し戦略 図 2 本章ではブロックコレスキー分解におけるデータドリブ タイル分割 ン型アルゴリズムの実装概要とタスク選択および GPU メ モリの掃出し戦略について詳しく説明する。 本プログラムではまず入力データをタイルという単位に 分割し、ブロックコレスキー分解の各ルーチンをタスクと して、タスクをタイル単位で実行するように実装している。 タイルには次の３つの実行状態を持つ変数を持たせている。 • RUNNABLE:タスクが実行可能な状態。 • FINISHED:そのタイルのタスクがすべて終了してい る状態。 • SLEEP:上記 2 つ以外。 また、タイルは実行ステップを表す変数ももっており、こ れを見ることで実行するべきタスクを判断することがで きる。各プロセスは実行可能なタスクを管理するための キューを持っている。まずプロセスはキューを確認し、タ スクが入っていればタスクを取り出し、GPU 上で実行す 図 3 MPI 通信パタン (2 段階に分けて行われる) る。このとき、GPU 上にすでにあるタイルのデータはその データを使うことにより冗長な通信が起こらないようにし 3.2 MPI 通信実装 ている。タスクが終了すると、依存関係のあるタイルのタ このプログラムでは、データドリブン型アルゴリズムを スクに通知を送り、必要なデータの揃ったタイルのタスク 採用しているため、各プロセスは独立して非同期でタスク を RUNNABLE にしてキューの末尾にプッシュする。もし を実行していく。そのため、MPI 通信も同様の性質を満た タスクを取り出す時、キューが空だったときはビジーウェ す必要がある。そのため、MPI 通信はポイントツーポイン イトにより他のプロセスのタスクが完了するのをまつ。タ トの非同期通信によって実装を行った。通信は計算データ スクの完了通知を受け取ると、タスクが終了した時と同様 の送信とタスク終了通知の２回に分けて行われる（図 3）。 に、必要なデータの揃ったタイルのタスクを RUNNABLE 通信は以下のように実行される。 にしてキューの末尾にプッシュする。そして再びキューか らタスクを取り出して、GPU 上で実行していく。 送信者ノードは 1) タスクが終了すると、そのタスクを 実行していたノードはそのタスクの計算結果が必要なノー ドへ計算結果を MPI Isend により送信する。 2) 続いて同 3.1 タイル分割手法 本プログラムでは、入力データ A を一辺 nb のタイルと じノードへタスクが終了したことを知らせるデータを送信 する。 いう単位で分割・保持し、タイル内での局所性が良くなる 一方、受信者ノードは常に持続的受信を起動し続けてお ようにデータを複製し並び替えている。特にコレスキー分 き、タスク終了通知が送られるのを待つ。タスク終了通知 解では A は対称行列となるため、下三角行列部分のみを保 を受信すると依存関係のあるタスクの発火処理を行い。実 持している (図 2)。タスクはこのタイル単位で実行される 行可能になったものをキューの末尾にプッシュする。計算 ため、タイルは入力データの他にタスクに関する情報を保 データはそのデータが必要になるタスクが初めて呼び出さ 持するようになっている。並列実行時、データはブロック れたときに、MPI Recv により受信されバッファに格納さ サイクリック分割により各プロセスに割り当てられる。各 れる。以降、そのデータが必要となる場合、バッファ内の プロセスは割り当てられたタイルのタスクのみを実行する データを使うことにより、冗長な通信が行われないように ようになっている。 している。 現在の実装には下記のような制限がある。バッファ内の データは不必要になった時に領域を解放するべきであるが、 ⓒ 2014 Information Processing Society of Japan 3 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report 略である。この戦略では i 行 j 列目のタイル T (i, j) の タスクが終わったとき、以下の手順により次に行われ るタスクが選ばれる。 ( 1 ) 列方向 (列 = j) のタイル T (·, j) のタスクがキュー 内に存在していれば、それを取り出す。存在しな ければ 2 へ。 ( 2 ) キュー内に行方向 (行 = i) のタイル T (i, ·) のタス 図 4 CPU メモリと GPU メモリの紐付状況 クが存在していれば、それを取り出し、存在しな ければ 3 へ。 現実装では解放できず、計算が進むとバッファが貯まって ( 3 ) キューの先頭のタスクを取り出す。 いく仕様となってしまっている。このバッファの扱いは今 このとき各ステップで該当するタイルが複数存在して 後の課題である。また、通信の実装上、プロセス数・行列 いる場合、先頭のタイルを取り出す。 サイズが増えていくと多くの通信がハングアップの状態で 放置されることになり、その処理を MPI の仕様に丸投げ 3.5 GPU メモリの掃出し戦略 している。これはスケーラビリティの観点から非常に重大 本プログラムでは、GPU メモリに紐付されているタイ な問題となる。ハングアップ状態の MPI 通信の取り扱い ルはリストにより管理されている。GPU メモリのデータ についても同様に今後の課題である。 を入れ替える時、このリストを使って GPU から掃き出さ れるタイルを選択している。今回、掃き出されるタイルの 3.3 CPU-GPU 間通信 CPU-GPU 間のデータ転送は、GPU メモリ上にできる 限り行列データを置いておけるようにするために、新た 選び方について次の２つを用意した。 • FIFO 戦略 • LRU 戦略 に行列データを送るときは既に GPU メモリ上にある行列 FIFO 戦略はリスト内にある最も古いタイルのデータを掃 データと入れ替えるようにして行う。その際、どのタイル き出す戦略であり、実装の簡単さから今回採用した。LRU の行列データが GPU メモリ上にあるのかを知るために、 戦略はリスト内で最も長い間アクセスされなかったタイル タイルは GPU メモリとの紐付状況を表す変数を持ってい のデータを掃き出す戦略で、GPU メモリの時間的局所性 る。紐付状況には次の 3 つの状態がある (図 4)。 から効率が良くなると考えられる。 • DIRTY：紐付された GPU メモリがあるが、CPU メ モリと値が異なる。 • CLEAN：紐付された GPU メモリがあり、CPU メモ リと値が同じ。 • NOGPU：紐付された GPU メモリをもたない。 4. 実験と評価 今回、実装したアルゴリズムの性能を測定するために SDPARA GPU 版に対して、データドリブン型アルゴリズ ムの導入によってどのように性能が変化したか実験を行っ DIRTY な GPU メモリが掃き出されるときは、まず対応 た。以降、データドリブン型のアルゴリズムを導入したも する CPU メモリを更新したあとに、新たに行列データを のを NEW、導入していないものを OLD と呼ぶ。なお今 送るタイルと紐を付け直して、GPU メモリへデータを転 回用いた OLD の実装は TSUBAME2.5 の 4080GPU を用 送する。一方、CLEAN な GPU メモリが掃き出されると いて 1.7PFlops を記録したものである [6]。 きは、CPU メモリを更新する必要がないので GPU から CPU への通信は省いている。 4.1 実験環境 今回の実験には東京工業大学学術国際情報センターが 3.4 タスク選択戦略 運用するコンピュータ、TSUBAME2.5 を用いた。TSUB- 前述のとおり、実行可能なタスクはキューにしまうこと AME2.5 は GPU 主体に設計されており、理論ピーク性能 で管理している。今回、次のタスクを選ぶ戦略として FIFO は 5.7PFlops に達している。TSUBAME2.5 には性能の異 戦略と ByIJ 戦略の２つを用意した。 なる Thin、Medium、Fat の 3 種類の計算ノードがあるが、 FIFO 戦略 今回は Thin ノードを利用して実験を行った。Thin ノード FIFO 戦略はキュー内にある最も古いタスクを取り出 のハードウェア構成は表 1 のとおりである。今回、1 ノー す戦略である。 ドあたり、1CPU-1GPU を利用し、GPU メモリは余裕を ByIJ 戦略 持たせて 1GPU あたり 5000MiB を埋めるようにした。 ByIJ 戦略はコレスキー分解が列方向・行方向のタス クに関してデータの再利用性が高いことに注目した戦 ⓒ 2014 Information Processing Society of Japan 4 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report 図 5 OLD を 1 としたときの PCIe の相対通信量 (1 ノード) 表 1 TSUBAME2.5 Thin ノードのマシン構成 CPU Intel Xeon 2.93 GHz (6 cores) x 2 CPU Memory 54GiB (一部 96GiB) GPU NVIDIA Tesla K20X × 3 GPU Memory 6GiB 4.2 PCIe 通信量 データドリブン型のアルゴリズムを導入することで CPU- GPU 間の通信がどのように変化したか実験を行った。実 験はノード数を 1 ノードと 4 ノードについて行い、1 ノー ドでは行列サイズを 36864、49152、57344 と変化させ、4 ノードでは行列サイズを 57344、73728、90112 と変化さ せて、OLD およびタスク選択戦略と GPU メモリの掃出 し戦略の各組合せ 4 パタンに対して行った。1 ノードでは 36864 は GPU メモリの容量と同程度でわずかに GPU メ モリの容量を超えるケースとなっていて、49152、57344 は GPU メモリの容量を超えるケースとなっている。同様に 4 ノードでは 57344 は GPU メモリの容量と同程度のケース であり、73728、90112 は GPU メモリの容量を超えるケー スとなっている。結果は図 5、図 6 のとおりである。 いずれの行列サイズに対してもすべての戦略の組み合わ せで大きく通信量を減っていることが確認できる。最も 削減できたのは、1 ノードのときでは行列サイズ 49152、 ByIJ-LRU のときで OLD のおよそ 8.6%まで、4 ノードの ときでは行列サイズ 57344、ByIJ-LRU のときで OLD のお よそ 9.6%まで削減することができた。また 4 ノードのと き、GPU の容量を超えるケースでも行列サイズ 73728 の ときに、ByIJ-LRU で OLD の 30%程度となり、行列サイ ズ 90112 のときでは、FIFO-LRU のときで OLD の 38%、 図 6 OLD を 1 としたときの PCIe の相対通信量 (4 ノード) る場合に対しても、うまく不要になった行列データを判別 して掃き出す対象として選択し、GPU メモリから掃き出 した後にもう一度 GPU メモリ上に送るといった冗長な通 信が減らせたため、通信量を減らせたと考えられる。加え てコレスキー分解では計算が発展していくと徐々に計算範 囲が右下へと縮小していくため、ある一定のサイズまで計 算範囲が狭まったとき、新たにデータを入れ替える必要が なくなる。この点も PCIe 通信量が減った要因の 1 つと考 えられる。 戦略ごとの違いをみると、1 ノードのときでは GPU の 容量を大きく超えるとき、掃出し戦略に比べてタスク選択 戦略の方が効果的に作用した。これはタスクを選択する際 にコレスキー分解の性質をうまく利用できたためと考えら れる。それに対して掃出し戦略ではあまり性能に違いは見 られなかった。これはコレスキー分解の性質により 1 ノー ドのとき、FIFO と LRU ではほぼ同じようなタイルの行列 データが掃き出す対象に選ばれたためと考えられる。 一方で 4 ノードのときではより強く効果に差が出たのは 掃出し戦略の方で、FIFO に比べて LRU の方がより良く 削減することができたが、その差は小さく原因は調査中で ある。またタスク選択戦略では ByIJ の方が FIFO より通 信量が少ない傾向があるものの、通信量にあまり差が表れ なかった。これはキュー内に選べるタスクの数が十分な量 なかったためにタスク選択戦略の効果があまり現れなかっ たからだと考えられる。例外的に 4 ノード、行列サイズ 73728 のとき FIFO-FIFO 戦略で大きく通信量を削減する ことができたが、詳しい理由は分からず、詳細は調査中で ある。 最も削減できなかった FIFO-FIFO でも 43%と良好な結果 となった。 PCIe 通信量が大きく減った要因として、OLD では各 ルーチンごとに PCIe 通信を行っているため、既に GPU メモリ上にある行列データも冗長に送られているのに対 し、NEW では GPU メモリ上にある行列データに対して は PCIe 通信を行わずに、GPU メモリにある行列データを 使い回せたためだと考えられる。また GPU メモリを超え ⓒ 2014 Information Processing Society of Japan 4.3 strong scaling 行列サイズを 49152 に固定し、ノード数を 1、4、9、16 と変化させて OLD と各戦略の組み合わせに対して性能を 調査した（図 7） 。図 7 をみると緩やかにスケールしている ことが確認できた。徐々に計算速度の向上が緩やかになっ ていった原因として、データの受信する際、現在ブロッキ ング通信を使って受信しているため、プロセス数が増加す 5 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report 図 7 strong scaling 図 9 行列サイズによるスケーリング アップ状態の MPI 通信やバッファーの未解放によるもの と考えられるが、原因は調査中である。 4.5 行列サイズによるスケーリング ノード数を 16 に固定して行列サイズを 36864 から 147456 と変化させて性能の変化を調査した。結果は図 9 のとお りである。図 9 をみると行列サイズが大きいとき、わず かながら戦略ごとに性能に差が現れた。より強くでたのは GPU メモリの掃出し戦略で、これは PCIe 通信量のとき 図 8 weak scaling に通信量が少なかった戦略の組み合わせほど計算速度が速 くなった。これはうまく GPU メモリの局所性を利用でき ることにより通信のオーバーヘッドの割合が大きくなって たことを表している。タスク選択戦略では行列サイズが小 いることが考えられる。また OLD と比較すると、ノード さいとき、FIFO 戦略の方が ByIJ 戦略よりかも性能が良 数が小さいときは OLD の方がいずれの戦略の組み合わせ くなった。これはキュー内のタスクの量が少なくタスクの よりかも良い性能をだしていた。しかしノード数が増えて 選び方を工夫しても差が出なかったため、選択手順が単純 いくとその差は縮まり、プロセス数 16 では NEW の各戦 だった FIFO の方に軍配が上がったと考えられる。一方、 略は OLD と同程度か、あるいは 2%程とわずかながら良い 行列サイズが大きくなっていくと ByIJ が有利になってく 性能を示した。 る。これはキュー内のタスクが十分量あるために、局所性 を考慮してタスクを選択したことで、性能が良くなったと 4.4 weak scaling 次に行列サイズの自乗に比例してノードの数を増やして、 考えられる。加えて ByIJ と LRU を組み合わせたとき、ど ちらも GPU メモリの時間的局所性を上げるように動作す １ノードにおけるタスクの量が一定となるようにして実験 るため、相乗効果で性能をより引き出せたと考えられる。 を行った。図 7 がその結果である。1 ノードのときの行列 このとき、FIFO-LRU の戦略のとき、行列サイズ 110592 サイズは 36864、16 ノードのときの行列サイズは 147456 で 7263GFlops を達成した。また、OLD と比較すると行 となっている。いずれの戦略でも良好なスケーラビリティ 列サイズが大きいときに NEW と比べて OLD の方が性能 を観測した。しかし、OLD と比べると性能の伸びは低く、 が良くなり、行列サイズ 110592 では OLD に対し最大で 16 ノード 147456 のときでは FIFO-LRU で OLD の性能 93%程度、147456 では最も性能の良かった ByIJ-LRU でも の 65%、最も性能の出ていた ByIJ-LRU でも 75%程度に 84%に留まった。これも weak scaling のときと同様、通信 留まった。これは OLD には PCIe 通信や MPI 通信に対し と計算のオーバーラップの有無が原因の 1 つと考えられる。 て計算と通信のオーバーラップを施されているのに対し、 NEW では PCI 通信に関してはオーバーラップが施されて 5. 関連研究 おらず、MPI 通信のうちデータを受信する際はブロッキ Bosilca ら [9] は DAG(Direct Acyclic Graph) を利用し ング通信を利用しているために通信の影響を大きく受けた た動的スケジュラー DAGuE を提案しており、ターゲット ためと考えられる。また、更にノード数を増やして実験を アプリケーションの 1 つにコレスキー分解を挙げている。 試みたところ、ノード数 25、行列サイズ 184320 のときに 彼らの、行列をタイル分割しデータドリブン型実行を行う 急激な速度低下を確認した。これは第 3 章で述べたハング 方式を、本論文では参考にしている。DAGuE では GPU ⓒ 2014 Information Processing Society of Japan 6 Vol.2014-HPC-145 No.46 2014/7/30 情報処理学会研究報告 IPSJ SIG Technical Report の対応がなされており、先行タスクの結果が GPU メモリ に残っていれば後続タスクがそれを再利用可能であるとさ れている。しかし、本研究で注目したような、GPU メモ リ容量を超えたときに対応可能であるか、その場合掃き出 [5] し戦略がどうなっているかは明記されていない。それらの 点における比較実験も今後の課題に含まれる。 [6] StarPU[10] は、移植性の高いデータ管理とスケジューリ ングフレームワークを統合したフレームワークで、局所性 を重視したスケージュリングでキャッシュの再利用を行っ ている。その大きな特徴は、タスクグラフ全体の実行性能 向上を目標として、タスクを CPU と GPU のいずれかふ [7] さわしい方で実行可能なことである。一方、StarPU 自身 は基本的には 1 ノードを想定しており、マルチノードを対 象としている本研究とは異なる。 [8] 6. まとめと今後の課題 本研究はマルチノード・マルチ GPU 上のコレスキー分解 を解くアルゴリズムに対して、データドリブン型アルゴリ [9] ズムを適用し、適切にタスクを選択し、GPU メモリの再利 用性を考慮しながらデータを入れ替えることで CPU-GPU 間の通信量を 1 ノードでは最大で適用する前の 8.6%。4 ノードでは GPU の容量を超えない場合で 9.6%、GPU の 容量を超える場合でも最大で適用する前の 30%まで削減 した。また計算速度では 16 ノード、行列サイズ 110592 で [10] ming Problems, Proceedings of IEEE/ACM International Conference for High Performance Computing, Networking, Storage and Analysis (SC12), pp. 1–11 (2012). Yamashita, M., Fujisawa, K. and Kojima., M.: SDPARA : SemiDefinite Programming Algorithm PARAllel Version, Parallel Computing, Vol. 29, pp. 1053–1067 (2003). Fujisawa, K., Endo, T., Yasui, Y., Sato, H., Matsuzawa, N., Matsuoka, S. and Waki, H.: Peta-scale General Solver for Semidefinite Programming Problems with over Two Million Constraints, In Proceedings of the International Conference on Parallel and Distributed Processing Symposium 2014 (IPDPS2014), p. 10pages (2014). Endo, T., Nukada, A., Matsuoka, S. and Maruyama, N.: Linpack Evaluation on a Supercomputer with Heterogeneous Accelerators, Proceedings of IEEE/ACM International Parallel and Distributed Processing Symposium (IPDPS 2010), pp. 1–8 (2010). Choi, J., Dongarra, J., Ostrouchov, S., Petitet, A., Walker, D. and Whaley, R. C.: The Design and Implementation of the ScaLAPACK LU, QR, and Cholesky Factorization Routines, Technial Report UT CS-94-246, LAPACK Working Note 80 (September 1994). Bosilca, G., Bouteiller, A., Danalis, A., Herault, T., Lemarinier, P. and Dongarra, J.: DAGuE: A generic distributed DAG engine for high performance computing, Parallel Computing, Vol. 38, No. 1-2, pp. 27–51, (2012). Augonnet, C., Thibault, S., Namyst, R. and Wacrenier, P.-A.: StarPU: a unified platform for task scheduling on heterogeneous multicore architectures, Concurrency and Computation: Practice and Experience, pp. 187– 198 (Februaly 23, 2011). 7263GFlops を達成した。 今後の課題としては第 3 章で触れたようにハングアップ した状態で放置されている MPI 通信をできる限り解消す ること、不必要になったバッファを適切に解放することで ある。また、より大規模の行列サイズ、プロセスサイズに 対応することも今後の課題である。今回の実験ではデータ ドリブン型のアルゴリズムによる性能の変化のみを評価し たが、関連研究にあげたソフトウェアとの比較実験、およ び理論性能とのギャップについても評価を行いたい。 謝辞 本研究は JST-CREST の研究課題「ポストペタスケール 時代のメモリ階層の深化に対応するソフトウェア技術」の 支援によります。最後に本研究に取り組むにあたって様々 なアドバイスをいただいた東京工業大学学術国際情報セン ターの野村哲弘さんに感謝いたします。 参考文献 [1] [2] [3] [4] : Top500, http://www.top500.org/. : Titan, http://www.olcf.ornl.gov/titan/. : TSUBAME2.5, http://tsubame.gsic.titech.ac. jp/. Fujisawa, K., Endo, T., Sato, H., Yamashita, M., Matsuoka, S. and Nakata, M.: High-Performancd General Solver for Extremely Largescale Semidefinite Program- ⓒ 2014 Information Processing Society of Japan 7