\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Monad に基づくメタ計算を基本とする Gears OS の設計}
\author{125716B 氏名 {伊波}{立樹} 指導教員 : 河野 真治}
\date{}
\maketitle
\thispagestyle{fancy} 

\section{先行研究}
本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なってきた。

CeriumではTaskと呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
依存関係はプログラマ自身が意識して記述する必要があり、
Taskの種類が増えると記述が複雑になり、 負担が大きくなる。
Taskの依存関係がデータの依存関係を正しく保証しない場合があるという問題がある。
また、Taskの取り扱うデータに型情報がないため、 汎用ポインタをキャストして利用するしかなく、型の検査が行われていない。
Cerium は C++で実装されているが、オブジェクトと並列処理が直接対応していないのでオブジェクト指向で記述する利点が少ない。

Alice では処理の単位である Code Segment、 データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
Alice は Javaで実装されており、実効速度が遅いという問題がある。
また、 Data SegmentをアクセスするAPIのシンタックスが特殊なため、Aliceを用いてプログラムを作成するには慣れが必要になる。

\section{Gears OS}
Cerium と Alice を開発して得られた知見から、並列実行をサポートするだけでなく、信頼性も確保したGears OS の設計・開発を行う。

Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
Code Gear は Input Data Gear  から Output Data Gearを生成する。
Input と Outputの関係から Code Gear 同士の依存関係を解決し、並列実行を行う。

Ceriumは初め、Cell\cite{cell} 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行形式が異なる。
Gears OSでは Many Core CPU、GPUをはじめとする様々なプロセッサを同等な実行機構でサポートする。

従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
Meta Computationは本論のComputationを支えるComputationのことである。
関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
Gears OS では、Meta Code/Data Gear を Monadとして定義し、Meta Computationを実現する。

Gears OS は並列実行をサポートするだけでなく、 信頼性も確保する。
そのために Gears OSを用いて作成されたプログラムに対する Model Checkingを行う機能\cite{model-check}を提供する。
並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。
これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
Model Checking の実現には Meta Code/Data Gearを用いる。

本研究室で開発している CbC(Continuation based C)\cite{cbc-llvm} を用いて、Gears OS を実装する。
CbC はプログラムを Code Segment, Data Segment という単位で記述する。
CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。

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

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

Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
の kernel に相当する。

Code Gear 処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書
き込む。また、接続された Data Gear 以外には参照を行わない。

Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
その代わりに、次に実行する 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 へのポインタを持っている。

\section{Context}
ある 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}

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

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

\section{Synchronized Queue}
Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。
Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。
この図を GearBox と呼ぶことにする。
図\ref{fig:sync}は Synchronized Queue の GearBox である。
M:get/put が CAS を行う Meta Code Gear となる。
今回は CAS で実装しているが、接続する Meta Code Gear を変更することで通常のQueueやLockを使用したsynchronizedQueueなど仕様変更にも対応できる。

\section{今後の課題}
Gears OS の今後の目的はCeriumと同等の例題を動かすことである。
現在、必要な機能として Context、 Allocator、 List、 Non-Destructive Red-Black Tree、 Synchronized Queue を CbC を用いて実装しており、足りない機能としてはWorkerがある。
Workerの実装後、動かす例題としては Bitonic Sort、 Word Count を予定している。
例題の実装後、測定・評価を行う。

\begin{figure}[ht]
    \centering
    \includegraphics[width=70mm]{pic/synchronizedQueue.pdf}
    \caption{Synchronized Queue}
    \label{fig:sync}
\end{figure}

\begin{thebibliography}{10}
    \bibitem{cerium}
        宮國　渡，河野真治，神里　晃，杉山千秋：Cell 用の Fine-grain Task Manager
        の実装，情報処理学会
        システムソフトウェアとオペレーティング・システム研究会(OS) (2008).

    \bibitem{alice}
        赤嶺一樹，河野真治：DataSegment API
        を用いた分散フレームワークの設計，日本ソフトウェア科学会第28回大会論文集
        (2011).

    \bibitem{cell}
        {Sony Corporation}: {Cell broadband engine architecture} (2005).

    \bibitem{segment}
        河野真治，杉本　優：Code Segment と Data Segment
        によるプログラミング手法，第54回プログラミング・シンポジウム (2013).

    \bibitem{cbc-llvm}
        徳森海斗，河野真治：Continuation based C の LLVM/clang 3.5
        上の実装について，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
        (2014).

    \bibitem{monad}
        Moggi, E.: Computational lambda-calculus and monads, {\em Proceedings of the Fourth Annual Symposium on Logic in computer science} (1989).

    \bibitem{model-check}
        下地篤樹，河野真治：線形時相論理によるContinuation based
        Cプログラムの検証，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
        (2007).

    \bibitem{opencl}
        {Aaftab Munshi, Khronos OpenCL Working Group}: {\em {The OpenCL Specification Version 1.0}} (2007).

    \bibitem{cuda}
        : {CUDA}, {https://developer.nvidia.com/category/zone/cuda-zone/}.

\end{thebibliography}
\end{document}