title: Gears OS の並列処理 author: 伊波 立樹 profile: 琉球大学理工学研究科 河野研 lang: Japanese code-engine: coderay ## 並列処理の重要性 - 並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている - しかし、並列処理のチューニングや信頼性を保証するのは難しい - 共通資源の競合などの非決定的な実行が発生するため、従来のテストやデバッグではテストしきれない部分が残ってしまう - GPU などのアーキテクチャに合わせた並列プログラミングの記述 ## Gears OS - 本研究室では処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している - 並列処理の Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される - 計算をノーマルレベルとメタレベルに階層化、 信頼性と拡張性をメタレベルで保証する - 並列処理の信頼性を通常の計算(ノーマルレベル) に保証 - CPU、GPU などの実行環境の切り替え、データ拡張等を提供 ## Gears OS - 本研究では Gears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う - また、並列処理を行う例題を用いて評価、 OpenMP、 Go 言語との比較を行う ## Code Gear/Data Gear - Gears OS は Code Gear、 Data Gear という単位で構成される - Code Gear はプログラムの処理そのものを表す - Data Gear はデータそのものを表す - Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する - Code Gear と Input/Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う
message
## メタ計算 - メタ計算 は通常の計算を実行するための計算 - 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる - メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる ## Meta Gear - メタ計算 は Code Gear の接続間に行われる - この Gear を Meta Code/Data Gearと呼ぶ - Meta Code Gear は メタ計算 のプログラム部分 - Meta Data Gear は Meta Code Gear で管理されるデータ部分 - Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う
message
## Continuation based C - Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる - CbC は Code Gear を用いて記述する事を基本とする ## Continuation based C - CbC の Code Gear の定義は **__code CG名** で行う - Code Gear 間は **goto CG名** で移動する。この移動を継続と呼ぶ - Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない - このような環境を持たない継続を軽量継続と呼ぶ - 下記のコードでは Code Gear を2つ定義し、 cg0 から cg1 への継続を示している ``` c __code cg0(int a, int b) { goto cg1(a+b); } __code cg1(int c) { goto cg2(c); } ``` ## Data Gear の表現 - Data Gear は構造体を用いて定義する - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される - Data Gear をメモリに確保する際のサイズ情報はこの型から決定する ``` c /* data Gear define */ union Data { struct Timer { union Data* timer; enum Code start; enum Code end; enum Code next; } Timer; struct TimerImpl { double time; } TimerImpl; .... }; ``` ## Context - Context は従来のOS のスレッドやプロセスに対応し、以下の要素をもっている Meta Data Gear - Data Gear を確保するためのメモリ空間 - Code Gear の名前と関数ポインタとの対応表 - Code Gear は番号(enum)で指定する - Code Gear が参照する Data Gear へのポインタ - Code Gear と同じく Data Gear も番号で指定する - 並列実行用の Task 情報 - Data Gear の型情報 - Gears OS ではメタ計算で Context を経由して Code/Data Gear に番号でアクセスする ## stub Code Gear - Data Gear にアクセスするには Context から番号を指定して行う - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある - Gears OS では Code Gear に接続する Data Gear を メタレベルである Context から取り出す処理を行う stub Code Gear を用意している
message
## Interface - Gears OS を実装するに連れて、stub Code Gear の記述が煩雑になることがわかった - そこで、Gears OS のモジュール化する仕組みとして **Interface** を導入した - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear - stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能 - Interface を導入することで、 Stack や Queue などのデータ構造を仕様と実装に分けて記述することが出来る - Interface は Java のインターフェース、 Haskell の型クラスに対応する ## Interface の定義 - Interface の定義には以下の内容を定義する - 操作(API)の引数群の型 - 操作(API)自体のCode Gear の型 ``` c typedef struct Queue{ // Data Gear parameter union Data* queue; union Data* data; __code next(...); __code whenEmpty(...); // Code Gear __code clear(Impl* queue, __code next(...)); __code put(Impl* queue, union Data* data, __code next(...)); __code take(Impl* queue, __code next(union Data*, ...)); __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); } Queue; ``` ## Interface の定義 - **__code next(...)** は継続を表している - ... は可変長引数に相当する - 可変長引数部分には呼び出し元の Interface の Data Gear が入る - 継続の引数で Output Data Gear を返すことが出来る ``` c typedef struct Queue{ // Data Gear parameter union Data* queue; union Data* data; __code next(...); __code whenEmpty(...); // Code Gear __code clear(Impl* queue, __code next(...)); __code put(Impl* queue, union Data* data, __code next(...)); __code take(Impl* queue, __code next(union Data*, ...)); __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); } Queue; ``` ## Interface のインスタンスの生成 - Interface は API に Code Gear を番号を入れることにより、複数の実装ヲ行うことが出来る - 代入する Code Gear を入れ替えることで別の実装を表現する - Interface を表す Data Gear の生成は以下の関数で行われる ``` c Queue* createSingleLinkedQueue(struct Context* context) { struct Queue* queue = new Queue(); // Allocate Queue interface struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement queue->queue = (union Data*)singleLinkedQueue; singleLinkedQueue->top = new Element(); singleLinkedQueue->last = singleLinkedQueue->top; queue->clear = C_clearSingleLinkedQueue; queue->put = C_putSingleLinkedQueue; queue->take = C_takeSingleLinkedQueue; queue->isEmpty = C_isEmptySingleLinkedQueue; return queue; } ``` ## Interface の使い方 - Interface を利用した Code Gear への継続は `goto interface->method` で行われる - **interface** は Interface を表す Data Gear、 **method** は実装した Code Gear に対応する ``` c __code code1() { Queue* queue = createSingleLinkedQueue(context); Node* node = new Node(); node->color = Red; goto queue->put(node, code2); } ``` ## メタレベルでの Interface の呼び出しの詳細 - Interface を利用した Code Gear の継続はスクリプトによってメタレベルの記述に変換される - 変換後は Context を参照するコードが生成される - Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す - Context には Interface の引数を渡すための Data Gear が予め用意されている - goto meta では Interface の Code Gear の番号を Code Gear へのポインタに変換して継続を行う ``` c __code code1(struct Context *context) { Queue* queue = createSingleLinkedQueue(context); Node* node = &ALLOCATE(context, Node)->Node; node->color = Red; Gearef(context, Queue)->queue = (union Data*) queue; Gearef(context, Queue)->data = (union Data*) node; Gearef(context, Queue)->next = C_code2; goto meta(context, queue->put); } ``` ## Interface での stub Code Gear - meta Code Gear では引数に指定された Code Gear の番号から stub Code Gear への関数ポインタを取り出し、 継続を行う - メタ計算で格納された引数は stub Code Gear で Code Gear に渡される - Interface を実装した Code Gear は Interface の定義から stub Code Gear の自動生成が可能 - 必要ならばメタ計算を meta Code Gear か stub Code Gear に埋め込むことができる ``` c // implement put code gear __code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) { ... } // generated by script __code putSingleLinkedQueue_stub(struct Context* context) { SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue); Data* data = Gearef(context, Queue)->data; enum Code next = Gearef(context, Queue)->next; goto putSingleLinkedQueue(context, queue, data, next); } __code meta(struct Context* context, enum Code next) { goto (context->code[next])(context); } ``` ## 並列処理の構成 - 今回は並列処理機構である - Task - 1つの Context 上で goto で遷移しながら実行される Code Gear の列 - TaskManager - 依存関係を解決したTask を Worker SynchronizedQueue に送信する - Worker - SynchronizedQueue から Task を一つずつ取得し、実行する - Worker 毎に POSIX Therad などを生成し、それぞれのスレッドで Code Gear を実行する - SynchronizedQueue - Gears OS で記述されたマルチスレッド環境でもデータの同期処理が行われる Queue - これらを Interface として実装した ## Task - Gears OS では Context が並列実行の Task に相当する - Context は Task用の情報として以下の情報を付け加えた - 実行する Code Gear - Input/Output Data Gear の格納場所 - 待っている Input Data Gear の数 - この Task を実行する Worker ## TaskManger - Worker をCPU、 GPU の数分生成する - 依存関係を解決した Task を各 Worker の Queue に送信する
message
  1. Task を Input Data Gear としてTaskManager の spawn を呼び出す
  2. Task が待っている Data Gear のカウンタである IDGCount をチェックする
  3. IDGCount が0の場合 Data Gear が 揃っているので Worker の Queue に Task を送信する
