Mercurial > hg > Papers > 2015 > kkb-sigos

--- a/paper/sigos.bib	Tue May 05 17:49:31 2015 +0900
+++ b/paper/sigos.bib	Wed May 06 02:52:05 2015 +0900
@@ -1,66 +1,58 @@
 @article{
-    Monad,
-    author = "{Eugenio Moggi}",
+    cerium,
+    author = "宮國 渡 and 河野 真治 and 神里 晃 and 杉山 千秋",
+    title = "Cell 用の Fine-grain Task Manager の実装",
+    journal = "情報処理学会 システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "April",
+    year = 2008
+}
+
+@article{
+    alice,
+    author = "赤嶺 一樹 and 河野 真治",
+    title = "DataSegment API を用いた分散フレームワークの設計",
+    journal = "日本ソフトウェア科学会第28回大会論文集",
+    month = "Sep",
+    year = 2011
+}
+
+@misc{cell,
+    author = "{Sony Corporation}",
+    title = "{Cell broadband engine architecture}",
+    year = 2005
+}
+
+@article{
+    cbc,
+    author = "河野 真治 and 島袋 仁",
+    title = "C with Continuation と、そのPlayStationへの応用",
+    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "May",
+    year = 2000
+}
+
+@article{
+    cbc-llvm,
+    author = "徳森 海斗 and 河野 真治",
+    title = " Continuation based C の LLVM/clang 3.5 上の実装について",
+    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "May",
+    year = 2014
+}
+@article{
+    monad,
+    author = "Eugenio Moggi",
     title = "Computational lambda-calculus and monads",
     journal = "Proceedings of the Fourth Annual Symposium on Logic in computer science",
     year = 1989
 }
-
-@misc{cell,
-author = "{Sony Corporation}",
-title = "{Cell broadband engine architecture}",
-year = 2005
-}
-
-@misc{cerium,
-author = "",
-title = "{SourceForge.JP: Cerium Rendering Engine}",
-howpublished = "{https//sourceforge.jp/projects/cerium/}"
-}
-
-@article{gongo:2008a,
-        author = "宮國 渡 and 河野 真治 and 神里 晃 and 杉山 千秋",
-        title = "Cell 用の Fine-grain Task Manager の実装",
-        journal = "情報処理学会 システムソフトウェアとオペレーティング・システム研究会",
-        month = "April",
-        year = 2008
-}
-
-@journal{chiaki,
-author = "{Chiaki SUGIYAMA}",
-title = "{SceneGraph と StatePattern を用いたゲームフレームワークの設計と実装}",
-journal = "{琉球大学工学部情報工学科 平成19年度卒業論文}",
-year = 2008
-}

-@article{yutaka:os,
-        author = "金城裕 and 河野真治 and 多賀野海人 and 小林佑亮(琉球大学)",
-        title = "ゲームフレームワークCerium TaskManagerの改良",
-        journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
-        month = "April",
-        year = 2011
-}
-
-@article{toma:2012a,
-        author = "當眞 大千 and 河野 真治",
-        title = "Cerium Task Manager におけるマルチコア上での並列実行機構の実装",
-        journal = " 第53回プログラミング・シンポジウム",
-        month = "Jan",
-        year = 2012
-}
-
 @manual{opencl,
 author = "{Aaftab Munshi, Khronos OpenCL Working Group}",
 title ="{The OpenCL Specification Version 1.0}",
 year = 2007
 }

