\documentclass[a4j,12pt]{jreport}
\usepackage[dvipdfmx]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{here}
\usepackage{url}
\usepackage{listings, jlisting}

\lstset{
    language=java, 
    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, 
    numbers=left 
}
\renewcommand{\lstlistingname}{Code}

\setlength{\itemsep}{-1zh}

\title{Code Gear Data Gear によるGPGPU処理実装}
%\title{Supporting NAT in Screen Sharing System TreeVNC}
\icon{
    \includegraphics[width=80mm,bb=0 0 595 642]{fig/ryukyu.pdf} %%元は 642じゃなくて842
}
\year{平成27年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{135704C 東恩納 琢偉 \\ 指導教員 {河野 真治} }

%% TreeVNC のNATへの対応
%% マルチスクリーン TreeVNC
%% プリアンブルに記述
%% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要
%%
\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}
%%% \input{./future.tex}
% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに

\chapter{GearsOSでのGPU実行}
CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。\\
そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。
マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
並列処理を行う上でこれらのリソースを無視することができない。\\
しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。\\
並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。\\
そのためには並列処理を行うプログラムの依存関係を解決することや、
%Gearsの強みは依存関係の解決以外に何がある？
本研究室で開発しているGears OS は Code Gear と Data Gear によって構成される。
Code Gear は処理の単位、Data Gear はデータの単位となる。
Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。\\
また、Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する。\\
Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される。
Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する。\\
依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。 
Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。
これらのことから、並列プログラミングで必要とされる GPU やマルチコア CPU をCPUと同等に扱うためには依存関係を明確に出来る Gears OS でCUDAによるGPU実装を行い、CbCによるGPU処理での有用性を発見することが本研究の目的である。

\label{chap:introduction}
\pagenumbering{arabic}

%序論の目安としては1枚半ぐらい．
%英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも．
\chapter{GearsOS}

\section{Continuation Baseed C}
Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行われている。。\\
CbC は処理を Code Segment を用いて分割して記述することを基本としている。、 Gears OS の Code Gear はCbCを元に記述されている。
CbC のプログラムでは C の関数の単位で Code Segment を用いて分割し、処理を記述している。
 Code Segment は C の関数と異なり戻り値を持たない。
Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使い宣言している。
Code Segment から Code Segment への移動は goto の後に移動先の Code Segment  名と引数を並べた記述する構文を用いて行う。
この goto による処理の遷移を継続と呼び、C での関数呼び出しにあたり、C では関数の引数の値がスタックに積まれていくが、Code Segment の goto では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要がない。
このようなスタックに積まない継続を軽量継続と呼び、呼び出し元の環境を持たない。
図\ref{fig:cbc_goto} は Code Segment 間の接続関係を表している。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/cbc_goto.pdf}
    \end{center}
    \caption{gotoによる Code Segment 間の接続}
    \label{fig:cbc_goto}
\end{figure}
\newpage
\section{Code Gear と Data Gear}
Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda} の kernel に相当する。

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


Code Gear はCbCを元に記述されており、処理の移行はfunction callではないので、呼び出し元に戻る概念はない。
その代わりに、次に実行する Code Gear を軽量継続の goto で指定する。

Data Gear は、int や文字列などの Primitive Data Type の組み合わせ（struct）である。
Data Gearは様々な型を持つunionとして定義される。

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

%Gearsの特性を活かせての並列性とは？
%Code Gear Data Gear にわけられることによって依存関係が解決されていること
%並列性と柔軟性は2つともSegment毎に分けられていることで成り立つわけだから、説明する際に2つでSegmentによって分けられるって事説明するのか？同じ事説明してるけど

% 並列処理するの問題、並列化刷ることによって依存関係のあるプログラムがあると並列化出来ない、ということだけど、依存関係ってもっとわかりやすく言うとなに？->要するに、Aの処理を行うにはBの処理を施した値を使わないといけないとかそういうこと、逆に依存関係が無い処理は同時に並列処理していいわけだけど、ソレはつまりここでいう並列性とは、並列化し易いとかそういうことでいいんだろうか、　依存関係の無い形、Gearという分けられた単位にはほかとの依存関係は無い、わけではなくて、あるけど、　　処理毎に分けることによって、依存している物を明確にしているって言うところが強みである。
Code Gear が処理するのに必要な Input Data Gear と処理の実行後に出力される Output Data Gear の組を Task と呼び、Code Gear は接続する Task 以外とは依存関係がなく、1つの Code Gear の中で処理の依存関係が解決しているため、変更なしに並列処理の Thread に乗せることが出来る。
%Code Gear を複数Threadに分けて並列処理刷る図を入れてもいいかも


