\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}
   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が入る。

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

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

% 表題などの出力
\maketitle

% 本文はここから始まる

% Introduce
\section{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=60mm]{./pic/codeGear_dataGear.pdf}
  \end{center}
  \caption{Meta\_code\_gear}
  \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=70mm]{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=70mm]{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}

\begin{figure}[ht]
  \centering
  \includegraphics[width=60mm]{pic/gearsos.pdf}
  \caption{Gears OS による GPGPU}
  \label{fig:gpgpu}
\end{figure}

% 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 名変えたい
\section{Task の設定の Meta Computation の問題}
現在の Gears OS では 並列実行する Task の設定を Code\ref{src:setting_task} のように行っている。
Code\ref{src:setting_task} では 実行する CodeGear、揃っていない Input Data Gear の数、Input/Output Data Gear への参照等の設定をノーマルレベルで記述している。
しかし、この記述方法では Meta Data Gear である Task(Context) を直接参照しているため、ノーマルレベルとしては好ましくなく、 メタレベルでの記述を行いたい。
そこで、 Code\ref{src:par_goto} のような goto の記述方法を新たに考案した。
par goto は Code\ref{src:setting_task} に変換される記述である。
この記述を行うことで、ノーマルレベルでは直接 Task を参照せずに par goto の引数で 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}

\section{結論}
\section{まとめ}
Code Gear Data Gear を用いてCUDAを利用した並列処理プログラムを記述した。
CUDA専用のコンパイラの nvcc と Code Gear Data Gear のコンパイラをCMakeを用いる事
で両立させた。
Gears OSでのGPUの基本的な実行を確認することができた
\section{今後の課題}
\subsection{meta Levelの明示的な分離}
\subsection{metaによる検証}
\subsection{並列実行のAPI}
%par gotoとかcomputationの話を入れて、こういうふうに実装を完成させたいって言うのを書く。
%
%今後はMeta computation部分の自動生成、GPGPUのMeta computationによるチューニングなどを行い、Gears OS における GPGPU のサポートを広げる。

% GPU の方も書く
% debug 手法

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

\end{document}