Mercurial > hg > Papers > 2015 > kkb-sigos

--- a/presen/index.html	Mon May 25 17:19:29 2015 +0900
+++ b/presen/index.html	Tue May 26 03:46:51 2015 +0900
@@ -19,7 +19,7 @@
 			<header>
 				<h2>Monad に基づくメタ計算を基本とする Gears OS の設計</h2>
 				<h3 id="author">小久保翔平</h3>
-				<h3 id="profile"></h3>
+				<h3 id="profile">琉球大学大学院修士2年</h3>
 			</header>
 		</section>
 	</div></div>
@@ -30,26 +30,26 @@
 <div class="slide" id="2"><div>
 		<section>
 			<header>
-				<h1 id="section">研究目的</h1>
+				<h1 id="gears-os-">Gears OS の並列性</h1>
 			</header>
 			<!-- === begin markdown block ===

       generated by markdown 1.1.1 on Ruby 2.0.0 (2013-02-24) [x86_64-darwin12.3.0]
-                on 2015-05-25 16:50:33 +0900 with Markdown engine kramdown (1.4.0)
+                on 2015-05-26 03:46:41 +0900 with Markdown engine kramdown (1.4.0)
                   using options {}
   -->

 <!-- _S9SLIDE_ -->

-<p>Many Core CPU, GPU, SpursEngine などの異なる演算資源を有効に利用するためには、それぞれのアーキテクチャに合わせた記述が必要になる。
-Gears OS は Many Core CPU, GPU といった並列環境に合わせた設計・開発を行う</p>
+<p>処理とデータの単位として Code Gear, Data Gear を用いる</p>
+
+<p>　並列実行の単位となる</p>

-<p>Gears OS では Gear という単位を用いて記述することで柔軟性のあるプログラムを作成することを可能とする。
-新たな Gear を接続することでデータの拡張や機能の追加を行うことができる</p>
+<p>　処理とデータの関係から依存関係を決定</p>

-<p>並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。
-並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。
-これにより、デッドロック等を検出することで信頼性を確保する</p>
+<p>Many Core CPU, GPU, Xeon Phi などを有効に利用するためにはそれぞれのアーキテクチャに合わせた記述が必要</p>
+
+<p>Gears OS では Gear を用いて並列実行環境に合わせた設計・実装を行う</p>


@@ -59,18 +59,13 @@
 <div class="slide" id="3"><div>
 		<section>
 			<header>
-				<h1 id="cerium--alice">Cerium と Alice</h1>
+				<h1 id="gears-os--1">Gears OS の柔軟性</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>先行研究として、本研究室では並列プログラミングフレームワーク Cerium と分散ネットフレームワーク Alice の開発を行なってきた</p>
+<p>Gear を追加することでデータ拡張や機能の追加が可能</p>

-<p>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列処理を実現する。
-依存関係はプログラム自身が記述する必要があり、Task の種類が増えるほど記述が繁雑になる。
-また、Task 間の依存関係のみに注目しており、データの依存関係を正しく保証することができない</p>
-
-<p>Task が取り扱うデータに型情報がない
-汎用ポインタを型変換して利用するしかなく、型検査を行うことができない</p>
+<p>バージョンが異なる Gears OS でもの Gear 共通部分を用いて通信を行う</p>


@@ -80,19 +75,21 @@
 <div class="slide" id="4"><div>
 		<section>
 			<header>
-				<h1 id="cerium--alice-1">Cerium と Alice</h1>
+				<h1 id="gears-os--2">Gears OS の信頼性</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラミングを行う。
-Code Segment が取り扱う Input/Output Data Segment を指定することで処理とデータの関係を決定する</p>
+<p>Code/Data Gear にはメタ計算に必要な情報として Meta Code/Data Gear が付属されている</p>
+
+<p>　関数型言語における Monad に相当</p>
+
+<p>プログラムに対してメタレベルで Model Checking する</p>

