Mercurial > hg > Papers > 2015 > kkb-sigos

view presen/index.html @ 17:dfd4f1eb8882

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
commit
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2015 16:22:34 +0900
parents ff895b2c6792
children 9159562b324c
line wrap: on
line source

<!DOCTYPE HTML>

<html lang="en-US">
<head>
	<title>Monad に基づくメタ計算を基本とする Gears OS の設計</title>
	<meta charset="UTF-8">
	<meta name="viewport" content="width=1274, user-scalable=no">
	<meta name="generator" content="Slide Show (S9)">
	<meta name="author" content="小久保翔平">
	<link rel="stylesheet" href="themes/ribbon/styles/style.css">
</head>
<body class="list">
	<header class="caption">
		<h1>Monad に基づくメタ計算を基本とする Gears OS の設計</h1>
		<p>小久保翔平</p>
	</header>
	<div class="slide cover" id="Cover"><div>
		<section>
			<header>
				<h2>Monad に基づくメタ計算を基本とする Gears OS の設計</h2>
				<h3 id="author">小久保翔平</h3>
				<h3 id="profile"></h3>
			</header>
		</section>
	</div></div>

<!-- todo: add slide.classes to div -->
<!-- todo: create slide id from header? like a slug in blogs? -->

<div class="slide" id="2"><div>
		<section>
			<header>
				<h1 id="section">研究目的</h1>
			</header>
			<!-- === begin markdown block ===

      generated by markdown 1.1.1 on Ruby 2.0.0 (2013-02-24) [x86_64-darwin12.3.0]
                on 2015-05-25 05:40:40 +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>Gears OS では Gear という単位を用いて記述することで柔軟性のあるプログラムを作成することを可能とする。
新たな Gear を接続することでデータの拡張や機能の追加を行うことができる</p>

<p>並列実行の信頼性を確保するため Gears OS では作成されたプログラムに対して Model Checking を行う。
並列プログラムに Model Checking を行うことでそのプログラムが取り得る状態を列挙する。
これにより、デッドロック等を検出することで信頼性を確保する</p>



		</section>
</div></div>

<div class="slide" id="3"><div>
		<section>
			<header>
				<h1 id="cerium--alice">Cerium と Alice</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>先行研究として、本研究室では並列プログラミングフレームワーク Cerium と分散ネットフレームワーク Alice の開発を行なってきた</p>

<p>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列処理を実現する。
依存関係はプログラム自身が記述する必要があり、Task の種類が増えるほど記述が繁雑になる。
また、Task 間の依存関係のみに注目しており、データの依存関係を正しく保証することができない</p>

<p>Task が取り扱うデータに型情報がない
汎用ポインタを型変換して利用するしかなく、型検査を行うことができない</p>



		</section>
</div></div>

<div class="slide" id="4"><div>
		<section>
			<header>
				<h1 id="cerium--alice-1">Cerium と Alice</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Alice では処理とデータの単位としてそれぞれ Code Segment, Data Segment と呼ばれる単位を用いてプログラミングを行う。
Code Segment が取り扱う Input/Output Data Segment を指定することで処理とデータの関係を決定する</p>

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

<p>Data Segment にアクセスする API が設計上の問題で複雑化している。
また、Meta Computation 自体が Alice で記述されていない</p>



		</section>
</div></div>

<div class="slide" id="5"><div>
		<section>
			<header>
				<h1 id="code-gear--data-gear">Code Gear と Data Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Gears OS ではプログラム実行単位として Gear を用いる。
Gear は変更実行の単位、データの分割、Gear 間の接続などになる</p>

<p>Code Gear は実行コードそのものであり、OpenCL/CUDA の kernel に相当する。
接続された複数の Input Data Gear を参照し、単一または複数の Output Data Gear に書き込む。
Code Gear では接続された Data Gear のみに干渉することができる</p>

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

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



		</section>
</div></div>

<div class="slide" id="6"><div>
		<section>
			<header>
				<h1 id="monad--meta-computation">Monad と Meta Computation</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるものがある。
メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副作用、メモリ管理などがある。
メタ計算の理論的な表現として Monad を用いることが Moggi らにより提案されている</p>

<p>Moand は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するのに必要な情報を格納している。
失敗する計算の場合は、計算が失敗したかどうかのフラグが Monad に含まれる。
通常の計算を Monad を返すように変更することでメタ関数が得られる。
逆に Monad の中にある通常の値のみに着目すると通常の関数となる</p>



		</section>
</div></div>

<div class="slide" id="7"><div>
		<section>
			<header>
				<h1 id="gears-os--meta-computation">Gears OS における Meta Computation</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Gears OS では Code/Data Gear に Meta Code/Data Gear を付属することで Monad を表現する。
Meta Code/Data Gear は Code/Data Gear へのポインタを持っている。
各 Gear の関連付けは Meta Gear を用いて行われる</p>

<p>オブジェクトレベルである Gear ではポインタを扱わず、メタレベルである Meta Gear でのみポインタを扱う。
これにより、ポインタ関連のセキュリティフローを防止する。</p>



		</section>
