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

\input{dummy.tex}
\begin{document}
\title{Code Gear Data Gear によるGPGPU処理実装}
\author{135704C 氏名 {東恩納}{琢偉} 指導教員 : 河野 真治}
\date{}
\twocolumn [
\maketitle
\begin{英語abst}

\end{英語abst}]
\thispagestyle{fancy} 

\section{Gears OS}
Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear
に細かく分割する。
Gearで表現される計算はメタ計算により実行される。例えば、
従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
接続する Gear を変更することでプログラムの振る舞いを変更することを可能
にする柔軟性、メタ計算による並行制御,モデル検査を用いた信頼性の確保を目的とする。
本研究では現状のGears OS のマルチCPUサポートに加えてGPGPUサポートを行
う。
GPGPUはCUDAまたはOpeCLで制御される。Gears OSからCide Gear Data Gearを
これらに正しく渡す必要がある。

Gears OS上のTaskはRed Black Tree上に格納される。rb\_treeはCbCで記述さ
れており、木をたどるためのStackを一つ持つ。
アルゴリズム全体はCode Gearの有向グラフで表される。実際にこの有向グラ
フを作成した。これは一種のフローチャートになっている。木とStackに格納
されるのはData Gearである。この木を用いて GPGPUを実行するエンジンに
Taskを渡す。


\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 の実行時間、メモリ使用量を予測可能なものにする。
\lstinputlisting[label=code_Gear&Data_Gear, caption=code_Gear&Data_Gear]{sr
c/sample.c}
\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{GPGPU}
 GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。
GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。
Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。また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=90mm]{pic/gearsosgpgpu.pdf}
    \caption{Gears OS による GPGPU}
    \label{fig:gpgpu}
\end{figure}
\section{今後の課題}

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

    \bibitem{alice}
        赤嶺一樹，河野真治：DataSegment API
        を用いた分散フレームワークの設計，日本ソフトウェア科学会第28回大会論文集
        (2011).
    
    \bibitem{gears}
      伊波 立樹, 東恩納 琢偉,河野 真治:Code Gear、Data Gear に基づく OS のプロトタイプ、
      情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2016).

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

    \bibitem{monad} 
        Eugenio Moggi, Notion of Computation and Monads(1991)

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

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