-<p>Alice では Computaion を Data Segment を待ち合わせて Code Segment を実行することと定義している。
-これに対し、Meta Computation は Computation を実現する Computation と定義することができる。
-通信中の切断や再接続の処理などは Meta Computation に相当する</p>
+<p>　元のプログラムに影響を与えない</p>

-<p>Data Segment にアクセスする API が設計上の問題で複雑化している。
-また、Meta Computation 自体が Alice で記述されていない</p>
+<p>　並列実行時のデッドロック検出</p>
+
+<p>　Code Gear 間での型検査</p>


@@ -102,22 +99,25 @@
 <div class="slide" id="5"><div>
 		<section>
 			<header>
-				<h1 id="code-gear--data-gear">Code Gear と Data Gear</h1>
+				<h1 id="cerium">Cerium</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Gears OS ではプログラム実行単位として Gear を用いる。
-Gear は変更実行の単位、データの分割、Gear 間の接続などになる</p>
+<p>Cerium では Task という分割された処理を依存関係に沿って並列実行する</p>
+
+<p>Task 同士の依存関係はプログラマ自身が記述する</p>
+
+<p>　Task の種類が増えるほど記述が複雑になる</p>
+
+<p>Task 間の依存関係にのみ着目</p>

-<p>Code Gear は実行コードそのものであり、OpenCL/CUDA の kernel に相当する。
-接続された複数の Input Data Gear を参照し、単一または複数の Output Data Gear に書き込む。
-Code Gear では接続された Data Gear のみに干渉することができる</p>
+<p>　データの依存関係を正しく保証しない</p>
+
+<p>Task が取り扱うデータに型情報がない</p>

-<p>Data Gear には、Primitive Data Type が格納される。
-直接ポインタを扱うことはなく、自分が知らない Code/Data Gear は名前で指し示す</p>
+<p>　汎用ポインタを型変換して利用</p>

-<p>Gear の特徴の一つとしてその処理が Code/Data Gear に閉じていることがある。
-これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする</p>
+<p>　型検査できない</p>


@@ -127,18 +127,25 @@
 <div class="slide" id="6"><div>
 		<section>
 			<header>
-				<h1 id="monad--meta-computation">Monad と Meta Computation</h1>
+				<h1 id="alice">Alice</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるものがある。
-メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副作用、メモリ管理などがある。
-メタ計算の理論的な表現として Monad を用いることが Moggi らにより提案されている</p>
+<p>Alice では処理とデータの単位として Code Segment, Data Segment を用いる</p>
+
+<p>処理とデータの関係から Code Segment 間の依存関係が決定</p>
+
+<p>Data Segment を待ち合わせて Code Segment を実行することを Computaion と定義</p>
+
+<p>Computaion を実現する Computaion を Meta Computaion と定義</p>

-<p>Moand は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するのに必要な情報を格納している。
-失敗する計算の場合は、計算が失敗したかどうかのフラグが Monad に含まれる。
-通常の計算を Monad を返すように変更することでメタ関数が得られる。
-逆に Monad の中にある通常の値のみに着目すると通常の関数となる</p>
+<p>　切断や再接続時の処理、データの圧縮の機能などが相当</p>
+
+<p>　通常の Computaion に影響しない</p>
+
+<p>　Meta Computaion 自体は Alice で記述されていない</p>
+
+<p>Data Segment にアクセスする API が設計上の問題で複雑化している</p>


@@ -148,16 +155,29 @@
 <div class="slide" id="7"><div>
 		<section>
 			<header>
-				<h1 id="gears-os--meta-computation">Gears OS における Meta Computation</h1>
+				<h1 id="codedata-gear">Code/Data Gear</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Gears OS では Code/Data Gear に Meta Code/Data Gear を付属することで Monad を表現する。
-Meta Code/Data Gear は Code/Data Gear へのポインタを持っている。
-各 Gear の関連付けは Meta Gear を用いて行われる</p>
+<p>通常レベルとして Code/Data Gear を用いる</p>
+
+<p>　ポインタを扱わない</p>
+
+<p>Code Gear は処理そのもの</p>
+
+<p>　OpenCL/CUDA の kernel に相当</p>
+
+<p>　接続された複数の Input Data Gear を参照</p>

