Mercurial > hg > Papers > 2016 > parusu-sigos
view presen/sigos.html @ 17:f2f9c7110b41
Update
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 29 May 2016 19:28:03 +0900 |
parents | f88786cba8b5 |
children | 4c465c6fe2cc |
line wrap: on
line source
<!DOCTYPE html> <html> <head> <meta http-equiv="content-type" content="text/html;charset=utf-8"> <title>Code Gear、 Data Gear に基づく OS のプロトタイプ</title> <meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15]"> <meta name="author" content="伊波 立樹" > <!-- style sheet links --> <link rel="stylesheet" href="s6/themes/projection.css" media="screen,projection"> <link rel="stylesheet" href="s6/themes/screen.css" media="screen"> <link rel="stylesheet" href="s6/themes/print.css" media="print"> <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection"> <!-- JS --> <script src="s6/js/jquery-1.11.3.min.js"></script> <script src="s6/js/jquery.slideshow.js"></script> <script src="s6/js/jquery.slideshow.counter.js"></script> <script src="s6/js/jquery.slideshow.controls.js"></script> <script src="s6/js/jquery.slideshow.footer.js"></script> <script src="s6/js/jquery.slideshow.autoplay.js"></script> <!-- prettify --> <link rel="stylesheet" href="scripts/prettify.css"> <script src="scripts/prettify.js"></script> <script> $(document).ready( function() { Slideshow.init(); $('code').each(function(_, el) { if (!el.classList.contains('noprettyprint')) { el.classList.add('prettyprint'); el.style.display = 'block'; } }); prettyPrint(); } ); </script> <!-- Better Browser Banner for Microsoft Internet Explorer (IE) --> <!--[if IE]> <script src="s6/js/jquery.microsoft.js"></script> <![endif]--> </head> <body> <div class="layout"> <div id="header"></div> <div id="footer"> <div align="right"> <img src="s6/images/logo.svg" width="200px"> </div> </div> </div> <div class="presentation"> <div class='slide cover'> <table width="90%" height="90%" border="0" align="center"> <tr> <td> <div align="center"> <h1><font color="#808db5">Code Gear、 Data Gear に基づく OS のプロトタイプ</font></h1> </div> </td> </tr> <tr> <td> <div align="left"> 伊波 立樹 琉球大学理工学研究科情報工学専攻 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;"> </div> </td> </tr> </table> </div> <div class='slide '> <!-- === begin markdown block === generated by markdown/1.2.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15] on 2016-05-29 18:34:59 +0900 with Markdown engine kramdown (1.11.1) using options {} --> <!-- _S9SLIDE_ --> <h2 id="gears-os">Gears OS</h2> <ul> <li>当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて、並列性、柔軟性、信頼性を指標とした Gears OS を設計してきた</li> <li>本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装し、並列処理を行う簡単な例題を用いて評価を行う</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os-">Gears OS の並列性</h2> <ul> <li>Code Gear と Data Gear という Code と Data の単位を使って構成される</li> <li>Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--1">Gears OS の柔軟性</h2> <ul> <li>Gear を追加することでデータ拡張や機能の追加が可能</li> <li>GPU 等のさまざまなアーキテクチャでも同じプログラムが動く</li> <li>バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う</li> <li>実行時の処理の変更を可能とする</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--2">Gears OS の信頼性</h2> <ul> <li>検証 <ul> <li>モデル検査を行う</li> <li>できるだけ有限状態</li> <li>スタックや環境など不必要に状態を入れない</li> </ul> </li> <li>証明 <ul> <li>Code Gear と Data Gear を理論に定義</li> </ul> </li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--gear">Gears OS での Gear</h2> <ul> <li>Gears OS はプログラムの単位として Gear を用いる</li> <li>Gear は並列実行の単位、データの分割、 Gear 間の接続等になる</li> <li>Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="code-gear-data-gear">Code Gear、 Data Gear</h2> <ul> <li>Code Gear はプログラムの処理そのものを表す</li> <li>Data Gear は int や 文字列などの Data そのものを表す</li> <li>Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する</li> </ul> <div style="text-align: center;"> <img src="./images/codeGear_dataGear.svg" alt="message" width="900" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="code-gear-data-gear-">Code Gear、 Data Gear での並列実行</h2> <ul> <li>Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う</li> </ul> <div style="text-align: center;"> <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="900" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="meta-computation">Meta Computation</h2> <ul> <li>Gears OS の柔軟性は Meta Computation で実現</li> <li>Meta Computation は通常の Computation のための Computation</li> <li>並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理など</li> <li>Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="meta-gear">Meta Gear</h2> <ul> <li>Meta Code Gear は 通常の Code Gear の直後に接続され、 Meta Computation を実行</li> <li>Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続</li> <li>Meta Data Gear はMeta Computation を行うために使用する Data Gear</li> <li>Meta 部分は Normal Level からなるべく見えない</li> </ul> <div style="text-align: center;"> <img src="./images/meta_gear.svg" alt="message" width="900" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="continuation-based-c">Continuation based C</h2> <ul> <li>Gears OS の実装は本研究室で開発しているCbC(Continuation based C)を用いる</li> <li>CbC は処理を Code Segment を用いて記述する事を基本とする</li> <li>Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="continuation-based-c-1">Continuation based C</h2> <ul> <li>Code Segment の定義は <code>__code CS名</code> で行う <ul> <li>Code Gear も同等に定義する</li> </ul> </li> <li>Code Segment 間は <code>goto CS名</code> で移動する。この移動を継続と呼ぶ</li> <li>C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ</li> </ul> <pre lang="c"><code>/* code1 define */ __code code1(List list) { .... goto code2(list) } /* code2 define */ __code code2(List list) { ... } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="context">Context</h2> <ul> <li>Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている Meta Data Gear</li> <li>各 Gear にアクセスする際は Context を経由する</li> <li>Worker 毎にContext を持っている</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="context-1">Context</h2> <ul> <li>実行可能な Code Gear の名前は <strong>enum</strong> で定義する</li> <li>Context の初期化時に名前と関数ポインタを対応付ける</li> </ul> <pre lang="c"><code>enum Code { Code1, Code2, Code3, Exit, }; </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="context-2">Context</h2> <ul> <li>Context は C の構造体で表現される</li> </ul> <pre lang="c"><code>/* context define */ struct Context { int codeNum; __code (**code) (struct Context*); void* heapStart; void* heap; long heapLimit; int dataNum; union Data **data; }; </code></pre> <ul> <li>実行可能な Code Gear の数を示す <strong>CodeNum</strong></li> <li>実行可能な Code Gear へのポインタ <strong>Code</strong></li> <li>Data Gear の Allocate 用の <strong>heapStart</strong>, <strong>heap</strong>, <strong>heapLimit</strong></li> <li>Data Gear の数を示す <strong>dataNum</strong></li> <li>Data Gear へのポインタ <strong>data</strong></li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="data-gear-">Data Gear の表現</h2> <ul> <li>使用する Data Gear は C の共用体と構造体を用いた表現をする</li> <li>これを元に Gears OS は 必要な Data Gear を allocate する</li> </ul> <pre lang="c"><code>/* data Gear define */ union Data { struct Time { enum Code next; double time; } time; struct LoopCounter { int i; } loopCounter; .... }; </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="code-gear--stub">Code Gear の stub</h2> <ul> <li>通常 Data Gear にアクセスするにはContext を経由しなければならない</li> <li>しかし、通常の Code Gear ではMeta Data Gear である Context をあまり参照したくない</li> <li>そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する</li> <li>stub は一種の Meta Code Gear である</li> </ul> <pre lang="c"><code>__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); } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="cbc--gears-os-">CbC の Gears OS サポート</h2> <ul> <li>通常の goto の継続では Meta Code Gear への継続が見えてしまう</li> <li>Code Gear の指定も 一度 Meta を挟む必要があるので enum を指定することで行っている</li> </ul> <pre lang="c"><code>__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { ... goto meta_code1(context, Code2); } __code code1_stub(struct Context* context) { goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter); } __code meta_code1(struct Context* context, enum Code next) { goto (context->code[next])(context); } __code code2(struct Context* context, struct Array* array) { ... } __code code2_stub(struct Context* context) { goto code1(context, &context->data[Node]->node.value->array); } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="cbc--gears-os--1">CbC の Gears OS サポート</h2> <ul> <li>Meta Code Gear への接続を自動的に行う構文サポートを行う</li> <li>stub の自動生成も行う</li> </ul> <pre lang="c"><code>__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { ... goto code2(array); } __code meta_code1(struct Context* context, enum Code next) { goto (context->code[next])(context); } __code code2(struct Context* context, struct Array* array) { ... } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--3">Gears OS の構成</h2> <ul> <li>Context <ul> <li>Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される</li> </ul> </li> <li>TaskQueue <ul> <li>CAS を利用したスレッドセーフなQueue</li> <li>ActiveTaskQueue と WaitTaskQueue の 2種類</li> </ul> </li> </ul> <div style="text-align: center;"> <img src="./images/gearsos.svg" alt="message" width="750" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--4">Gears OS の構成</h2> <ul> <li>Persistent Data Tree <ul> <li>Code Gear によって参照される Data Gear の管理を行う</li> </ul> </li> <li>TaskManager <ul> <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li> </ul> </li> </ul> <div style="text-align: center;"> <img src="./images/gearsos.svg" alt="message" width="750" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="gears-os--5">Gears OS の構成</h2> <ul> <li>Worker <ul> <li>Worker は ActiveTaskQueue から Task を取得する</li> <li>取得した Task から必要な Data Gear を Tree から取得し、 Code Gear を実行</li> <li>実行後必要なデータを Persistent Data Tree 書き出す</li> </ul> </li> </ul> <div style="text-align: center;"> <img src="./images/gearsos.svg" alt="message" width="750" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="taskqueue">TaskQueue</h2> <ul> <li>Task Queue は Task の管理を行う</li> <li>すべての Worker の Context で共有される</li> <li>TaskQueue は 2つで Data Gear で表現される <ul> <li>先頭と末尾の要素を持った Queue 表す Data Gear</li> <li>Task と次の要素へのポインタを持った、List を表現する Element という Data Gear</li> </ul> </li> </ul> <pre lang="c"><code>// Data Gear define union Data { struct Queue { struct Element* first; struct Element* last; } queue; struct Element { struct Task* task; struct Elemen* next; } element }; </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="taskqueueenqueue">TaskQueueの操作(Enqueue)</h2> <ul> <li>Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定</li> <li>正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある</li> </ul> <pre lang="c"><code>__code putQueue3(struct Context* context, 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 meta(context, context->next); } else { goto meta(context, PutQueue3); } } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="persistent-data-tree">Persistent Data Tree</h2> <ul> <li>Persistent Data Tree は Data Gear の管理を行う</li> <li>TaskQueue と同じですべての Context で共有される</li> <li>挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ</li> <li>Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="worker">Worker</h2> <ul> <li>Worker は TaskQueue から Task を取得して実行する</li> <li>TaskQueue へのアクセスは Enqueue 操作と同じで CAS を用いる</li> <li>Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている</li> <li>Task が完了したら次の Task を取得する</li> </ul> <pre lang="c"><code>// Task define union Data { // size: 8 byte struct Task { enum Code code; int key; } task; } </code></pre> <pre lang="c"><code>__code getQueue(struct Context* context, struct Queue* queue, struct Node* node) { if (queue->first == 0) return; struct Element* first = queue->first; if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) { queue->count--; context->next = GetQueue; context->next = first->task->code; node->key = first->task->key; struct Traverse *t = &context->data[Traverse]->traverse; t->next = GetQueue; goto meta(context, Get); } else { goto meta(context, GetQueue); } } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="worker-1">Worker</h2> <ul> <li>Worker で実行される Code Gear は他の Code Gear と同様の記述である</li> <li>つまり依存関係のない Code Gear は並列で動作させることができる</li> <li>Gears OS 自体が Code Gear によって構成されるため、 Gears OS の実装自体が Gears でプログラミングを行う際の指針になる</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="taskmanger">TaskManger</h2> <ul> <li>TaskManager は Task の依存関係の解決を行う</li> <li>Worker の作成と停止も行う</li> </ul> <pre lang="c"><code>// Code Gear __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { int i = loopCounter->i; if (i < worker->num) { struct Context* worker_context = &worker->contexts[i]; worker_context->next = GetQueue; worker_context->data[Tree] = context->data[Tree]; worker_context->data[ActiveQueue] = context->data[ActiveQueue]; pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context); worker_context->thread_num = i; loopCounter->i++; goto meta(context, CreateWorker); } loopCounter->i = 0; goto meta(context, TaskManager); } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="section">プロトタイプの評価</h2> <ul> <li>今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った</li> <li>これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった</li> <li>Gears OS の評価として依存関係のない例題を実装して評価を行う</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="twice">Twice</h2> <ul> <li>依存関係のない例題として Twice を実装した</li> <li>Twice は与えられた整数配列を2倍にする例題である</li> </ul> <pre lang="c"><code>// Twice Code Gear __code twice(struct Context* context, 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 meta(context, Twice); } loopCounter->i = 0; goto meta(context, context->next); } </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="section-1">実験環境</h2> <ul> <li>測定環境 <ul> <li>Model : MacPro Mid 2010</li> <li>OS : Mac OS X 10.10.5</li> <li>Memory : 16GB</li> <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li> </ul> </li> <li>要素数 : 2^17 * 1000</li> <li>分割数 : 640 タスク</li> <li>1 Task 当たりの処理量 : 2^11 * 100 elements</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="section-2">結果</h2> <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> <div style="text-align: center;"> <img src="./images/twice_640.svg" alt="message" width="900" /> </div> <ul> <li>1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた</li> <li>十分な台数効果が出てる事がわかる</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="cerium-">Cerium との比較</h2> <ul> <li>Cerium は本研究室で開発していた並列プログラミングフレームワーク</li> <li>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする <ul> <li>本来 Task はデータに依存するもので Task 感の依存関係ではデータの依存関係を保証することが出来ない</li> <li>Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる</li> </ul> </li> <li>また Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、型の検査を行うことが出来ない <ul> <li>Gears OS では 型情報をもつ Data Gear を定義</li> </ul> </li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="os-">既存の OS との比較</h2> <ul> <li>Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義</li> <li>通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="section-3">まとめ</h2> <ul> <li>Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li> <li>Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li> <li>依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="section-4">今後の課題</h2> <ul> <li>一般的に並列処理には依存関係が存在する <ul> <li>複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する</li> </ul> </li> <li>GPUなどの他のプロセッサ演算に利用することが出来ない <ul> <li>Data Gear などのデータをGPUにマッピングするための機構が必要</li> </ul> </li> <li>Gears OS でのデバック手法 <ul> <li>軽量継続はスタックを積まないため、スタックトレースが見えない</li> <li>Context から Data Gear を取得できるため、そこから現在の状況を把握することができる</li> <li>Context を見ることができる コードを Meta Computation として入れることで Code Gear を止めて、 Data Gear の状態を見ることができる</li> <li>しかし、 Gears OS は並列実行を基本とするため、 並列で動いているCode Gear に対しては綺麗にデバック出来ない</li> <li>並列処理でのデバック手法も考案する必要がある</li> </ul> </li> <li>型情報の検査 <ul> <li>プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する</li> </ul> </li> </ul> <!-- === end markdown block === --> </div> </div><!-- presentation --> </body> </html>