Mercurial > hg > Papers > 2018 > parusu-master

--- a/paper/introduction.tex	Sat Feb 10 00:19:52 2018 +0900
+++ b/paper/introduction.tex	Sat Feb 10 03:01:54 2018 +0900
@@ -1,5 +1,5 @@
 \chapter{メタ計算を使った並列処理}
-並列処理は現代主流のマルチコアCPU の性能を発揮するには重要なものになっている。
+並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている。
 しかし、並列処理のプログラミングはスレッド間の共通資源の競合など非決定的な実行を持っており、その信頼性を保証するには従来のテストやデバッグでは不十分であり、テストしきれない部分が残ってしまう。

 また、マルチコア CPU 以外にも  GPU や CPU と GPU を複合したヘテロジニアスなプロセッサも並列処理をする上で無視できない。
Binary file paper/master_paper.pdf has changed
--- a/slide/slide.html	Sat Feb 10 00:19:52 2018 +0900
+++ b/slide/slide.html	Sat Feb 10 03:01:54 2018 +0900
@@ -87,7 +87,7 @@
 <!-- === begin markdown block ===

       generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16]
-                on 2018-02-09 18:08:42 +0900 with Markdown engine kramdown (1.13.2)
+                on 2018-02-10 02:47:53 +0900 with Markdown engine kramdown (1.13.2)
                   using options {}
   -->

@@ -112,82 +112,6 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="gears-os-">Gears OS の並列性</h2>
-<ul>
-  <li>Gears OS はプログラムの単位として Gear を用いる</li>
-  <li>Gear OSには プログラムの処理を示す Code Gear、 データを示す Data Gear がある</li>
-  <li>並列処理の Task は Code Gear と 実行に必要なInput Data Gear、 結果の書き出す Output Data Gear の組で表現する</li>
-  <li>Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能</li>
-</ul>
-
-<div style="text-align: center;">
-    <img src="./images/codeGear_dataGear.svg" alt="message" width="450" />
-</div>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="gears-os--1">Gears OS の拡張性</h2>
-<ul>
-  <li>Gears OS は Meta Computation を使用することで
-    <ul>
-      <li>データ拡張や機能の追加</li>
-      <li>GPU 等のさまざまなアーキテクチャでも同じプログラムの動作</li>
-      <li>バージョンが異なる者同士がネットワーク接続しても通信</li>
-    </ul>
-  </li>
-</ul>
-
-<p>等を柔軟に対応する</p>
-
-<ul>
-  <li>Meta Computation は 通常の Computaiton と階層を分けて処理を行う</li>
-</ul>
-
-<div style="text-align: center;">
-    <img src="./images/meta_gear.svg" alt="message" width="800" />
-</div>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="gears-os--2">Gears OS の信頼性</h2>
-<ul>
-  <li>検証
-    <ul>
-      <li>モデル検査を行う</li>
-      <li>モデル検査は状態の数が膨大になると検査するのが難しい</li>
-      <li>そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う</li>
-    </ul>
-  </li>
-  <li>証明
-    <ul>
-      <li>Code Gear と Data Gear を理論的に定義</li>
-    </ul>
-  </li>
-</ul>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="section">この発表は</h2>
-<ul>
-  <li>Gears OS でのGear</li>
-  <li>Meta Computation</li>
-  <li>Continuation based C(CbC)</li>
-  <li>CbC を用いた Gears OS の記述</li>
-  <li>Gears OS の並列処理機構</li>
-  <li>まとめ</li>
-  <li>課題</li>
-</ul>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
 <h2 id="code-gear-data-gear">Code Gear、 Data Gear</h2>
 <ul>
   <li>Gears OS は Code Gear、 Data Gear という Gear で構成される</li>