-<p>オブジェクトレベルである Gear ではポインタを扱わず、メタレベルである Meta Gear でのみポインタを扱う。
-これにより、ポインタ関連のセキュリティフローを防止する。</p>
+<p>　単一または複数の Output Data Gear に書き出す</p>
+
+<p>　自分が知らない Code/Data Gear は名前で指し示す</p>
+
+<p>Data Gear はデータそのもの</p>
+
+<p>　C の構造体で表現</p>
+
+<p>　Primitive Data Type を格納</p>


@@ -167,16 +187,19 @@
 <div class="slide" id="8"><div>
 		<section>
 			<header>
-				<h1 id="section-1">実装言語</h1>
+				<h1 id="meta-codedata-gear">Meta Code/Data Gear</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Gears OS の実装には、本研究室で開発している Continuation based C(CbC) を用いる</p>
+<p>メタレベルとして Meta Code/Data Gear を用いる</p>
+
+<p>　ポインタを扱う</p>

-<p>CbC ではプログラムを Code Segment, Data Segment という単位で記述する。
-Code Segment 間の処理の移動には関数呼び出しではなく、goto を用いた軽量継続を用いている</p>
+<p>各 Gear の関連付け</p>

-<p>CbC のコンパイルには LLVM をバックエンドとしたコンパイラを用いる</p>
+<p>Model Checking</p>
+
+<p>平行制御</p>


@@ -186,16 +209,15 @@
 <div class="slide" id="9"><div>
 		<section>
 			<header>
-				<h1 id="gears-os-">Gears OS の構成</h1>
+				<h1 id="gear--list-">Gear を用いた List の表現</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>
+<p>通常 List は要素と次へのポインタを持つ構造体で表現する</p>

-<p>Gears OS では Context を生成し、Worker を起動する。
-Worker は Synchronized Queue から Code Gear を取得し、実行する。
-実行に必要な Data Gear は Context を通して、Persistent Data Gear から読み込みを行う。
-処理が終わると必要な Data Gear を Persistent Data Gear に書き込みを行う</p>
+<p>Gears OS では任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List を表現する</p>
+
+<p><img src="pictures/List.svg" alt="List" style="width: 70%" /></p>


@@ -205,15 +227,19 @@
 <div class="slide" id="10"><div>
 		<section>
 			<header>
-				<h1 id="code-gear-">Code Gear の継続</h1>
+				<h1 id="codedata-gear-">Code/Data Gear の性質</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Code Gear では、次に実行する Code Gear を名前で指定する。
-Meta Code Gear が名前を解釈して、対応する Code Gear に引き渡す。
-Gear OS では、この Meta Code Gear を Context と定義する</p>
+<p>ポインタの使用を通常レベルとメタレベルで分離</p>
+
+<p>　ポインタ関連のセキュリティフローを防止</p>

-<p>Context には Code Gear の名前とポインタの対応表、Data Gear の Allocation 用の情報、Code Gear が参照する Data Gear へのポインタ、Data Gear に格納される Data Type の情報が格納されている</p>
+<p>処理が Code/Data Gear に閉じている</p>
+
+<p>　接続された Gear のみに干渉できる</p>
+
+<p>　処理の実行時間、メモリ使用量が予測可能</p>


@@ -223,15 +249,15 @@
 <div class="slide" id="11"><div>
 		<section>
 			<header>
-				<h1 id="persistent-data-gear">Persistent Data Gear</h1>
+				<h1 id="gears-os--meta-computation">Gears OS における Meta Computation</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Data Gear の管理には木構造を用いる。
-この木構造は非破壊で構成される。
-非破壊的木構造では、ロックなしに平行して読み書き・参照を行うことが可能である</p>
+<p>関数型言語における Monad に基づいて Meta Computation を行う</p>

