Mercurial > hg > Papers > 2018 > parusu-master
view slide/slide.md @ 77:161db9fd907a
Add slide
author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 09 Feb 2018 19:49:46 +0900 |
parents | |
children | cae61efc3f26 |
line wrap: on
line source
title: Gears OS の並列処理 author: 伊波 立樹 profile: 琉球大学理工学研究科 河野研 lang: Japanese code-engine: coderay ## Gears OS - 並列処理のチューニングや信頼性を保証するのは難しい - スレッド間の共通資源の競合などの非決定的な実行 - 従来のテストやデバッグではテストしきれない部分が残ってしまう - Gears OS では計算をノーマルレベルとメタレベルに階層化 - ノーマルレベルの計算に対してメタレベルで信頼性を保証したい - メタレベルの計算はデータ拡張や実行環境の切り替え等の拡張性のための計算を行う ## Code Gear、 Data Gear - Gears OS は Code Gear、 Data Gear という Gear で構成される - Code Gear はプログラムの処理そのものを表す - Data Gear はデータそのものを表す - Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Input Data Gear が揃った Code Gear の並列実行を行う <div style="text-align: center;"> <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600"> </div> ## Continuation based C - Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる - CbC は処理を Code Gear を用いて記述する事を基本とする ## Continuation based C - Code Gear の定義は ``__code CS名`` で行う - Code Gear 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ - Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない - このような環境を持たない継続を軽量継続と呼ぶ ## Continuation based C - このコードは cg0、cg1 の2つの Code Gear を定義している - cg0 内の ``goto cg1`` でgj1 への継続を行っている - ここで(a+b) が cg1 への入力になる ``` c __code cg0(int a, int b) { goto cg1(a+b); } __code cg1(int c) { goto cg2(c); } ``` ## メタ計算 - メタ計算 は通常の計算を実行するための計算 - 信頼性の確保やメモリ管理、スレッド管理、 CPU、 GPU の資源管理等 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる ## Meta Gear - メタ計算 は Code Gearの接続の間に行われる - メタ計算 の処理も Code/Data Gear で実現する - この Gear を Meta Code/Data Gearと呼ぶ - Meta Code Gear は メタ計算 のプログラム部分 - Meta Data Gear は Meta Code Gear で管理されるデータ部分 - Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う <div style="text-align: center;"> <img src="./images/meta_cg_dg.svg" alt="message" width="850"> </div> ## Context - Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear - 従来のOS のスレッドやプロセスに対応 - 独立したメモリ空間を持つ - Code Gear、 Data Gear へのポインタ - 並列実行用の Task 情報 - を持つ - Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする ## 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; .... }; ``` ## Code Gear の stub - Data Gear にアクセスするにはContext を経由する - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある - Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する - stub は一種の Meta Code Gear であるため、 CbC で自動生成される - このコードでは Array と LoopCounter が必要な code1 の stub を示している ``` c __code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { ... } /* stub define */ __code code1_stub(struct Context* context) { goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter); } ``` ## Context での stub Code Gear の記述の問題点 - Context プログラム全体で使用する Code Gear と Data Gear の集合 - 全ての Code と Data の組合せをContext から 全て展開し、その組合せを stub Code Gear に書く必要がある - Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた - そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した ## Interface - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear - これは Context より小さい集合のため、 stub Code Gear での各API で決まった形になる - Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る - Interface は Java のインターフェース、 Haskell の型クラスに対応する ## プロトタイプ の構成 - 今回は並列処理を行う機構の実装を行う - 必要な要素は大きく5つ - Context - TaskQueue - 実行される Task のリストを扱う - Persistent Data Tree - Code Gear によって参照される Data Gear の管理を行う - Worker - TaskQueue から Task を取得し、実行する - TaskManager - Persistent Data Tree を監視し、 Task の依存関係を解決する ※ TaskManager は今回未実装 ## TaskQueue - Task Queue は Task のリストを扱う - すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する - TaskQueue は 2つで Data Gear で表現される - 先頭と末尾の要素を持った Queue 表す Data Gear - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear ``` c // Data Gear define union Data { struct Queue { struct Element* first; struct Element* last; } queue; struct Element { struct Task* task; struct Elemen* next; } element }; ``` ## TaskQueueの操作(Enqueue) - Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定 - 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある ``` c __code putQueue3(struct Queue* queue, struct Element* new_element) { struct Element* last = queue->last; if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) { last->next = new_element; goto exit(); } else { goto putQueue3(queue, new_element); } } ``` ## Worker - Worker は TaskQueue から Task を取得して実行する <table align='center'> <tbody> <tr> <td> <div> <img src="./images/worker.svg" alt="message" width="600"> </div> </td> <td> <ol> <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li> <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li> <li> Task に格納されている Code Gear を実行する </li> <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li> </ol> </td> </tr> </tbody> </table> - Task が完了したら次の Task を取得する ## TaskManger - TaskManager は Task の依存関係の解決を行う - Thread の作成と停止も行う <div style="text-align: center;"> <img src="./images/taskManager.svg" alt="message" width="800"> </div> ## プロトタイプの実行 - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった ## Gears OS で実行する Code Gear 例 - プロトタイプのタスクの例題として Twice を実装した - Twice は与えられた整数配列を2倍にする例題である ``` c // Twice Code Gear __code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) { int i = loopCounter->i; if (i < alignment) { array[i+index*alignment] = array[i+index*alignment]*2; loopCounter->i++; goto twice(loopCounter, index, alignment, array); } loopCounter->i = 0; goto exit(); } ``` ## 並列処理の確認 - Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った - 環境 - Memory : 16GB - CPU : 6-core Intel Xeon 2.66GHZ x 2 - 要素数 : 2^17 * 1000 - 分割数 : 640 タスク - 1 Task 当たりの処理量 : 2^11 * 100 elements <table border="1" align='center' width='50%'> <tbody> <tr> <td style="text-align: center;">Number of Processors</td> <td style="text-align: center;">Time(ms)</td> </tr> <tr> <td style="text-align: center;">1 CPU</td> <td style="text-align: right;">1315</td> </tr> <tr> <td style="text-align: center;">2 CPUs</td> <td style="text-align: right;">689</td> </tr> <tr> <td style="text-align: center;">4 CPUs</td> <td style="text-align: right;">366</td> </tr> <tr> <td style="text-align: center;">8 CPUs</td> <td style="text-align: right;">189</td> </tr> <tr> <td style="text-align: center;">12 CPUs</td> <td style="text-align: right;">111</td> </tr> </tbody> </table> - 1cpu と 12cpu では 11.8 倍の向上が見られた ## Cerium との比較 - Cerium は本研究室で開発していた並列プログラミングフレームワーク - Cerium では Task を依存関係に沿って実行することで並列実行を可能にする - 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない - Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる - Task には汎用ポインタとしてデータの受け渡しを行う - 型情報がなく、型の検査を行うことが出来ない - Gears OS では 型情報をもつ Data Gear を定義 ## 既存の OS への対応 - Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義 - 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う ## まとめ - Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った - 依存関係のない Twice を実装し、並列処理が行えることを確認した ## 今後の課題 - 一般的に並列処理には依存関係が存在する - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、 依存関係のある並列処理の例題を作成し、評価する - GPUなどの他のプロセッサ演算に利用することが出来ない - Data Gear などのデータをGPUにマッピングするための機構が必要 - Gears OS でのデバック手法 - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案 - 並列処理でのデバック手法も考案する必要がある - 型情報の検査 - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを メタ計算 として実装する - Contextの動的生成 - 今は静的に自分で生成している - CbC 用の Runtime をつくり、 Context を動的に生成