\documentclass[techrep]{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{listings,jlisting}
\usepackage{enumitem}

\lstset{
    language=C, 
    tabsize=2, 
    frame=single, 
    basicstyle={\ttfamily\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=0.5zw,% 
    lineskip=-0.5ex, 
}
\renewcommand{\lstlistingname}{Code}

\input{dummy.tex} %% Font 

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

\begin{document}

% 和文表題
\title{Gears OS における並列処理}
% 英文表題
\etitle{}

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


% 和文著者名
\author{
  東恩納 琢偉\affiref{1}
  \and
  伊波 立樹 \affiref{2}
  \and
  河野 真治\affiref{1}
}

% 英文著者名
\eauthor{
  Takui HIGASHIONNA\affiref{1}
  \and
  Tatsuki IHA\affiref{2}
  \and
  Shinji KONO\affiref{1}
}

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

% 和文概要
\begin{abstract}
現代の OS では拡張性と信頼性を両立させることが要求されている。
信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
Gears OS は継続を中心とした言語で記述されており、メタ計算をノーマルレベルと分けて記述することができる。並列処理はメタ計算によって記述されており、CbC自体には並列処理の機能はない。
メタレベルでの並列処理は新規に実行環境を作り引数を設定するなどの煩雑な処理であり、ノーマルレベルでは簡潔な並列構文があることが望ましい。
本論文では並列構文と並列処理の実装について記述する。

Gears OS のプログラムはCode Gear とData Gear の集まりであるinterfaceによって行われる。
Gears OSでのスレッドはinterfaceの集合で出来ており、code gear data gearを接続するcontextというmeta data gear を持つ。
並行実行する場合は新しくcontextを生成し、それを時分割または、物理的なCPUに割り当てることによって実現される。 つまり、contextそのものがスレッドとなる。

Gears OSでの同期機構はdata gear を待ち合わせることによって行われる。例えば、GPU上で実行する場合は必要なdata gearをGPU内部に転送し、それらが揃った時点で並列実行される。data gear の待ち合わせはメモリ上のdata gearのmeta data gear に待ち合わせ用のキューを作ることによって行われる。キューにはGears OSのスレッドつまりcontext meta data gearが入る。

並列処理をメタレベルで行うことにより、並列処理で重要なチューニングや性能測定あるいはデバッグをメタ計算を切り替えることにより、ノーマルレベルの計算を変更することなく行うことができることを示す。
\end{abstract}

% 英文概要
\begin{eabstract}
\end{eabstract}

% 表題などの出力
\maketitle

% 本文はここから始まる

% Introduce
\section{Gears OS}
OS に要求される信頼性はテストやモデル検査あるいは証明によって保証される。
一方で新しいアプリケーションや新しいアーキテクチャへの対応を OS が提供する必要がある。
様々な拡張のたびに信頼性の保証をゼロからやり直すのは現実的ではない。本研究室で開発している Gears OS は
信頼性の保証を比較的固定されたノーマルレベルの計算に対しておこない、
拡張性をメタレベルの計算で対応する。
メタ計算の一つは並列処理であり、OS の機能の重要な部分である。
本論文では Gears OS の並列構文と並列処理の実装について述べる。

Gears OS は本研究室で開発している CbC(Continuation based C)を用いて行われている。
CbC は処理を Code Segment を用いて分割して記述することを基本としている。
Gears OS では Code Gear が CbC の Code Segement にあたる。
Gears OS のプログラムは C の関数の単位で Code Gear を用いて分割し、処理を記述している。
Code Gear から Code Gear への移動は goto の後に移動先の Code Gear 名と引数を並べた記述する構文を用いて行う。
この goto による処理の遷移を継続と呼び、C での関数呼び出しにあたり、C では関数の引数の値がスタックに積まれていくが、Code Gear の goto では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要がない。
このようなスタックに積まない継続を軽量継続と呼び、呼び出し元の環境を持たない。


Code Gear は処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書き込む。また、接続された Data Gear 以外には参照を行わない。(図\ref{fig:codeGear_dataGear})
Input Data Gear と Output Data Gear の2つによって、Code Gear の Data に対する依存関係が解決し Code Gear の並列実行を可能とする。

\begin{figure}[ht]
  \begin{center}
    \includegraphics[width=70mm]{./pic/codeGear_dataGear.pdf}
  \end{center}
  \caption{Gears OS の依存関係}
  \label{fig:codeGear_dataGear}
\end{figure}

Gears OS の通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。
例として、 Code Gear が次に実行する Code Gear を goto で名前指定する。
この継続処理に対してMeta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
この Meta Data Gear を Context と呼び、これは従来の OS の Process や Thread を表す構造体に対応する。
Meta Computation を使用することで以下のことが可能になる。
\begin{itemize}
\item 元の計算を保存したデータ拡張や機能の追加
\item GPU 等のさまざまなアーキテクチャでの動作
\item 並列処理や分散処理の細かいチューニングや信頼性の制御
\item Meta Computation は 通常の Computaiton の間に挟まれる
\end{itemize}
\begin{figure}[ht]
  \begin{center}
    \includegraphics[width=80mm]{./pic/meta_gear.pdf}
  \end{center}
  \caption{Meta\_code\_gear}
  \label{fig:meta_gear}
\end{figure}


%図で言うよりも goto の説明をしたほうがわかりやすいかも、gotoがどういったものでどういう事に使われているのか、これがわかればわかるのでは？

\section{GearsOSの構成}
%去年のOS研究会で構成については発表しているので、この辺はまとめてよい
Gears OS の以下の要素で並列処理を行う。

\begin{itemize}
    \item Context(Task)
    \item TaskManager
    \item Worker 
\end{itemize}

Gears OS では、 Context という Meta Data Gear を通して Code Gear と Data Gear の接続を行う。
また、 並列実行を行う際はこの Context を生成し、それを Task として実行する。
そのため、 Context は 接続に必要な Code/Data Gear のリスト、 Data Gear を確保するためのメモリ空間、 実行する Code Gear、 Code Gear の実行に必要な Input Data Gear のカウンタ等をもっている。

TaskManager は Task、 Worker の生成、 Worker に生成した Task を送信する。
また、生成した Worker の終了処理等を行う。

Worker は thread と実行する Task が入っているQueueを持っている。
Worker は TaskManager から送信された Task を Queue から取り出し、Code Gearを実行する。
Task は Context なので、Code Gear の実行に必要な Input Data Gear はその Context から参照される。
Code Gear を実行した後は出力される Output Data Gear から依存関係を解決する。

Gears OS の並列処理の構成を図\ref{fig:gears_structure}に示す。
%\lstinputlisting[label=src:sync\_dequeue, caption=sync\_dequeue.c]{./src/sync\_dequeue.c}

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=100mm]{pic/gears_structure}
    \end{center}
    \caption{並列処理の構成}
    \label{fig:gears_structure}
\end{figure}


\section{並列処理の依存関係の解決}
Gears OS の並列処理の依存関係の解決は Data Gear に依存関係解決のための Queue をもたせることで行う。
Queue にはその Data Gear を Input Data Gear として使用する Task(Context) が入っている。
依存関係の解決の流れは図\ref{fig:dependency} に示す。
Worker は Task の Code Gear を実行後、 書き出された Output Data Gear の Queue から, 依存関係にある Task を参照する。
参照した Task には 実行に必要な Input Data Gear のカウンタをもっているので、そのカウンタのデクリメントを行う。
カウンタが $0$ になったら Task が待っている Data Gear が揃ったことになるので、その Task を Worker に送信する。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=80mm]{pic/dependency}
    \end{center}
    \caption{依存関係の解決}
    \label{fig:dependency}
