Papers/2015/kkb-sigos: presen/index.md comparison

comparison presen/index.md @ 19:40686d8028c5

edit

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Tue, 26 May 2015 03:46:51 +0900
parents
children	bb2bf03f09b4

comparison

equal deleted inserted replaced

-:9159562b324c
+:40686d8028c5
+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 を行う

Mercurial > hg > Papers > 2015 > kkb-sigos

comparison presen/index.md @ 19:40686d8028c5