いわゆるグラフィックボードに使用されているグラフィック処理用プロセッサ (GPU: Graphics Processing Unit)は、 PCで高度なグラフィック性能が要求されるのに合わせて、高性能化してきた。 GPUは単純なプロセッサ・コア(CUDAコア)を多数並べる構成をとっており、 個々のコアの性能はそれほど高くないものの、 GPU全体の計算能力はPC本体側のCPUを上回っている。
最近はこの高性能をグラフィック処理以外に利用する試み (GPGPU: General-purpose computing on GPU) が活発になっており、 CUDAやOpenCLといった処理系を用いることで、 C言語を拡張した記法でGPUを利用するプログラムを作成できる。
しかし、GPUプログラミングには、 以下のような難しい問題があり、 実際に性能の高いプログラムを作成するのは難易度が高く、手間がかかる。
そこで、より簡単にプログラムを作成でき、 処理系が自動最適化することで高性能を達成できるような GPUプログラミング環境を目指すフレームワーク MESI-CUDAの研究・開発を行っている。
MESI-CUDAでは、 CPU(ホスト)・GPU(デバイス)が単一の大域メモリを共有するという、 共有メモリに基づくプログラミングモデルを採用している。 MESI-CUDA処理系は、ユーザが宣言した共有変数に対するアクセスを静的解析し、 必要に応じてホストメモリ・デバイスメモリ間のデータ転送を行うコードを自動生成することで、 仮想的な共有メモリを実現する。 データ転送と複雑なメモリ構成をユーザに隠蔽し、 コンパイラに任せることで、 より簡単に移植性の高いプログラムを書けるようにする一方で、 転送タイミングやメモリの利用方法を最適化できるようにすることを図っている。
なお、CUDAの最新版であるCUDA6では、 MESI-CUDAと同様なプログラミングモデルを可能にするUnified Memoryが実現されており、 プログラミングの難易度という問題はあるていど解消されている。 しかし、 CUDA6のUnified Memoryはハードウェアとランタイムレベルで実現するものであり、 手動で最適化されたCUDAコードほどの性能は期待できない。 たとえば手動最適化では、 後で必要になるデータを早めに非同期転送しておくことでデータ転送待ちを減らす、 といった工夫が行われるが、 Unified Memoryではこのようなプログラム依存の最適化を自動化できない。 これに対しMESI-CUDAでは、 プログラムの静的解析と静的に最適化されたコード生成を自動で行うことで、 同様の使い勝手ながらより高い性能を達成することを目指している。
MESI-CUDAの基本的なアイディアはコンパイラレベルでの仮想共有メモリだが、 ホスト・デバイス間で完全にメモリ空間を共有するのはオーバヘッドが大きい一方、 アプリ記述レベルでは実用上、オーバスペックである。 また、共有メモリモデルは明示的な通信が不要である一方、 同期や排他制御という低レベルな記述が必要という欠点がある。
そこで、記述性と性能の面から妥当なモデルとAPIを設計した。 具体的には、明示的に指定した変数のみがホスト・デバイス間で共有されるものとし、 こうした変数へのアクセスに対して 必要な転送・同期コードが自動生成されるようにした。 また、もともとGPUの性能を発揮するためには特定の並列処理スタイルが要求される (粒度の揃った、データ競合しないタスクの集合が望ましい)ことから、 実用上問題のない範囲でプログラミングスタイルを限定し、 明示的な同期や排他制御なしにプログラムを書けるようにした。
CUDAではストリームと呼ばれる機能と非同期データ転送を用いることで、 ホスト・デバイス間のデータ転送とスレッド実行をオーバラップさせることができ、 これを利用すると手動最適化により転送時間を隠蔽できる。 そこで、このような最適化を自動で行う手法を開発した。
リストや木構造など、ポインタを利用したデータ構造を、 MESI-CUDAの仮想共有メモリ上で扱えるようにした。
MESI-CUDAの仮想共有メモリは、同じ変数の領域をホスト・デバイスの両方で確保し、 必要に応じて内容のコピーを行うことで実現する。 しかし、C言語のポインタの値はアドレス値であり、 CPU側で書き込んだポインタ値をGPU側で読み出しても利用できない。 そこで、コンパイル時に構造体型などに含まれるポインタメンバを抽出し、 それらの値をCPU・GPU間で変換するコードを生成しておく。 実行時には、コピーが発生したときにこの変換コードを実行することで、 コピー後の領域に含まれるポインタ値はコピー先で有効なアドレスとなる。
GPUは全コアが共有する低速・大容量のデバイスメモリの他、 高速・小容量のシェアードメモリを持つ。 CUDAプログラムはホスト・デバイスメモリのみで記述できるが、 適切なデータをシェアードメモリ上に置くようにユーザがコードを記述することで 大幅に速度向上が得られる。
従来のMESI-CUDAが自動的に使用するのはホスト・デバイスメモリだけである。 CUDAと同様の手動最適化でシェアードメモリを利用することも可能だが、 最終的な目標は複雑なメモリ構造の隠蔽であり、 シェアードメモリも自動的に利用されることが望ましい。 そこで、プログラム中で使用される配列のアクセス範囲やアクセス回数を静的解析し、 もっとも効果の高いものをシェアードメモリ上に配置するような自動最適化手法を開発している。
CUDAではGPU上で実行する処理を「カーネル関数」として記述し、 この関数を実行するスレッドを大量に並列起動する。 現在のCUDAでは、スレッドの集まりである「ブロック」という概念を導入し、 「ブロック数」と「ブロックの大きさ(1ブロック当たりのスレッド数)」 を指定してスレッド起動を行う。 各ブロックおよび同一ブロック内のスレッドは、 それぞれ物理SMおよび同一SM上のCUDAコアに自動的に割り当てられる。
この方式では物理資源へのマッピングは自動化されているが、 本来の並列アルゴリズムとは無関係な「ブロックの大きさ」を、 ユーザプログラム内で指定する必要がある。 この値はSM・コアの利用効率や1スレッド当たりで利用可能なシェアードメモリの量などに影響するため、 デバイスの物理パラメータを考慮して決定しなければ実行性能が低下する。 さらに、 個々のスレッドがどの配列要素にアクセスするかといったデータマッピングはブロックとスレッドのインデックスを表すビルトイン変数を用いて行われる。 このため配列アクセス時の添え字式はブロック・スレッドインデックスを使った複雑なものになりやすい。 さらに、GPUのデバイスメモリはアクセスパターンによりアクセス効率が大きく変わるため、 性能向上のためには適切なアクセスパターンになるよう、 添え字式を工夫したり配列を転置したりする必要がある。
そこで、ブロックの概念を用いず、 単一のスレッド配列の形で並列スレッド数を指定するAPIを追加した。 この配列の次元数や各次元方向の大きさは任意であり、 デバイスの特性を考慮せずユーザプログラム上の都合だけで決定できるため、 素直な添え字式を書くことができる。 また、このように「論理的にデータマッピングされた」スレッド群は MESI-CUDA処理系により従来のCUDAコードへと変換する。 その際に資源の利用やメモリアクセスの効率が高くなるような自動最適化を行う手法を開発している。
1台のPCには1〜3枚程度のGPUデバイスを搭載できるが、 現在のCUDAではAPI関数により対象デバイスを切り換えてから、 そのデバイス上での処理を指示する方法をとっている。 このため、複数デバイスを並列利用して大きな計算を行わせるには、 デバイスを適時切り換えながら、スレッド起動やデータ転送を行っていく必要がある。 この際に、一部のデバイスが仕事をしていない状態を作らないためには、 個々のデバイスの性能や各スレッドの実行時間を考慮し、 割り当てるスレッド数を調整する必要がある。 さらに、配列などのデータ領域についても、 各デバイス上のスレッドがアクセスする部分だけを転送する必要がある。
こうした記述をユーザプログラム内で行うのは非常に煩雑で難易度が高い。 このため、上記のMESI-CUDAモデルを拡張した 「CPUコアと全デバイスのCUDAコアが単一の大域メモリを共有する」 によりユーザプログラムを記述し、 各デバイスへのスレッドマッピングや必要なデータ転送コードの生成は MESI-CUDA処理系が行う方式を研究している。
複数の計算機で構成された実行環境上で多数のタスクを実行する際には、 どのタスクをどの計算機でどの順序で実行するか、 というスケジューリングを考える必要があり、このやり方によって実行効率が左右される。 このため、開発中のMegaScriptに適したタスクスケジューリングの研究を行っている。
タスクスケジューリングの研究は多数行われているが、 MegaScriptでは以下のような特徴があり、 短いスケジューリング時間と良いスケジューリング結果の両立が困難である。
そこで、様々なヒューリスティックを利用することで、 短いスケジューリング時間で妥当なスケジューリング結果を出すことを目指している。
MegaScriptはワークフロー型のプログラミングモデルに基づく言語であるため、 MPIなどのメッセージ通信型のプログラミングなどに比べると記述の難易度は低い。 しかし、頭の中でDAGとして考えたワークフロー構造を、 明示的に組み立てるコードに変換して記述する必要がある。
そこで、GUIによりDAGを図の形で入力し、 それを自動的にMegaScriptプログラムに変換することで、 より容易に並列プログラミングが可能な開発環境の研究を行っている。 この種の「ビジュアルプログラミング」は多数提案されており、 直感的に理解しやすく取っつきが良いといった利点を持つ。 しかし一方で、テキストベースのプログラミングと比べると、 多次元構造や条件分岐を扱いにくい、 熟練者にとっては入力・編集効率が悪いといった欠点も持つ。 そこで、従来のテキストコード表現とそれを可視化したグラフ表現の双方をユーザに提示し、 どちらの表現を編集しても直ちにもう一方に反映されるようなシステムを構築した。
Orgelや(Perl)+の成果を踏まえて、並列スクリプト言語MegaScriptの設計・開発を行っている。
MegaScriptはRubyをベースとするオブジェクト指向スクリプト言語である。 Cなどで記述されたプログラムをタスクとして扱い、 タスクのパラメータやタスク間のデータフローを定義するワークフローを、 スクリプトプログラムとして記述する。
タスクの配列やサブワークフローを定義するクラスを用意することにより、 一般的な実ワークフローであれば、 直感的な複雑さと同程度の簡潔な記述ができるように設計されている。 また、XMLなどで記述されたワークフロー構造を事前に実環境へマッピングする方式と異なり、 ワークフロー実行時に直接スクリプトのコードを実行するため、 特定イベント時のハンドラをスクリプト内に記述するといった、 細かい処理も可能である。
近年、安価なネットワークやPCが普及してきたため、 マルチプロセッサマシンやPCクラスタなどの並列計算機環境が、 エンドユーザにも手が届くものになりつつある。 こうした資源を生かすには、従来の高性能な並列言語処理系だけでなく、 お手軽に並列処理を記述できるプログラミング言語と処理系が必要である。 逐次環境ではPerlなどのスクリプト言語がCなどの性能重視型言語を 補完するものとして普及しているが、 並列プログラミングにおいてはこのような言語はあまり存在しない。
そこでPerlをベースとする並列スクリプト言語(Perl)+の研究を行った。 (Perl)+はRPCによりPerlサブルーチンを並列タスクとして実行する機能を持つ。 RPCの返り値の評価は代入時点ではなく値の参照時点まで遅延されるため、 呼び出し側はRPCを行った後、自分も並行して別の処理を行い、 その後に先ほどの返り値を評価する、 といったスタイルのプログラミングが可能である。
また、タスク間の情報のやりとりはサブルーチンの引数・返り値を用いるほか、 通信ストリームを介したメッセージ通信も可能である。 ストリームはプログラム上、特殊なファイルとして扱われ、 同名のストリームをオープンしたタスク同士が、通信相手として結びつけられる。 ストリームに対するメッセージの送受信は、 ファイルと同じ入出力構文により行うことができる。
マルチエージェント型の並列モデルと宣言的な通信路を用いた、 並列言語Orgelの研究を行った。
Orgelのプログラムはストリームと呼ばれる抽象通信路で結合された エージェントの集まりとして記述する． エージェントは枠組として，非同期メッセージの受信・応答機構や 未到着メッセージの参照に対する中断・再開機構を備える． ユーザはこのエージェントが実行する逐次コードを記述し、 その中で明示的なメッセージ送信を行う。
Orgelでは、ストリームとエージェントの接続を、 操作ではなく宣言として行う。 KL1などでは並行プロセスやストリームを動的に生成し、 接続も操作的、つまり動的に行う。 これに対してOrgelでは、エージェントやストリームを変数として宣言し、 これらの間の接続関係も宣言文で記述する。 これにより、 一対一、一対多といったエージェント間の通信関係がコンパイル時に決定され、 通信処理の効率よい実装が可能になる。
第五世代計算機計画で開発された並列論理型言語は、 暗黙の通信・同期により並列記述が容易であり、 また論理型言語であることから非定型的な非数値処理に適している。 このため、 とくに記号処理・知識処理といった分野の並列プログラム記述に力を発揮する。
しかし、Cなどの手続き型言語に比べ、 KL1ではユーザが明示しないために処理系が解決すべき要素が多い。 たとえば通信・同期のタイミング、 並列・並行実行の最小単位であるゴールの実行順序(スケジューリング)などである。 これらの要素は一般に実行時まで決定できないため、 多くの処理系では実行時に動的な処理を行っており、 効率を低下させる要因となっている。 この結果、Cなどの処理系と比較して性能が劣るという欠点を生じている。
そこで、この動的処理の一部をコンパイル時に静的に解決することによって、 KL1処理系の実行効率向上を図った。 具体的には、KL1プログラムの静的解析を行って実行時の振舞いを予測し、 その結果を用いてプログラムを最適化する手法を開発した。
論理型言語の解析手法としては、従来よりさまざまな方法が提案されている。 我々の研究では、制約充足による型解析をベースとし、 型情報を拡張して依存ゴールや入出力方向といった情報を持たせることで、 プロセッサ間の通信パターン解析やゴール間の依存解析などに応用した。
論理型言語では、二つのゴールに同じ変数を引数として与えることで、 この変数が両ゴールの共有変数となる。 KL1ではこれらのゴールが違うプロセッサで実行される場合、 プロセッサ間の共有変数が生まれる。この変数へのアクセスが生じると、 ランタイムはプロセッサ間の単一化を実現するための物理通信を自動的に行う。
この機構により、KL1では他のプロセッサが生成した値をもらうためには、 単に共有変数を参照するだけで良く、明示的なsend/receiveを記述する負担がない。 しかし、どの値を送信すべきかはその値が参照されるまでわからないため、 値が参照されるたびに細粒度の通信が発生し、大きなオーバヘッドとなる。
この問題はとくにリストなどの構造型データにおいて大きな速度低下を引き起こす。 構造型データの場合、そのどの要素が必要になるかは各々が参照されるまで わからない。このため、リストの個々の要素をそれぞれ1メッセージとして転送 してしまう。これを改善するには構造型データを一度に転送すれば良いが、 この場合、結果的にデータの一部しか参照しなければ、 残りの転送は無駄になってしまう。
そこで我々の手法では、プログラムの静的解析により参照される部分を抽出し、 その部分だけをまとめ送りする送信コードを生成する。 本手法では、 リストの先頭n要素を参照するといった実行時の値で決まる部分は予測できない。 しかし、リストのリストに対し、 外側のリストは参照するがネストした内側のリストは参照しない、 といったパターンを抽出し、 外側のリスト要素のみまとめ送りするコードを生成することができる。
実行順序の決まっているPrologと異なり、 KL1では生成済みゴールからあるスケジューリング戦略に従って次実行ゴールを選ぶ。 このゴールが未具体化引数を参照していれば中断して他のゴールの実行に切り替え、 後に他のゴールによりこの未具体化引数が具体化されれば、 中断したゴールの実行を再開する。 このため、節内のゴールの記述順序に関わりなく、 依存関係に応じて自動的に正しく実行される。
しかし、このゴールの中断・再開機構のオーバヘッドのため、 単一プロセッサ上での逐次実行効率はCなどに比べると劣っている。 とくに、すべてのゴールについて中断可能にするため、 ゴールの環境はヒープ上に生成しており、 Cなど環境をスタックで管理する言語実装に比べると、 参照の局所性が低い、ヒープのGC時間だけ実行時間が増加する、といった問題がある。
そこで静的解析によりゴール間の依存解析を調べ、 ゴール間の相互依存がない部分についてはデータフロー順に並べ替え、 実行順序を静的に固定する。 この実行順を固定したゴール列をスレッドと呼ぶ。 スレッド間は従来のゴールと同様に、 データ依存による中断・再開によって動的スケジューリングを行うが、 スレッド内ゴールはスタック上に環境を生成し、固定順序で高速に実行できる。
最終更新: 2015年 4月 1日 水曜日 18:14:24 JST
御意見、御感想は ohno@arch.info.mie-u.ac.jp まで