@@ -205,38 +129,6 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-1">メタ計算</h2>
-<ul>
-  <li>メタ計算 は通常の計算を実行するための計算</li>
-  <li>信頼性の確保やGPUなどのアーキテクチャでの実行のために行う処理などを行う</li>
-  <li>Gears OS では メタ計算 を Meta Code Gear, Meta Data Gear で表現</li>
-</ul>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="meta-gear">Meta Gear</h2>
-<ul>
-  <li>メタ計算 は Code Gearの接続の間に行われる</li>
-  <li>メタ計算 の処理も Code/Data Gear で実現する</li>
-  <li>この Gear を Meta Code/Data Gearと呼ぶ
-    <ul>
-      <li>Meta Code Gear は メタ計算 のプログラム部分</li>
-      <li>Meta Data Gear は Meta Code Gear で管理されるデータ部分</li>
-    </ul>
-  </li>
-  <li>Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う</li>
-</ul>
-
-<div style="text-align: center;">
-    <img src="./images/meta_cg_dg.svg" alt="message" width="850" />
-</div>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
 <h2 id="continuation-based-c">Continuation based C</h2>
 <ul>
   <li>Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる</li>
@@ -286,57 +178,34 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="cbc--gears-os-">CbC を用いた Gears OS の記述</h2>
+<h2 id="section">メタ計算</h2>
 <ul>
-  <li>Gears OS での Code Gear は CbC の Code Gear と同じように定義する</li>
-  <li>各 Code Gear の引数は 必要な Data Gear を示す</li>
-  <li>このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている</li>
+  <li>メタ計算 は通常の計算を実行するための計算</li>
+  <li>信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等</li>
+  <li>Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる</li>
+  <li>メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる</li>
 </ul>

-<pre lang="c"><code>__code code1(struct Array* array, struct LoopCounter* loopCounter) {
-    ...
-    goto code2(array);
-}
-
-__code meta_code1(struct Context* context, enum Code next) {
-    goto (context-&gt;code[next])(context);
-}
-
-__code code2(struct Array* array) {
-    ...
-}
-</code></pre>
-

 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="cbc--gears-os--1">CbC の Gears OS サポート</h2>
+<h2 id="meta-gear">Meta Gear</h2>
 <ul>
-  <li>実際は code1 から code2 への継続の間には Meta Code Gear である meta_code1 が実行される</li>
-  <li>通常は Meta Level の継続をプログラマーは意識する必要はない</li>
-  <li>そこで、CbC は Code Gear 間の接続に自動的に Meta Code Gear を挟むというサポートを行う</li>
-  <li>CbC のサポートを行うとこのコードのように展開される</li>
-  <li>メタレベルのサポートの際は <strong>context</strong> という Meta Data Gear を使用する</li>
+  <li>メタ計算 は Code Gearの接続の間に行われる</li>
+  <li>メタ計算 の処理も Code/Data Gear で実現する</li>
+  <li>この Gear を Meta Code/Data Gearと呼ぶ
+    <ul>
+      <li>Meta Code Gear は メタ計算 のプログラム部分</li>
+      <li>Meta Data Gear は Meta Code Gear で管理されるデータ部分</li>
+    </ul>
+  </li>
+  <li>Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う</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, &amp;context-&gt;data[Node]-&gt;node.value-&gt;array, &amp;context-&gt;data[LoopCounter]-&gt;loopCounter);
-}
-
-__code meta_code1(struct Context* context, enum Code next) {
-    goto (context-&gt;code[next])(context);
-}
-
-__code code2(struct Context* context, struct Array* array) {
-    ...
-}
-</code></pre>
+<div style="text-align: center;">
+    <img src="./images/meta_cg_dg.svg" alt="message" width="850" />
+</div>


 </div>
@@ -344,84 +213,40 @@
 <!-- _S9SLIDE_ -->
 <h2 id="context">Context</h2>
 <ul>
-  <li>Context は
+  <li>Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear</li>
+  <li>従来のOS のスレッドやプロセスに対応
     <ul>