\end{figure}

\section{GPGPU}
GPGPU とは、元々は画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術の事である。
画像の編集はピクセル毎に行われるため多大な数の処理を行う必要があるが、 GPU は CPU に比べコア数が多数あり、多数のコアで同時に計算することによって CPU よりも多数の並列な処理を行う事が出来る。
これによってGPUは画像処理のような多大な処理を並列処理することで、 CPU で処理するよりも高速に並列処理することが出来る。
しかし、GPU のコアはCPUのコアに比べ複雑な計算は出来ない構造であるため単純計算しか出来ない、また一般的にユーザーから GPU 単体に直接命令を書き込むことも出来ないなどの問題点も存在する。
GPGPU は CPU によって単純計算のTaskを GPU に振り分ける事によって、 GPU の問題点を解決しつつ、高速な並列処理を行うことである。
また Data Gear  へのアクセスは接続された Code Gear からのみであるから、処理中に変数が書き変わる事がない。
図\ref{fig:gpgpu}では以下の流れで処理が行われる。
\begin{itemize}
\item Data Gear をPersistent Data Tree に挿入。
\item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。
\item 生成したTaskをTaskQueueに挿入。
\item Workerの起動。
\item WorkerがTskQueueからTaskを取得。
\item 取得した Task を元に必要なData Gear を Persistent Data Tree から取得。
\item 並列処理される Code Gear を実行。
\end{itemize}

% CPUからGPUにTaskを振り分ける図があってもいい
\section{CUDA}
%CUDAの説明
CUDA とは NVIDIA 社が提供している並列コンピューティング用の統合開発環境で、コンパイラ、ライブラリなどの並列コンピューティングを行うのに必要なサポートを提供している。
一般的にも広く使われているGPUの開発環境である。
Task(kernel) は .ptx という GPU用のアセンブラに変換され、プログラム内部から直接kernel を呼び出す構文を持つ API である。さらにメモリ転送と kernel 呼び出しを自分で制御する DriverAPI の2種類をもつ。

%helper_cuda.h cmakeは一つの言語のコンパイルしか出来ない、CbCはC言語としてコンパイル出来るが、C++の言語がCUDAのhelper_cuda.hなどには含まれる。