</div></div>

<div class="slide" id="8"><div>
		<section>
			<header>
				<h1 id="section-1">実装言語</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Gears OS の実装には、本研究室で開発している Continuation based C(CbC) を用いる</p>

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

<p>CbC のコンパイルには LLVM をバックエンドとしたコンパイラを用いる</p>



		</section>
</div></div>

<div class="slide" id="9"><div>
		<section>
			<header>
				<h1 id="gears-os-">Gears OS の構成</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p><img src="pictures/GearsOS_arch.svg" alt="arch" style="width: 50%" /></p>

<p>Gears OS では Context を生成し、Worker を起動する。
Worker は Synchronized Queue から Code Gear を取得し、実行する。
実行に必要な Data Gear は Context を通して、Persistent Data Gear から読み込みを行う。
処理が終わると必要な Data Gear を Persistent Data Gear に書き込みを行う</p>



		</section>
</div></div>

<div class="slide" id="10"><div>
		<section>
			<header>
				<h1 id="code-gear-">Code Gear の継続</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Code Gear では、次に実行する Code Gear を名前で指定する。
Meta Code Gear が名前を解釈して、対応する Code Gear に引き渡す。
Gear OS では、この Meta Code Gear を Context と定義する</p>

<p>Context には Code Gear の名前とポインタの対応表、Data Gear の Allocation 用の情報、Code Gear が参照する Data Gear へのポインタ、Data Gear に格納される Data Type の情報が格納されている</p>



		</section>
</div></div>

<div class="slide" id="11"><div>
		<section>
			<header>
				<h1 id="persistent-data-gear">Persistent Data Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Data Gear の管理には木構造を用いる。
この木構造は非破壊で構成される。
非破壊的木構造では、ロックなしに平行して読み書き・参照を行うことが可能である</p>

<p>変更前の木構造をすべて保持しているので過去のデータにアクセスすることもできる</p>



		</section>
</div></div>

<div class="slide" id="12"><div>
		<section>
			<header>
				<h1 id="list">List</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>通常 List は要素と次へのポインタを持つ構造体で表現される</p>

<p>Gears OS の場合、オブジェクトレベルではポインタを扱わないので、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される</p>

<p><img src="pictures/List.svg" alt="List" style="width: 70%" /></p>



		</section>
</div></div>

<div class="slide" id="13"><div>
		<section>
			<header>
				<h1 id="synchronized-queue">Synchronized Queue</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する</p>

<p>Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた GearBox という図で表現する。
M:receiver/sender が CAS を行う Meta Code Gear となる</p>

<p><img src="pictures/synchronizedQueue.svg" alt="sync" style="width: 80%" /></p>



		</section>
</div></div>

<div class="slide" id="14"><div>
		<section>
			<header>
				<h1 id="context">Context</h1>
			</header>
			<!-- _S9SLIDE_ -->

<pre><code>/* Context definition */
enum Code {
    Code1,
    Code2,
    Allocator,
};

enum UniqueData {
    Allocate,
    Tree,
};

struct Context {
    int codeNum;
    __code (**code) (struct Context *);
    void* heap_start;
    void* heap;
    long dataSize;
    int dataNum;
    union Data **data;
};
</code></pre>



		</section>
</div></div>

<div class="slide" id="15"><div>
		<section>
			<header>
				<h1 id="code-gear">Code Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<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);
}

// 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);
}

// 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);
}

// Code Gear
__code code2(struct Context* context) {
    // processing content
}
</code></pre>



		</section>
</div></div>

<div class="slide" id="16"><div>
		<section>
			<header>
				<h1 id="data-gear">Data Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<pre><code>union Data {
    struct Tree {
        union Data* root;
        union Data* current;
        union Data* prev;
        int result;
    } tree;
    struct Node {
        int key;
        int value;
        enum Color {
            Red,
            Black,
        } color;
        union Data* left;
        union Data* right;
    } node;
    struct Allocate {
        long size;
        enum Code next;
    } allocate;
};
</code></pre>



		</section>
</div></div>

<div class="slide" id="17"><div>
		<section>
			<header>
				<h1 id="section-2">比較</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Code Gear は Cerium の Task、Alice の Code Segment, OpenCL/CUDA の kernel に相当する</p>

<p>Data Gear は Alice の Data Segment に相当する。
Ceirum, OpenCL/CUDA には Data Gear に相当する物は存在しない</p>

<p>Cerium, OpenCL/CUDA では処理同士の依存関係を記述する必要があるが、Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する</p>



		</section>
</div></div>

<div class="slide" id="18"><div>
		<section>
			<header>
				<h1 id="section-3">まとめ</h1>
			</header>
			<!-- _S9SLIDE_ -->

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

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

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

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

		</section>
</div></div>


	<script src="scripts/script.js"></script>
	<!-- Copyright © 2010–2011 Vadim Makeev, http://pepelsbey.net/ -->
</body>
</html>