Mercurial > hg > Papers > 2016 > parusu-sigos
changeset 16:f88786cba8b5
Update
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 29 May 2016 16:34:28 +0900 (2016-05-29) |
parents | f3161681d273 |
children | f2f9c7110b41 |
files | presen/sigos.html presen/sigos.md sigos.mm |
diffstat | 3 files changed, 532 insertions(+), 122 deletions(-) [+] |
line wrap: on
line diff
--- a/presen/sigos.html Sat May 28 18:57:36 2016 +0900 +++ b/presen/sigos.html Sun May 29 16:34:28 2016 +0900 @@ -87,57 +87,47 @@ <!-- === begin markdown block === generated by markdown/1.2.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15] - on 2016-05-28 18:56:26 +0900 with Markdown engine kramdown (1.11.1) + on 2016-05-29 16:21:21 +0900 with Markdown engine kramdown (1.11.1) using options {} --> <!-- _S9SLIDE_ --> -<h2 id="gears-os">Gears OS</h2> +<h2 id="gears-os-">Gears OS の並列性</h2> <ul> - <li>CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている</li> - <li>そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある</li> - <li>マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない</li> - <li>また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している</li> - <li>並列処理をする上でこれらのリソースを無視することができない</li> - <li>しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる</li> - <li>並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる</li> - <li>本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS のプロトタイプ設計・実装を行い、簡単な例題を用いて評価を行う</li> + <li>Code Gear と Data Gear という Code と Data の単位を使って構成される</li> + <li>Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cerium">Cerium</h2> +<h2 id="gears-os--1">Gears OS の柔軟性</h2> <ul> - <li>Cerium は本研究室で開発していた並列プログラミングフレームワーク</li> - <li>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする</li> - <li>依存関係を Task 間で設定する</li> + <li>Gear を追加することでデータ拡張や機能の追加が可能</li> + <li>GPU などの CPU とは異なるアーキテクチャでも同じプログラムが動く</li> + <li>バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う</li> + <li>実行時の処理の変更を可能とする</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cerium-">Cerium の問題点</h2> +<h2 id="gears-os--2">Gears OS の信頼性</h2> <ul> - <li>本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない</li> - <li>Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、 汎用ポインタをキャストして利用している</li> -</ul> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="gears-os-1">Gears OS</h2> -<ul> - <li>Gears OS は Code Gear と Data Gear によって構成される</li> - <li>Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする</li> - <li>Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する</li> - <li>Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される</li> - <li>Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する</li> - <li>依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる</li> - <li>Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される</li> + <li>検証 + <ul> + <li>モデル検査を行う</li> + <li>できるだけ有限状態</li> + <li>スタックや環境など不必要に状態を入れない</li> + </ul> + </li> + <li>証明 + <ul> + <li>Code Gear と Data Gear を理論に定義</li> + </ul> + </li> </ul> @@ -158,12 +148,10 @@ <h2 id="code-gear-data-gear">Code Gear、 Data Gear</h2> <ul> <li>Code Gear はプログラムの処理そのものを表す</li> - <li>任意の数の Input Data Gear を参照し、 Code Gear の処理が完了すると任意の数の Output Data Gear を生成する</li> - <li>Code Gear は接続された Input Data Gear 以外の Data にはアクセスしない</li> - <li>Data Gear は Data そのものを表す</li> - <li>int や 文字列などの Primitive Data Type が入っている</li> - <li>Code Gear から参照される Data Gear を Input Data Gear、 Code Gear の処理で生成される結果を Output Data 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> @@ -187,9 +175,10 @@ <!-- _S9SLIDE_ --> <h2 id="meta-computation">Meta Computation</h2> <ul> - <li>Gears OS では通常の Computation のために実行する Computation を Meta Computation として扱う</li> - <li>Meta Computation の例として並列処理の依存関係の解決、 OSが行うネットワーク管理、メモリ管理等がある</li> - <li>Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現する</li> + <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> @@ -198,8 +187,10 @@ <!-- _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 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;"> @@ -214,7 +205,7 @@ <ul> <li>Gears OS の実装は本研究室で開発しているCbC(Continuation based C)を用いる</li> <li>CbC は処理を Code Segment を用いて記述する事を基本とする</li> - <li>そのため Gears OS の Code Gear を記述する事に適している</li> + <li>Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している</li> </ul> @@ -223,21 +214,192 @@ <!-- _S9SLIDE_ --> <h2 id="continuation-based-c-1">Continuation based C</h2> <ul> - <li>Code Segment の定義は <code>__code CS名</code> で行う</li> + <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> <li>このような元の環境を持たない継続を計量継続と呼ぶ</li> </ul> -<div style="text-align: center;"> - <img src="./images/cbc_goto.svg" alt="message" width="900" /> +<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, 独立したメモリ空間をもっている</li> + <li>Gear にアクセスする際は Context を経由する</li> + <li>Gears OS では 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="gears-os-">Gears OS の構成</h2> +<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 Code 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 code1_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> @@ -262,7 +424,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears-os--1">Gears OS の構成</h2> +<h2 id="gears-os--4">Gears OS の構成</h2> <ul> <li>Persistent Data Tree <ul> @@ -286,7 +448,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears-os--2">Gears OS の構成</h2> +<h2 id="gears-os--5">Gears OS の構成</h2> <ul> <li>Worker <ul> @@ -305,10 +467,9 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="context">Context</h2> +<h2 id="context-3">Context</h2> <ul> <li>Context は接続可能な Code/Data Gearへの参照をもっている</li> - <li>Gears OS では必要な Code/Data Gear を参照したい場合、 Context を通す必要がある</li> <li>メインとなる Context と Worker 用 Context がある <ul> <li>TaskQueue と Persistent Data Tree はすべての Context で共有する</li> @@ -345,7 +506,7 @@ Element }; -// Data Gear definication +// Data Gear define union Data { struct Queue { struct Element* first; @@ -422,7 +583,7 @@ <li>Task が完了したら次の Task を取得する</li> </ul> -<pre lang="c"><code>// Task definication +<pre lang="c"><code>// Task define union Data { // size: 8 byte struct Task { @@ -441,7 +602,6 @@ queue->count--; context->next = GetQueue; - stack_push(context->code_stack, &context->next); context->next = first->task->code; node->key = first->task->key; @@ -532,7 +692,6 @@ loopCounter->i = 0; - stack_pop(context->code_stack, &context->next); goto meta(context, context->next); } </code></pre> @@ -596,6 +755,7 @@ <ul> <li>1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた</li> + <li>十分な台数効果が出てる事がわかる</li> </ul> @@ -610,21 +770,41 @@ <!-- _S9SLIDE_ --> <h2 id="section-4">まとめ</h2> <ul> - <li>Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li> + <li>Cerium を開発して得られた知見か らCode Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li> <li>Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li> - <li>依存関係のない Twice を用いて並列処理を行い性能を示した</li> + <li>依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-5">課題</h2> +<h2 id="section-5">今後の課題</h2> <ul> - <li>依存関係のある並列処理の例題を作成し、評価する</li> - <li>GPU への対応</li> - <li>Gears OS でのデバック手法</li> - <li>型情報の検査を Meta Computation で行う</li> + <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>
--- a/presen/sigos.md Sat May 28 18:57:36 2016 +0900 +++ b/presen/sigos.md Sun May 29 16:34:28 2016 +0900 @@ -4,33 +4,23 @@ lang: Japanese code-engine: coderay -## Gears OS -- CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている -- そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある -- マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない -- また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している -- 並列処理をする上でこれらのリソースを無視することができない -- しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる -- 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる -- 本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS のプロトタイプ設計・実装を行い、簡単な例題を用いて評価を行う +## Gears OS の並列性 +- Code Gear と Data Gear という Code と Data の単位を使って構成される +- Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能 -## Cerium -- Cerium は本研究室で開発していた並列プログラミングフレームワーク -- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする -- 依存関係を Task 間で設定する - -## Cerium の問題点 -- 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない -- Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、 汎用ポインタをキャストして利用している +## Gears OS の柔軟性 +- Gear を追加することでデータ拡張や機能の追加が可能 +- GPU などの CPU とは異なるアーキテクチャでも同じプログラムが動く +- バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う +- 実行時の処理の変更を可能とする -## Gears OS -- Gears OS は Code Gear と Data Gear によって構成される -- Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする -- Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する -- Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される -- Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する -- 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる -- Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される +## Gears OS の信頼性 +- 検証 + - モデル検査を行う + - できるだけ有限状態 + - スタックや環境など不必要に状態を入れない +- 証明 + - Code Gear と Data Gear を理論に定義 ## Gears OS での Gear - Gears OS はプログラムの単位として Gear を用いる @@ -39,11 +29,9 @@ ## Code Gear、 Data Gear - Code Gear はプログラムの処理そのものを表す -- 任意の数の Input Data Gear を参照し、 Code Gear の処理が完了すると任意の数の Output Data Gear を生成する -- Code Gear は接続された Input Data Gear 以外の Data にはアクセスしない -- Data Gear は Data そのものを表す -- int や 文字列などの Primitive Data Type が入っている -- Code Gear から参照される Data Gear を Input Data Gear、 Code Gear の処理で生成される結果を Output Data Gear を呼ぶ +- Data Gear は int や 文字列などの Data そのものを表す +- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する + <div style="text-align: center;"> <img src="./images/codeGear_dataGear.svg" alt="message" width="900"> </div> @@ -56,33 +44,168 @@ </div> ## Meta Computation -- Gears OS では通常の Computation のために実行する Computation を Meta Computation として扱う -- Meta Computation の例として並列処理の依存関係の解決、 OSが行うネットワーク管理、メモリ管理等がある -- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現する +- Gears OS の柔軟性は Meta Computation で実現 +- Meta Computation は通常の Computation のための Computation +- 並列処理の依存関係の解決、 GPUなどの別アーキテクチャでの実行のための処理など +- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現 ## Meta Gear -- Meta Code Gear は 通常の Code Gear の直後に接続され、 Meta Computation を実行する -- Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続する +- Meta Code Gear は 通常の Code Gear の直後に接続され、 Meta Computation を実行 +- Meta Computation の実行後は通常の Code Gear で指定した Code Gear へ接続 +- Meta Data Gear はMeta Computation を行うために使用する Data Gear +- Meta 部分は Normal Level からなるべく見えない <div style="text-align: center;"> <img src="./images/meta_gear.svg" alt="message" width="900"> </div> + ## Continuation based C - Gears OS の実装は本研究室で開発しているCbC(Continuation based C)を用いる - CbC は処理を Code Segment を用いて記述する事を基本とする -- そのため Gears OS の Code Gear を記述する事に適している +- Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している ## Continuation based C - Code Segment の定義は ``__code CS名`` で行う + - Code Gear も同等に定義する - Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ - C の関数呼び出しとは違い、 Code Segment では戻り値を持たないため、スタックに値を積まない - このような元の環境を持たない継続を計量継続と呼ぶ -<div style="text-align: center;"> - <img src="./images/cbc_goto.svg" alt="message" width="900"> -</div> +``` c +/* code1 define */ +__code code1(List list) { + .... + goto code2(list) +} + +/* code2 define */ +__code code2(List list) { + ... +} +``` + +## Context +- Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている +- Gear にアクセスする際は Context を経由する +- Gears OS では Worker 毎にContext を持っている + +## Context +- 実行可能な Code Gear の名前は **enum** で定義する +- Context の初期化時に名前と関数ポインタを対応付ける + +``` c +enum Code { + Code1, + Code2, + Code3, + Exit, +}; +``` + +## Context +- Context は C の構造体で表現される + +``` c +/* context define */ +struct Context { + int codeNum; + __code (**code) (struct Context*); + void* heapStart; + void* heap; + long heapLimit; + int dataNum; + union Data **data; +}; +``` + +- 実行可能な Code Gear の数を示す **CodeNum** +- 実行可能な Code Gear へのポイント **Code** +- Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit** +- Data Gear の数を示す **dataNum** +- Data Gear へのポインタ **data** + +## Data Gear の表現 +- 使用する Data Gear は C の共用体と構造体を用いた表現をする +- これを元に Gears OS は 必要な Data Gear を allocate する +``` c +/* data Gear define */ +union Data { + struct Time { + enum Code next; + double time; + } time; + struct LoopCounter { + int i; + } loopCounter; + .... +}; +``` + +## Code Gear の stub +- 通常 Data Gear にアクセスするにはContext を経由しなければならない +- しかし、通常の Code Gear ではMeta Code Gear である Context をあまり参照したくない +- そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する +- stub は一種の Meta Code Gear である + +``` 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); +} +``` + + +## CbC の Gears OS サポート +- 通常の goto の継続では Meta Code Gear への継続が見えてしまう +- Code Gear の指定も 一度 Meta を挟む必要があるので enum を指定することで行っている + +``` c +__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 code1_stub(struct Context* context) { + goto code1(context, &context->data[Node]->node.value->array); +} +``` + +## CbC の Gears OS サポート +- Meta Code Gear への接続を自動的に行う構文サポートを行う +- stub の自動生成も行う + +``` c +__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) { + ... +} +``` ## Gears OS の構成 - Context @@ -121,7 +244,6 @@ ## Context - Context は接続可能な Code/Data Gearへの参照をもっている -- Gears OS では必要な Code/Data Gear を参照したい場合、 Context を通す必要がある - メインとなる Context と Worker 用 Context がある - TaskQueue と Persistent Data Tree はすべての Context で共有する - Worker 毎に作られる Temporal Data Gear のメモリ空間は Context 毎に異なる @@ -146,7 +268,7 @@ Element }; -// Data Gear definication +// Data Gear define union Data { struct Queue { struct Element* first; @@ -183,16 +305,7 @@ ## Persistent Data Tree - Persistent Data Tree は Data Gear の管理を行う - TaskQueue と同じですべての Context で共有される -- 一度破壊した木構造を破壊すること無く新しい木構造を構築するため、変更して読み書き可能 -- 非破壊木構造はルートから変更したいノードへのパスすべてをコピーし、パズ上に存在しないノードはコピー元の木構造と共有する - -<div style="text-align: center;"> - <img src="./images/persistent_date_tree.svg" alt="message" width="750"> -</div> - -## Persistent Data Tree -- 木構造を構築するとき最悪なケースでは事実上の線形リストになる -- そのため、挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ +- 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ ## Worker - Worker は TaskQueue から Task を取得して実行する @@ -201,7 +314,7 @@ - Task が完了したら次の Task を取得する ``` c -// Task definication +// Task define union Data { // size: 8 byte struct Task { @@ -221,7 +334,6 @@ queue->count--; context->next = GetQueue; - stack_push(context->code_stack, &context->next); context->next = first->task->code; node->key = first->task->key; @@ -290,7 +402,6 @@ loopCounter->i = 0; - stack_pop(context->code_stack, &context->next); goto meta(context, context->next); } ``` @@ -340,16 +451,29 @@ </div> - 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた +- 十分な台数効果が出てる事がわかる -## 比較 +## Cerium との比較 +- Cerium は本研究室で開発していた並列プログラミングフレームワークである。 +- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。 +- Gears OS の Task は + ## まとめ - Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った - Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った -- 依存関係のない Twice を用いて並列処理を行い性能を示した +- 依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した -## 課題 -- 依存関係のある並列処理の例題を作成し、評価する -- GPU への対応 +## 今後の課題 +- 一般的に並列処理には依存関係が存在する + - 複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する +- GPUなどの他のプロセッサ演算に利用することが出来ない + - Data Gear などのデータをGPUにマッピングするための機構が必要 - Gears OS でのデバック手法 -- 型情報の検査を Meta Computation で行う + - 軽量継続はスタックを積まないため、スタックトレースが見えない + - Context から Data Gear を取得できるため、そこから現在の状況を把握することができる + - Context を見ることができる コードを Meta Computation として入れることで Code Gear を止めて、 Data Gear の状態を見ることができる + - しかし、 Gears OS は並列実行を基本とするため、 並列で動いているCode Gear に対しては綺麗にデバック出来ない + - 並列処理でのデバック手法も考案する必要がある +- 型情報の検査 + - プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する
--- a/sigos.mm Sat May 28 18:57:36 2016 +0900 +++ b/sigos.mm Sun May 29 16:34:28 2016 +0900 @@ -82,5 +82,111 @@ <node CREATED="1464423975183" ID="ID_1777784060" MODIFIED="1464423977105" TEXT="評価"/> <node CREATED="1464423978224" ID="ID_1029156077" MODIFIED="1464423980762" TEXT="今後の課題"/> </node> +<node CREATED="1464432833136" ID="ID_470663877" MODIFIED="1464432840853" POSITION="left" TEXT="修正"> +<node CREATED="1464432842046" ID="ID_1983987511" MODIFIED="1464432848326" TEXT="研究目的"> +<node CREATED="1464432848326" ID="ID_364905917" MODIFIED="1464432856028" TEXT="並列 "> +<node CREATED="1464432866718" ID="ID_1196580896" MODIFIED="1464432875424" TEXT="CodeとDataの単位毎に並列"/> +</node> +<node CREATED="1464432856315" ID="ID_1334097915" MODIFIED="1464432860386" TEXT="柔軟性"> +<node CREATED="1464432878880" ID="ID_252983780" MODIFIED="1464432889032" TEXT="いろんな柔軟性"> +<node CREATED="1464432897863" ID="ID_916591592" MODIFIED="1464432902966" TEXT="テクノロジーマッピング"> +<node CREATED="1464432908806" ID="ID_824969951" MODIFIED="1464432916941" TEXT="異なるアーキテクチャでも同じプログラムが動く"/> +</node> +<node CREATED="1464432924107" ID="ID_833483745" MODIFIED="1464432929190" TEXT="異なるversionの混在"> +<node CREATED="1464432932148" ID="ID_740305121" MODIFIED="1464432936676" TEXT="特にネットワーク接続"/> +</node> +<node CREATED="1464432957020" ID="ID_636970555" MODIFIED="1464432961452" TEXT="プログラムの変更"/> +<node CREATED="1464432979855" ID="ID_1778076535" MODIFIED="1464432984898" TEXT="実行時の変更"/> +</node> +</node> +<node CREATED="1464432860766" ID="ID_1355016039" MODIFIED="1464433031671" TEXT="信頼性"> +<node CREATED="1464432989376" ID="ID_1254636196" MODIFIED="1464432996179" TEXT="検証"> +<node CREATED="1464432997568" ID="ID_515833313" MODIFIED="1464433000809" TEXT="モデル検査を使う"> +<node CREATED="1464433005779" ID="ID_548893933" MODIFIED="1464433009796" TEXT="できるだけ有限状態"/> +<node CREATED="1464433013043" ID="ID_1702758027" MODIFIED="1464433018498" TEXT="不必要に状態を入れない"> +<node CREATED="1464433019769" ID="ID_147579656" MODIFIED="1464433026144" TEXT="特に環境とかスタック"/> +</node> +</node> +</node> +<node CREATED="1464433032106" ID="ID_1163520693" MODIFIED="1464433034513" TEXT="証明"> +<node CREATED="1464433038681" ID="ID_1903319486" MODIFIED="1464433048944" TEXT="Code と Dataを理論に定義"/> +</node> +</node> +</node> +<node CREATED="1464433060055" ID="ID_160981626" MODIFIED="1464433064591" TEXT="Gears のアプローチ"> +<node CREATED="1464433065885" ID="ID_181737657" MODIFIED="1464433083653" TEXT="並列実行はInput が揃った CG から実行"/> +<node CREATED="1464433095134" ID="ID_1902548270" MODIFIED="1464433113565" TEXT="Worker 自体もGears で記述"/> +<node CREATED="1464433123669" ID="ID_985948767" MODIFIED="1464433129459" TEXT="柔軟性はmeta computation で実現"> +<node CREATED="1464433150410" ID="ID_1817582445" MODIFIED="1464433178425" TEXT="CGの継続の間にmeta CGを挟む"/> +<node CREATED="1464433181016" ID="ID_1604650295" MODIFIED="1464433189503" TEXT="DS に meta DS を追加"/> +<node CREATED="1464433196240" ID="ID_59209401" MODIFIED="1464433208000" TEXT="meta 部分は Normal leve からなるべく見えない"/> +</node> +<node CREATED="1464433230340" ID="ID_990233636" MODIFIED="1464433239886" TEXT="Gears の実行Context"> +<node CREATED="1464433242101" ID="ID_1461397474" MODIFIED="1464433256112" TEXT="実行されるすべてのDS"/> +<node CREATED="1464433256949" ID="ID_1562417638" MODIFIED="1464433262957" TEXT="すべてのCS"/> +<node CREATED="1464433268468" ID="ID_1357583690" MODIFIED="1464433281652" TEXT="それらを結びつけるMDS,MCS"/> +</node> +<node CREATED="1464433294904" ID="ID_1418757401" MODIFIED="1464433296724" TEXT="CbC"> +<node CREATED="1464433299944" ID="ID_1452816780" MODIFIED="1464433312435" TEXT="Cのtail call version"/> +<node CREATED="1464433319489" ID="ID_430937148" MODIFIED="1464433327461" TEXT="meta 部分を隠す構文サポート"/> +</node> +<node CREATED="1464433348594" ID="ID_506423800" MODIFIED="1464433355520" TEXT="有限状態遷移の記述"> +<node CREATED="1464433357727" ID="ID_1850570123" MODIFIED="1464433360008" TEXT="Gear Box"> +<node CREATED="1464433362630" ID="ID_807557934" MODIFIED="1464433370833" TEXT="state chart"/> +<node CREATED="1464433373575" ID="ID_453284389" MODIFIED="1464433380191" TEXT="状態間を結ぶDG"/> +</node> +</node> +<node CREATED="1464433416173" ID="ID_396737367" MODIFIED="1464433417927" TEXT="実装"> +<node CREATED="1464433423308" ID="ID_1702142469" MODIFIED="1464433431550" TEXT="OSX 上のマルチスレッドworker"/> +<node CREATED="1464433438458" ID="ID_866863090" MODIFIED="1464433450964" TEXT="context は手書きな巨大なunion"/> +<node CREATED="1464433459685" ID="ID_1501887204" MODIFIED="1464433469755" TEXT="red black tree をつかったpersitent data gear"/> +<node CREATED="1464433472153" ID="ID_1289317838" MODIFIED="1464433501262" TEXT="有限状態幾何的なsynchronized queue"/> +</node> +</node> +<node CREATED="1464433526194" ID="ID_1694664580" MODIFIED="1464433537985" TEXT="Gears OS プロトタイプの詳細"> +<node CREATED="1464433539999" ID="ID_1486726647" MODIFIED="1464433542119" TEXT="全体構成"> +<node CREATED="1464433545327" ID="ID_1248461308" MODIFIED="1464433551583" TEXT="context"> +<node CREATED="1464433590773" ID="ID_1581705994" MODIFIED="1464433597242" TEXT="実行の様子"/> +</node> +<node CREATED="1464433552006" ID="ID_1194746624" MODIFIED="1464433553391" TEXT="worker"/> +<node CREATED="1464433553631" ID="ID_269109589" MODIFIED="1464433557488" TEXT="synchronized queue"/> +<node CREATED="1464433557819" ID="ID_928959023" MODIFIED="1464433561695" TEXT="red black tree"/> +<node CREATED="1464433562016" ID="ID_978814003" MODIFIED="1464433567518" TEXT="task manager"/> +</node> +</node> +<node CREATED="1464433603258" ID="ID_915464781" MODIFIED="1464433606173" TEXT="比較"> +<node CREATED="1464433628753" ID="ID_1792167946" MODIFIED="1464433634051" TEXT="Cerium"/> +<node CREATED="1464433644124" ID="ID_1978156315" MODIFIED="1464433657426" TEXT="既存のUnix OS"> +<node CREATED="1464433668985" ID="ID_1254303748" MODIFIED="1464433670841" TEXT="Linux"/> +</node> +<node CREATED="1464433659705" ID="ID_1192298961" MODIFIED="1464433663930" TEXT="組み込み OS"> +<node CREATED="1464433673666" ID="ID_1090022093" MODIFIED="1464433677313" TEXT="itron"/> +<node CREATED="1464433684418" ID="ID_1270208101" MODIFIED="1464433686409" TEXT="vxmax"/> +</node> +<node CREATED="1464433704565" ID="ID_95607994" MODIFIED="1464433708824" TEXT="micro kernel os"/> +</node> +<node CREATED="1464433618477" ID="ID_1600905308" MODIFIED="1464433621920" TEXT="まとめ、課題"> +<node CREATED="1464433740836" ID="ID_1449910541" MODIFIED="1464433753301" TEXT="  クリーンナップ"> +<node CREATED="1464433753742" ID="ID_1610227753" MODIFIED="1464433760958" TEXT="meta と normal の切り分け"> +<node CREATED="1464433764741" ID="ID_1639200751" MODIFIED="1464433769118" TEXT="特に構文的な切り替え"/> +</node> +<node CREATED="1464433774641" ID="ID_1756649286" MODIFIED="1464433787485" TEXT="不要なstack_push, pop"/> +</node> +<node CREATED="1464433793850" ID="ID_1527710141" MODIFIED="1464433795116" TEXT="GPU"/> +<node CREATED="1464433796033" ID="ID_771561797" MODIFIED="1464433815987" TEXT="依存関係"/> +<node CREATED="1464433799820" ID="ID_604700760" MODIFIED="1464433811276" TEXT="Context の動的生成"> +<node CREATED="1464433818282" ID="ID_1473851385" MODIFIED="1464433823203" TEXT="Runtime を作る"/> +</node> +<node CREATED="1464433833572" ID="ID_1406524402" MODIFIED="1464433838025" TEXT="Persistent store"> +<node CREATED="1464433839273" ID="ID_585114386" MODIFIED="1464433852344" TEXT="RBTree を別ストレージに移す機能"> +<node CREATED="1464433857245" ID="ID_89430560" MODIFIED="1464433861009" TEXT="IOが必要"/> +</node> +</node> +<node CREATED="1464433870637" ID="ID_8559213" MODIFIED="1464433876129" TEXT="プロセス"> +<node CREATED="1464433877985" ID="ID_944176938" MODIFIED="1464433898047" TEXT="現状ではDSは全部同じメモリ空間上にあるのでそれを別空間にする"/> +</node> +<node CREATED="1464433916620" ID="ID_186762386" MODIFIED="1464433920646" TEXT="検証系"/> +</node> +</node> </node> </map>