-<p>変更前の木構造をすべて保持しているので過去のデータにアクセスすることもできる</p>
+<p>　Monad を用いる手法は Moggi らが提案</p>
+
+<p>Gears OS の Meta Computation は Meta Code/Data Gear を用いる</p>


@@ -241,15 +267,19 @@
 <div class="slide" id="12"><div>
 		<section>
 			<header>
-				<h1 id="list">List</h1>
+				<h1 id="section">実装言語</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>通常 List は要素と次へのポインタを持つ構造体で表現される</p>
+<p>本研究室で開発している Continuation based C(CbC) で実装</p>
+
+<p>　LLVM をバックエンドした CbC コンパイラを用いる</p>

-<p>Gears OS の場合、オブジェクトレベルではポインタを扱わないので、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される</p>
+<p>CbC ではプログラムを Code Segment, Data Segment という単位で記述</p>

-<p><img src="pictures/List.svg" alt="List" style="width: 70%" /></p>
+<p>Code Segment 間の処理の移動は goto を用いた軽量継続</p>
+
+<p>　末尾最適化を強制</p>


@@ -259,16 +289,25 @@
 <div class="slide" id="13"><div>
 		<section>
 			<header>
-				<h1 id="synchronized-queue">Synchronized Queue</h1>
+				<h1 id="context">Context</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する</p>
+<p>実行に必要な情報をまとめた Context を生成</p>
+
+<p>　OS の Process, Thread に相当</p>
+
+<p>　メタレベル</p>
+
+<p>Code Gear の名前とポインタの対応</p>

-<p>Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する。
-M:receiver/sender が CAS を行う Meta Code Gear となる</p>
+<p>Data Gear を Allocate するための情報</p>
+
+<p>Code Gear が参照する Data Gear へのポインタ</p>

-<p><img src="pictures/synchronizedQueue.svg" alt="sync" style="width: 80%" /></p>
+<p>Data Gear に格納される Data Type の情報</p>
+
+<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>


@@ -278,7 +317,7 @@
 <div class="slide" id="14"><div>
 		<section>
 			<header>
-				<h1 id="context">Context</h1>
+				<h1 id="context-1">Context</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

@@ -288,16 +327,11 @@
     Code2,
     Allocator,
 };
-
-enum UniqueData {
-    Allocate,
-    Tree,
-};
 </code></pre>

-<p>enum Code で宣言されているものがこの Context を通して実行可能な Code Gear となる</p>
+<p>実行可能な Code Gear の名前を enum Code で宣言</p>

-<p>enum UniqueData は Context の初期化時に確保する Data Gear となる</p>
+<p>初期化時に名前と関数ポインタを対応付ける</p>


@@ -307,7 +341,27 @@
 <div class="slide" id="15"><div>
 		<section>
 			<header>
-				<h1 id="context-1">Context</h1>
+				<h1 id="context-2">Context</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<pre><code>enum UniqueData {
+    Allocate,
+    Tree,
+};
+</code></pre>
+
+<p>初期化時に確保する Data Gear を enum UniqueData で宣言</p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="16"><div>
+		<section>
+			<header>
+				<h1 id="context-3">Context</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

@@ -322,69 +376,15 @@
 };
 </code></pre>

-
-
-		</section>
-</div></div>
-
-<div class="slide" id="16"><div>
-		<section>
-			<header>
-				<h1 id="code-gear">Code Gear</h1>
-			</header>
-			<!-- _S9SLIDE_ -->
+<p>実行可能な Code Gear の数を示す codeNum</p>