\section{柔軟性}
%プログラムの処理が Gearという単位で分けられて記述されているって言うけど、プログラムの処理ってなに？という疑問を持つのが一般的だと思われ
Code Gear Data Gear はCbCを用いて記述されており、処理の遷移には goto を用いた軽量継続によって移行している。
また Code Gear は C の関数と同じ単位で分割されており、処理の遷移に用いられている goto の遷移先を変更することで、容易に処理の順番を変更や新しい処理を追加することが出来る
%図\ref{fig:CG_Flexibility}は Code Gear C と Code Gear D を入れ替えたものであり、この入れ替えを行う場合 Code Gear C を指していた goto の先を Code Gear D に書き換えるだけで済む。


\newpage
%図で言うよりも goto の説明をしたほうがわかりやすいかも、gotoがどういったものでどういう事に使われているのか、これがわかればわかるのでは？
\section{Gears でのMeta computation の実行}
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 を表す構造体に対応する。

\chapter{Gears OSの構成}

\section{TaskManager}
Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。
Task には Input/Output Data Gear の情報が格納されている。
Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。
Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。
この Input と Output の関係が依存関係となる。
TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。
\section{Worker}
Worker は TaskQueue から Task を取得し、実行する。
Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。
実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。

各 Worker は個別の Context を参照しており、 メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。
ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。

Worker が TaskQueue から Task の取得を行う Code Gear を Code \ref{src:sync_dequeue} に示す。
Task Queue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。

\lstinputlisting[label=src:sync_dequeue, caption=GetTask]{./src/sync_dequeue.c}

Worker から取得された Task の Code Gear は並列実行される。
並列実行される Code Gear と言っても他の Code Gear と同じである。
これは Gears OS 自体が Code Gear によって構成されていることに起因する。
つまり、 Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないとき、全て並列に実行することができる。


\chapter{GPGPU}

\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を持つTas\
k を生成。
    \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=120mm]{pic/gearsos.pdf}
    \caption{Gears OS による GPGPU}
    \label{fig:gpgpu}
\end{figure}
\newpage

 % CPUからGPUにTaskを振り分ける図があってもいい
\section{CUDAとは}
%CUDAの説明
CUDA とは NVIDIA 社が提供している並列コンピューティング用の統合開発環境で、並列プログラムの記述や、コンパイラ、ライブラリなど、また GPU といった並列コンピューティングを行うのに必要なサポートを提供しており、一般的にも広く使われているGPUの開発環境です。

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

\chapter{GPU 実装}

\section{GPUWoker の実装}
%そもそも実装してない？
%実装したって言えるのはtwiceとかのCudaExsampleをGPUで動かすことが出来るってだけで、WorkerによってTaskManagmentしてるとは言えないのでは？

\section{CUDATwiceの実装}

\section{CMake}
CMakeはビルド自動化ツールであり、プログラムをコンパイル行う際にライブラリや動作環境によって様々な設定を行う必要がありますが、CMakeにはそれらのファイルやライブラリを探し出して実行することが出来ます。\\
CMakeのビルドは2段階からなり、最初にビルドに必要なライブラリやファイルを探し、通常のビルド環境用のビルドファイルを作成し、次にビルドするファイルにあったビルドを行います。
CMakeはWindows や Linux 等、複数のOS の環境に対応している他、
\section{性能評価}

\section{比較}


\chapter{今後の課題}
\section{GPU並列実行}

% 今後の課題

\chapter{結論}

\section{まとめ}

\section{今後の課題}



% 参考文献
\def\line{−\hspace*{-.7zw}−}
\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}


\chapter*{謝辞}
\thispagestyle{empty}

%基本的な内容は以下の通り．参考にしてみて下さい．
%厳密な決まりは無いので，個々人の文体でも構わない．
%GISゼミや英語ゼミに参加した人はその分も入れておく．
%順番は重要なので気を付けるように．(提出前に周りの人に確認してもらう．)

\begin{flushright}
    2017年 3月 \\ 
\end{flushright}

% 付録

\end{document}