## Worker - 初期化時に Worker 用の Context を生成し、Code Gear を実行していく - TaskManager から送信された Task を一つずつ取得して実行する
message
  1. Worker は Queue から Task(Context)を取得する
  2. Worker の Context からTask の Context へ入れ替える
  3. Task に設定されている Code Gear を実行
  4. Task の Output Data Gear の書き出し
  5. Task Context から Worker の Context へ入れ替える
  6. Worker は再び Queue から Task を取得する
## Synchronized Queue - TaskManager と Worker 間の通信を行うための Queue - Queue は Worker の数だけ生成される - マルチスレッド間でのデータの同期処理を行える - Gears OS では 同期機構として CAS(Check and Set、 Compare and Swap) を使用した実装を行った - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較し、変化がなければ値を更新する - メモリ番地の値が変わっているなら、もう一度 CAS を行う
message
## 依存関係の解決 - 依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する - この Queue には Data Gear に依存関係がある Context が格納されている
message
  1. Task に設定されている Code Gear を実行する
  2. Output Data Gear の書き出し処理を行う際にメタレベルの Queue を参照する
  3. 依存関係にある Task を取り出し、IDGCount をデクリメントする
- IDGCountの値が0になった実行可能な Task は TaskManager を通して Worker に送信される ## 並列構文 - 並列実行する際は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述としては好ましくない - Context の設定は煩雑な記述だが、並列実行されることを除けば通常の CbC の goto 文と同等 - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した ## par goto 構文 - par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される - par goto 構文には引数として Input/Output Data Gear等を渡す - スクリプトによって Code Gear の Input/Output の数を解析し、待っている Input Data Gear の数を設定する - 並列実行される Task は **__exit** に継続することで終了する - Gears OS の Task はOutput Data Gear を書き出す処理で終了するため **__exit** に直接継続せずに Data Gear を書き出す処理に継続する - par goto 構文は通常のプログラミングの関数呼び出しのように扱える ``` c __code code1(Integer *integer1, Integer * integer2, Integer *output) { par goto add(integer1, integer2, output, __exit); goto code2(); } ``` ## CUDA への対応 - Gears OS は GPU での実行もサポートしている - GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる - CUDA は GPU を Device、 CPU を Host として定義する - CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する - 今回、CUDA に合わせた並列処理機構である CUDAWorker、 CUDAExecutor をInterface を用いて実装し、 CPU、GPU 間のデータのマッピングのために CUDABuffer を用意した ## CUDAWorker - CUDA で実行する Task を受け取る Worker - 初期化の際に CUDA ライブラリの初期化や CUDAExecutor の生成を行う ## CUDAExecutor - CUDAExecutor は Executor Interface を実装した Data Gear - 以下の Code Gear を実装している - HostからDevice へのデータの送信(read) - kernel の実行(exec) - Device から Host へのデータの書き出し(write) ``` c typedef struct Executor{ union Data* Executor; struct Context* task; __code next(...); // method __code read(Impl* executor, struct Context* task, __code next(...)); __code exec(Impl* executor, struct Context* task, __code next(...)); __code write(Impl* executor, struct Context* task, __code next(...)); } ``` ## CUDABuffer - Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある - CUDA Buffer ではそのマッピングを行う - このマッピングは Task に設定されている stub Code Gear で行われる
message
## CUDA での呼び出し - Gears OS では Task に設定している Code Gear の stub Code Gear で CUDA実行を切り替える - CUDABuffer でのマッピング、実行する kernel の読み込みは stub Code Gear で行われる - CUDA で実行する際は stub Code Gear に対応する Code Gear ではなく、 CUDAExecutor の Code Gear に継続する
message
## Gears OS の評価 - 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った - CPU 環境 - Model : Dell PowerEdgeR630 - Memory : 768GB - CPU : 2 x 18-Core Intel Xeon 2.30GHz - GPU 環境 - GPU : GeForce GTX 1070 - Cores : 1920 - ClockSpeed : 1683MHz - Memory Size : 8GB GDDR5 ## Twice - Twice は与えられた整数配列を2倍にする例題である - 並列実行の依存関係がなく、並列度が高い課題である - 要素数 2^27 - CPU での実行時は要素数 2^27 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で kernel を実行 ## Twice の結果 - GPU は CPU との通信時間を含めた時間、 GPU(kernel only) は kernel のみの実行時間を示している - 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた - GPU は通信時間を含めると 8 CPU の約1.25倍、 kernel のみの実行では 32 CPU の約7.22倍になった - 通信時間がオーバーヘッドになっている
Processor Time(ms)
1 CPU 1181.215
2 CPUs 627.914
4 CPUs 324.059
8 CPUs 159.932
16 CPUs 85.518
32 CPUs 43.496
GPU 127.018
GPU(kernel only) 6.018
## BitonicSort - 並列処理向けのソートアルゴリズム - 決まった2点間の要素の入れ替えを並列に行うことでソーティングを進めていく - 要素数 2^24 - CPU での実行時は要素数 2^24 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で kernel を実行 ## BitonicSort の結果 - 1 CPU と 32 CPU で約22.12倍の速度向上 - GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった - 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった
Processor Time(s)
1 CPU 41.416
2 CPUs 23.340
4 CPUs 11.952
8 CPUs 6.320
16 CPUs 3.336
32 CPUs 1.872
GPU 5.420
GPU(kernel only) 0.163
## OpenMP との比較 - OpenMP は C、 C++ のプログラムにアノテーションを付けることで並列化を行う - データの待ち合わせ処理はバリア等のアノテーションで記述する - Gears OS は並列処理を par goto 構文、 データの待ち合わせを Code Gear と Input/Ouput Data Gear の関係で行う ``` c #pragma omp parallel for for(int i = 0; i < length; i++) { a[i] = a[i] * 2; } ``` ## Go 言語との比較 - Go 言語は並列実行を **go funciton(argv)** の構文で行う。 この実行を goroutine と呼ぶ - goroutine 間のデータの待ち合わせはチャネルというデータ構造で行う - チャネルでのデータの送受信は **<-** を使用して行うため、簡潔に書くことが出来る - しかし、 チャネルは複数の goroutine で共有されるため、データの送信元が推測しづらい - Gears OS では goroutine は par goto 文とほぼ同等に扱える - par goto 文では書き出す Data Gear を指定するため、書き出し元が推測しやすい ``` go c := make(chan []int) for i :=0; i < *split; i++ { // call goroutine go twice(list, prefix, i, c); } func twice(list []int, prefix int, index int, c chan []int) { for i := 0; i < prefix; i++ { list[prefix*index+i] = list[prefix*index+i] * 2; } c <- list } ``` ## まとめ - Gears OS の並列処理機構を Interface を用いて実装を行った - Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった - par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった - 2つの例題である程度の台数効果が出ることを確認した ## 今後の課題 - Gears OS の並列処理の信頼性の保証、チューニングを行う - Gears OS では証明とモデル検査をメタレベルで実現することで信頼性を保証する - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う - 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う ## 今後の課題 - OpenMP、 Go 言語で Twice を実装し、 Gears OS の性能比較を行った - その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう - モデル検査で par goto で実行する Code Gear のフローを解析し、処理が軽い場合は Context を生成せずに関数呼出しを行う等の最適化が必要
message
## データ並列 - data並列はあるデータ構造がサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法 - Gears OS ではdata 並列は par goto 構文に**iterate(分割数)**を追加することで可能になる - データ並列の Task は CPU で実行する際は Task にインデックスを付与して分割数分コピーして実行する - CUDA の場合は Kernel を実行する際にパラメーターとして分割数を渡す ## Task 間の同期処理 - Context 間での同期処理を行うために Semaphore を実装 - Semaphore はContext 停止用の待ち Queue を持つ
message