Mercurial > hg > Papers > 2015 > kkb-sigos
changeset 17:dfd4f1eb8882
commit
| author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2015 16:22:34 +0900 |
| parents | 99329dbc5e00 |
| children | 9159562b324c |
| files | Gears OS.mm paper/sigos.pdf presen/index.html |
| diffstat | 3 files changed, 398 insertions(+), 108 deletions(-) [+] |
line wrap: on
line diff
--- a/Gears OS.mm Mon May 25 02:37:02 2015 +0900 +++ b/Gears OS.mm Mon May 25 16:22:34 2015 +0900 @@ -70,5 +70,87 @@ <node CREATED="1430479676724" ID="ID_1992721974" MODIFIED="1430479700307" TEXT="node js"/> </node> </node> +<node CREATED="1432462187555" ID="ID_217972086" MODIFIED="1432462192906" POSITION="left" TEXT="presen"> +<node CREATED="1432462202226" ID="ID_152640162" MODIFIED="1432462205033" TEXT="目的"> +<node CREATED="1432462210569" ID="ID_543183455" MODIFIED="1432462223338" TEXT="様々なアーキテクチャに対応する"/> +<node CREATED="1432462223992" ID="ID_117989368" MODIFIED="1432462225842" TEXT="信頼性"> +<node CREATED="1432462226483" ID="ID_1564600924" MODIFIED="1432462236944" TEXT="model checking"/> +<node CREATED="1432462238566" ID="ID_1334653108" MODIFIED="1432462238566" TEXT=""/> +</node> +<node CREATED="1432462241599" ID="ID_864685123" MODIFIED="1432462245059" TEXT="柔軟性"> +<node CREATED="1432462245060" ID="ID_362059801" MODIFIED="1432462247983" TEXT="open system"/> +</node> +</node> +<node CREATED="1432462255239" ID="ID_1283001614" MODIFIED="1432462261681" TEXT="いままでやってきたこと"> +<node CREATED="1432462262001" ID="ID_221183482" MODIFIED="1432462267104" TEXT="Cerium"> +<node CREATED="1432462275565" ID="ID_378050683" MODIFIED="1432462280545" TEXT="依存関係"/> +<node CREATED="1432462295269" ID="ID_1445754486" MODIFIED="1432462302980" TEXT="型検査できない"/> +</node> +<node CREATED="1432462267583" ID="ID_1013298206" MODIFIED="1432462269080" TEXT="Alice"> +<node CREATED="1432462327516" ID="ID_1168573736" MODIFIED="1432462334516" TEXT="code segment, data segment"/> +<node CREATED="1432462335036" ID="ID_237592460" MODIFIED="1432462360715" TEXT="meta computation"> +<node CREATED="1432462535566" ID="ID_1851614386" MODIFIED="1432462535566" TEXT=""/> +</node> +<node CREATED="1432462369725" ID="ID_1048942223" MODIFIED="1432462380806" TEXT="設計がダメ"> +<node CREATED="1432462381190" ID="ID_1926371723" MODIFIED="1432462402677" TEXT="meta computation が alice で書かれてない"/> +<node CREATED="1432462403244" ID="ID_1265810001" MODIFIED="1432462403244" TEXT=""/> +</node> +</node> +</node> +<node CREATED="1432462469564" ID="ID_1349007743" MODIFIED="1432462479937" TEXT="gears の設計方針"> +<node CREATED="1432462652638" ID="ID_1470161465" MODIFIED="1432462669627" TEXT="code/data segment"/> +<node CREATED="1432462503835" ID="ID_955641489" MODIFIED="1432462549828" TEXT="meta computaion は moanad"/> +<node CREATED="1432462552638" ID="ID_1265853574" MODIFIED="1432462584164" TEXT="monad を meta code/data gear で表現する"/> +<node CREATED="1432462588464" ID="ID_68838938" MODIFIED="1432462673491" TEXT="cbc"> +<node CREATED="1432462673821" ID="ID_764648865" MODIFIED="1432462675530" TEXT="llvm"/> +</node> +<node CREATED="1432462488380" ID="ID_804017415" MODIFIED="1432462717343" TEXT="object レベルではポインタを扱わない"> +<node CREATED="1432462717612" ID="ID_1091211404" MODIFIED="1432462726131" TEXT="code/data gear"/> +</node> +<node CREATED="1432462655458" ID="ID_339781281" MODIFIED="1432462737629" TEXT="meta レベルでポインタを"> +<node CREATED="1432462738110" ID="ID_1857151017" MODIFIED="1432462748436" TEXT="meta code/data gear"/> +<node CREATED="1432462751273" ID="ID_10957770" MODIFIED="1432462751273" TEXT=""/> +</node> +<node CREATED="1432462790573" ID="ID_1719490880" MODIFIED="1432462790573" TEXT=""/> +</node> +<node CREATED="1432462765976" ID="ID_1663093882" MODIFIED="1432462770981" TEXT="gears のアーキテクチャ"> +<node CREATED="1432462773702" ID="ID_1082409470" MODIFIED="1432462783236" TEXT="アーキテクチャの図"> +<node CREATED="1432462807825" ID="ID_589465323" MODIFIED="1432462825339" TEXT="persistent tree から data を読み込む"/> +<node CREATED="1432462827880" ID="ID_1664113676" MODIFIED="1432462849412" TEXT="code を実行する worker"/> +<node CREATED="1432462849817" ID="ID_277111991" MODIFIED="1432462890658" TEXT="worker 間を結ぶ sysnchronized queue"/> +<node CREATED="1432462896655" ID="ID_1772883162" MODIFIED="1432462937090" TEXT="context"> +<node CREATED="1432462937500" ID="ID_944372429" MODIFIED="1432462950691" TEXT="data segmet のsigunture"/> +<node CREATED="1432462950994" ID="ID_1426616123" MODIFIED="1432462959908" TEXT="code segment の 一覧"/> +</node> +</node> +</node> +<node CREATED="1432462996382" ID="ID_1696934405" MODIFIED="1432463001490" TEXT="gears の構成要素"> +<node CREATED="1432463009290" ID="ID_649106530" MODIFIED="1432463010746" TEXT="context"/> +<node CREATED="1432463025831" ID="ID_1819686668" MODIFIED="1432463030167" TEXT="red black tree"/> +<node CREATED="1432463030632" ID="ID_1862618257" MODIFIED="1432463098436" TEXT="worke"> +<node CREATED="1432463083527" ID="ID_151541875" MODIFIED="1432463089806" TEXT="syscrhonized queue"> +<node CREATED="1432463090555" ID="ID_406059206" MODIFIED="1432463092614" TEXT="gear box"/> +</node> +</node> +</node> +<node CREATED="1432463110357" ID="ID_1751226582" MODIFIED="1432463255497" TEXT="cbc による実装"> +<node CREATED="1432463120390" ID="ID_773590568" MODIFIED="1432463142817" TEXT="context"/> +<node CREATED="1432463163473" ID="ID_1004753545" MODIFIED="1432463171945" TEXT="code segment"> +<node CREATED="1432463172473" ID="ID_1993287652" MODIFIED="1432463174483" TEXT="理想"/> +<node CREATED="1432463175167" ID="ID_1356879450" MODIFIED="1432463176818" TEXT="実際"/> +</node> +<node CREATED="1432463179052" ID="ID_1329394086" MODIFIED="1432463202993" TEXT="data segment"/> +</node> +<node CREATED="1432463256069" ID="ID_997477641" MODIFIED="1432463258413" TEXT="これから"> +<node CREATED="1432463259673" ID="ID_1563609239" MODIFIED="1432463293922" TEXT="比較"> +<node CREATED="1432463294191" ID="ID_380660560" MODIFIED="1432463295888" TEXT="cerium"/> +<node CREATED="1432463296478" ID="ID_1054858327" MODIFIED="1432463297577" TEXT="alice"/> +<node CREATED="1432463298679" ID="ID_1982541054" MODIFIED="1432463303545" TEXT="opencl"/> +<node CREATED="1432463303786" ID="ID_576953825" MODIFIED="1432463304553" TEXT="cuda"/> +</node> +<node CREATED="1432463312946" ID="ID_1071238929" MODIFIED="1432463341252" TEXT="まとめ"/> +</node> +</node> +<node CREATED="1432462253109" ID="ID_574856930" MODIFIED="1432462253109" POSITION="left" TEXT=""/> </node> </map>
--- a/presen/index.html Mon May 25 02:37:02 2015 +0900 +++ b/presen/index.html Mon May 25 16:22:34 2015 +0900 @@ -30,18 +30,40 @@ <div class="slide" id="2"><div> <section> <header> - <h1 id="cerium--alice">Cerium と Alice</h1> + <h1 id="section">研究目的</h1> </header> <!-- === begin markdown block === generated by markdown 1.1.1 on Ruby 2.0.0 (2013-02-24) [x86_64-darwin12.3.0] - on 2015-05-24 16:59:22 +0900 with Markdown engine kramdown (1.4.0) + on 2015-05-25 05:40:40 +0900 with Markdown engine kramdown (1.4.0) using options {} --> <!-- _S9SLIDE_ --> -<p>本研究室では並列プログラミングフレームワーク Cerium と分散ネットフレームワーク Alice の開発を行なってきた</p> +<p>Many Core CPU, GPU, SpursEngine などの異なる演算資源を有効に利用するためには、それぞれのアーキテクチャに合わせた記述が必要になる。 +Gears OS は Many Core CPU, GPU といった並列環境に合わせた設計・開発を行う</p> + +<p>Gears OS では Gear という単位を用いて記述することで柔軟性のあるプログラムを作成することを可能とする。 +新たな Gear を接続することでデータの拡張や機能の追加を行うことができる</p> + +<p>並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。 +並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。 +これにより、デッドロック等を検出することで信頼性を確保する</p> + + + + </section> +</div></div> + +<div class="slide" id="3"><div> + <section> + <header> + <h1 id="cerium--alice">Cerium と Alice</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>先行研究として、本研究室では並列プログラミングフレームワーク Cerium と分散ネットフレームワーク Alice の開発を行なってきた</p> <p>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列処理を実現する。 依存関係はプログラム自身が記述する必要があり、Task の種類が増えるほど記述が繁雑になる。 @@ -55,36 +77,22 @@ </section> </div></div> -<div class="slide" id="3"><div> +<div class="slide" id="4"><div> <section> <header> <h1 id="cerium--alice-1">Cerium と Alice</h1> </header> <!-- _S9SLIDE_ --> -<p>Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラムを記述する。 +<p>Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラミングを行う。 Code Segment が取り扱う Input/Output Data Segment を指定することで処理とデータの関係を決定する</p> +<p>Alice では Computaion を Data Segment を待ち合わせて Code Segment を実行することと定義している。 +これに対し、Meta Computation は Computation を実現する Computation と定義することができる。 +通信中の切断や再接続の処理などは Meta Computation に相当する</p> + <p>Data Segment にアクセスする API が設計上の問題で複雑化している。 -また、Java で実装されており、実行速度が遅いという問題がある</p> - - - - </section> -</div></div> - -<div class="slide" id="4"><div> - <section> - <header> - <h1 id="gears-os">Gears OS</h1> - </header> - <!-- _S9SLIDE_ --> - -<p>本研究では Cerium と Alice を開発して得られた知見から並列分散フレームワーク Gears OS の設計・開発を行う</p> - -<p>Gears OS では Alice の Code/Data Segment に相当する Code/Data Gear という単位を用いてプログラムを細かく分割する。 -Code Gear は Input Data Gear から Output Data Gear を生成する。 -Input/Output Data Gear の関係から Code Gear 間の依存関係を決定し、並列・分散処理を行う</p> +また、Meta Computation 自体が Alice で記述されていない</p> @@ -94,48 +102,7 @@ <div class="slide" id="5"><div> <section> <header> - <h1 id="gears-os-1">Gears OS</h1> - </header> - <!-- _S9SLIDE_ --> - -<p>従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。 -関数型言語では Meta Computation に Monad を用いる手法があり、Gears OS では Code/Data Gear を Monad として定義して Meta Computation を実現する</p> - -<p>並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。 -並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。 -これにより、デッドロック等を検出することで信頼性を確保する</p> - - - - </section> -</div></div> - -<div class="slide" id="6"><div> - <section> - <header> - <h1 id="features">Features</h1> - </header> - <!-- _S9SLIDE_ --> - -<p>Inherent Parallel</p> - -<p>Distributed Open Computation</p> - -<p>Reliablity </p> - -<p> Separated Data Segment </p> - -<p> Model Checking</p> - - - - </section> -</div></div> - -<div class="slide" id="7"><div> - <section> - <header> - <h1 id="codedata-gear">Code/Data Gear</h1> + <h1 id="code-gear--data-gear">Code Gear と Data Gear</h1> </header> <!-- _S9SLIDE_ --> @@ -146,6 +113,52 @@ 接続された複数の Input Data Gear を参照し、単一または複数の Output Data Gear に書き込む。 Code Gear では接続された Data Gear のみに干渉することができる</p> +<p>Data Gear には、Primitive Data Type が格納される。 +直接ポインタを扱うことはなく、自分が知らない Code/Data Gear は名前で指し示す</p> + +<p>Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。 +これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする</p> + + + + </section> +</div></div> + +<div class="slide" id="6"><div> + <section> + <header> + <h1 id="monad--meta-computation">Monad と Meta Computation</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるものがある。 +メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副作用、メモリ管理などがある。 +メタ計算の理論的な表現として Monad を用いることが Moggi らにより提案されている</p> + +<p>Moand は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するのに必要な情報を格納している。 +失敗する計算の場合は、計算が失敗したかどうかのフラグが Monad に含まれる。 +通常の計算を Monad を返すように変更することでメタ関数が得られる。 +逆に Monad の中にある通常の値のみに着目すると通常の関数となる</p> + + + + </section> +</div></div> + +<div class="slide" id="7"><div> + <section> + <header> + <h1 id="gears-os--meta-computation">Gears OS における Meta Computation</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>Gears OS では Code/Data Gear に Meta Code/Data Gear を付属することで Monad を表現する。 +Meta Code/Data Gear は Code/Data Gear へのポインタを持っている。 +各 Gear の関連付けは Meta Gear を用いて行われる</p> + +<p>オブジェクトレベルである Gear ではポインタを扱わず、メタレベルである Meta Gear でのみポインタを扱う。 +これにより、ポインタ関連のセキュリティフローを防止する。</p> + </section> @@ -154,14 +167,16 @@ <div class="slide" id="8"><div> <section> <header> - <h1 id="code-data-gear">Code Data Gear</h1> + <h1 id="section-1">実装言語</h1> </header> <!-- _S9SLIDE_ --> -<p>Code/Data Gear ではポインタを直接には扱わず、Code と Data の分離性を上げることで、ポインタ関連のセキュリティフローを防止する</p> +<p>Gears OS の実装には、本研究室で開発している Continuation based C(CbC) を用いる</p> -<p>Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。 -これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。</p> +<p>CbC ではプログラムを Code Segment, Data Segment という単位で記述する。 +Code Segment 間の処理の移動には関数呼び出しではなく、goto を用いた軽量継続を用いている</p> + +<p>CbC のコンパイルには LLVM をバックエンドとしたコンパイラを用いる</p> @@ -171,11 +186,16 @@ <div class="slide" id="9"><div> <section> <header> - <h1 id="list">list</h1> + <h1 id="gears-os-">Gears OS の構成</h1> </header> <!-- _S9SLIDE_ --> -<p><img src="pictures/List.jpg" alt="List" title="List" style="width: 80%;" /></p> +<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p> + +<p>Gears OS では Context を生成し、Worker を起動する。 +Worker は Synchronized Queue から Code Gear を取得し、実行する。 +実行に必要な Data Gear は Context を通して、Persistent Data Gear から読み込みを行う。 +処理が終わると必要な Data Gear を Persistent Data Gear に書き込みを行う</p> @@ -185,27 +205,15 @@ <div class="slide" id="10"><div> <section> <header> - <h1 id="singly-linked-list-">singly linked list の実装</h1> + <h1 id="code-gear-">Code Gear の継続</h1> </header> <!-- _S9SLIDE_ --> -<ul> - <li>Context - <ul> - <li>list の先頭を示す head</li> - </ul> - </li> - <li>DataSegment - <ul> - <li>任意</li> - </ul> - </li> - <li>MetaDataSegment - <ul> - <li>次の mds を示す next</li> - </ul> - </li> -</ul> +<p>Code Gear では、次に実行する Code Gear を名前で指定する。 +Meta Code Gear が名前を解釈して、対応する Code Gear に引き渡す。 +Gear OS では、この Meta Code Gear を Context と定義する</p> + +<p>Context には Code Gear の名前とポインタの対応表、Data Gear の Allocation 用の情報、Code Gear が参照する Data Gear へのポインタ、Data Gear に格納される Data Type の情報が格納されている</p> @@ -215,27 +223,227 @@ <div class="slide" id="11"><div> <section> <header> - <h1 id="section">操作</h1> + <h1 id="persistent-data-gear">Persistent Data Gear</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>Data Gear の管理には木構造を用いる。 +この木構造は非破壊で構成される。 +非破壊的木構造では、ロックなしに平行して読み書き・参照を行うことが可能である</p> + +<p>変更前の木構造をすべて保持しているので過去のデータにアクセスすることもできる</p> + + + + </section> +</div></div> + +<div class="slide" id="12"><div> + <section> + <header> + <h1 id="list">List</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>通常 List は要素と次へのポインタを持つ構造体で表現される</p> + +<p>Gears OS の場合、オブジェクトレベルではポインタを扱わないので、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される</p> + +<p><img src="pictures/List.svg" alt="List" style="width: 70%" /></p> + + + + </section> +</div></div> + +<div class="slide" id="13"><div> + <section> + <header> + <h1 id="synchronized-queue">Synchronized Queue</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する</p> + +<p>Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する。 +M:receiver/sender が CAS を行う Meta Code Gear となる</p> + +<p><img src="pictures/synchronizedQueue.svg" alt="sync" style="width: 80%" /></p> + + + + </section> +</div></div> + +<div class="slide" id="14"><div> + <section> + <header> + <h1 id="context">Context</h1> + </header> + <!-- _S9SLIDE_ --> + +<pre><code>/* Context definition */ +enum Code { + Code1, + Code2, + Allocator, +}; + +enum UniqueData { + Allocate, + Tree, +}; + +struct Context { + int codeNum; + __code (**code) (struct Context *); + void* heap_start; + void* heap; + long dataSize; + int dataNum; + union Data **data; +}; +</code></pre> + + + + </section> +</div></div> + +<div class="slide" id="15"><div> + <section> + <header> + <h1 id="code-gear">Code Gear</h1> </header> <!-- _S9SLIDE_ --> -<ul> - <li>append - <ul> - <li>head から探索して末尾に新たな DS を追加</li> - </ul> - </li> - <li>delete - <ul> - <li>head を next に変更</li> - </ul> - </li> - <li>traverse - <ul> - <li>list を先頭から表示</li> - </ul> - </li> -</ul> +<pre><code>// Code Gear +__code code1(Allocate allocate) { + allocate.size = sizeof(long); + allocate.next = Code2; + goto Allocate(allocate); // goes through meta +} + +// Meta Code Gear +__code meta(struct Context* context, enum Code next) { + // meta computation + goto (context->code[next])(context); +} + +// Meta Code Gear +__code allocate(struct Context* context) { + context->data[++context->dataNum] = context->heap; + context->heap += context->data[Allocate]->allocate.size; + goto (context->code[context->data[Allocate]->allocate.next])(context); +} + +// Code Gear +__code code2(Allocate allocate, Count count) { + // processing +} +</code></pre> + +<pre><code>// Code Gear +__code code1(struct Context* context) { + context->data[Allocate]->allocate.size = sizeof(struct Node); + context->data[Allocate]->allocate.next = Code2; + goto meta(context, Allocate); +} + +// Meta Code Gear +__code meta(struct Context* context, enum Code next) { + // meta computation + goto (context->code[next])(context); +} + +// Meta Code Gear +__code allocate(struct Context* context) { + context->data[++context->dataNum] = context->heap; + context->heap += context->data[Allocate]->allocate.size; + goto (context->code[context->data[Allocate]->allocate.next])(context); +} + +// Code Gear +__code code2(struct Context* context) { + // processing content +} +</code></pre> + + + + </section> +</div></div> + +<div class="slide" id="16"><div> + <section> + <header> + <h1 id="data-gear">Data Gear</h1> + </header> + <!-- _S9SLIDE_ --> + +<pre><code>union Data { + struct Tree { + union Data* root; + union Data* current; + union Data* prev; + int result; + } tree; + struct Node { + int key; + int value; + enum Color { + Red, + Black, + } color; + union Data* left; + union Data* right; + } node; + struct Allocate { + long size; + enum Code next; + } allocate; +}; +</code></pre> + + + + </section> +</div></div> + +<div class="slide" id="17"><div> + <section> + <header> + <h1 id="section-2">比較</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>Code Gear は Cerium の Task、Alice の Code Segment, OpenCL/CUDA の kernel に相当する</p> + +<p>Data Gear は Alice の Data Segment に相当する。 +Ceirum, OpenCL/CUDA には Data Gear に相当する物は存在しない</p> + +<p>Cerium, OpenCL/CUDA では処理同士の依存関係を記述する必要があるが、Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する</p> + + + + </section> +</div></div> + +<div class="slide" id="18"><div> + <section> + <header> + <h1 id="section-3">まとめ</h1> + </header> + <!-- _S9SLIDE_ --> + +<p>Gears OS では処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった</p> + +<p>Gear という単位を用いて記述することでプログラムを柔軟に変更することを可能とした</p> + +<p>Meta Computation を Moand に基づいて実現する。 +Gears OS では Meta Code/Data Gear を用いて Monad を表現する</p> + +<p>機能として Model Checking を提供し、プログラムの信頼性を確保する</p> <!-- === end markdown block === --> </section>