\section{CPUWoker}
%そもそも実装してない？
%実装したって言えるのはtwiceとかのCudaExsampleをGPUで動かすことが出来るってだけで、WorkerによってTaskManagmentしてるとは言えないのでは？
Worker thread で動くTaskスケジューラーである。
synchronized queue からTaskのListを読み込み実行する。
Data Gear の待ち合わせの管理を行う。
CPUWorkerはreceive Task というAPIを持ち、Taskがなくなるまで繰り返す。

\section{CUDAWorkerの実装}
CPUWorkerを再利用して作成するTaskスケジューラー。
CUDAライブラリの初期化を行う以外の動作はCUDAWorker と全く同じになる。
GPUへのデータ転送及びGPU側でのTaskの実行はTaskのMeta Code Gear で行われる。

% session 名変えたい
% __exit は そのcontext(thread)での終わりを示している(説明追加)
\section{Gears OS の並列構文}
Gears OS では 並列実行する Task の設定をメタレベルで Code\ref{src:setting_task} のように行っている。
Code\ref{src:setting_task} では 実行する CodeGear、待ち合わせ中の
Input Data Gear の数、Input/Output Data Gear への参照等の設定を記述し
ている。
これらの記述は Context などを含む煩雑な記述であるが、並列実行されるこ
とを除けば通常のCbC の goto 文と同等である。 
そこで、Context などを直接用いないノーマルレベルの並列構文を用意するこ
とが望ましい。Code\ref{src:par_goto} のような par goto を用いる記述方法を新たに考案した。
この記述は メタレベル生成スクリプトにより、 Code\ref{src:setting_task} に変換される。
また、メタレベルの記述を変換することで、 CPU、 GPU での実行の切り替え
等を行うことが出来るようになる。

% この例題微妙かなぁ
\lstinputlisting[label=src:setting_task, caption=createTask]{./src/setting_task.c}
\lstinputlisting[label=src:par_goto, caption=parGoto]{./src/par_goto.c}

par goto で生成された Task は\verb+__exit+ と言うcontination に goto
することにより終了する。終了時には Task の Context が解放される。
Gears OS では Task は output Data Gear を生成した時点で終了するので、
par goto では直接に\verb+__exit+ に継続するのではなく、Data Gear に書
き込み依存関係の処理をおこなう継続を指定する。これらの継続は interface
での Data Gear の定義に従って生成される。

これにより Code Gear と Data Gear の依存関係をノーマルレベルで記述でき
るようになる。

\section{考察}
従来の OS の並列処理は、例えば Unix の fork 、pthread の
\verb+pthread_create+で記述される。これらはプロセスIDや thread 構造体を
含むメタレベルの記述であり、並列処理の煩雑さを解消できなかった。
これに対して、プログラミング言語レベルで並列処理構文を用意する方法があ
る。例えば Java の thread あるいは Go 言語の go routine などである。
これらは OS によって直接サポートされているわけではない。
言語レベルでの並列処理を細かく制御する場合は言語機能そのものに変更を加
える必要がある。例えば、 Java の thread やgo routine を GPU で動かすた
めには言語のサポートを待つ必要がある。

並列処理ではチューニングが重要であり、どの Task を どのCPU とメモリに
割り当てるかを細かく制御する必要がある。これらを可能にするためには言語
レベルでのサポートを非常に複雑にするか、言語レベルでの記述を諦めて OS
レベルでの記述をおこなう必要がある。

Gears OS ではノーマルレベルとメタレベルの記述を分離することにより、並
列処理の煩雑な記述を避け、チューニングなどをメタレベルの記述で行うこと
が可能になる。
メタレベルの記述の変更は現状では CbC レベルで行う。goto 文の行き先を
実行時に変更することも可能であり(goto meta)、この場合は実行時のチュー
ニングなどのメタ計算を行うことに相当する。

プログラムの信頼性をノーマルレベルで示しておけば、メタ計算がノーマルレ
ベルの意味を保存すれば信頼性はそのまま維持される。
このように Gears OS ではノーマルレベルでのプログラムの信頼性を再利用し
ながら、メタ計算により様々な拡張を行うことができる。拡張部分の信頼性は
独立して示す必要がある。これらは Gears OS のモデル検査の機能などを用い
て示すことになる。
\section{まとめ}
Code Gear Data Gear を用いてCUDAを利用した並列処理プログラムを記述した。
CUDA専用のコンパイラの nvcc と Code Gear Data Gear のコンパイラをCMakeを用いる事
で両立させた。
Gears OSでのGPUの基本的な実行を確認することができた。
これらの部分は Gears OS のメタ計算として実装されている。
par goto 構文の実装は今後の課題である。

%par gotoとかcomputationの話を入れて、こういうふうに実装を完成させたいって言うのを書く。
%
%今後はMeta computation部分の自動生成、GPGPUのMeta computationによるチューニングなどを行い、Gears OS における GPGPU のサポートを広げる。

% GPU の方も書く
% debug 手法

\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{sigos}

\end{document}