\documentclass[techrep]{ipsjpapers}
\usepackage[dvipdfm]{graphicx}
\usepackage{url}
\usepackage{listings}
\usepackage{enumitem}

\lstset{
  language=C,
  tabsize=2,
  frame=single,
  basicstyle={\footnotesize},%
  identifierstyle={\footnotesize},%
  commentstyle={\footnotesize\itshape},%
  keywordstyle={\footnotesize\bfseries},%
  ndkeywordstyle={\footnotesize},%
  stringstyle={\footnotesize\ttfamily},
  breaklines=true,
  captionpos=b,
  columns=[l]{fullflexible},%
  xrightmargin=0zw,%
  xleftmargin=1zw,%
  aboveskip=1zw,
  numberstyle={\scriptsize},%
  stepnumber=1,
  numbersep=1zw,%
  lineskip=-0.5ex%
}

\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

% ユーザが定義したマクロなど．
\makeatletter

\begin{document}

% 和文表題
\title{Monad に基づくメタ計算を基本とする Gears OS の設計}
% 英文表題
\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.}
\affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}

% 和文著者名
\author{
  小久保 翔平\affiref{1}
  \and
  伊波 立樹\affiref{2}
  \and
  河野 真治\affiref{2}
}

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

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{小久保 翔平\\
        〒903-0213 沖縄県西原町千原1番地\\
	琉球大学工学部情報工学科\\
        TEL: (098)895-2221\qquad FAX: (098)895-8727\\
        email: kokubo@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
  本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
  並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。
  今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と  Meta Data Gear を付属させる。
  Code Gear が実行されるとそれに属する Meta Code Gear が実行され、Meta Computation が行われる。
  Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
  本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
\end{abstract}

% 英文概要
\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}

% 表題などの出力
\maketitle

% 本文はここから始まる

% 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}
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 に基づいて実現する。

Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。
Model Chaecking によって、並列実行時のデッドロックの検出などを行う。
これにより、プログラムの信頼性を保証する。

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

% Theory
\section{Monad とメタ計算}
関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
がある。
メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
作用、メモリ管理などがある。
メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{monad}
されている。
Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。

Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの
に必要な情報を格納している。
失敗する可能性がある計算の場合は、計算が失敗したかどうかのフラグが
Monad に含まれる。
並行処理の場合は、Monad は可能な計算の interleaving(並び替え) になるが、
実際に並び替えを持っているわけではなく、マルチプロセッサで実行する環境
そのものが Monad に対応する。

通常の関数を Monad を返すように変更することにより、メタ関数が得られる。
逆に Monad の中にある通常の戻り値のみに着目すると通常の関数に戻る。
このように、Monad を用いたメタ計算の表現では通常の計算とメタ計算が一対
一に対応する。

一般的には複数の Monad の組み合わせが Monad になることを示すのは難しい。
Gears OS では Code と Data を分離して、Code から他の Code への呼び出し
を継続を用いて行う。
Gears OS での Monad は Meta Code と Meta Data になる。

% Code Gear
% Data Gear
% Meta Code Gear
% Meta Data Gear
\section{Code Gear と Data Gear}
Gears OS ではプログラムの実行単位として様々な Gear を使う。
Gear が平行実行の単位、データ分割、Gear 間の接続などになる。

Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
の kernel に相当する。
Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
き込む。
Code Gear は接続された Data Gear 以外には触らない。
Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。
その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。

Data Gear には、int や文字列などの Primitive Data Type が入る。
自分が持っていない Code Gear, Data Gear は名前で指し示す。

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

Code Gear, Data Gear はポインタを直接には扱わない。
これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフ
ローを防止する。

Code Gear, Data Gear はそれぞれ関係を持っている。
例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ
Data Gear などである。
Gear の関連付けは Meta Gear を通して行う。
Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当
する。
なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
% s/Segment/Gear

% Context
\section{継続}
ある Code Gear から継続するときには、次に実行する Code Gear を名前で指
定する。
Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対
応する。
名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
この Meta Data Gear を Context と呼ぶことにする。
これは従来の OS の Process や Thread に対応する。

Context には以下のようなものが格納される。
\begin{itemize}
\item Code Gear の名前とポインタの対応表
\item Data Gear の Allocation 用の情報
\item Code Gear が参照する Data Gear へのポインタ
\item Data Gear に格納される Data Type の情報
\end{itemize}

\lstinputlisting[caption=Context]{source/context.h}

\paragraph*{Code Gear の名前とポインタの対応表}
Code Gear の名前とポインタの対応は enum と関数ポインタによって表現される。
これにより、実行時に比較ルーチンなどを動的に変更することが可能になる。

\paragraph*{Data Gear の Allocation 用の情報}
Context の生成時にある程度の領域を確保する。
Context にはその領域へのポインタとサイズが格納されている。
そのポインタを必要な Data Gear のサイズに応じて、インクリメントすることによって Data Gear の Allocation を実現する。

\paragraph*{Code Gear が参照する Data Gear へのポインタ}
Context には Data Gear へのポインタが格納されている。
Code Gear は Context を通して Data Gear へアクセスする。

\paragraph*{Data Gear に格納される Data Type の情報}
Data Gear は union と struct によって表現される。
Context には Data Gear の Data Type の情報が格納されている。
この情報から確保する Data Gear のサイズなどを決定する。

\lstinputlisting[caption=initContext]{source/context.c}

% Persistent
\section{Persistent Data Gear}
Data Gear の管理には木構造を用いる。
この木構造は非破壊で構築される。
非破壊的木構造では、図\ref{fig:non-destructive_tree}のように編集元の木構造を破壊することなく新しい木構造を構成する。
破壊的木構造と異なりロックの必要がなく、平行して読み書き、参照を行うことが可能である。
また、変更前の木構造をすべて保持しているので過去のデータにアクセスすることができる。

\begin{figure}[!h]
  \centering
  \includegraphics[width=70mm]{images/nondestructive_tree_modification.pdf}
  \caption{木構造の非破壊的編集}
  \label{fig:non-destructive_tree}
\end{figure}

% allocator
\section{Allocator}
Gears OS では Context の生成時にある程度の領域を確保し、その領域を指すポインタをインクリメントすることで Allocation を実現する。

Context には Allocation 用の Data Gear が格納されている。
この Data Gear に確保するサイズと確保後に接続する Code Gear の名前を書き込み、Allocation を行う Code Gear に接続することで必要な領域を確保する。

\lstinputlisting[caption=Allocator]{source/allocate.h}

% List
\section{List}
通常 List は要素と次へのポインタを持つ構造体で表現される。
Gears OS の場合、Meta レベル以外でポインタは扱わないので図\ref{fig:list}のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。

\begin{figure}[!h]
  \centering
  \includegraphics[width=70mm]{images/List.pdf}
  \caption{List の表現}
  \label{fig:list}
\end{figure}

\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}

\end{document}