Mercurial > hg > Papers > 2017 > ikkun-sigos

Binary file paper/.DS_Store has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/sigos.txt	Tue May 16 13:56:24 2017 +0900
@@ -0,0 +1,56 @@
+@article{
+    cerium,
+    author = "宮國 渡 and 河野 真治 and 神里 晃 and 杉山 千秋",
+    title = "Cell 用の Fine-grain Task Manager の実装",
+    journal = "情報処理学会 システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "April",
+    year = 2008
+}
+
+@article{
+    alice,
+    author = "照屋 のぞみ and 河野 真治",
+    title = "分散フレームワークAliceのPC画面配信システムへの応用",
+    journal = "第57回プログラミング・シンポジウム",
+    month = "Jan",
+    year = 2016
+}
+
+@article{
+    segment,
+    author = "河野 真治 and 杉本 優",
+    title = "Code Segment と Data Segment によるプログラミング手法",
+    journal = "第54回プログラミング・シンポジウム",
+    month = "Jan",
+    year = 2013
+}
+
+
+@manual{opencl,
+author = "{Aaftab Munshi, Khronos OpenCL Working Group}",
+title ="{The OpenCL Specification Version 1.0}",
+year = 2007
+}
+
+@misc{cuda,
+    title = "{CUDA}",
+    howpublished = "{https://developer.nvidia.com/category/zone/cuda-zone/}"
+}
+
+@article{
+    gears,
+    author = "小久保 翔平 and 伊波 立樹 and 河野 真治",
+    title = "Monad に基づくメタ計算を基本とする Gears OS の設計",
+    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "May",
+    year = 2015
+}
+
+@article{
+    cbc-lola,
+    author = "Kaito TOKKMORI and Shinji KONO",
+    title = "Implementing Continuation based language in LLVM and Clang",
+    journal = "LOLA 2015",
+    month = "July",
+    year = 2015
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/sigos.html	Tue May 16 13:56:24 2017 +0900
@@ -0,0 +1,90 @@
+<!DOCTYPE html>
+<html>
+<head>
+   <meta http-equiv="content-type" content="text/html;charset=utf-8">
+   <title>Gears OSにおける並列処理</title>
+
+<meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 1.9.3 (2011-10-30) [x86_64-darwin10]">
+<meta name="author"    content="東恩納 琢偉" >
+
+<!-- style sheet links -->
+<link rel="stylesheet" href="s6/themes/projection.css"   media="screen,projection">
+<link rel="stylesheet" href="s6/themes/screen.css"       media="screen">
+<link rel="stylesheet" href="s6/themes/print.css"        media="print">
+<link rel="stylesheet" href="s6/themes/blank.css"        media="screen,projection">
+
+<!-- JS -->
+<script src="s6/js/jquery-1.11.3.min.js"></script>
+<script src="s6/js/jquery.slideshow.js"></script>
+<script src="s6/js/jquery.slideshow.counter.js"></script>
+<script src="s6/js/jquery.slideshow.controls.js"></script>
+<script src="s6/js/jquery.slideshow.footer.js"></script>
+<script src="s6/js/jquery.slideshow.autoplay.js"></script>
+
+<!-- prettify -->
+<link rel="stylesheet" href="scripts/prettify.css">
+<script src="scripts/prettify.js"></script>
+
+<script>
+  $(document).ready( function() {
+    Slideshow.init();
+
+    $('code').each(function(_, el) {
+      if (!el.classList.contains('noprettyprint')) {
+        el.classList.add('prettyprint');
+        el.style.display = 'block';
+      }
+    });
+    prettyPrint();
+  } );
+
+
+</script>
+
+<!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
+<!--[if IE]>
+<script src="s6/js/jquery.microsoft.js"></script>
+<![endif]-->
+
+
+
+</head>
+<body>
+
+<div class="layout">
+  <div id="header"></div>
+  <div id="footer">
+    <div align="right">
+      <img src="s6/images/logo.svg" width="200px">
+    </div>
+  </div>
+</div>
+
+<div class="presentation">
+
+  <div class='slide cover'>
+    <table width="90%" height="90%" border="0" align="center">
+      <tr>
+        <td>
+          <div align="center">
+            <h1><font color="#808db5">Gears OSにおける並列処理</font></h1>
+          </div>
+        </td>
+      </tr>
+      <tr>
+        <td>
+          <div align="left">
+            東恩納 琢偉
+            琉球大学理工学研究科
+            <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
+          </div>
+        </td>
+      </tr>
+    </table>
+  </div>
+
+
+
+</div><!-- presentation -->
+</body>
+</html>
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/sigos.md	Tue May 16 13:56:24 2017 +0900
@@ -0,0 +1,463 @@
+title: Gears OSにおける並列処理
+author: 東恩納 琢偉
+profile: 琉球大学理工学研究科
+lang: Japanese
+code-engine: coderay
+## Gears OS
+- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて分けることによって
+    - 並列性
+    - 柔軟性
+    - 信頼性
+
+を指標とした Gears OS を設計してきた
+
+- 本研究では Gears OS のプロトタイプとして並列処理機構を Continuation based C(CbC) で実装を行う
+
+## Gears OS の並列性
+- Gears OS はプログラムの単位として Gear を用いる
+- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある
+- Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能
+
+<div style="text-align: center;">
+    <img src="./images/codeGear_dataGear.svg" alt="message" width="450">
+</div>
+
+## Gears OS の柔軟性
+- Gears OS は Meta Computation を使用することで
+    - データ拡張や機能の追加
+    - GPU 等のさまざまなアーキテクチャでも同じプログラムの動作
+    - バージョンが異なる者同士がネットワーク接続しても通信
+
+等を柔軟に対応する
+
+- Meta Computation は 通常の Computaiton と階層を分けて処理を行う
+
+<div style="text-align: center;">
+    <img src="./images/meta_gear.svg" alt="message" width="800">
+</div>
+
+## Gears OS の信頼性
+- 検証
+    - モデル検査を行う
+    - モデル検査は状態の数が膨大になると検査するのが難しい
+    - そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う
+- 証明
+    - Code Gear と Data Gear を理論的に定義
+
+## この発表は
+- Gears OS でのGear
+- Meta Computation
+- Continuation based C(CbC)
+- CbC を用いた Gears OS の記述
+- Gears OS の並列処理のプロトタイプ
+- まとめ
+- 課題
+
+## Code Gear、 Data Gear
+- Gears OS は Code Gear、 Data Gear という Gear で構成される
+- Code Gear はプログラムの処理そのものを表す
+- Data Gear は int や 文字列などの Data そのものを表す
+- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
+- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う
+
+<div style="text-align: center;">
+    <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
+</div>
+
+
+## Meta Computation
+- Meta Computation は通常の Computation のための Computation
+- 並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理などを行う
+- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現
+
+## Meta Gear
+- Meta Computation は Code/Data Gearの接続の間に行われる
+- Meta Computation の処理も Code/Data Gear で実現する
+- この Gear を Meta Code/Data Gearと呼ぶ
+    - Meta Code Gear は Meta Computation のプログラム部分
+    - Meta Data Gear は Meta Code Gear で管理されるデータ部分
+- Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う
+
+<div style="text-align: center;">
+    <img src="./images/meta_cg_dg.svg" alt="message" width="850">
+</div>
+
+
+## Continuation based C
+- Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる
+- CbC は処理を Code Segment を用いて記述する事を基本とする
+- Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している
+
+## Continuation based C
+- Code Segment の定義は ``__code CS名`` で行う
+- Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
+- Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
+    - このような環境を持たない継続を軽量継続と呼ぶ
+
+## Continuation based C
+- このコードは code1、code2 の2つの Code Segment を定義している
+- code1 内の ``goto code2`` でcode2 への継続を行っている
+
+``` c
+/* code1 define */
+__code code1(List list) {
+    ....
+    goto code2(list)
+}
+
+/* code2 define */
+__code code2(List list) {
+    ...
+}
+```
+
+## CbC を用いた Gears OS の記述
+- Gears OS での Code Gear も  Code Segment の定義のように記述する
+- 各 Code Gear の引数は 必要な Data Gear を示す
+- このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている
+
+``` c
+__code code1(struct Array* array, struct LoopCounter* loopCounter) {
+    ...
+    goto code2(array);
+}
+
+__code meta_code1(struct Context* context, enum Code next) {
+    goto (context->code[next])(context);
+}
+
+__code code2(struct Array* array) {
+    ...
+}
+```
+
+## CbC の Gears OS サポート
+- 実際は code1 から code2 への継続の間には Meta Code Gear である meta_code1 が実行される
+- 通常は Meta Level の継続をプログラマーは意識する必要はない
+- そこで、CbC は Code Gear 間の接続に自動的に Meta Code Gear を挟むというサポートを行う
+- CbC のサポートを行うとこのコードのように展開される
+- メタレベルのサポートの際は **context** という Meta Data Gear を使用する
+
+``` c
+__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
+    ...
+    goto meta_code1(context, Code2);
+}
+
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
+}
+
+__code meta_code1(struct Context* context, enum Code next) {
+    goto (context->code[next])(context);
+}
+
+__code code2(struct Context* context, struct Array* array) {
+    ...
+}
+```
+
+## Context
+- Context は
+    - 接続可能な Code/Data Gear のリスト
+    - 独立したメモリ空間
+をもっている
+
+- 各 Code/Data Gear にアクセスする際は Context を経由する
+
+## Context
+- Context は
+    - 実行可能な Code Gear の数を示す **codeNum**
+    - 実行可能な Code Gear のリストを示す **code**
+    - Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit**
+    - Data Gear の数を示す **dataNum**
+    - Data Gear のリストを示す **data**
+で構成される
+
+``` c
+/* context define */
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+```
+
+## Context
+- 実行可能な Code Gear の名前は **enum code** で定義する
+- Context の初期化時に名前と関数ポインタを対応付ける
+- 現在の Gears ではこの enum code 使って接続先の Code Gear を指定する
+
+``` c
+enum Code {
+    Code1,
+    Code2,
+    Code3,
+    Exit,
+};
+```
+
+## Data Gear の表現
+- 使用する Data Gear は C の共用体と構造体を用いた表現をする
+- これを元に Gears OS は 必要な Data Gear を allocate する
+
+``` c
+/* data Gear define */
+union Data {
+    struct Time {
+        enum Code next;
+        double time;
+    } time;
+    struct LoopCounter {
+        int i;
+    } loopCounter;
+    ....
+};
+```
+
+## Code Gear の stub
+- Data Gear にアクセスするにはContext を経由する
+- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
+- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
+- stub は一種の Meta Code Gear であるため、 CbC で自動生成される
+- このコードでは Array と LoopCounter が必要な code1 の stub を示している
+
+``` 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);
+}
+```
+
+## プロトタイプ の構成
+- 今回は並列処理を行う機構の実装を行う
+- 必要な要素は大きく5つ
+    - Context
+    - TaskQueue
+        - 実行される Task のリストを扱う
+    - Persistent Data Tree
+        - Code Gear によって参照される Data Gear の管理を行う
+    - Worker
+        -  TaskQueue から 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;
+
+    struct Element {
+        struct Task* task;
+        struct Elemen* next;
+    } element
+};
+```
+
+## TaskQueueの操作(Enqueue)
+- Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
+- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
+
+``` 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);
+    }
+}
+
+```
+
+## Persistent Data Tree
+- Persistent Data Tree は Data Gear の管理を行う
+- TaskQueue と同じですべての Thread で共有される
+- Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
+- 木構造から読み出される Data Gear は Code Gear の Input Data Gear, 書き出すData Gear は Output Data Gear になる
+
+<div style="text-align: center;">
+    <img src="./images/persistent_date_tree_2.svg" alt="message" width="800">
+</div>
+
+## Persistent Data Tree
+- Persistent Data Tree は
+    - Tree 自体を示す Data Gear
+    - Node を示す Data Gear
+
+を用いて木構造を表現する
+
+``` c
+union Data {
+    struct Tree {
+        struct Node* root;
+    } tree;
+    struct Node {
+        int key; // comparable data segment
+        union Data* value;
+        struct Node* left;
+        struct Node* right;
+        // need to balancing
+        enum Color {
+            Red,
+            Black,
+        } color;
+    } node;
+};
+```
+
+
+## Worker
+- Worker は TaskQueue から Task を取得して実行する
+
+<table align='center'>
+  <tbody>
+    <tr>
+      <td>
+        <div>
+            <img src="./images/worker.svg" alt="message" width="600">
+        </div>
+     </td>
+     <td>
+        <ol>
+            <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
+            <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
+            <li> Task に格納されている Code Gear を実行する </li>
+            <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
+        </ol>
+     </td>
+    </tr>
+  </tbody>
+</table>
+
+- Task が完了したら次の Task を取得する
+
+## TaskManger
+- TaskManager は Task の依存関係の解決を行う
+- Thread の作成と停止も行う
+
+<div style="text-align: center;">
+    <img src="./images/taskManager.svg" alt="message" width="800">
+</div>
+
+
+## プロトタイプの実行
+- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
+- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
+
+## Gears OS で実行する Code Gear 例
+- プロトタイプのタスクの例題として Twice を実装した
+- Twice は与えられた整数配列を2倍にする例題である
+
+``` c
+// Twice Code Gear
+__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
+    int i = loopCounter->i;
+
+    if (i < alignment) {
+        array[i+index*alignment] = array[i+index*alignment]*2;
+        loopCounter->i++;
+
+        goto twice(loopCounter, index, alignment, array);
+    }
+
+    loopCounter->i = 0;
+
+    goto exit();
+}
+```
+
+## 並列処理の確認
+- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
+- 環境
+    - Memory : 16GB
+    - CPU : 6-core Intel Xeon 2.66GHZ x 2
+- 要素数 : 2^17 * 1000
+- 分割数 : 640 タスク
+- 1 Task 当たりの処理量 : 2^11 * 100 elements
+
+<table  border="1" align='center' width='50%'>
+  <tbody>
+    <tr>
+      <td style="text-align: center;">Number of Processors</td>
+      <td style="text-align: center;">Time(ms)</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">1 CPU</td>
+      <td style="text-align: right;">1315</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">2 CPUs</td>
+      <td style="text-align: right;">689</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">4 CPUs</td>
+      <td style="text-align: right;">366</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">8 CPUs</td>
+      <td style="text-align: right;">189</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">12 CPUs</td>
+      <td style="text-align: right;">111</td>
+    </tr>
+  </tbody>
+</table>
+
+- 1cpu と 12cpu では 11.8 倍の向上が見られた
+
+
+## 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が行ってきた制御の提供を行う
+
+## まとめ
+- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
+- 依存関係のない Twice を実装し、並列処理が行えることを確認した
+
+## 今後の課題
+- 一般的に並列処理には依存関係が存在する
+    - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、  依存関係のある並列処理の例題を作成し、評価する
+- GPUなどの他のプロセッサ演算に利用することが出来ない
+    - Data Gear などのデータをGPUにマッピングするための機構が必要
+- Gears OS でのデバック手法
+    - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案
+    - 並列処理でのデバック手法も考案する必要がある
+- 型情報の検査
+    - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する
+- Contextの動的生成
+    - 今は静的に自分で生成している
+    - CbC 用の Runtime をつくり、 Context を動的に生成
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/sigos.md~	Tue May 16 13:56:24 2017 +0900
@@ -0,0 +1,463 @@
+title: Gears OSにおける並列処理
+author: 東恩納 琢偉
+profile: 琉球大学理工学研究科
+lang: Japanese
+code-engine: coderay
+## Gears OS
+- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて
+    - 並列性
+    - 柔軟性
+    - 信頼性
+
+を指標とした Gears OS を設計してきた
+
+- 本研究では Gears OS のプロトタイプとして並列処理機構を Continuation based C(CbC) で実装を行う
+
+## Gears OS の並列性
+- Gears OS はプログラムの単位として Gear を用いる
+- Gear には プログラムの処理を示す Code Gear、 Data を示す Data Gear がある
+- Code/Data Gear を用いて記述することでプログラム全体の並列度を高め、効率的に並列処理することが可能
+
+<div style="text-align: center;">
+    <img src="./images/codeGear_dataGear.svg" alt="message" width="450">
+</div>
+
+## Gears OS の柔軟性
+- Gears OS は Meta Computation を使用することで
+    - データ拡張や機能の追加
+    - GPU 等のさまざまなアーキテクチャでも同じプログラムの動作
+    - バージョンが異なる者同士がネットワーク接続しても通信
+
+等を柔軟に対応する
+
+- Meta Computation は 通常の Computaiton と階層を分けて処理を行う
+
+<div style="text-align: center;">
+    <img src="./images/meta_gear.svg" alt="message" width="800">
+</div>
+
+## Gears OS の信頼性
+- 検証
+    - モデル検査を行う
+    - モデル検査は状態の数が膨大になると検査するのが難しい
+    - そのため、不必要な状態である環境やスタックをなるべく取り除き、処理を行う
+- 証明
+    - Code Gear と Data Gear を理論的に定義
+
+## この発表は
+- Gears OS でのGear
+- Meta Computation
+- Continuation based C(CbC)
+- CbC を用いた Gears OS の記述
+- Gears OS の並列処理のプロトタイプ
+- まとめ
+- 課題
+
+## Code Gear、 Data Gear
+- Gears OS は Code Gear、 Data Gear という Gear で構成される
+- Code Gear はプログラムの処理そのものを表す
+- Data Gear は int や 文字列などの Data そのものを表す
+- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
+- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を行う
+
+<div style="text-align: center;">
+    <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
+</div>
+
+
+## Meta Computation
+- Meta Computation は通常の Computation のための Computation
+- 並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理などを行う
+- Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現
+
+## Meta Gear
+- Meta Computation は Code/Data Gearの接続の間に行われる
+- Meta Computation の処理も Code/Data Gear で実現する
+- この Gear を Meta Code/Data Gearと呼ぶ
+    - Meta Code Gear は Meta Computation のプログラム部分
+    - Meta Data Gear は Meta Code Gear で管理されるデータ部分
+- Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う
+
+<div style="text-align: center;">
+    <img src="./images/meta_cg_dg.svg" alt="message" width="850">
+</div>
+
+
+## Continuation based C
+- Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる
+- CbC は処理を Code Segment を用いて記述する事を基本とする
+- Code Segment は Code Gear を同等のものため、 Gears OS を記述するのに適している
+
+## Continuation based C
+- Code Segment の定義は ``__code CS名`` で行う
+- Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
+- Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
+    - このような環境を持たない継続を軽量継続と呼ぶ
+
+## Continuation based C
+- このコードは code1、code2 の2つの Code Segment を定義している
+- code1 内の ``goto code2`` でcode2 への継続を行っている
+
+``` c
+/* code1 define */
+__code code1(List list) {
+    ....
+    goto code2(list)
+}
+
+/* code2 define */
+__code code2(List list) {
+    ...
+}
+```
+
+## CbC を用いた Gears OS の記述
+- Gears OS での Code Gear も  Code Segment の定義のように記述する
+- 各 Code Gear の引数は 必要な Data Gear を示す
+- このコードでは 2つの Code Gear と 1つの Meta Code Gear を定義しており、 code1 から code2への継続を行っている
+
+``` c
+__code code1(struct Array* array, struct LoopCounter* loopCounter) {
+    ...
+    goto code2(array);
+}
+
+__code meta_code1(struct Context* context, enum Code next) {
+    goto (context->code[next])(context);
+}
+
+__code code2(struct Array* array) {
+    ...
+}
+```
+
+## CbC の Gears OS サポート
+- 実際は code1 から code2 への継続の間には Meta Code Gear である meta_code1 が実行される
+- 通常は Meta Level の継続をプログラマーは意識する必要はない
+- そこで、CbC は Code Gear 間の接続に自動的に Meta Code Gear を挟むというサポートを行う
+- CbC のサポートを行うとこのコードのように展開される
+- メタレベルのサポートの際は **context** という Meta Data Gear を使用する
+
+``` c
+__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
+    ...
+    goto meta_code1(context, Code2);
+}
+
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
+}
+
+__code meta_code1(struct Context* context, enum Code next) {
+    goto (context->code[next])(context);
+}
+
+__code code2(struct Context* context, struct Array* array) {
+    ...
+}
+```
+
+## Context
+- Context は
+    - 接続可能な Code/Data Gear のリスト
+    - 独立したメモリ空間
+をもっている
+
+- 各 Code/Data Gear にアクセスする際は Context を経由する
+
+## Context
+- Context は
+    - 実行可能な Code Gear の数を示す **codeNum**
+    - 実行可能な Code Gear のリストを示す **code**
+    - Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit**
+    - Data Gear の数を示す **dataNum**
+    - Data Gear のリストを示す **data**
+で構成される
+
+``` c
+/* context define */
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+```
+
+## Context
+- 実行可能な Code Gear の名前は **enum code** で定義する
+- Context の初期化時に名前と関数ポインタを対応付ける
+- 現在の Gears ではこの enum code 使って接続先の Code Gear を指定する
+
+``` c
+enum Code {
+    Code1,
+    Code2,
+    Code3,
+    Exit,
+};
+```
+
+## Data Gear の表現
+- 使用する Data Gear は C の共用体と構造体を用いた表現をする
+- これを元に Gears OS は 必要な Data Gear を allocate する
+
+``` c
+/* data Gear define */
+union Data {
+    struct Time {
+        enum Code next;
+        double time;
+    } time;
+    struct LoopCounter {
+        int i;
+    } loopCounter;
+    ....
+};
+```
+
+## Code Gear の stub
+- Data Gear にアクセスするにはContext を経由する
+- だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
+- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
+- stub は一種の Meta Code Gear であるため、 CbC で自動生成される
+- このコードでは Array と LoopCounter が必要な code1 の stub を示している
+
+``` 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);
+}
+```
+
+## プロトタイプ の構成
+- 今回は並列処理を行う機構の実装を行う
+- 必要な要素は大きく5つ
+    - Context
+    - TaskQueue
+        - 実行される Task のリストを扱う
+    - Persistent Data Tree
+        - Code Gear によって参照される Data Gear の管理を行う
+    - Worker
+        -  TaskQueue から 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;
+
+    struct Element {
+        struct Task* task;
+        struct Elemen* next;
+    } element
+};
+```
+
+## TaskQueueの操作(Enqueue)
+- Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
+- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
+
+``` 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);
+    }
+}
+
+```
+
+## Persistent Data Tree
+- Persistent Data Tree は Data Gear の管理を行う
+- TaskQueue と同じですべての Thread で共有される
+- Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
+- 木構造から読み出される Data Gear は Code Gear の Input Data Gear, 書き出すData Gear は Output Data Gear になる
+
+<div style="text-align: center;">
+    <img src="./images/persistent_date_tree_2.svg" alt="message" width="800">
+</div>
+
+## Persistent Data Tree
+- Persistent Data Tree は
+    - Tree 自体を示す Data Gear
+    - Node を示す Data Gear
+
+を用いて木構造を表現する
+
+``` c
+union Data {
+    struct Tree {
+        struct Node* root;
+    } tree;
+    struct Node {
+        int key; // comparable data segment
+        union Data* value;
+        struct Node* left;
+        struct Node* right;
+        // need to balancing
+        enum Color {
+            Red,
+            Black,
+        } color;
+    } node;
+};
+```
+
+
+## Worker
+- Worker は TaskQueue から Task を取得して実行する
+
+<table align='center'>
+  <tbody>
+    <tr>
+      <td>
+        <div>
+            <img src="./images/worker.svg" alt="message" width="600">
+        </div>
+     </td>
+     <td>
+        <ol>
+            <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
+            <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
+            <li> Task に格納されている Code Gear を実行する </li>
+            <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
+        </ol>
+     </td>
+    </tr>
+  </tbody>
+</table>
+
+- Task が完了したら次の Task を取得する
+
+## TaskManger
+- TaskManager は Task の依存関係の解決を行う
+- Thread の作成と停止も行う
+
+<div style="text-align: center;">
+    <img src="./images/taskManager.svg" alt="message" width="800">
+</div>
+
+
+## プロトタイプの実行
+- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
+- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
+
+## Gears OS で実行する Code Gear 例
+- プロトタイプのタスクの例題として Twice を実装した
+- Twice は与えられた整数配列を2倍にする例題である
+
+``` c
+// Twice Code Gear
+__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
+    int i = loopCounter->i;
+
+    if (i < alignment) {
+        array[i+index*alignment] = array[i+index*alignment]*2;
+        loopCounter->i++;
+
+        goto twice(loopCounter, index, alignment, array);
+    }
+
+    loopCounter->i = 0;
+
+    goto exit();
+}
+```
+
+## 並列処理の確認
+- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
+- 環境
+    - Memory : 16GB
+    - CPU : 6-core Intel Xeon 2.66GHZ x 2
+- 要素数 : 2^17 * 1000
+- 分割数 : 640 タスク
+- 1 Task 当たりの処理量 : 2^11 * 100 elements
+
+<table  border="1" align='center' width='50%'>
+  <tbody>
+    <tr>
+      <td style="text-align: center;">Number of Processors</td>
+      <td style="text-align: center;">Time(ms)</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">1 CPU</td>
+      <td style="text-align: right;">1315</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">2 CPUs</td>
+      <td style="text-align: right;">689</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">4 CPUs</td>
+      <td style="text-align: right;">366</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">8 CPUs</td>
+      <td style="text-align: right;">189</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">12 CPUs</td>
+      <td style="text-align: right;">111</td>
+    </tr>
+  </tbody>
+</table>
+
+- 1cpu と 12cpu では 11.8 倍の向上が見られた
+
+
+## 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が行ってきた制御の提供を行う
+
+## まとめ
+- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
+- 依存関係のない Twice を実装し、並列処理が行えることを確認した
+
+## 今後の課題
+- 一般的に並列処理には依存関係が存在する
+    - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、  依存関係のある並列処理の例題を作成し、評価する
+- GPUなどの他のプロセッサ演算に利用することが出来ない
+    - Data Gear などのデータをGPUにマッピングするための機構が必要
+- Gears OS でのデバック手法
+    - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案
+    - 並列処理でのデバック手法も考案する必要がある
+- 型情報の検査
+    - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する
+- Contextの動的生成
+    - 今は静的に自分で生成している
+    - CbC 用の Runtime をつくり、 Context を動的に生成