Mercurial > hg > Papers > 2019 > mitsuki-master
changeset 59:09c168f8116a
update
| author | mir3636 |
|---|---|
| date | Wed, 13 Feb 2019 09:47:53 +0900 |
| parents | 9727ceb711b3 |
| children | ecf9d73f18f5 |
| files | paper/fig/normal_Code_Gear.pdf slide/images/normal_Code_Gear.pdf slide/slide.html slide/slide.md |
| diffstat | 4 files changed, 1015 insertions(+), 1106 deletions(-) [+] |
line wrap: on
line diff
--- a/slide/slide.html Tue Feb 12 15:19:09 2019 +0900 +++ b/slide/slide.html Wed Feb 13 09:47:53 2019 +0900 @@ -86,7 +86,7 @@ <!-- === begin markdown block === generated by markdown/1.2.0 on Ruby 2.4.0 (2016-12-24) [x86_64-darwin16] - on 2019-02-12 13:32:52 +0900 with Markdown engine kramdown (1.16.2) + on 2019-02-13 08:59:24 +0900 with Markdown engine kramdown (1.16.2) using options {} --> @@ -108,7 +108,7 @@ <ul> <li>さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。</li> <li>時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。</li> - <li>その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。</li> + <li>その信頼性を保証するには、従来のテストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。</li> </ul> @@ -116,9 +116,8 @@ <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="os--1">OS の拡張性と信頼性の両立</h2> - <ul> - <li>これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。</li> + <li>これに対処するためには、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。</li> <li>検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。</li> <li>このため信頼性と拡張性を両立させることが重要である。</li> </ul> @@ -127,7 +126,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-1">メタ計算</h2> +<h2 id="section-1">メタ計算とは</h2> <ul> <li>プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。</li> <li>メタ計算はノーマルレベルの計算から切り離して記述したい。</li> @@ -141,11 +140,11 @@ <!-- _S9SLIDE_ --> <h2 id="continuation-based-c-cbc">Continuation based C (CbC)</h2> <ul> - <li>Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。</li> - <li>Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。</li> + <li>Continuation based C (CbC) は Code Gear を処理の単位としたプログラミング言語として開発している。</li> + <li>Code Gear は 関数呼び出しとは異なり、次の Code Gear へと goto 文によって遷移する。</li> <li>この goto 文による遷移を軽量継続と呼ぶ。</li> - <li>継続によって状態遷移ベースでのプログラミングが可能。</li> - <li>C と互換性のある言語で、C の関数も呼び出すことができる。</li> + <li>継続を用いることによって状態遷移ベースでのプログラミングが可能である。</li> + <li>CbC は C と互換性のある言語なので、C の関数も呼び出すことができる。</li> </ul> @@ -154,15 +153,11 @@ <!-- _S9SLIDE_ --> <h2 id="gears-os">Gears OS</h2> <ul> - <li>Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。</li> - <li>並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。</li> - <li>Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。</li> + <li>Gears OS は Code Gear と、データの単位である Data Gear を用いて開発されており、CbC で記述されている。</li> + <li>Gears OS は Context と呼ばれる全ての Code Gear と Data Gear を持ったデータ構造体を常に持ち歩いて処理を行う。</li> + <li>必要な Code Gear、Data Gear は、この Context から取り出して処理を実行する。</li> </ul> -<div style="text-align: center;"> - <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600" /> -</div> - </div> <div class='slide '> @@ -172,7 +167,8 @@ <li>xv6 は 2006 年に MIT のオペレーティングシステムコースで教育用の目的として開発されたオペレーティングシステムである。</li> <li>xv6 は UNIX V6 を x86 向けに再実装した OS である。</li> <li>OS としての基本的な構造を持つにも関わらず、シンプルで扱いやすい。</li> - <li>継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。</li> + <li>信頼性を保証するために xv6 を CbC で書き換え、Gears OS の機能を導入したい。</li> + <li>さらに、継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。</li> </ul> @@ -199,41 +195,15 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears-">Gears でのメタ計算</h2> +<h2 id="cbc--1">CbC の継続</h2> <ul> - <li>Gears OS ではメタ計算を Meta Code/Data Gear で表現する。</li> - <li>Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。</li> - <li>Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。</li> + <li>Code Gear の継続を表す図である。</li> + <li>Code Gear 間の遷移は goto によって行われる。</li> + <li>アセンブラレベルで見ると call ではなく jmp となっている。</li> </ul> <div style="text-align: center;"> - <img src="./images/meta_Code_Gear.pdf" alt="MetaCodeGear" width="600" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="gears--1">Gears でのメタ計算</h2> -<ul> - <li>ノーマルレベルとメタレベルの処理はそれぞれ並行して存在するものではなく、 -メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、 -階層上の構造となっている。</li> - <li>この2つのレベルはプログラミング言語レベルでの変換として実現される。</li> - <li>本研究では Perl スクリプトによって実装されている。</li> -</ul> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="meta-gear">Meta Gear</h2> -<ul> - <li>Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。</li> - <li>通常の計算からはメタ計算は見ることができない。</li> -</ul> -<div style="text-align: center;"> - <img src="./images/meta_gear.pdf" alt="MetaGear" width="600" /> + <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600" /> </div> @@ -242,7 +212,7 @@ <!-- _S9SLIDE_ --> <h2 id="data-gear-">Data Gear の表現</h2> <ul> - <li>Data Gear は構造体を用いて定義する</li> + <li>Data Gear は Gears OS におけるデータの単位である。</li> <li>メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される</li> <li>Data Gear をメモリに確保する際のサイズ情報はこの型から決定する</li> </ul> @@ -266,135 +236,118 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="context">Context</h2> +<h2 id="gears-">Gears でのメタ計算</h2> <ul> - <li>Context は従来のOS のスレッドやプロセスに対応し、以下の要素をもっている Meta Data Gear - <ul> - <li>Data Gear を確保するためのメモリ空間</li> - <li>Code Gear の名前と関数ポインタとの対応表 - <ul> - <li>Code Gear は番号(enum)で指定する</li> - </ul> - </li> - <li>Code Gear が参照する Data Gear へのポインタ - <ul> - <li>Code Gear と同じく Data Gear も番号で指定する</li> - </ul> - </li> - <li>並列実行用の Task 情報</li> - <li>Data Gear の型情報</li> - </ul> - </li> - <li>Gears OS ではメタ計算で Context を経由して Code/Data Gear に番号でアクセスする</li> + <li>Gears OS ではメタ計算を Meta Code/Data Gear で表現する。</li> + <li>Meta Code Gear は通常の Code Gear の直後で遷移し、メタ計算を実行する。</li> + <li>Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。</li> +</ul> + +<div style="text-align: center;"> + <img src="./images/meta_Code_Gear.pdf" alt="MetaCodeGear" width="600" /> +</div> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="gears--1">Gears でのメタ計算</h2> +<ul> + <li>ノーマルレベルとメタレベルの処理はそれぞれ並行して存在するものではなく、 +メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、 +階層上の構造となっている。</li> + <li>この2つのレベルはプログラミング言語レベルでの変換として実現される。</li> + <li>本研究では Perl スクリプトによってノーマルレベルからメタレベルへの変換が実装されている。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="stub-code-gear">stub Code Gear</h2> +<h2 id="meta-gear">Meta Gear</h2> <ul> - <li>Data Gear にアクセスするには Context から番号を指定して行う</li> - <li>だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある</li> - <li>Gears OS では Code Gear に接続する Data Gear を メタレベルである Context から取り出す処理を行う stub Code Gear を用意している</li> + <li>Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。</li> + <li>通常の計算からはメタ計算は見ることができない。</li> </ul> - <div style="text-align: center;"> - <img src="./images/contextContinuation.svg" alt="message" width="600" /> + <img src="./images/meta_gear.pdf" alt="MetaGear" width="600" /> </div> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface">Interface</h2> +<h2 id="context">Context</h2> <ul> - <li>Gears OS を実装するに連れて、stub Code Gear の記述が煩雑になることがわかった</li> - <li>そこで、Gears OS のモジュール化する仕組みとして <strong>Interface</strong> を導入した</li> - <li>Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Data Gear</li> - <li>stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能</li> - <li>Interface を導入することで、 Stack や Queue などのデータ構造を仕様と実装に分けて記述することが出来る</li> - <li>Interface は Java のインターフェース、 Haskell の型クラスに対応する</li> + <li>Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている。</li> + <li>Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある。</li> + <li>Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface-">Interface の定義</h2> -<ul> - <li>Interface の定義には以下の内容を定義する - <ul> - <li>操作(API)の引数群の型</li> - <li>操作(API)自体のCode Gear の型</li> - </ul> - </li> +<h2 id="context-1">Context</h2> +<ul lang="c"> + <li>Context は全ての Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。</li> </ul> - -<pre lang="c"><code>typedef struct Queue<Impl>{ - // 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; +<pre lang="c"><code>enum Code { + C_popSingleLinkedStack, + C_pushSingleLinkedStack, + C_stackTest3, + C_assert3, + ... +}; +</code></pre> +<pre><code>context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub; +context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub; +context->code[C_stackTest3] = stackTest3_stub; +context->code[C_assert3] = assert3_stub; </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--1">Interface の定義</h2> -<ul> - <li><strong>__code next(…)</strong> は継続を表している</li> - <li>… は可変長引数に相当する</li> - <li>可変長引数部分には呼び出し元の Interface の Data Gear が入る</li> - <li>継続の引数で Output Data Gear を返すことが出来る</li> +<h2 id="context-2">Context</h2> +<ul lang="c"> + <li>Data Gear も Code Gear と同様に Context が全ての Data Gear のリストを持っている。</li> + <li>Data Gear のリストも enum で管理されている。</li> + <li>これは引数格納用の Data Gear の番号である。</li> </ul> - -<pre lang="c"><code>typedef struct Queue<Impl>{ - // 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; +<pre><code>enum DataType { + D_Code, + D_SingleLinkedStack, + D_Stack, + D_TaskManager, + D_Worker, + ... + }; </code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--2">Interface のインスタンスの生成</h2> -<ul> - <li>Interface は API に Code Gear を番号を入れることにより、複数の実装ヲ行うことが出来る</li> - <li>代入する Code Gear を入れ替えることで別の実装を表現する</li> - <li>Interface を表す Data Gear の生成は以下の関数で行われる</li> +<h2 id="stub-code-gear">stub Code Gear</h2> +<ul lang="c"> + <li>ノーマルレベルの Gears OS では継続先に渡す Data Gear は引数の集合に見える。</li> + <li>しかし、メタレベルで見ると、Data Gear は Context が管理しており、 +アクセスするには Context を介さなくてはならない。</li> </ul> +<pre><code>__code cg1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stackPush(stack, node); +} -<pre lang="c"><code>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; +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } </code></pre> @@ -402,17 +355,24 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--3">Interface の使い方</h2> -<ul> - <li>Interface を利用した Code Gear への継続は <code>goto interface->method</code> で行われる</li> - <li><strong>interface</strong> は Interface を表す Data Gear、 <strong>method</strong> は実装した Code Gear に対応する</li> +<h2 id="stub-code-gear-1">stub Code Gear</h2> +<ul lang="c"> + <li>このノーマルレベルとメタレベルのズレを合わせるための Meta Code Gear である +Stub Code Gear が Code Gear の間に挿入される。</li> + <li>stub Code Gear は Context から継続先の Code Gear が必要とする Data Gear を取り出す作業を行う。</li> </ul> +<pre><code>__code stackPush_stub(struct Contet* context) { + Stack* stack = &context->data[D_Stack]->Stack; + Node* node = &context->data[D_Node]->Node; + goto stackPush(context, stack, node); +} -<pre lang="c"><code>__code code1() { - Queue* queue = createSingleLinkedQueue(context); - Node* node = new Node(); - node->color = Red; - goto queue->put(node, code2); +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } </code></pre> @@ -420,53 +380,32 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--4">メタレベルでの Interface の呼び出しの詳細</h2> +<h2 id="stub-code-gear-2">stub Code Gear</h2> <ul> - <li>Interface を利用した Code Gear の継続はスクリプトによってメタレベルの記述に変換される - <ul> - <li>変換後は Context を参照するコードが生成される</li> - </ul> - </li> - <li>Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す</li> - <li>Context には Interface の引数を渡すための Data Gear が予め用意されている</li> - <li>goto meta では Interface の Code Gear の番号を Code Gear へのポインタに変換して継続を行う</li> + <li>メタレベル で見た Code Gear の引き渡し</li> </ul> - -<pre lang="c"><code>__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); -} -</code></pre> +<div style="text-align: center;"> + <img src="./images/Context_ref.pdf" alt="Context_ref" width="600" /> +</div> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--stub-code-gear">Interface での stub Code Gear</h2> -<ul> - <li>meta Code Gear では引数に指定された Code Gear の番号から stub Code Gear への関数ポインタを取り出し、 継続を行う</li> - <li>メタ計算で格納された引数は stub Code Gear で Code Gear に渡される</li> - <li>Interface を実装した Code Gear は Interface の定義から stub Code Gear の自動生成が可能</li> - <li>必要ならばメタ計算を meta Code Gear か stub Code Gear に埋め込むことができる</li> +<h2 id="goto-meta">goto meta</h2> +<ul lang="c"> + <li>Gears OS では Code Gear もリストで管理しており、継続する際には一度 __code meta へと継続する。</li> + <li>ここでノーマルレベルの Code Gear には変換が行われているが、これはコンパイル時に変換される。</li> + <li>この変換によりノーマルレベルでは隠れていた Context が見えるようになっている。</li> + <li>context に引き渡しているコードもここで生成される。</li> </ul> - -<pre lang="c"><code>// implement put code gear -__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, - union Data* data, enum Code next) { - ... +<pre><code>__code cg1(struct Context* context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + &context->data[D_Stack]->Stack = (union Data*) stack; + &context->data[D_Node]->Node = node; + goto meta(C_stackPush); } -// 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); @@ -477,181 +416,61 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-2">並列処理の構成</h2> +<h2 id="interface">Interface</h2> <ul> - <li>今回は並列処理機構である - <ul> - <li>Task - <ul> - <li>1つの Context 上で goto で遷移しながら実行される Code Gear の列</li> - </ul> - </li> - <li>TaskManager - <ul> - <li>依存関係を解決したTask を Worker SynchronizedQueue に送信する</li> - </ul> - </li> - <li>Worker - <ul> - <li>SynchronizedQueue から Task を一つずつ取得し、実行する</li> - <li>Worker 毎に POSIX Therad などを生成し、それぞれのスレッドで Code Gear を実行する</li> - </ul> - </li> - <li>SynchronizedQueue - <ul> - <li>Gears OS で記述されたマルチスレッド環境でもデータの同期処理が行われる Queue</li> - </ul> - </li> - </ul> - </li> - <li>これらを Interface として実装した</li> -</ul> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="task">Task</h2> -<ul> - <li>Gears OS では Context が並列実行の Task に相当する</li> - <li>Context は Task用の情報として以下の情報を付け加えた - <ul> - <li>実行する Code Gear</li> - <li>Input/Output Data Gear の格納場所</li> - <li>待っている Input Data Gear の数</li> - <li>この Task を実行する Worker</li> - </ul> - </li> + <li>Interface は Gears OS のモジュール化の仕組みである。</li> + <li>Interface はある Data Gear と、それに対する操作(API)を行う +Code Gear とその操作に用いる Data Gear の集合を表現する。</li> + <li>Java の Interface に対応し、定義することで複数の実装を持つことができる。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="taskmanger">TaskManger</h2> +<h2 id="interface-">Interface の定義</h2> <ul> - <li>Worker をCPU、 GPU の数分生成する</li> - <li>依存関係を解決した Task を各 Worker の Queue に送信する</li> + <li>Stack の Interface の例である。</li> + <li>typedef struct Interface 名で記述する。</li> + <li>Impl は実際に実装した際のデータ構造の型になる。</li> </ul> -<div> - <img src="./images/sendTask.svg" alt="message" style="float: left;width: 50%;" /> - <div style="float: left; width: 50%;"> - <ol> - <li value="0">Task を Input Data Gear としてTaskManager の spawn を呼び出す</li> - <li value="1">Task が待っている Data Gear のカウンタである IDGCount をチェックする</li> - <li value="2">IDGCount が0の場合 Data Gear が 揃っているので Worker の Queue に Task を送信する</li> - </ol> - </div> - <div style="clear: both;"></div> -</div> - +<pre lang="c"><code>typedef struct Stack<Impl> { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="worker">Worker</h2> -<ul> - <li>初期化時に Worker 用の Context を生成し、Code Gear を実行していく</li> - <li>TaskManager から送信された Task を一つずつ取得して実行する</li> -</ul> - -<div> - <img src="./images/workerRun.svg" alt="message" style="float: left;width: 50%;" /> - <div style="float: left; width: 50%;"> - <ol> - <li>Worker は Queue から Task(Context)を取得する</li> - <li>Worker の Context からTask の Context へ入れ替える</li> - - <li>Task に設定されている Code Gear を実行</li> - <li>Task の Output Data Gear の書き出し</li> - <li>Task Context から Worker の Context へ入れ替える</li> - <li>Worker は再び Queue から Task を取得する</li> - </ol> - </div> - <div style="clear: both;"></div> -</div> + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + +} +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="synchronized-queue">Synchronized Queue</h2> +<h2 id="interface--1">Interface の定義</h2> <ul> - <li>TaskManager と Worker 間の通信を行うための Queue</li> - <li>マルチスレッドでのデータの同期処理を行える SynchronizedQueue として実装する</li> - <li>Gears OS では 同期機構として CAS(Check and Set、 Compare and Swap) を使用した実装を行った - <ul> - <li>CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較し、変化がなければ値を更新する</li> - <li>メモリ番地の値が変わっているなら、もう一度 CAS を行う</li> - </ul> - </li> -</ul> - -<div style="text-align: center;"> - <img src="./images/synchronizedQueue.svg" alt="message" width="600" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="section-3">依存関係の解決</h2> -<ul> - <li>依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する</li> - <li>この Queue には Data Gear に依存関係がある Context が格納されている</li> + <li>Data Gear は 操作する Data Gear と +操作に必要な全ての Data Gear Gear が記述されている。</li> + <li>__code で記述されているものが操作の Code Gear である。</li> </ul> -<div> - <img src="./images/dependency.svg" alt="message" style="float: left;width: 50%;" /> - <div style="float: left; width: 50%;"> - <ol> - <li>Task に設定されている Code Gear を実行する</li> - <li>Output Data Gear の書き出し処理を行う際にメタレベルの Queue を参照する</li> - - <li>依存関係にある Task を取り出し、IDGCount をデクリメントする</li> - - </ol> - </div> - <div style="clear: both;"></div> -</div> - -<ul> - <li>IDGCountの値が0になった実行可能な Task は TaskManager を通して Worker に送信される</li> -</ul> - +<pre lang="c"><code>typedef struct Stack<Impl> { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="section-4">並列構文</h2> -<ul> - <li>並列実行する際は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する</li> - <li>この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述としては好ましくない</li> - <li>Context の設定は煩雑な記述だが、並列実行されることを除けば通常の CbC の goto 文と同等</li> - <li>そこで Context を直接参照しない並列構文、 <strong>par goto</strong> 構文を新たに考案した</li> -</ul> - + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="par-goto-">par goto 構文</h2> -<ul> - <li>par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される</li> - <li>par goto 構文には引数として Input/Output Data Gear等を渡す</li> - <li>スクリプトによって Code Gear の Input/Output の数を解析し、待っている Input Data Gear の数を設定する</li> - <li>並列実行される Task は <strong>__exit</strong> に継続することで終了する - <ul> - <li>Gears OS の Task はOutput Data Gear を書き出す処理で終了するため <strong>__exit</strong> に直接継続せずに Data Gear を書き出す処理に継続する</li> - </ul> - </li> - <li>par goto 構文は通常のプログラミングの関数呼び出しのように扱える</li> -</ul> - -<pre lang="c"><code>__code code1(Integer *integer1, Integer * integer2, Integer *output) { - par goto add(integer1, integer2, output, __exit); - goto code2(); } </code></pre> @@ -659,49 +478,101 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cuda-">CUDA への対応</h2> +<h2 id="interface--2">Interface の実装の記述</h2> +<ul lang="c"> + <li>ソースコードは Interface の実装の初期化のコードである。</li> + <li>操作の Code Gear には実装した Code Gear の番号が代入されるが、ここを入れ替えることで、複数の実装を持つことができる。</li> +</ul> +<pre><code>Stack* createSingleLinkedStack(struct Context* context) { + struct Stack* stack = new Stack(); + struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack(); + stack->stack = (union Data*)singleLinkedStack; + singleLinkedStack->top = NULL; + stack->push = C_pushSingleLinkedStack; + stack->pop = C_popSingleLinkedStack; + stack->isEmpty = C_isEmptySingleLinkedStack; + stack->clear = C_clearSingleLinkedStack; + return stack; +} +</code></pre> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="interface--3">Interface の操作の呼び出し</h2> <ul> - <li>Gears OS は GPU での実行もサポートしている</li> - <li>GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる</li> - <li>CUDA は GPU を Device、 CPU を Host として定義する</li> - <li>CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する</li> - <li>今回、CUDA に合わせた並列処理機構である CUDAWorker、 CUDAExecutor をInterface を用いて実装し、 CPU、GPU 間のデータのマッピングのために CUDABuffer を用意した</li> + <li>Interface の操作の呼び出しは、ノーマルレベルでは <code>goto interface->method</code> の形で記述される。</li> + <li>interface は Interface を表す Data Gear 、method は実装した Code Gear に対応する。</li> </ul> +<pre lang="c"><code>__code stackTest1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stack->push(node, stackTest2) +} +</code></pre> + </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cudaworker">CUDAWorker</h2> -<ul> - <li>CUDA で実行する Task を受け取る Worker</li> - <li>初期化の際に CUDA ライブラリの初期化や CUDAExecutor の生成を行う</li> +<h2 id="interface--4">Interface の操作の呼び出し</h2> +<ul lang="c"> + <li>interface の操作の呼び出しは、メタレベルでは以下のように変換される。</li> + <li>stack->push には enum の番号が入っているため、__code meta で +対応する番号の Code Gear へと継続する。</li> </ul> +<pre><code>__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cudaexecutor">CUDAExecutor</h2> -<ul> - <li>CUDAExecutor は Executor Interface を実装した Data Gear</li> - <li>以下の Code Gear を実装している - <ul> - <li>HostからDevice へのデータの送信(read)</li> - <li>kernel の実行(exec)</li> - <li>Device から Host へのデータの書き出し(write)</li> - </ul> - </li> +<h2 id="interface--5">Interface の操作の呼び出し</h2> +<ul lang="c"> + <li>ここで Gearef という記述があるが、これは Context を参照するためのマクロである。 +<code>Gearef(context, t) (&(context)->data[D_##t]->t)</code></li> + <li>格納先は Interface の型が持つ Data Gear へ格納される。</li> </ul> +<pre><code>__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +</code></pre> -<pre lang="c"><code>typedef struct Executor<Impl>{ - 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(...)); + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="interface--stub-code-gear">Interface における stub Code Gear</h2> +<ul lang="c"> + <li>Interface の情報から stub Code Gear は自動生成される。</li> + <li>引数に必要な Data Gear は Interface の型が持つ Data Gear から取り出す。</li> + <li>GearImpl は interface の操作が対象にする Data Gear を取り出すマクロである。 +<code>GearImpl(context, intf, name) (Gearef(context, intf)->name->intf.name)</code></li> +</ul> +<pre><code>__code pushSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,union Data* data, enum Code next) { + ... +} + +__code pushSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); + Data* data = Gearef(context, Stack)->data; + enum Code next = Gearef(context, Stack)->next; + goto pushSingleLinkedStack(context, stack, data, next); } </code></pre> @@ -709,204 +580,101 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="cudabuffer">CUDABuffer</h2> -<ul> - <li>Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある</li> - <li>CUDA Buffer ではそのマッピングを行う - <ul> - <li>このマッピングは Task に設定されている stub Code Gear で行われる</li> - </ul> - </li> -</ul> - -<div style="text-align: center;"> - <img src="./images/cudaDataArchitecture.svg" alt="message" width="400" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="cuda--1">CUDA での呼び出し</h2> +<h2 id="xv6--cbc--1">xv6 の CbC 書き換え</h2> <ul> - <li>Gears OS では Task に設定している Code Gear の stub Code Gear で CUDA実行を切り替える</li> - <li>CUDABuffer でのマッピング、実行する kernel の読み込みは stub Code Gear で行われる</li> - <li>CUDA で実行する際は stub Code Gear に対応する Code Gear ではなく、 CUDAExecutor の Code Gear に継続する</li> -</ul> - -<div style="text-align: center;"> - <img src="./images/gotoCUDAExecutor.svg" alt="message" width="600" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="gears-os-">Gears OS の評価</h2> -<ul> - <li>並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った</li> - <li>CPU 環境 - <ul> - <li>Model : Dell PowerEdgeR630</li> - <li>Memory : 768GB</li> - <li>CPU : 2 x 18-Core Intel Xeon 2.30GHz</li> - </ul> - </li> - <li>GPU 環境 - <ul> - <li>GPU : GeForce GTX 1070</li> - <li>Cores : 1920</li> - <li>ClockSpeed : 1683MHz</li> - <li>Memory Size : 8GB GDDR5</li> - </ul> - </li> + <li>xv6 は UNIX V6 を x86 向けに再実装した OS である。</li> + <li>プロセスや仮想メモリ、カーネルとユーザーの分離、割り込み、ファイルシステムなどの基本的な Unix の構造を持つ</li> + <li>CbC は Code Gear 間の遷移が goto による継続で行われるため、状態遷移ベースでのプログラミングに適している。</li> + <li>CbC で xv6 を書き換えることにより、状態遷移モデルによるモデル検査が可能となることを期待する。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="twice">Twice</h2> +<h2 id="xv6-">xv6 の書き換えの方針</h2> <ul> - <li>Twice は与えられた整数配列を2倍にする例題である</li> - <li>並列実行の依存関係がなく、並列度が高い課題である</li> - <li>要素数 2^27</li> - <li>CPU での実行時は要素数 2^27 を 2^6 個に分割して Task を生成する</li> - <li>GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で kernel を実行</li> + <li>xv6 を CbC で書き換え、Gears OS の機能と置き換えることで Gears OS に OS の基本構造を持たせたい。</li> + <li>このためには xv6 をモジュール化することで、xv6 の機能を明らかにする必要がある。</li> + <li>xv6 の Interface を定義し、Gears OS の機能をこれに合わせることによって実現したい。</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="section-2">システムコールの書き換え</h2> +<ul> + <li>CbC は C と互換性のある言語であるため、元のソースコードから大きく崩すことなく必要な機能のみを CbC へと書き換えることが可能である。</li> + <li>ここでは実際にシステムコールを CbC で書き換えることによって、状態遷移ベースで書き換えるには何が必要か示すことにした。</li> + <li>今回は read システムコールの CbC 書き換えを行なった。</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="twice-">Twice の結果</h2> -<ul> - <li>GPU は CPU との通信時間を含めた時間、 GPU(kernel only) は kernel のみの実行時間を示している</li> - <li>1 CPU と 32 CPU では 約27.1倍の速度向上が見られた</li> - <li>GPU は通信時間を含めると 8 CPU の約1.25倍、 kernel のみの実行では 32 CPU の約7.22倍になった</li> - <li>通信時間がオーバーヘッドになっている</li> +<h2 id="syscall">syscall関数</h2> +<ul lang="c"> + <li>syscall 関数 はシステムコールを呼び出す関数である。</li> </ul> - -<table border="1" align="center" width="50%"> - <tbody> - <tr> - <td style="text-align: center;">Processor</td> - <td style="text-align: center;">Time(ms)</td> - </tr> - <tr> - <td style="text-align: center;">1 CPU</td> - <td style="text-align: right;">1181.215</td> - </tr> - <tr> - <td style="text-align: center;">2 CPUs</td> - <td style="text-align: right;">627.914</td> - </tr> - <tr> - <td style="text-align: center;">4 CPUs</td> - <td style="text-align: right;">324.059</td> - </tr> - <tr> - <td style="text-align: center;">8 CPUs</td> - <td style="text-align: right;">159.932</td> - </tr> - <tr> - <td style="text-align: center;">16 CPUs</td> - <td style="text-align: right;">85.518</td> - </tr> - <tr> - <td style="text-align: center;">32 CPUs</td> - <td style="text-align: right;">43.496</td> - </tr> - <tr> - <td style="text-align: center;">GPU</td> - <td style="text-align: right;">127.018</td> - </tr> - <tr> - <td style="text-align: center;">GPU(kernel only)</td> - <td style="text-align: right;">6.018</td> - </tr> - </tbody> -</table> +<pre><code>void syscall(void) +{ + int num; + int ret; + num = proc->tf->r0; + if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) { + proc->cbc_arg.cbc_console_arg.num = num; + goto (cbccodes[num])(cbc_ret); + } + if((num > 0) && (num <= NELEM(syscalls)) && syscalls[num]) { + ret = syscalls[num](); + if (num != SYS_exec) { + proc->tf->r0 = ret; + } + } else { + cprintf("%d %s: unknown sys call %d\n", proc->pid, proc->name, num); + proc->tf->r0 = -1; + } +} +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="bitonicsort">BitonicSort</h2> -<ul> - <li>並列処理向けのソートアルゴリズム</li> - <li>決まった2点間の要素の入れ替えを並列に行うことでソーティングを進めていく</li> - <li>要素数 2^24</li> - <li>CPU での実行時は要素数 2^24 を 2^6 個に分割して Task を生成する</li> - <li>GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で kernel を実行</li> +<h2 id="sysread-">sys_read 関数</h2> +<ul lang="c"> + <li>読み込むファイルの情報とアドレスを取り出し、fileread に渡している</li> </ul> +<pre><code>int sys_read(void) +{ + struct file *f; + int n; + char *p; + + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + return -1; + } + + return fileread(f, p, n); +} +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="bitonicsort-">BitonicSort の結果</h2> -<ul> - <li>1 CPU と 32 CPU で約22.12倍の速度向上</li> - <li>GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった</li> - <li>現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった</li> -</ul> +<h2 lang="c" id="cbcread">cbc_read</h2> +<pre><code>__code cbc_read(__code (*next)(int ret)){ + struct file *f; + int n; + char *p; -<table border="1" align="center" width="50%"> - <tbody> - <tr> - <td style="text-align: center;">Processor</td> - <td style="text-align: center;">Time(s)</td> - </tr> - <tr> - <td style="text-align: center;">1 CPU</td> - <td style="text-align: right;">41.416</td> - </tr> - <tr> - <td style="text-align: center;">2 CPUs</td> - <td style="text-align: right;">23.340</td> - </tr> - <tr> - <td style="text-align: center;">4 CPUs</td> - <td style="text-align: right;">11.952</td> - </tr> - <tr> - <td style="text-align: center;">8 CPUs</td> - <td style="text-align: right;">6.320</td> - </tr> - <tr> - <td style="text-align: center;">16 CPUs</td> - <td style="text-align: right;">3.336</td> - </tr> - <tr> - <td style="text-align: center;">32 CPUs</td> - <td style="text-align: right;">1.872</td> - </tr> - <tr> - <td style="text-align: center;">GPU</td> - <td style="text-align: right;">5.420</td> - </tr> - <tr> - <td style="text-align: center;">GPU(kernel only)</td> - <td style="text-align: right;">0.163</td> - </tr> - </tbody> -</table> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="openmp-">OpenMP との比較</h2> -<ul> - <li>OpenMP は C、 C++ のプログラムにアノテーションを付けることで並列化を行う</li> - <li>データの待ち合わせ処理はバリア等のアノテーションで記述する</li> - <li>Gears OS は並列処理を par goto 構文、 データの待ち合わせを Code Gear と Input/Ouput Data Gear の関係で行う</li> -</ul> - -<pre lang="c"><code>#pragma omp parallel for -for(int i = 0; i < length; i++) { - a[i] = a[i] * 2; + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + goto next(-1); + } + goto cbc_fileread(f, p, n, next); } </code></pre> @@ -914,27 +682,35 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="go-">Go 言語との比較</h2> -<ul> - <li>Go 言語は並列実行を <strong>go funciton(argv)</strong> の構文で行う。 この実行を goroutine と呼ぶ</li> - <li>goroutine 間のデータの待ち合わせはチャネルというデータ構造で行う</li> - <li>チャネルでのデータの送受信は <strong><-</strong> を使用して行うため、簡潔に書くことが出来る</li> - <li>しかし、 チャネルは複数の goroutine で共有されるため、データの送信元が推測しづらい</li> - <li>Gears OS では goroutine は par goto 文とほぼ同等に扱える</li> - <li>par goto 文では書き出す Data Gear を指定するため、書き出し元が推測しやすい</li> +<h2 id="fileread">fileread</h2> +<ul lang="c"> + <li>file の状態を確認し、対応した関数へ移行する。</li> </ul> +<pre><code>int fileread (struct file *f, char *addr, int n) +{ + int r; + + if (f->readable == 0) { + return -1; + } -<pre lang="go"><code>c := make(chan []int) -for i :=0; i < *split; i++ { - // call goroutine - go twice(list, prefix, i, c); -} + if (f->type == FD_PIPE) { + return piperead(f->pipe, addr, n); + } + + if (f->type == FD_INODE) { + ilock(f->ip); -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; + if ((r = readi(f->ip, addr, f->off, n)) > 0) { + f->off += r; + } + + iunlock(f->ip); + + return r; } - c <- list + + panic("fileread"); } </code></pre> @@ -942,99 +718,82 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-5">まとめ</h2> -<ul> - <li>Gears OS の並列処理機構を Interface を用いて実装を行った</li> - <li>Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった</li> - <li>par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった</li> - <li>2つの例題である程度の台数効果が出ることを確認した</li> -</ul> - +<h2 lang="c" id="cbcfileread">cbc_fileread</h2> +<pre><code>__code cbc_fileread1 (int r) +{ + struct file *f = proc->cbc_arg.cbc_console_arg.f; + __code (*next)(int ret) = cbc_ret; + if (r > 0) + f->off += r; + iunlock(f->ip); + goto next(r); +} -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="section-6">今後の課題</h2> -<ul> - <li>Gears OS の並列処理の信頼性の保証、チューニングを行う</li> - <li>Gears OS では証明とモデル検査をメタレベルで実現することで信頼性を保証する - <ul> - <li>証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある</li> - <li>モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う</li> - </ul> - </li> - <li>現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった - <ul> - <li>Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う</li> - </ul> - </li> -</ul> +__code cbc_fileread (struct file *f, char *addr, int n, __code (*next)(int ret)) +{ + if (f->readable == 0) { + goto next(-1); + } + + if (f->type == FD_PIPE) { + //goto cbc_piperead(f->pipe, addr, n, next); + goto next(-1); + } + + if (f->type == FD_INODE) { + ilock(f->ip); + proc->cbc_arg.cbc_console_arg.f = f; + goto cbc_readi(f->ip, addr, f->off, n, cbc_fileread1); + } + + goto cbc_panic("fileread"); +} +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-7">今後の課題</h2> -<ul> - <li>OpenMP、 Go 言語で Twice を実装し、 Gears OS の性能比較を行った</li> - <li>その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 - <ul> - <li>par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう</li> - <li>モデル検査で par goto で実行する Code Gear のフローを解析し、処理が軽い場合は Context を生成せずに関数呼出しを行う等の最適化が必要</li> - </ul> - </li> +<h2 id="readi">readi</h2> +<ul lang="c"> + <li>readi はファイルシステム上か特殊なデバイスを制御するかどうかで分岐する</li> + <li>ここでは consoleread へ向かう処理を確認する。</li> </ul> +<pre><code>int readi (struct inode *ip, char *dst, uint off, uint n) +{ + uint tot, m; + struct buf *bp; -<div style="text-align: center;"> - <img src="./images/compareExamples.svg" alt="message" width="500" /> -</div> - + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) { + return -1; + } -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="section-8">データ並列</h2> -<ul> - <li>data並列はあるデータ構造がサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法</li> - <li>Gears OS ではdata 並列は par goto 構文に<strong>iterate(分割数)</strong>を追加することで可能になる</li> - <li>データ並列の Task は CPU で実行する際は Task にインデックスを付与して分割数分コピーして実行する</li> - <li>CUDA の場合は Kernel を実行する際にパラメーターとして分割数を渡す</li> -</ul> + return devsw[ip->major].read(ip, dst, n); + } +... +</code></pre> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="task-">Task 間の同期処理</h2> -<ul> - <li>Context 間での同期処理を行うために Semaphore を実装</li> - <li>Semaphore はContext 停止用の待ち Queue を持つ</li> -</ul> - -<div style="text-align: center;"> - <img src="./images/semaphoreSequence.svg" alt="message" width="700" /> -</div> +<h2 lang="c" id="cbcreadi">cbc_readi</h2> +<pre><code>__code cbc_readi (struct inode *ip, char *dst, uint off, uint n, __code (*next)(int ret)) +{ + uint tot, m; + struct buf *bp; + + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !cbc_devsw[ip->major].read) { + goto next(-1); + } + + goto cbc_devsw[ip->major].read(ip, dst, n, next); + } +... +</code></pre> -<!-- -## OpenMP との比較 -- OpenMP で Twice を実装し、速度比較を行った -- OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた -- 一方 Gears OS では約27.1倍と台数効果は高くなっている -- しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている - -<div style="text-align: center;"> - <img src="./images/vsopenmp.svg" alt="message" width="500"> -</div> - -## Go 言語との比較 -- Go 言語でも OpenMP と同様に Twice を実装し、速度比較を行った -- Go 言語は 1CPU と 32CPU で約4.33倍の速度向上が見られた -- OpenMP と同様に台数効果自体は Gears OS が高いが、 1CPU での実行時間は Go 言語が大幅に速い - -<div style="text-align: center;"> - <img src="./images/vsgo.svg" alt="message" width="500"> -</div> ---> <!-- === end markdown block === --> </div>
--- a/slide/slide.md Tue Feb 12 15:19:09 2019 +0900 +++ b/slide/slide.md Wed Feb 13 09:47:53 2019 +0900 @@ -14,41 +14,49 @@ ## OS の拡張性と信頼性の両立 - さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。 - 時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。 -- その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。 +- その信頼性を保証するには、従来のテストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。 ## OS の拡張性と信頼性の両立 - -- これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。 +- これに対処するためには、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。 - 検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。 - このため信頼性と拡張性を両立させることが重要である。 -## メタ計算 +## メタ計算とは - プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。 - メタ計算はノーマルレベルの計算から切り離して記述したい。 - そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。 - そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。 ## Continuation based C (CbC) -- Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。 -- Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。 +- Continuation based C (CbC) は Code Gear を処理の単位としたプログラミング言語として開発している。 +- Code Gear は 関数呼び出しとは異なり、次の Code Gear へと goto 文によって遷移する。 - この goto 文による遷移を軽量継続と呼ぶ。 -- 継続によって状態遷移ベースでのプログラミングが可能。 -- C と互換性のある言語で、C の関数も呼び出すことができる。 +- 継続を用いることによって状態遷移ベースでのプログラミングが可能である。 +- CbC は C と互換性のある言語なので、C の関数も呼び出すことができる。 ## Gears OS -- Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。 -- 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。 -- Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。 - -<div style="text-align: center;"> - <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600"> -</div> +- Gears OS は Code Gear と、データの単位である Data Gear を用いて開発されており、CbC で記述されている。 +- Gears OS は Context と呼ばれる全ての Code Gear と Data Gear を持ったデータ構造体を常に持ち歩いて処理を行う。 +- 必要な Code Gear、Data Gear は、この Context から取り出して処理を実行する。 ## xv6 の CbC 書き換え - xv6 は 2006 年に MIT のオペレーティングシステムコースで教育用の目的として開発されたオペレーティングシステムである。 - xv6 は UNIX V6 を x86 向けに再実装した OS である。 - OS としての基本的な構造を持つにも関わらず、シンプルで扱いやすい。 -- 継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。 +- 信頼性を保証するために xv6 を CbC で書き換え、Gears OS の機能を導入したい。 +- さらに、継続を用いる CbC で記述することにより、実行可能な OS がそのまま状態遷移モデルに落ちる。 + +## 目次 +- 今回の研究発表は大きく分けて 2部の構成となっている。 +- 第1部では Gears OS のモジュール化の仕組みの導入と解説。 +- 第2部では xv6 の CbC による書き換え について発表する。 + +## 目次 +- Code Gear と Data Gear +- Gears OS におけるメタ計算 +- Context +- Meta Code Gear +- Interface ## CbC のコード例 - Code Gear は\_\_code Code Gear 名 (引数) の形で記述される。 @@ -65,6 +73,15 @@ } ``` +## CbC の継続 +- Code Gear の継続を表す図である。 +- Code Gear 間の遷移は goto によって行われる。 +- アセンブラレベルで見ると call ではなく jmp となっている。 + +<div style="text-align: center;"> + <img src="./images/normal_Code_Gear.pdf" alt="normalCodeGear" width="600"> +</div> + ## Data Gear の表現 - Data Gear は Gears OS におけるデータの単位である。 - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される @@ -88,7 +105,7 @@ ## Gears でのメタ計算 - Gears OS ではメタ計算を Meta Code/Data Gear で表現する。 -- Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。 +- Meta Code Gear は通常の Code Gear の直後で遷移し、メタ計算を実行する。 - Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。 <div style="text-align: center;"> @@ -100,7 +117,7 @@ メタレベルの処理にも Meta Meta Gear となるメタレベルの処理が存在するように、 階層上の構造となっている。 - この2つのレベルはプログラミング言語レベルでの変換として実現される。 -- 本研究では Perl スクリプトによって実装されている。 +- 本研究では Perl スクリプトによってノーマルレベルからメタレベルへの変換が実装されている。 ## Meta Gear - Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する。 @@ -115,518 +132,651 @@ - Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする。 ## Context -- Context は Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。 -- - +- Context は全ての Code Gear のリストを持っており、enum で番号とアドレスを対応付けている。 +```c +enum Code { + C_popSingleLinkedStack, + C_pushSingleLinkedStack, + C_stackTest3, + C_assert3, + ... +}; +``` +```c +context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub; +context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub; +context->code[C_stackTest3] = stackTest3_stub; +context->code[C_assert3] = assert3_stub; +``` - - - +## Context +- Data Gear も Code Gear と同様に Context が全ての Data Gear のリストを持っている。 +- Data Gear のリストも enum で管理されている。 +- これは引数格納用の Data Gear の番号である。 +```c +enum DataType { + D_Code, + D_SingleLinkedStack, + D_Stack, + D_TaskManager, + D_Worker, + ... + }; +``` ## stub Code Gear -- Data Gear にアクセスするには Context から番号を指定して行う -- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある -- Gears OS では Code Gear に接続する Data Gear を メタレベルである Context から取り出す処理を行う stub Code Gear を用意している - -<div style="text-align: center;"> - <img src="./images/contextContinuation.svg" alt="message" width="600"> -</div> - -## Interface -- Gears OS を実装するに連れて、stub Code Gear の記述が煩雑になることがわかった -- そこで、Gears OS のモジュール化する仕組みとして **Interface** を導入した -- Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Data Gear -- stub Code Gear はInteface を実装した Code Gear で決まった形になるため、自動生成が可能 -- Interface を導入することで、 Stack や Queue などのデータ構造を仕様と実装に分けて記述することが出来る -- Interface は Java のインターフェース、 Haskell の型クラスに対応する - -## Interface の定義 -- Interface の定義には以下の内容を定義する - - 操作(API)の引数群の型 - - 操作(API)自体のCode Gear の型 - -``` c -typedef struct Queue<Impl>{ - // 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; -``` +- ノーマルレベルの Gears OS では継続先に渡す Data Gear は引数の集合に見える。 +- しかし、メタレベルで見ると、Data Gear は Context が管理しており、 +アクセスするには Context を介さなくてはならない。 +```c +__code cg1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stackPush(stack, node); +} -## Interface の定義 -- **__code next(...)** は継続を表している -- ... は可変長引数に相当する -- 可変長引数部分には呼び出し元の Interface の Data Gear が入る -- 継続の引数で Output Data Gear を返すことが出来る - -``` c -typedef struct Queue<Impl>{ - // 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; +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } ``` -## Interface の使い方 -- Interface を利用した Code Gear への継続は `goto interface->method` で行われる -- **interface** は Interface を表す Data Gear、 **method** は実装した Code Gear に対応する +## stub Code Gear +- このノーマルレベルとメタレベルのズレを合わせるための Meta Code Gear である +Stub Code Gear が Code Gear の間に挿入される。 +- stub Code Gear は Context から継続先の Code Gear が必要とする Data Gear を取り出す作業を行う。 +```c +__code stackPush_stub(struct Contet* context) { + Stack* stack = &context->data[D_Stack]->Stack; + Node* node = &context->data[D_Node]->Node; + goto stackPush(context, stack, node); +} -``` c -__code code1() { - Queue* queue = createSingleLinkedQueue(context); - Node* node = new Node(); - node->color = Red; - goto queue->put(node, code2); +__code stackPush(struct Stack* stack, struct Node* node) { + Element* element = new Element(); + element->next = stack->top; + element->data = (union Data*)node; + stack->stack->SingleLinkedStack.top = element; + goto cg2(...); } ``` -## メタレベルでの 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); -} -``` +## stub Code Gear +- メタレベル で見た Code Gear の引き渡し +<div style="text-align: center;"> + <img src="./images/Context_ref.pdf" alt="Context_ref" width="600"> +</div> -## 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) { - ... +## goto meta +- Gears OS では Code Gear もリストで管理しており、継続する際には一度 \_\_code meta へと継続する。 +- ここでノーマルレベルの Code Gear には変換が行われているが、これはコンパイル時に変換される。 +- この変換によりノーマルレベルでは隠れていた Context が見えるようになっている。 +- context に引き渡しているコードもここで生成される。 +```c +__code cg1(struct Context* context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + &context->data[D_Stack]->Stack = (union Data*) stack; + &context->data[D_Node]->Node = node; + goto meta(C_stackPush); } -// 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 として実装した +## Interface +- Interface は Gears OS のモジュール化の仕組みである。 +- Interface はある Data Gear と、それに対する操作(API)を行う +Code Gear とその操作に用いる Data Gear の集合を表現する。 +- Java の Interface に対応し、定義することで複数の実装を持つことができる。 + +## Interface の定義 +- Stack の Interface の例である。 +- typedef struct Interface 名で記述する。 +- Impl は実際に実装した際のデータ構造の型になる。 + +```c +typedef struct Stack<Impl> { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -## Task -- Gears OS では Context が並列実行の Task に相当する -- Context は Task用の情報として以下の情報を付け加えた - - 実行する Code Gear - - Input/Output Data Gear の格納場所 - - 待っている Input Data Gear の数 - - この Task を実行する Worker + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + +} +``` -## TaskManger -- Worker をCPU、 GPU の数分生成する -- 依存関係を解決した Task を各 Worker の Queue に送信する +## Interface の定義 +- Data Gear は 操作する Data Gear と +操作に必要な全ての Data Gear Gear が記述されている。 +- \_\_code で記述されているものが操作の Code Gear である。 -<div> - <img src="./images/sendTask.svg" alt="message" style="float: left;width: 50%;"> - <div style="float: left; width: 50%;"> - <ol> - <li value="0">Task を Input Data Gear としてTaskManager の spawn を呼び出す</li> - <li value="1">Task が待っている Data Gear のカウンタである IDGCount をチェックする</li> - <li value="2">IDGCount が0の場合 Data Gear が 揃っているので Worker の Queue に Task を送信する</li> - </ol> - </div> - <div style="clear: both;"></div> -</div> +```c +typedef struct Stack<Impl> { + union Data* stack; + union Data* data; + __code next(...); + __code whenEmpty(...); -## Worker -- 初期化時に Worker 用の Context を生成し、Code Gear を実行していく -- TaskManager から送信された Task を一つずつ取得して実行する + __code clear(Impl* stack, __code next(...)); + __code push(Impl* stack, union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data* ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + +} +``` -<div> - <img src="./images/workerRun.svg" alt="message" style="float: left;width: 50%;"> - <div style="float: left; width: 50%;"> - <ol> - <li>Worker は Queue から Task(Context)を取得する</li> - <li>Worker の Context からTask の Context へ入れ替える</li> - - <li>Task に設定されている Code Gear を実行</li> - <li>Task の Output Data Gear の書き出し</li> - <li>Task Context から Worker の Context へ入れ替える</li> - <li>Worker は再び Queue から Task を取得する</li> - </ol> - </div> - <div style="clear: both;"></div> -</div> +## Interface の実装の記述 +- ソースコードは Interface の実装の初期化のコードである。 +- 操作の Code Gear には実装した Code Gear の番号が代入されるが、ここを入れ替えることで、複数の実装を持つことができる。 +```c +Stack* createSingleLinkedStack(struct Context* context) { + struct Stack* stack = new Stack(); + struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack(); + stack->stack = (union Data*)singleLinkedStack; + singleLinkedStack->top = NULL; + stack->push = C_pushSingleLinkedStack; + stack->pop = C_popSingleLinkedStack; + stack->isEmpty = C_isEmptySingleLinkedStack; + stack->clear = C_clearSingleLinkedStack; + return stack; +} +``` -## Synchronized Queue -- TaskManager と Worker 間の通信を行うための Queue -- マルチスレッドでのデータの同期処理を行える SynchronizedQueue として実装する -- Gears OS では 同期機構として CAS(Check and Set、 Compare and Swap) を使用した実装を行った - - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較し、変化がなければ値を更新する - - メモリ番地の値が変わっているなら、もう一度 CAS を行う +## Interface の操作の呼び出し +- Interface の操作の呼び出しは、ノーマルレベルでは `goto interface->method` の形で記述される。 +- interface は Interface を表す Data Gear 、method は実装した Code Gear に対応する。 -<div style="text-align: center;"> - <img src="./images/synchronizedQueue.svg" alt="message" width="600"> -</div> - -## 依存関係の解決 -- 依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する -- この Queue には Data Gear に依存関係がある Context が格納されている +```c +__code stackTest1(struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + goto stack->push(node, stackTest2) +} +``` -<div> - <img src="./images/dependency.svg" alt="message" style="float: left;width: 50%;"> - <div style="float: left; width: 50%;"> - <ol> - <li>Task に設定されている Code Gear を実行する</li> - <li>Output Data Gear の書き出し処理を行う際にメタレベルの Queue を参照する</li> - - <li>依存関係にある Task を取り出し、IDGCount をデクリメントする</li> - - </ol> - </div> - <div style="clear: both;"></div> -</div> - -- IDGCountの値が0になった実行可能な Task は TaskManager を通して Worker に送信される +## Interface の操作の呼び出し +- interface の操作の呼び出しは、メタレベルでは以下のように変換される。 +- stack->push には enum の番号が入っているため、\_\_code meta で +対応する番号の Code Gear へと継続する。 +```c +__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +``` -## 並列構文 -- 並列実行する際は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する -- この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述としては好ましくない -- Context の設定は煩雑な記述だが、並列実行されることを除けば通常の CbC の goto 文と同等 -- そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した +## Interface の操作の呼び出し +- ここで Gearef という記述があるが、これは Context を参照するためのマクロである。 +`Gearef(context, t) (&(context)->data[D_##t]->t)` +- 格納先は Interface の型が持つ Data Gear へ格納される。 +```c +__code stackTest1(struct Context *context, struct Stack* stack) { + Node* node = new Node(); + node->color = Red; + Gearef(context, Stack)->stack = (union Data*)stack; + Gearef(context, Stack)->data = node; + Gearef(context, Stack)->next = C_stackTest2; + goto meta(context, stack->push) +} +``` -## 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 構文は通常のプログラミングの関数呼び出しのように扱える +## Interface における stub Code Gear +- Interface の情報から stub Code Gear は自動生成される。 +- 引数に必要な Data Gear は Interface の型が持つ Data Gear から取り出す。 +- GearImpl は interface の操作が対象にする Data Gear を取り出すマクロである。 +`GearImpl(context, intf, name) (Gearef(context, intf)->name->intf.name)` +```c +__code pushSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,union Data* data, enum Code next) { + ... +} -``` c -__code code1(Integer *integer1, Integer * integer2, Integer *output) { - par goto add(integer1, integer2, output, __exit); - goto code2(); +__code pushSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); + Data* data = Gearef(context, Stack)->data; + enum Code next = Gearef(context, Stack)->next; + goto pushSingleLinkedStack(context, stack, data, next); } ``` -## CUDA への対応 -- Gears OS は GPU での実行もサポートしている -- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる -- CUDA は GPU を Device、 CPU を Host として定義する -- CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する -- 今回、CUDA に合わせた並列処理機構である CUDAWorker、 CUDAExecutor をInterface を用いて実装し、 CPU、GPU 間のデータのマッピングのために CUDABuffer を用意した +## 目次 +- xv6 の書き換えの方針について +- システムコールの書き換えについての考察 +- 書き換えたシステムコールを追う + +## xv6 の CbC 書き換え +- xv6 は UNIX V6 を x86 向けに再実装した OS である。 +- プロセスや仮想メモリ、カーネルとユーザーの分離、割り込み、ファイルシステムなどの基本的な Unix の構造を持つ +- CbC は Code Gear 間の遷移が goto による継続で行われるため、状態遷移ベースでのプログラミングに適している。 +- CbC で xv6 を書き換えることにより、状態遷移モデルによるモデル検査が可能となることを期待する。 + +## xv6 の書き換えの方針 +- xv6 を CbC で書き換え、Gears OS の機能と置き換えることで Gears OS に OS の基本構造を持たせたい。 +- このためには xv6 をモジュール化することで、xv6 の機能を明らかにする必要がある。 +- xv6 の Interface を定義し、Gears OS の機能をこれに合わせることによって実現したい。 + +## システムコールの書き換え +- CbC は C と互換性のある言語であるため、元のソースコードから大きく崩すことなく必要な機能のみを CbC へと書き換えることが可能である。 +- ここでは実際にシステムコールを CbC で書き換えることによって、状態遷移ベースで書き換えるには何が必要か示すことにした。 +- 今回は read システムコールの CbC 書き換えを行なった。 -## CUDAWorker -- CUDA で実行する Task を受け取る Worker -- 初期化の際に CUDA ライブラリの初期化や CUDAExecutor の生成を行う +## syscall関数 +- syscall 関数 はシステムコールを呼び出す関数である。 +```c +void syscall(void) +{ + int num; + int ret; + num = proc->tf->r0; + if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) { + proc->cbc_arg.cbc_console_arg.num = num; + goto (cbccodes[num])(cbc_ret); + } + if((num > 0) && (num <= NELEM(syscalls)) && syscalls[num]) { + ret = syscalls[num](); + if (num != SYS_exec) { + proc->tf->r0 = ret; + } + } else { + cprintf("%d %s: unknown sys call %d\n", proc->pid, proc->name, num); + proc->tf->r0 = -1; + } +} +``` + +## sys\_read 関数 +- 読み込むファイルの情報とアドレスを取り出し、fileread に渡している +```c +int sys_read(void) +{ + struct file *f; + int n; + char *p; + + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + return -1; + } + + return fileread(f, p, n); +} +``` + +## cbc\_read +```c +__code cbc_read(__code (*next)(int ret)){ + struct file *f; + int n; + char *p; -## CUDAExecutor -- CUDAExecutor は Executor Interface を実装した Data Gear -- 以下の Code Gear を実装している - - HostからDevice へのデータの送信(read) - - kernel の実行(exec) - - Device から Host へのデータの書き出し(write) + if(argfd(0, 0, &f) < 0 || argint(2, &n) < 0 || argptr(1, &p, n) < 0) { + goto next(-1); + } + goto cbc_fileread(f, p, n, next); +} +``` + +## fileread +- file の状態を確認し、対応した関数へ移行する。 +```c +int fileread (struct file *f, char *addr, int n) +{ + int r; + + if (f->readable == 0) { + return -1; + } + + if (f->type == FD_PIPE) { + return piperead(f->pipe, addr, n); + } + + if (f->type == FD_INODE) { + ilock(f->ip); + + if ((r = readi(f->ip, addr, f->off, n)) > 0) { + f->off += r; + } + + iunlock(f->ip); + + return r; + } -``` c -typedef struct Executor<Impl>{ - 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(...)); + panic("fileread"); +} +``` + +## cbc\_fileread +```c +__code cbc_fileread1 (int r) +{ + struct file *f = proc->cbc_arg.cbc_console_arg.f; + __code (*next)(int ret) = cbc_ret; + if (r > 0) + f->off += r; + iunlock(f->ip); + goto next(r); +} + +__code cbc_fileread (struct file *f, char *addr, int n, __code (*next)(int ret)) +{ + if (f->readable == 0) { + goto next(-1); + } + + if (f->type == FD_PIPE) { + //goto cbc_piperead(f->pipe, addr, n, next); + goto next(-1); + } + + if (f->type == FD_INODE) { + ilock(f->ip); + proc->cbc_arg.cbc_console_arg.f = f; + goto cbc_readi(f->ip, addr, f->off, n, cbc_fileread1); + } + + goto cbc_panic("fileread"); } ``` -## CUDABuffer -- Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある -- CUDA Buffer ではそのマッピングを行う - - このマッピングは Task に設定されている stub Code Gear で行われる - -<div style="text-align: center;"> - <img src="./images/cudaDataArchitecture.svg" alt="message" width="400"> -</div> +## readi +- readi はファイルシステム上か特殊なデバイスを制御するかどうかで分岐する +- ここでは consoleread へ向かう処理を確認する。 +```c +int readi (struct inode *ip, char *dst, uint off, uint n) +{ + uint tot, m; + struct buf *bp; -## CUDA での呼び出し -- Gears OS では Task に設定している Code Gear の stub Code Gear で CUDA実行を切り替える -- CUDABuffer でのマッピング、実行する kernel の読み込みは stub Code Gear で行われる -- CUDA で実行する際は stub Code Gear に対応する Code Gear ではなく、 CUDAExecutor の Code Gear に継続する + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !devsw[ip->major].read) { + return -1; + } -<div style="text-align: center;"> - <img src="./images/gotoCUDAExecutor.svg" alt="message" width="600"> -</div> + return devsw[ip->major].read(ip, dst, n); + } +... +``` -## 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 +## cbc\_readi +```c +__code cbc_readi (struct inode *ip, char *dst, uint off, uint n, __code (*next)(int ret)) +{ + uint tot, m; + struct buf *bp; + + if (ip->type == T_DEV) { + if (ip->major < 0 || ip->major >= NDEV || !cbc_devsw[ip->major].read) { + goto next(-1); + } + + goto cbc_devsw[ip->major].read(ip, dst, n, next); + } +... +``` -## 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倍になった -- 通信時間がオーバーヘッドになっている +## consoleread +- console への入力を読み込み、待っている間スリープする +```c +int consoleread (struct inode *ip, char *dst, int n) +{ + uint target; + int c; + iunlock(ip); + target = n; + acquire(&input.lock); -<table border="1" align='center' width='50%'> - <tbody> - <tr> - <td style="text-align: center;">Processor</td> - <td style="text-align: center;">Time(ms)</td> - </tr> - <tr> - <td style="text-align: center;">1 CPU</td> - <td style="text-align: right;">1181.215</td> - </tr> - <tr> - <td style="text-align: center;">2 CPUs</td> - <td style="text-align: right;">627.914</td> - </tr> - <tr> - <td style="text-align: center;">4 CPUs</td> - <td style="text-align: right;">324.059</td> - </tr> - <tr> - <td style="text-align: center;">8 CPUs</td> - <td style="text-align: right;">159.932</td> - </tr> - <tr> - <td style="text-align: center;">16 CPUs</td> - <td style="text-align: right;">85.518</td> - </tr> - <tr> - <td style="text-align: center;">32 CPUs</td> - <td style="text-align: right;">43.496</td> - </tr> - <tr> - <td style="text-align: center;">GPU</td> - <td style="text-align: right;">127.018</td> - </tr> - <tr> - <td style="text-align: center;">GPU(kernel only)</td> - <td style="text-align: right;">6.018</td> - </tr> - </tbody> -</table> - -## BitonicSort -- 並列処理向けのソートアルゴリズム -- 決まった2点間の要素の入れ替えを並列に行うことでソーティングを進めていく -- 要素数 2^24 -- CPU での実行時は要素数 2^24 を 2^6 個に分割して Task を生成する -- GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で kernel を実行 + while (n > 0) { + while (input.r == input.w) { + if (proc->killed) { + release(&input.lock); + ilock(ip); + return -1; + } + sleep(&input.r, &input.lock); + } + c = input.buf[input.r++ % INPUT_BUF]; + if (c == C('D')) { // EOF + if (n < target) { + input.r--; + } + break; + } + *dst++ = c; + --n; + if (c == '\n') { + break; + } + } + release(&input.lock); + ilock(ip); + return target - n; +} +``` -## 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 の結果の書き出しを行っているため、差がでてしまった +## cbc\_consoleread -<table border="1" align='center' width='50%'> - <tbody> - <tr> - <td style="text-align: center;">Processor</td> - <td style="text-align: center;">Time(s)</td> - </tr> - <tr> - <td style="text-align: center;">1 CPU</td> - <td style="text-align: right;">41.416</td> - </tr> - <tr> - <td style="text-align: center;">2 CPUs</td> - <td style="text-align: right;">23.340</td> - </tr> - <tr> - <td style="text-align: center;">4 CPUs</td> - <td style="text-align: right;">11.952</td> - </tr> - <tr> - <td style="text-align: center;">8 CPUs</td> - <td style="text-align: right;">6.320</td> - </tr> - <tr> - <td style="text-align: center;">16 CPUs</td> - <td style="text-align: right;">3.336</td> - </tr> - <tr> - <td style="text-align: center;">32 CPUs</td> - <td style="text-align: right;">1.872</td> - </tr> - <tr> - <td style="text-align: center;">GPU</td> - <td style="text-align: right;">5.420</td> - </tr> - <tr> - <td style="text-align: center;">GPU(kernel only)</td> - <td style="text-align: right;">0.163</td> - </tr> - </tbody> -</table> - - -## 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; +```c +__code cbc_consoleread (struct inode *ip, char *dst, int n, __code(*next)(int ret)) +{ + uint target; + + iunlock(ip); + + target = n; + acquire(&input.lock); + + if (n > 0) { + proc->cbc_arg.cbc_console_arg.n = n; + proc->cbc_arg.cbc_console_arg.target = target; + proc->cbc_arg.cbc_console_arg.dst = dst; + proc->cbc_arg.cbc_console_arg.ip = ip; + proc->cbc_arg.cbc_console_arg.next = next; + goto cbc_consoleread2(); + } + goto cbc_consoleread1(); } ``` -## 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); +## cbc\_consoleread +```c +__code cbc_consoleread2 () +{ + struct inode *ip = proc->cbc_arg.cbc_console_arg.ip; + __code(*next)(int ret) = proc->cbc_arg.cbc_console_arg.next; + if (input.r == input.w) { + if (proc->killed) { + release(&input.lock); + ilock(ip); + goto next(-1); + } + goto cbc_sleep(&input.r, &input.lock, cbc_consoleread2); + } + goto cbc_consoleread1(); } -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; +__code cbc_consoleread1 () +{ + int cont = 1; + int n = proc->cbc_arg.cbc_console_arg.n; + int target = proc->cbc_arg.cbc_console_arg.target; + char* dst = proc->cbc_arg.cbc_console_arg.dst; + struct inode *ip = proc->cbc_arg.cbc_console_arg.ip; + __code(*next)(int ret) = proc->cbc_arg.cbc_console_arg.next; + + int c = input.buf[input.r++ % INPUT_BUF]; + + if (c == C('D')) { // EOF + if (n < target) { + input.r--; + } + cont = 0; + } + + *dst++ = c; + --n; + if (c == '\n') { + cont = 0; + } + if (cont == 1) { + if (n > 0) { + proc->cbc_arg.cbc_console_arg.n = n; + proc->cbc_arg.cbc_console_arg.target = target; + proc->cbc_arg.cbc_console_arg.dst = dst; + proc->cbc_arg.cbc_console_arg.ip = ip; + proc->cbc_arg.cbc_console_arg.next = next; + goto cbc_sleep(&input.r, &input.lock, cbc_consoleread2); + } } - c <- list + release(&input.lock); + ilock(ip); + goto next(target - n); +} +``` +## sleep +- プロセスをスリープ状態にしてスケジューラーへ引き渡す。 +```c +void sleep(void *chan, struct spinlock *lk) +{ + if(proc == 0) { + panic("sleep"); + } + + if(lk == 0) { + panic("sleep without lk"); + } + + if(lk != &ptable.lock){ //DOC: sleeplock0 + acquire(&ptable.lock); //DOC: sleeplock1 + release(lk); + } + + proc->chan = chan; + proc->state = SLEEPING; + sched(); + + proc->chan = 0; + + if(lk != &ptable.lock){ //DOC: sleeplock2 + release(&ptable.lock); + acquire(lk); + } } ``` -## まとめ -- Gears OS の並列処理機構を Interface を用いて実装を行った -- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった -- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった -- 2つの例題である程度の台数効果が出ることを確認した +## cbc\_sleep +```c +__code cbc_sleep1() +{ + struct spinlock *lk = proc->lk; + proc->chan = 0; + + if(lk != &ptable.lock){ //DOC: sleeplock2 + release(&ptable.lock); + acquire(lk); + } + goto proc->cbc_next(); +} -## 今後の課題 -- 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 を生成せずに関数呼出しを行う等の最適化が必要 - -<div style="text-align: center;"> - <img src="./images/compareExamples.svg" alt="message" width="500"> -</div> +__code cbc_sleep(void *chan, struct spinlock *lk, __code(*next1)()) +{ + if(proc == 0) { + panic("sleep"); + } + + if(lk == 0) { + panic("sleep without lk"); + } + + if(lk != &ptable.lock){ //DOC: sleeplock0 + acquire(&ptable.lock); //DOC: sleeplock1 + release(lk); + } + proc->chan = chan; + proc->state = SLEEPING; + proc->lk = lk; + proc->cbc_next = next1; + + goto cbc_sched(cbc_sleep1); +} +``` -## データ並列 -- data並列はあるデータ構造がサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法 -- Gears OS ではdata 並列は par goto 構文に**iterate(分割数)**を追加することで可能になる -- データ並列の Task は CPU で実行する際は Task にインデックスを付与して分割数分コピーして実行する -- CUDA の場合は Kernel を実行する際にパラメーターとして分割数を渡す - -## Task 間の同期処理 -- Context 間での同期処理を行うために Semaphore を実装 -- Semaphore はContext 停止用の待ち Queue を持つ - -<div style="text-align: center;"> - <img src="./images/semaphoreSequence.svg" alt="message" width="700"> -</div> +## sched +- レジスタの値を切り替えて、スケジューラーへと戻る +- 再開時は swtch の下から再開する。 +```c +void sched(void) +{ + int intena; + + if(!holding(&ptable.lock)) { + panic("sched ptable.lock"); + } + + if(cpu->ncli != 1) { + panic("sched locks"); + } + + if(proc->state == RUNNING) { + panic("sched running"); + } + + if(int_enabled ()) { + panic("sched interruptible"); + } + + intena = cpu->intena; + swtch(&proc->context, cpu->scheduler); + cpu->intena = intena; +} +``` -<!-- -## OpenMP との比較 -- OpenMP で Twice を実装し、速度比較を行った -- OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた -- 一方 Gears OS では約27.1倍と台数効果は高くなっている -- しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている +## cbc\_sched +```c +__code cbc_sched(__code(*next)()) +{ + int intena; + + if(!holding(&ptable.lock)) { + panic("sched ptable.lock"); + } + + if(cpu->ncli != 1) { + panic("sched locks"); + } + + if(proc->state == RUNNING) { + panic("sched running"); + } + + if(int_enabled ()) { + panic("sched interruptible"); + } + + intena = cpu->intena; + swtch(&proc->context, cpu->scheduler); + cpu->intena = intena; + + goto next(); +} +``` +## read システムコールの遷移図 +- CbC へ書き換えることで状態遷移ベースのプログラムに書き換えることができた。 +- 現在はシステムコールのみだが、カーネル全体を書き換えることで、OS の状態遷移モデルができる。 <div style="text-align: center;"> - <img src="./images/vsopenmp.svg" alt="message" width="500"> + <img src="./images/state.pdf" alt="state" width="600"> </div> - -## Go 言語との比較 -- Go 言語でも OpenMP と同様に Twice を実装し、速度比較を行った -- Go 言語は 1CPU と 32CPU で約4.33倍の速度向上が見られた -- OpenMP と同様に台数効果自体は Gears OS が高いが、 1CPU での実行時間は Go 言語が大幅に速い - -<div style="text-align: center;"> - <img src="./images/vsgo.svg" alt="message" width="500"> -</div> --->