Mercurial > hg > Papers > 2015 > kkb-sigos

view presen/index.html @ 20:bb2bf03f09b4 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add graffle files
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 04 Feb 2016 17:28:04 +0900
parents 40686d8028c5
children
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">琉球大学大学院修士2年</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="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-26 17:03:53 +0900 with Markdown engine kramdown (1.4.0)
                  using options {}
  -->

<!-- _S9SLIDE_ -->

<p>処理とデータの単位として Code Gear, Data Gear を用いる</p>

<p>　並列実行の単位となる</p>

<p>　処理とデータの関係から依存関係を決定</p>

<p>Many Core CPU, GPU, Xeon Phi などを有効に利用するためにはそれぞれのアーキテクチャに合わせた記述が必要</p>

<p>Gears OS では Gear を用いて並列実行環境に合わせた設計・実装を行う</p>



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

<div class="slide" id="3"><div>
		<section>
			<header>
				<h1 id="gears-os--1">Gears OS の柔軟性</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Gear を追加することでデータ拡張や機能の追加が可能</p>

<p>バージョンが異なる Gears OS でもの Gear 共通部分を用いて通信を行う</p>



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

<div class="slide" id="4"><div>
		<section>
			<header>
				<h1 id="gears-os--2">Gears OS の信頼性</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Code/Data Gear にはメタ計算に必要な情報として Meta Code/Data Gear が付属されている</p>

<p>　関数型言語における Monad に相当</p>

<p>プログラムに対してメタレベルで Model Checking する</p>

<p>　元のプログラムに影響を与えない</p>

<p>　並列実行時のデッドロック検出</p>

<p>　Code Gear 間での型検査</p>



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

<div class="slide" id="5"><div>
		<section>
			<header>
				<h1 id="cerium">Cerium</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>Cerium では Task という分割された処理を依存関係に沿って並列実行する</p>

<p>Task 同士の依存関係はプログラマ自身が記述する</p>

<p>　Task の種類が増えるほど記述が複雑になる</p>

<p>Task 間の依存関係にのみ着目</p>

<p>　データの依存関係を正しく保証しない</p>

<p>Task が取り扱うデータに型情報がない</p>

<p>　汎用ポインタを型変換して利用</p>

<p>　型検査できない</p>



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

<div class="slide" id="6"><div>
		<section>
			<header>
				<h1 id="alice">Alice</h1>
			</header>
			<!-- _S9SLIDE_ -->

<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>　切断や再接続時の処理、データの圧縮の機能などが相当</p>

<p>　通常の Computaion に影響しない</p>

<p>　Meta Computaion 自体は Alice で記述されていない</p>

<p>Data Segment にアクセスする API が設計上の問題で複雑化している</p>



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

<div class="slide" id="7"><div>
		<section>
			<header>
				<h1 id="codedata-gear">Code/Data Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>通常レベルとして Code/Data Gear を用いる</p>

<p>　ポインタを扱わない</p>

<p>Code Gear は処理そのもの</p>

<p>　OpenCL/CUDA の kernel に相当</p>

<p>　接続された複数の Input Data Gear を参照</p>

<p>　単一または複数の Output Data Gear に書き出す</p>

<p>　自分が知らない Code/Data Gear は名前で指し示す</p>

<p>Data Gear はデータそのもの</p>

<p>　C の構造体で表現</p>

<p>　Primitive Data Type を格納</p>



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

<div class="slide" id="8"><div>
		<section>
			<header>
				<h1 id="meta-codedata-gear">Meta Code/Data Gear</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>メタレベルとして Meta Code/Data Gear を用いる</p>

<p>　ポインタを扱う</p>

<p>各 Gear の関連付け</p>

<p>Model Checking</p>

<p>平行制御</p>



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

<div class="slide" id="9"><div>
		<section>
			<header>
				<h1 id="gear--list-">Gear を用いた 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="10"><div>
		<section>
			<header>
				<h1 id="codedata-gear-">Code/Data Gear の性質</h1>
			</header>
			<!-- _S9SLIDE_ -->

<p>ポインタの使用を通常レベルとメタレベルで分離</p>

<p>　ポインタ関連のセキュリティフローを防止</p>

<p>処理が Code/Data Gear に閉じている</p>

<p>　接続された Gear のみに干渉できる</p>

<p>　処理の実行時間、メモリ使用量が予測可能</p>



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

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

<p>関数型言語における Monad に基づいて Meta Computation を行う</p>

<p>　Monad を用いる手法は Moggi らが提案</p>

<p>Gears OS の Meta Computation は Meta Code/Data Gear を用いる</p>



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

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

<p>本研究室で開発している Continuation based C(CbC) で実装</p>

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

<p>CbC ではプログラムを Code Segment, Data Segment という単位で記述</p>

<p>Code Segment 間の処理の移動は goto を用いた軽量継続</p>

<p>　末尾最適化を強制</p>



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

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

<img src="pictures/GearsOS_arch.svg" alt="arch" width="50%" align="right"/>
<p>実行に必要な情報をまとめた Context を生成</p>

<p>　OS の Process, Thread に相当</p>

<p>　メタレベル</p>

<p>Code Gear の名前とポインタの対応</p>

<p>Data Gear を Allocate するための情報</p>

<p>Code Gear が参照する Data Gear へのポインタ</p>

<p>Data Gear に格納される Data Type の情報</p>




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

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

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

<p>実行可能な Code Gear の名前を enum Code で宣言</p>

<p>初期化時に名前と関数ポインタを対応付ける</p>



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

<div class="slide" id="15"><div>
		<section>
			<header>
				<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_ -->

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

<p>実行可能な Code Gear の数を示す codeNum</p>

<p>実行可能な Code Gear へのポインタ code</p>

<p>Data Gear の Allocate 用のポインタ heap_start, heap, dataSize</p>

<p>Data Gear の数を示す dataNum</p>

<p>Data Gear へのポインタ data</p>



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

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

<pre><code>union Data {
    struct Tree {
        // Tree member definition
    } tree;
    struct Node {
        // Node member definition
    } node;
    struct Allocate {
        long size;
        enum Code next;
    } allocate;
};
</code></pre>

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



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

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

<p>Data Gear の管理には木構造を用いる</p>

<p>非破壊で構成する</p>

<p>　平行して読み書き・参照を行うことが可能</p>

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

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



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

<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(struct Node);
    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>必要な機能の実装</p>

                        <p>　Synchronized Queue</p>


<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>処理とデータの関係から処理同士の依存関係を解決し、並列実行するように設計を行なった</p>

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

<p>Meta Code/Data Gear を用いて Meta Computation を実現する</p>

<!-- === end markdown block === -->

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


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