（様式 20）成果報告書

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

利用課題名 ポストペタ時代の大規模並列数値計算のための技術開発
英文：Research and Development on Large Scale Parallel Numerical Computations in the Post-Peta Era
須田 礼仁
Reiji Suda
東京大学 情報理工学系研究科
Graduate School of Information Science and Technology, the University of Tokyo
http://sudalab.is.s.u-tokyo.ac.jp/~reiji/
邦文抄録（300 字程度）
本研究では，ポストペタスケールの計算機での大規模数値計算を目標として，手法の開発を行っている．いく
つかのテーマに取り組んでいるうちから，本稿では，複数 GPU が搭載されているときに，CPU と GPU の間でのデータ転送の所要時間を最小にする転送方式を決定するアルゴリズムについて報告する．この問題は線形計画問題として定式化できるが，双対問題を考えることで，幾何学的な解釈をすることができる．これにより，データ転送時間を最小にする転送方式は，たかだか 2 つのシステム状態（データ転送の組み合わせ）により実現されることが示された．
英文抄録（100 words 程度）
We are developing several methods toward large scale numerical computations on post-peta scale
supercomputers. Among several works we achieved, this report considers a problem of finding datatransfer schedule between CPU and multiple GPUs, and gives an algorithm that gives a schedulewith minimal data transfer time for given data sizes. This problem can be solved via linear
programming, but we present a geometric interpretation of the problem, which leads us a theorem
that at most 2 system states (i.e. combination of types of data transfer) realizes minimal timeschedule.

Keywords: ５つ程度Scheduling, multi-GPU system, GPU-CPU data transfer, optimal schedule, linear programming.

背景と目的れているシステムに対して，CPU と GPU の間のデータポストペタ時代の大規模並列計算機として，GPU の転送の最適な手法を開発した．(3) また，(2) の成果にようなアクセラレータを搭載した並列計算機は有力なア基づいて，divisible load model により，複数 GPU をーキテクチャである．しかしながら，電力消費における用いた漸近最適なタスク分割・スケジューリング手法を課題，超大規模並列化プログラミングのための手法の提案した．(4) 将来の超大規模並列計算機に向けて，必要性，強スケーリングのための新たなアルゴリズム

Krylov 部分空間法の集団通信の回数の削減が求めら開発，プログラマビリティの課題など，多くの課題が浮れており，block Krylov と Chebyshev 基底を併用しかび上がってきている．これらの課題の解決をめざし，

た Block Chebshev Basis CG (BCBCG) を提案した．

我々はソフトウェアとアルゴリズムの視点で取り組みを(5) 数値的に限りなく安定な Krylov 部分空間を生成す進めている．特に大規模並列数値計算を主なターゲッることをめざし，Arnoldi 過程を通信削減で実現するア

トとして，並列化手法やアルゴリズム開発を行っていルゴリズムを開発した．(6) GPU を用いて多倍長精度る．の行列計算基本アルゴリズムを実装し，高速化を達成した．(7) 将来の超大規模並列計算機における細粒度

概要

並列化に向けて，OS ジッタの影響を緩和する集団通

平成 25 年度には，以下の成果を挙げた．(1) 超大信アルゴリズムの開発・実装を行った．(8) 今後一層問

規模離散最適化問題の超並列 GPU 実装を実現した．

題となる，電力最適化に向けて，オンライン自動チュー(2) TSUBAME のように 1 ノードに複数 GPU が搭載さニングのアルゴリズムを開発・実装した．

（様式 20）成果報告書
これらすべてについて詳細を報告することは困難なのスループット S1N/S に等しく，G0 と G1 に同時に送信ので，本稿では，上記の内，(2) の複数 GPU に対するするときには両方に同じスループットで転送される（すデータ転送の最適アルゴリズムについて詳述する．

なわち S0S/S = S1S/S）などとする．
さらに，簡単のため，2 つの GPU へのデータ転送要

CPU と GPU とのデータ通信は，GPU プログラミン求は等しいとして，合計の送信データサイズを XS, 合グにおける重要なテーマの一つである．近年では，1 つ計の受信データサイズを XR とする．従って，各 GPU にのマザーボードに複数の GPU を搭載することができる

は，それぞれの半分，つまり XS/2，XR/2 のデータが送ようになっており，TSUBAME 2.0/2.5 もそのような構信・受信されることになる．

成になっている．また，複数ストリームを利用することにさて，各システム状態 q で時間 Tq だけデータを転送