-<pre><code>// Code Gear
-__code code1(Allocate allocate) {
-    allocate.size = sizeof(long);
-    allocate.next = Code2;
-    goto Allocate(allocate); // goes through meta
-}
-
-// Meta Code Gear
-__code meta(struct Context* context, enum Code next) {
-    // meta computation
-    goto (context-&gt;code[next])(context);
-}
-
-// Meta Code Gear
-__code allocate(struct Context* context) {
-    context-&gt;data[++context-&gt;dataNum] = context-&gt;heap;
-    context-&gt;heap += context-&gt;data[Allocate]-&gt;allocate.size;
-    goto (context-&gt;code[context-&gt;data[Allocate]-&gt;allocate.next])(context);
-}
+<p>実行可能な Code Gear へのポインタ code</p>

-// Code Gear
-__code code2(Allocate allocate, Count count) {
-    // processing
-}
-</code></pre>
-
-<pre><code>// Code Gear
-__code code1(struct Context* context) {
-    context-&gt;data[Allocate]-&gt;allocate.size = sizeof(struct Node);
-    context-&gt;data[Allocate]-&gt;allocate.next = Code2;
-    goto meta(context, Allocate);
-}
+<p>Data Gear の Allocate 用のポインタ heap_start, heap, dataSize</p>

-// Meta Code Gear
-__code meta(struct Context* context, enum Code next) {
-    // meta computation
-    goto (context-&gt;code[next])(context);
-}
+<p>Data Gear の数を示す dataNum</p>

-// Meta Code Gear
-__code allocate(struct Context* context) {
-    context-&gt;data[++context-&gt;dataNum] = context-&gt;heap;
-    context-&gt;heap += context-&gt;data[Allocate]-&gt;allocate.size;
-    goto (context-&gt;code[context-&gt;data[Allocate]-&gt;allocate.next])(context);
-}
-
-// Code Gear
-__code code2(struct Context* context) {
-    // processing content
-}
-</code></pre>
+<p>Data Gear へのポインタ data</p>