-      <li>接続可能な Code/Data Gear のリスト</li>
-      <li>独立したメモリ空間
-をもっている</li>
-    </ul>
-  </li>
-  <li>各 Code/Data Gear にアクセスする際は Context を経由する</li>
-</ul>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="context-1">Context</h2>
-<ul>
-  <li>Context は
-    <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>
+      <li>独立したメモリ空間を持つ</li>
+      <li>Code Gear、 Data Gear へのポインタ</li>
+      <li>並列実行用の Task 情報</li>
     </ul>
   </li>
+  <li>を持つ</li>
+  <li>Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする</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>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="context-2">Context</h2>
-<ul>
-  <li>実行可能な Code Gear の名前は <strong>enum code</strong> で定義する</li>
-  <li>Context の初期化時に名前と関数ポインタを対応付ける</li>
-  <li>現在の Gears ではこの enum code 使って接続先の Code Gear を指定する</li>
-</ul>
-
-<pre lang="c"><code>enum Code {
-    Code1,
-    Code2,
-    Code3,
-    Exit,
-};
-</code></pre>
-

 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="data-gear-">Data Gear の表現</h2>
 <ul>
-  <li>使用する Data Gear は C の共用体と構造体を用いた表現をする</li>
-  <li>これを元に Gears OS は 必要な Data Gear を allocate する</li>
+  <li>Data Gear は構造体を用いて定義する</li>
+  <li>メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される</li>
+  <li>Data Gear のメモリに確保する際のサイズ情報はこの型から決定する</li>
 </ul>

 <pre lang="c"><code>/* data Gear define */
 union Data {
-    struct Time {
+    struct Timer {
+        union Data* timer;
+        enum Code start;
+        enum Code end;
         enum Code next;
+    } Timer;
+    struct TimerImpl {
         double time;
-    } time;
-    struct LoopCounter {
-        int i;
-    } loopCounter;
+    } TimerImpl;
     ....
 };
 </code></pre>
@@ -430,48 +255,71 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="code-gear--stub">Code Gear の stub</h2>
+<h2 id="code-gear--stub-code-gear">Code Gear の stub Code 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 を用意する</li>
-  <li>stub は一種の Meta Code Gear であるため、 CbC で自動生成される</li>
-  <li>このコードでは Array と LoopCounter が必要な code1 の stub を示している</li>
+  <li>Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub 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, &amp;context-&gt;data[Node]-&gt;node.value-&gt;array, &amp;context-&gt;data[LoopCounter]-&gt;loopCounter);
-}
+<pre lang="c"><code>
 </code></pre>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-2">プロトタイプ の構成</h2>
+<h2 id="context--stub-code-gear-">Context での stub Code Gear の記述の問題点</h2>
+<ul>
+  <li>Context プログラム全体で使用する Code Gear と Data Gear の集合</li>
+  <li>全ての Code と Data の組合せをContext から 全て展開し、その組合せを stub Code Gear に書く必要がある</li>
+  <li>Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた</li>
+  <li>そのため Gears OS のモジュール化する仕組みとして <strong>Interface</strong> を導入した</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface">Interface</h2>
+<ul>
+  <li>Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear</li>
+  <li>stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である</li>
+  <li>Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る</li>
+  <li>Interface は Java のインターフェース、 Haskell の型クラスに対応する</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface-">Interface の定義</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface--1">Interface の実装</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface--code-gear-">Interface を利用した Code Gear の呼び出し</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-1">並列処理の構成</h2>
 <ul>
   <li>今回は並列処理を行う機構の実装を行う</li>
-  <li>必要な要素は大きく5つ
+  <li>構成要素
     <ul>
-      <li>Context</li>
-      <li>TaskQueue
-        <ul>
-          <li>実行される Task のリストを扱う</li>
-        </ul>
-      </li>
-      <li>Persistent Data Tree
-        <ul>
-          <li>Code Gear によって参照される Data Gear の管理を行う</li>
-        </ul>
-      </li>
+      <li>Task(Context)</li>
       <li>Worker
         <ul>
-          <li>TaskQueue から Task を取得し、実行する</li>
+          <li>Queue から Task を取得し、実行する</li>
         </ul>
       </li>
       <li>TaskManager