-@manual{opencl:ref,
-author = "{Khronos OpenCL Working Group}",
-title ="{OpenCL 1.2 Reference Pages}",
-year = 2012
-}
-
 @misc{cuda,
 title = "{CUDA}",
 howpublished = "{https://developer.nvidia.com/category/zone/cuda-zone/}"
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Tue May 05 17:49:31 2015 +0900
+++ b/paper/sigos.tex	Wed May 06 02:52:05 2015 +0900
@@ -37,7 +37,7 @@
 % 和文表題
 \title{Monad に基づくメタ計算を基本とする Gears OS の設計}
 % 英文表題
-\etitle{}
+\etitle{Design of Gears OS with Meta Computation based on Monad}

 % 所属ラベルの定義
 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
@@ -54,8 +54,10 @@

 % 英文著者名
 \eauthor{
-  Shohei KOKUBO\affiref{1}\and
-  Tatsuki Iha\affiref{2}\and
+  Shohei KOKUBO\affiref{1}
+  \and
+  Tatsuki Iha\affiref{2}
+  \and
   Shinji KONO\affiref{2}
 }

@@ -78,6 +80,12 @@

 % 英文概要
 \begin{eabstract}
+  We are developing parallel framework using Code Gear, Data Gear.
+  We obtain meta function for parallel execution, based on Monad in Functional Language.
+  Meta Code Gear and Meta Data Gear attached to Code Gear and Data Gear with designed Gears OS.
+  Meta Code Gear is executed after Code Gear, this is Meta Computation.
+  Meta Computation performs Network Management, Memory Management and more.
+  We implement basic functions using CbC and evaluate it.
 \end{eabstract}

 % 表題などの出力
@@ -86,10 +94,35 @@
 % 本文はここから始まる

 % Introduce
+\section{Cerium と Alice}
+本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なっている。
+
+Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
+依存関係はプログラマ自身が意識して記述する必要がある。
+Task の種類が増えると記述が煩雑になり、プログラマの負担が大きくなる。
+依存関係の記述がデータの依存関係と無関係という問題もある。
+また、Task の取り扱うデータには型情報がなく、Task とデータも分離されていない。
+Cerium は C++ で実装されている。
+Cell\cite{cell}, Many Core CPU, GPU といった様々なプロセッサをサポートしている。
+高速で動作するが、非常に複雑な実装となっており機能の追加やデバッグが難しい現状である。
+
+Alice は本研究室で開発を行なっている分散管理フレームワークである。
+Alice では処理の単位である Code Segment, データの単位である Data Segment を用いてプログラムを記述する。
+Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。
+Alice は Java で実装されている。
+ガベージコレクション(GC)が実行されると性能が低下するといった問題がある。
+また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。
+
+Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
+
 \section{Gears OS}
-並列実行は Code の並列実行だけでなく、Data の単位が重要である。
-本研究では Code Gear, Data Gear という単位で細かく分割し、依存関係を記述することで並列実行するフレームワーク Gears OS の開発を行なっている。
-Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能である。
+Cerium と Alice から並列実行には Code の並列実行だけでなく、Data の単位が重要であることが明らかとなった。
+本研究では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割し、Code と Data の関係から Code Gear 同士の依存関係を解決して並列実行するフレームワーク Gears OS の開発を行なっている。
+Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能となるように設計する。
+Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。
+Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。
+Gears OS は本研究室で開発している CbC(Continuation based C)\cite{cbc} で実装する。
+CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる

 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
 Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。
@@ -98,7 +131,8 @@
 Model Chaecking によって、並列実行時のデッドロックの検出などを行う。
 これにより、プログラムの信頼性を保証する。

-Gears OS は接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
+Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
+また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。

 % Theory
 \section{Monad とメタ計算}
@@ -106,7 +140,7 @@
 がある。
 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
 作用、メモリ管理などがある。
-メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{Monad}
+メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{monad}
 されている。
 Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。

@@ -136,7 +170,7 @@
 Gears OS ではプログラムの実行単位として様々な Gear を使う。
 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。

-Code Gear はプログラムの実行コードそのものであり、CUDA
+Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
 の kernel に相当する。
 Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
 き込む。
@@ -241,7 +275,38 @@
   \label{fig:list}
 \end{figure}

-\section{}
+\section{比較}
+Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。
+
+\paragraph*{Cerium/Alice}
+Gears OS の Code Gear は Cerium の Task, Context は HTask に相当する。
+Cerium とは異なり、Gears OS は処理とデータが分離している。
+Gears OS では分離したデータを Data Gear と呼称する。
+これは Alice の Data Segment と同等のものである。
+Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。
+
+\paragraph*{OpenCL/CUDA}
+Code Gear は OpenCL/CUDA の kernel に相当する。
+OpenCL/CUDA には Data Gear に相当する仕組みはない。
+接続された複数の Code Gear は接続された順番通りに実行される。
+これは、OpenCL の CommandQueue, CUDA の Stream と同等のものである。
+OpenCL/CUDA では kernel の依存関係を複雑に記述する必要があるが、Gears OS では Code と Data の関係から自動的に依存関係を解決する。
+
+\paragraph*{従来の OS}
+従来の OS が行なってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code Gear, Meta Data Gear を用いて行う。
+このメタ計算は Monad に基づいて実現される。
+
+\section{まとめ}
+Gears OS は Inherent Parallel をキーワードとして、Gears OS 上で実行されるプログラムが自動的に並列で処理されるように設計した。
+Gear を他の Gear に接続することで機能およびデータの拡張を行える柔軟性を持つ。
+Meta な機能や並行制御を関数型言語における Monad に基づいて実現する。
+また、機能として Model Checking を持ち、Gears OS 上で実行されるプログラムの信頼性を保証する。
+本論文では必要な機能の一部である Context, Allocator, List, Non-Destructive Red-Black Tree を CbC を用いて実装した。
+今後は、Synchronized Queue, Woker を実装する予定である。
+これにより、Cerium と同等の例題を動かすことが可能となる。
+例題としては Bitonic Sort, Word Count を予定している。
+例題が動くことを確認し次第、Gears OS の測定・評価を行う。
+
 \nocite{*}
 \bibliographystyle{ipsjunsrt}
 \bibliography{sigos}