@@ -400,20 +400,10 @@

 <pre><code>union Data {
     struct Tree {
-        union Data* root;
-        union Data* current;
-        union Data* prev;
-        int result;
+        // Tree member definition
     } tree;
     struct Node {
-        int key;
-        int value;
-        enum Color {
-            Red,
-            Black,
-        } color;
-        union Data* left;
-        union Data* right;
+        // Node member definition
     } node;
     struct Allocate {
         long size;
@@ -422,6 +412,8 @@
 };
 </code></pre>

+<p>Data Gear は C の共用体と構造体を用いた表現する</p>
+


 		</section>
@@ -430,16 +422,19 @@
 <div class="slide" id="18"><div>
 		<section>
 			<header>
-				<h1 id="section-2">比較</h1>
+				<h1 id="persistent-data-gear">Persistent Data Gear</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Code Gear は Cerium の Task、Alice の Code Segment, OpenCL/CUDA の kernel に相当する</p>
+<p>Data Gear の管理には木構造を用いる</p>
+
+<p>非破壊で構成する</p>

-<p>Data Gear は Alice の Data Segment に相当する。
-Ceirum, OpenCL/CUDA には Data Gear に相当する物は存在しない</p>
+<p>　平行して読み書き・参照を行うことが可能</p>

-<p>Cerium, OpenCL/CUDA では処理同士の依存関係を記述する必要があるが、Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する</p>
+<p>　変更前の木構造をすべて保持しているので過去のデータにアクセス可能</p>
+
+<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>


@@ -449,18 +444,157 @@
 <div class="slide" id="19"><div>
 		<section>
 			<header>
+				<h1 id="worker">Worker</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<p>Worker は Synchronized Queue から実行する Code Gear を取得</p>
+
+<p>実行に必要な Data Gear は Persistent Data Gear から読み込む</p>
+
+<p>処理が完了したら Persistent Data Gear に書き込む</p>
+
+<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="20"><div>
+		<section>
+			<header>
+				<h1 id="synchronized-queue">Synchronized Queue</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<p>List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する</p>
+
+<p>Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する</p>
+
+<p>M:receiver/sender が CAS を行う Meta Code Gear となる</p>
+
+<p><img src="pictures/synchronizedQueue.svg" alt="sync" style="width: 80%" /></p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="21"><div>
+		<section>
+			<header>
+				<h1 id="code-gear-">Code Gear の例</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<pre><code>// Code Gear
+__code code1(struct Context* context) {
+    context-&gt;data[Allocate]-&gt;allocate.size = sizeof(struct Node);
+    context-&gt;data[Allocate]-&gt;allocate.next = Code2;
+    goto meta(context, Allocate);
+}
+</code></pre>
+
+<p>必要な情報を Data Gear に書き込み Allocate を行う Code Gear に接続する Code Gear</p>
+
+<p>ポインタを扱っており設計思想と異なる</p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="22"><div>
+		<section>
+			<header>
+				<h1 id="code-gear--1">Code Gear の例</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<pre><code>// Code Gear
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate); // goes through meta
+}
+</code></pre>
+
+<p>前の Code Gear として解釈するように CbC コンパイラを改良する</p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="23"><div>
+		<section>
+			<header>
+				<h1 id="section-1">比較</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<p>Code Gear</p>
+
+<p>　Cerium の Task</p>
+
+<p>　Alice の Code Segment</p>
+
+<p>　OpenCL/CUDA の kernel</p>
+
+<p>Data Gear</p>
+
+<p>　Alice の Data Segment</p>
+
+<p>　Ceirum, OpenCL/CUDA には同等のものはない</p>
+
+<p>Gears OS は Alice と同様に処理とデータの関係から依存関係を決定</p>
+
+<p>Cerium, OpenCL/CUDA では処理同士の依存関係を記述する</p>
+
+<p>　データの依存関係を保証できない</p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="24"><div>
+		<section>
+			<header>
+				<h1 id="section-2">今後の課題</h1>
+			</header>
+			<!-- _S9SLIDE_ -->
+
+<p>Cerium と同様の例題を動かし比較・評価</p>
+
+<p>　Sort</p>
+
+<p>　Word Count</p>
+
+<p>　FFT</p>
+
+<p>GPGPU のサポート</p>
+
+
+
+		</section>
+</div></div>
+
+<div class="slide" id="25"><div>
+		<section>
+			<header>
 				<h1 id="section-3">まとめ</h1>
 			</header>
 			<!-- _S9SLIDE_ -->

-<p>Gears OS では処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった</p>
+<p>処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった</p>

 <p>Gear という単位を用いて記述することでプログラムを柔軟に変更することを可能とした</p>

-<p>Meta Computation を Moand に基づいて実現する。
-Gears OS では Meta Code/Data Gear を用いて Monad を表現する</p>
+<p>Meta Code/Data Gear を用いて Meta Computation を実現する</p>