@@ -489,55 +337,21 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="taskqueue">TaskQueue</h2>
-<ul>
-  <li>Task Queue は Task のリストを扱う</li>
-  <li>すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li>
-  <li>TaskQueue は 2つで Data Gear で表現される
-    <ul>
-      <li>先頭と末尾の要素を持った Queue 表す Data Gear</li>
-      <li>Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear</li>
-    </ul>
-  </li>
-</ul>
-
-<pre lang="c"><code>// Data Gear define
-union Data {
-    struct Queue {
-        struct Element* first;
-        struct Element* last;
-    } queue;
-
-    struct Element {
-        struct Task* task;
-        struct Elemen* next;
-    } element
-};
-</code></pre>
+<h2 id="taskcontext">Task(Context)</h2>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="taskqueueenqueue">TaskQueueの操作(Enqueue)</h2>
+<h2 id="taskmanger">TaskManger</h2>
 <ul>
-  <li>Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定</li>
-  <li>正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある</li>
+  <li>初期化時に決まった数の Worker を作成</li>
+  <li>依存関係を解決した Task を各 Worker の Queue に送信する</li>
 </ul>

-<pre lang="c"><code>__code putQueue3(struct Queue* queue, struct Element* new_element) {
-    struct Element* last = queue-&gt;last;
-
-    if (__sync_bool_compare_and_swap(&amp;queue-&gt;last, last, new_element)) {
-        last-&gt;next = new_element;
-
-        goto exit();
-    } else {
-        goto putQueue3(queue, new_element);
-    }
-}
-
-</code></pre>
+<div style="text-align: center;">
+    <img src="./images/taskManager.svg" alt="message" width="800" />
+</div>


 </div>
@@ -567,7 +381,6 @@
     </tr>
   </tbody>
 </table>
-
 <ul>
   <li>Task が完了したら次の Task を取得する</li>
 </ul>
@@ -576,21 +389,43 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="taskmanger">TaskManger</h2>
+<h2 id="synchronized-queue">Synchronized Queue</h2>
 <ul>
-  <li>TaskManager は Task の依存関係の解決を行う</li>
-  <li>Thread の作成と停止も行う</li>
+  <li>Task Queue は Task のリストを扱う</li>
+  <li>Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li>
+  <li>TaskQueue は 2つで Data Gear で表現される
+    <ul>
+      <li>先頭と末尾の要素を持った Queue 表す Data Gear</li>
+      <li>Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear</li>
+    </ul>
+  </li>
 </ul>

-<div style="text-align: center;">
-    <img src="./images/taskManager.svg" alt="message" width="800" />
-</div>
-

 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-3">プロトタイプの実行</h2>
+<h2 id="section-2">依存関係の解決</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-3">データ並列</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="cuda-">CUDA への対応</h2>
+<p>## CUDA Worker
+## CUDA Executor</p>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="gears-os-">Gears OS の評価</h2>
 <ul>
   <li>今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った</li>
   <li>これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった</li>
@@ -600,9 +435,24 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="gears-os--code-gear-">Gears OS で実行する Code Gear 例</h2>
+<h2 id="section-4">実験環境</h2>
 <ul>
-  <li>プロトタイプのタスクの例題として Twice を実装した</li>
+  <li>CPU 環境
+    <ul>
+      <li>Memory : 16GB</li>
+      <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li>
+    </ul>
+  </li>
+  <li>GPU 環境</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="twice">Twice</h2>
+<ul>
+  <li>タスクの例題として Twice と BitonicSort を実装した</li>
   <li>Twice は与えられた整数配列を2倍にする例題である</li>
 </ul>