より，CPU から GPU へのデータ転送（以下，CPU 側することを考える．このとき，G0 に送信されるデータサから見て，「送信」と呼ぶ）と，GPU から CPU へのデー

イズは XS0 = ∑q Tq S0q，G1 から受信するデータサイタ転送（以下，「受信」と呼ぶ）も同時に実行できる．

ズは XR1 = ∑q Tq R1q などとなる．またデータ転送の例えば，送受信を同時に行うと，送信だけや受信だ所要時間は T = ∑q Tq である．このモデルではバンけとは異なるスループットが得られる．また，複数 GPUド幅のみ考慮しており，転送のスタートアップ時間などに同時にデータ転送をすると，その影響も受ける．これは考慮していない．このモデルによれば，転送スループらの要因のため，CPU と GPU の間のデータ転送の最ットはスケジューリングの順序によらず，各システム状適な方法は必ずしも自明ではない．本稿ではこの問題

態での時間のみ決定すればよい．所要時間最小でデに対する解を提示する．

ータを送る問題はMinimize T

さて，各 GPU について見ると，subject to XS0 = XS1 = XS/2, XR0 = XR1 = XR/2



N: データ転送をしていないという線形計画問題になる．これを「所要時間最小化問



S: CPU→GPU のデータ転送（送信）題」と呼ぶことにする．

R: GPU→CPU のデータ転送（受信）

SR: 送受信の双方向同時転送

上記の線形計画問題は，通常の方法で容易に解くことという 4 つの状態がある．従って，n 台の GPU があれができるが，以下では幾何的な解釈によりその特徴をば，システム全体として 4n 通りの状態がある．CPU と説明する．

GPU の間で，あるデータ量を転送しようとしたときに，まず，本稿でおいている仮定として，両 GPU に同じ

この 4n 通りの状態のどれをどのように組み合わせれば，だけデータ転送するため，対称なデータ転送は同じ時最大のスループットが得られるかが，課題である．

間かけると制限しても最適解が得られることが証明でき

以下では，簡単のため 2 台の GPU の場合についてる．すなわち TS/N = TN/S, TR/N = TN/R, TSR/R = TR/SR な説明する．GPU のうち 1 台を G0，もう 1 台を G1 と呼どの 6 つの等式が成り立つ．最適解では自明に TN/N =ぶ．システム全体としてのデータ転送状態は 16 通りあ0 なので，あわせて 7 つの等式が得られ，もともと 16るが，G0 の状態と G1 の状態を / で区切って並べて示あった自由度のうち，9 つだけが残る．

す．例えば S/N は G0 に送信のみしている状態，さて，システム状態 S/N と N/S は同じ時間かけるのSR/SR は両方の GPU ともに送受信同時に行っているで，これらをペアにして，一つのシステム状態 S/N とし状態である．システム状態が q のとき，Gi への送信のて改めて定義する．転送時間 TS/N およびスループット

スループットを Siq, 受信のスループットを Riq と書く．

SS/N も，2 つのシステム状態のペアに対して定義する．

また，本稿では，2 つの GPU は同じ仕様で，同じ接このようにすることで，「すべてのシステム状態において続になっているものとする．例えば，G0 だけに送信す2 つの GPU に等しいデータ量が転送される」という簡るときのスループット S0S/N は，G1 だけに送信するとき単化がなされる．すなわち，各システム状態 q は，2 つ（様式 20）成果報告書の GPU に対する合計送信スループット Sq と合計受信含むどのような通信スケジュールよりもデータ転送量がスループット Rq の 2 つのパラメタで完全に特徴づけら多い．すなわち，(a) では状態 q2 は使う意味がない．

れる．これを 2 次元平面上の点 Pq = (Sq, Rq) に対応

一方，図 2 (b) のようになっていれば，q1 と q3 の凸結付けよう．この対応付けにより，9 つのシステム状態が合よりも，q1 と q2 の凸結合，あるいは q2 と q3 の凸結平面上の 9 つの点に対応する．

合のほうが右上にあり，データ転送量が多い．すなわち，q1 と q3 の凸結合，あるいは 3 つの状態すべてを使っ次に，所要時間最小化問題の双対問題を考える．これは，データ転送の合計時間 T を固定したときに，デた凸結合よりも，q1 と q2，あるいは q2 と q3 の 2 状態の凸結合がよい．