-<p>機能として Model Checking を提供し、プログラムの信頼性を確保する</p>
+<p>Meta Computation の一つとして Model Checking を行う</p>
 <!-- === end markdown block === -->

 		</section>
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/index.md	Tue May 26 03:46:51 2015 +0900
@@ -0,0 +1,313 @@
+title: Monad に基づくメタ計算を基本とする Gears OS の設計
+author: 小久保翔平
+profile: 琉球大学大学院修士2年
+
+# Gears OS の並列性
+処理とデータの単位として Code Gear, Data Gear を用いる
+
+　並列実行の単位となる
+
+　処理とデータの関係から依存関係を決定
+
+Many Core CPU, GPU, Xeon Phi などを有効に利用するためにはそれぞれのアーキテクチャに合わせた記述が必要
+
+Gears OS では Gear を用いて並列実行環境に合わせた設計・実装を行う
+
+# Gears OS の柔軟性
+Gear を追加することでデータ拡張や機能の追加が可能
+
+バージョンが異なる Gears OS でもの Gear 共通部分を用いて通信を行う
+
+# Gears OS の信頼性
+Code/Data Gear にはメタ計算に必要な情報として Meta Code/Data Gear が付属されている
+
+　関数型言語における Monad に相当
+
+プログラムに対してメタレベルで Model Checking する
+
+　元のプログラムに影響を与えない
+
+　並列実行時のデッドロック検出
+
+　Code Gear 間での型検査
+
+# Cerium
+Cerium では Task という分割された処理を依存関係に沿って並列実行する
+
+Task 同士の依存関係はプログラマ自身が記述する
+
+　Task の種類が増えるほど記述が複雑になる
+
+Task 間の依存関係にのみ着目
+
+　データの依存関係を正しく保証しない
+
+Task が取り扱うデータに型情報がない
+
+　汎用ポインタを型変換して利用
+
+　型検査できない
+
+# Alice
+Alice では処理とデータの単位として Code Segment, Data Segment を用いる
+
+処理とデータの関係から Code Segment 間の依存関係が決定
+
+Data Segment を待ち合わせて Code Segment を実行することを Computaion と定義
+
+Computaion を実現する Computaion を Meta Computaion と定義
+
+　切断や再接続時の処理、データの圧縮の機能などが相当
+
+　通常の Computaion に影響しない
+
+　Meta Computaion 自体は Alice で記述されていない
+
+Data Segment にアクセスする API が設計上の問題で複雑化している
+
+# Code/Data Gear
+通常レベルとして Code/Data Gear を用いる
+
+　ポインタを扱わない
+
+Code Gear は処理そのもの
+
+　OpenCL/CUDA の kernel に相当
+
+　接続された複数の Input Data Gear を参照
+
+　単一または複数の Output Data Gear に書き出す
+
+　自分が知らない Code/Data Gear は名前で指し示す
+
+Data Gear はデータそのもの
+
+　C の構造体で表現
+
+　Primitive Data Type を格納
+
+# Meta Code/Data Gear
+メタレベルとして Meta Code/Data Gear を用いる
+
+　ポインタを扱う
+
+各 Gear の関連付け
+
+Model Checking
+
+平行制御
+
+# Gear を用いた List の表現
+通常 List は要素と次へのポインタを持つ構造体で表現する
+
+Gears OS では任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List を表現する
+
+![List](pictures/List.svg){: style="width: 70%"}
+
+# Code/Data Gear の性質
+ポインタの使用を通常レベルとメタレベルで分離
+
+　ポインタ関連のセキュリティフローを防止
+
+処理が Code/Data Gear に閉じている
+
+　接続された Gear のみに干渉できる
+
+　処理の実行時間、メモリ使用量が予測可能
+
+# Gears OS における Meta Computation
+関数型言語における Monad に基づいて Meta Computation を行う
+
+　Monad を用いる手法は Moggi らが提案
+
+Gears OS の Meta Computation は Meta Code/Data Gear を用いる
+
+# 実装言語
+本研究室で開発している Continuation based C(CbC) で実装
+
+　LLVM をバックエンドした CbC コンパイラを用いる
+
+CbC ではプログラムを Code Segment, Data Segment という単位で記述
+
+
+Code Segment 間の処理の移動は goto を用いた軽量継続
+
+　末尾最適化を強制
+
+# Context
+実行に必要な情報をまとめた Context を生成
+
+　OS の Process, Thread に相当
+
+　メタレベル
+
+Code Gear の名前とポインタの対応
+
+Data Gear を Allocate するための情報
+
+Code Gear が参照する Data Gear へのポインタ
+
+Data Gear に格納される Data Type の情報
+
+![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}
+
+# Context
+```
+/* Context definition */
+enum Code {
+    Code1,
+    Code2,
+    Allocator,
+};
+```
+
+実行可能な Code Gear の名前を enum Code で宣言
+
+初期化時に名前と関数ポインタを対応付ける
+
+# Context
+```
+enum UniqueData {
+    Allocate,
+    Tree,
+};
+```
+
+初期化時に確保する Data Gear を enum UniqueData で宣言
+
+# Context
+```
+struct Context {
+    int codeNum;
+    __code (**code) (struct Context *);
+    void* heap_start;
+    void* heap;
+    long dataSize;
+    int dataNum;
+    union Data **data;
+};
+```
+
+実行可能な Code Gear の数を示す codeNum
+
+実行可能な Code Gear へのポインタ code
+
+Data Gear の Allocate 用のポインタ heap_start, heap, dataSize
+
+Data Gear の数を示す dataNum
+
+Data Gear へのポインタ data
+
+# Data Gear
+```
+union Data {
+    struct Tree {
+        // Tree member definition
+    } tree;
+    struct Node {
+        // Node member definition
+    } node;
+    struct Allocate {
+        long size;
+        enum Code next;
+    } allocate;
+};
+```
+
+Data Gear は C の共用体と構造体を用いた表現する
+
+# Persistent Data Gear
+Data Gear の管理には木構造を用いる
+
+非破壊で構成する
+
+　平行して読み書き・参照を行うことが可能
+
+　変更前の木構造をすべて保持しているので過去のデータにアクセス可能
+
+![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}
+
+# Worker
+Worker は Synchronized Queue から実行する Code Gear を取得
+
+実行に必要な Data Gear は Persistent Data Gear から読み込む
+
+処理が完了したら Persistent Data Gear に書き込む
+
+![arch](pictures/GearsOS_arch.svg){: style="width: 50%"}
+
+# Synchronized Queue
+List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する
+
+Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する
+
+M:receiver/sender が CAS を行う Meta Code Gear となる
+
+![sync](pictures/synchronizedQueue.svg){: style="width: 80%"}
+
+# Code Gear の例
+```
+// Code Gear
+__code code1(struct Context* context) {
+    context->data[Allocate]->allocate.size = sizeof(struct Node);
+    context->data[Allocate]->allocate.next = Code2;
+    goto meta(context, Allocate);
+}
+```
+
+必要な情報を Data Gear に書き込み Allocate を行う Code Gear に接続する Code Gear
+
+ポインタを扱っており設計思想と異なる
+
+# Code Gear の例
+```
+// Code Gear
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate); // goes through meta
+}
+```
+
+前の Code Gear として解釈するように CbC コンパイラを改良する
+
+# 比較
+Code Gear
+
+　Cerium の Task
+
+　Alice の Code Segment
+
+　OpenCL/CUDA の kernel
+
+Data Gear
+
+　Alice の Data Segment
+
+　Ceirum, OpenCL/CUDA には同等のものはない
+
+Gears OS は Alice と同様に処理とデータの関係から依存関係を決定
+
+Cerium, OpenCL/CUDA では処理同士の依存関係を記述する
+
+　データの依存関係を保証できない
+
+# 今後の課題
+Cerium と同様の例題を動かし比較・評価
+
+　Sort
+
+　Word Count
+
+　FFT
+
+GPGPU のサポート
+
+# まとめ
+処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった
+
+Gear という単位を用いて記述することでプログラムを柔軟に変更することを可能とした
+
+Meta Code/Data Gear を用いて Meta Computation を実現する
+
+Meta Computation の一つとして Model Checking を行う
\ No newline at end of file
--- a/presen/themes/ribbon/styles/style.css	Mon May 25 17:19:29 2015 +0900
+++ b/presen/themes/ribbon/styles/style.css	Tue May 26 03:46:51 2015 +0900
@@ -181,21 +181,21 @@
 .slide.cover H2 {
 	color:#666;
 	text-align:center;
-	font-size:120%;
+	font-size:115%;
         margin-top:20%;
 }
 .slide.cover H3#author {
 	color:#888;
 	text-align:right;
 	font-size:80%;
-	margin-top:10%;
+	margin-top:8%;
 	margin-right:55px;
 }

 .slide.cover H3#profile {
 	color:#888;
 	text-align:right;
-	font-size:24px;
+	font-size:70%;
 	margin-right:55px;
 }