@@ -627,19 +477,19 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-4">並列処理の確認</h2>
-<ul>
-  <li>Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った</li>
-  <li>環境
-    <ul>
-      <li>Memory : 16GB</li>
-      <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li>
-    </ul>
-  </li>
-  <li>要素数 : 2^17 * 1000</li>
-  <li>分割数 : 640 タスク</li>
-  <li>1 Task 当たりの処理量 : 2^11 * 100 elements</li>
-</ul>
+<h2 id="twice-">Twice の結果</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="bitonicsort">BitonicSort</h2>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="bitonicsort-">BitonicSort の結果</h2>

 <table border="1" align="center" width="50%">
   <tbody>
@@ -678,32 +528,13 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="cerium-">Cerium との比較</h2>
-<ul>
-  <li>Cerium は本研究室で開発していた並列プログラミングフレームワーク</li>
-  <li>Cerium では Task を依存関係に沿って実行することで並列実行を可能にする
-    <ul>
-      <li>本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない</li>
-      <li>Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる</li>
-    </ul>
-  </li>
-  <li>Task には汎用ポインタとしてデータの受け渡しを行う
-    <ul>
-      <li>型情報がなく、型の検査を行うことが出来ない</li>
-      <li>Gears OS では 型情報をもつ Data Gear を定義</li>
-    </ul>
-  </li>
-</ul>
+<h2 id="openmp-">OpenMP との比較</h2>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="os-">既存の OS への対応</h2>
-<ul>
-  <li>Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義</li>
-  <li>通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う</li>
-</ul>
+<h2 id="go-">Go との比較</h2>


 </div>
--- a/slide/slide.md	Sat Feb 10 00:19:52 2018 +0900
+++ b/slide/slide.md	Sat Feb 10 03:01:54 2018 +0900
@@ -3,20 +3,20 @@
 profile: 琉球大学理工学研究科 河野研
 lang: Japanese
 code-engine: coderay
+
 ## Gears OS
 - 並列処理のチューニングや信頼性を保証するのは難しい
     - スレッド間の共通資源の競合などの非決定的な実行
     - 従来のテストやデバッグではテストしきれない部分が残ってしまう
 - Gears OS では計算をノーマルレベルとメタレベルに階層化
-    - ノーマルレベルの計算に対してメタレベルで信頼性を保証したい
-    - メタレベルの計算はデータ拡張や実行環境の切り替え等の拡張性のための計算を行う
+    - 信頼性と拡張性をメタレベルで保証する

 ## Code Gear、 Data Gear
 - Gears OS は Code Gear、 Data Gear という Gear で構成される
 - Code Gear はプログラムの処理そのものを表す
 - Data Gear はデータそのものを表す
-- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
-- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Input Data Gear が揃った Code Gear の並列実行を行う
+- Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する
+- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う

 <div style="text-align: center;">
     <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
@@ -50,8 +50,9 @@

 ## メタ計算
 - メタ計算 は通常の計算を実行するための計算
-- 信頼性の確保やメモリ管理、スレッド管理、 CPU、 GPU の資源管理等
+- 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等
 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる
+- メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる

 ## Meta Gear
 - メタ計算 は Code Gearの接続の間に行われる
@@ -95,22 +96,12 @@
 };
 ```

-## Code Gear の stub
+## Code Gear の stub Code Gear
 - Data Gear にアクセスするにはContext を経由する
 - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
-- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
-- stub は一種の Meta Code Gear であるため、 CbC で自動生成される
-- このコードでは Array と LoopCounter が必要な code1 の stub を示している
+- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub 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);
-}
 ```

 ## Context での stub Code Gear の記述の問題点
@@ -121,64 +112,36 @@

 ## Interface
 - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
-- これは Context より小さい集合のため、 stub Code Gear での各API で決まった形になる
+- stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である
 - Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る
 - Interface は Java のインターフェース、 Haskell の型クラスに対応する
-## プロトタイプ の構成
+
+## Interface の定義
+
+## Interface の実装
+
+## Interface を利用した Code Gear の呼び出し
+
+## 並列処理の構成
 - 今回は並列処理を行う機構の実装を行う
-- 必要な要素は大きく5つ
-    - Context
-    - TaskQueue
-        - 実行される Task のリストを扱う
-    - Persistent Data Tree
-        - Code Gear によって参照される Data Gear の管理を行う
+- 構成要素
+    - Task(Context)
     - Worker