ータ転送量 (XS, XR) が最大となるデータ転送方法を決める問題である．ただし，「データ転送量が最大である」とは，所要時間が T となる他のどのようなスケジュールでも，「データ送信量が XS 以下」または「データ受信量が XR 以下」のどちらか（または両方）が成立することをいう．すなわち，2 つの目的関数 XS，XR に対するパレート最適解が「データ転送量が最大」である．これを「データ転送量最大化問題」と呼ぶことにする．一般

図 2. 3 つの状態の凸結合．

性を失うことなく T = 1 としてよい．
さて，最初に，2 つのシステム状態 q1 と q2 のみを使これを一般化すると，図 3 のようになる．すべての状う場合を考察しよう．合計所要時間が 1 であるから，状態を使って時間 1 の間に転送できるデータ量は，各状態 q1 に時間 a，状態 q2 に時間 1 — a を費やすとしよ

態に対応する点から構成される凸包の内部または境界う（0≦a≦1）．このとき転送データ量は上の点に対応している．従って，転送データサイズが最XS = a Sq1 + (1 — a) Sq2,大になる転送方法は，右上凸包の頂点または辺上のXR = a Rq1 + (1 — a) Rq2

点に対応している．となる．この点 (XS, XR) は，図 1 に示すように，点 Pq1と点 Pq2 を結ぶ線分上にある．0≦a≦1 を適当に選ぶことで，線分上の任意の点を取ることができる．これを「状態 q1 と状態 q2 の凸結合」と呼ぶことにする．

図 1. 状態 q1 と状態 q2 の凸結合．

図 3. データ転送量最大化問題の解．
赤い線と凸包の交点から，所要時間最小のスケジュー

次に，3 つのシステム状態 q1, q2, q3 を使う場合を考ルに用いるシステム状態 q1, q2 がわかる．

える．このとき，先と同様に考えると，点 Pq1, Pq2, Pq3が作る三角形の内部を取ることができることがわかる．

所要時間最小化問題の解は，データ転送量最大化

図 2 (a) のようになっていれば，q1 と q3 の凸結合が右問題の解でもなければならない．従って，図 3 の右上凸上の辺，すなわちパレート最適解に対応しており，q2 を包の頂点または辺上の点である．図 3 には，データ転（様式 20）成果報告書
送量 (XS, XR) が与えられたときに，所要時間を最小るが，本稿では複数 GPU に対するデータ転送の最適にする 2 つの状態 q1, q2 の求め方が示されている．すなアルゴリズムについて詳しく報告した．ここでは対称なわち，(XS, XR) と原点を通る直線と，右上凸包とのな GPU に対する対称なデータ転送しか論じていないが，交点を求め，その辺の両側の頂点に対応する状態を非対称な GPU システムや非対称なデータ転送につい用いればよい．交点の位置から，状態 q1 および q2 でて も 考 え て い く 必 要 が あ る ． ま た ， divisible load

通信に要する時間が計算できる．

model はタスクが一様であると仮定しているが，非一様なタスクも現実にはあるので，そのようなモデルに対以上が所要時間最小化問題に対する幾何的な解法である．
GPU の台数が増えても同様で，システム状態の数が増えることに伴って点の数は増えるが，やはり 2 次元平面上の凸包の問題に帰着される．ここから重要な結論が 1 つ導かれる．
定理：対称 GPU システムに対する所要時間最小のデータ転送スケジュールは，1 つまたは 2 つのシステム状態からなる．

ただし，1 つのシステム状態は対称性により再定義される前の複数のシステム状態を含んでいる可能性がある．
しかし，もともと 4n 個あったシステム状態のうち，ほんのわずかだけを用いるのが最適であることが示されたことになる．

結果および考察
本研究により，複数 GPU に対して最小時間でデータ転送するスケジューリングが明らかになった．また，その幾何学的な解釈と，そこから導かれる性質について説明した．
我々はこの成果をもとにして，divisible load modelに基づくタスク分割とパイプライン型のスケジューリングアルゴリズムを提案している．そこでは，（本稿では無視した）通信やカーネル起動のオーバーヘッドを考慮に入れても，タスクサイズが無限に大きい極限において，理論的な最適解に限りなく近づくという，漸近最適性を証明することができている．これらの成果は論文にまとめて近く投稿する予定である．

まとめ、今後の課題本プロジェクトではいくつかのテーマに取り組んでいする解も求めてゆきたい．