-        -  TaskQueue から Task を取得し、実行する
+        -  Queue から Task を取得し、実行する
     - TaskManager
         - Persistent Data Tree を監視し、 Task の依存関係を解決する

 ※ TaskManager は今回未実装

-## TaskQueue
-- Task Queue は Task のリストを扱う
-- すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
-- TaskQueue は 2つで Data Gear で表現される
-    - 先頭と末尾の要素を持った Queue 表す Data Gear
-    - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
-
-``` c
-// Data Gear define
-union Data {
-    struct Queue {
-        struct Element* first;
-        struct Element* last;
-    } queue;
+## Task(Context)

-    struct Element {
-        struct Task* task;
-        struct Elemen* next;
-    } element
-};
-```
-
-## TaskQueueの操作(Enqueue)
-- Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
-- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
+## TaskManger
+- 初期化時に決まった数の Worker を作成
+- 依存関係を解決した Task を各 Worker の Queue に送信する

-``` c
-__code putQueue3(struct Queue* queue, struct Element* new_element) {
-    struct Element* last = queue->last;
-
-    if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
-        last->next = new_element;
-
-        goto exit();
-    } else {
-        goto putQueue3(queue, new_element);
-    }
-}
-
-```
+<div style="text-align: center;">
+    <img src="./images/taskManager.svg" alt="message" width="800">
+</div>

 ## Worker
 - Worker は TaskQueue から Task を取得して実行する
@@ -202,24 +165,35 @@
     </tr>
   </tbody>
 </table>
-
 - Task が完了したら次の Task を取得する

-## TaskManger
-- TaskManager は Task の依存関係の解決を行う
-- Thread の作成と停止も行う
+## Synchronized Queue
+- Task Queue は Task のリストを扱う
+- Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
+- TaskQueue は 2つで Data Gear で表現される
+    - 先頭と末尾の要素を持った Queue 表す Data Gear
+    - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear

-<div style="text-align: center;">
-    <img src="./images/taskManager.svg" alt="message" width="800">
-</div>
+## 依存関係の解決
+
+## データ並列

+## CUDA への対応
+## CUDA Worker
+## CUDA Executor

-## プロトタイプの実行
+## Gears OS の評価
 - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
 - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった

-## Gears OS で実行する Code Gear 例
-- プロトタイプのタスクの例題として Twice を実装した
+## 実験環境
+- CPU 環境
+    - Memory : 16GB
+    - CPU : 6-core Intel Xeon 2.66GHZ x 2
+- GPU 環境
+
+## Twice
+- タスクの例題として Twice と BitonicSort を実装した
 - Twice は与えられた整数配列を2倍にする例題である

 ``` c
@@ -240,14 +214,11 @@
 }
 ```

-## 並列処理の確認
-- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
-- 環境
-    - Memory : 16GB
-    - CPU : 6-core Intel Xeon 2.66GHZ x 2
-- 要素数 : 2^17 * 1000
-- 分割数 : 640 タスク
-- 1 Task 当たりの処理量 : 2^11 * 100 elements
+## Twice の結果
+
+## BitonicSort
+
+## BitonicSort の結果

 <table  border="1" align='center' width='50%'>
   <tbody>
@@ -280,19 +251,9 @@

 - 1cpu と 12cpu では 11.8 倍の向上が見られた

+## OpenMP との比較

-## Cerium との比較
-- Cerium は本研究室で開発していた並列プログラミングフレームワーク
-- Cerium では Task を依存関係に沿って実行することで並列実行を可能にする
-    - 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない
-    - Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
-- Task には汎用ポインタとしてデータの受け渡しを行う
-    - 型情報がなく、型の検査を行うことが出来ない
-    - Gears OS では 型情報をもつ Data Gear を定義
-
-## 既存の OS への対応
-- Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
-- 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う
+## Go との比較

 ## まとめ
 - Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った