\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{CodeGear,DataGearによるGPGPU処理}
\author{135704C 氏名 {東恩納}{琢偉} 指導教員 : 河野 真治}
\date{}
\maketitle
\thispagestyle{fancy} 

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

Cerium と Alice を開発して得られた知見から、並列分散処理の信頼性を向上させるにはCodeの分割だけでなくDataの分割も必要であることがわかった。それををふまえ Gears OS\cite{gears}を設計、実装している。\\
Alice では処理の単位である Code Segment、 データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
これは Alice の Code Segment、 Data Segment にそれぞれ対応する\\
従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
Meta Computationは本論のComputationを支えるComputationのことである。
関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
Gears OS では、Meta Code Gear, Meta Data Gear を Monadとして定義し、Meta Computationを実現する。\\
また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性\
、Monad に基づくメタ計算による並行制御を用いた信頼性の確保を目的とする。

\section{Continuation based C}
CbC のプログラムでは C の関数の代わりに Code Segment を用いて処理を記述している。
Code Segment は C の関数と異なり戻り値を持たない。
Code Segment の宣言はCの関数の構文と同様に行い、型に \_\_code を使うことで宣言できる。

Code SegmentからCode Segmentへの移動は goto の後にCode Segment 名と引数を並べて記述するという CbC独自の構文で行う。
この goto による処理の遷移を継続と呼ぶ。 
図\ref{fig:codesegment}はCode Segment 間の継続関係を表している。

C では関数呼び出しを繰り返し行う場合、呼びだされた関数の引数の数だけスタックに値が積まれていくが、戻り値を持たない Code Segment ではスタックに値を積んでいく必要が無くスタックを変更する必要が無い。
このようなスタックに値を積まない継続、つまり呼び出し元の環境を持たない継続を軽量継続と呼び、軽量継続による並列化、ループ制御、関数コールとスタックの意識した最適化がソースコードで行えるようになる。

\begin{figure}[ht]
    \centering
    \includegraphics[width=65mm]{pic/codesegment.pdf}
    \caption{goto による Code Segment 間の継続}
    \label{fig:codesegment}
\end{figure}


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

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


Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。

Data Gear には、int や文字列などの Primitive Data Type が入る。

Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
これにより、Code 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{Red Black Tree}
 Red Black Tree(赤黒木)は平衡二分木の一種で、主に連想配列の実装に使われる。Red Black Tree の Stack Pop,Stack Push している部分に Stub を仲介させることによって、Stack pop と Stack psuh を Data Segment に分けることで CbC による記述に直した。
\begin{figure}[ht]
    \centering
    \includegraphics[width=70mm]{pic/rb_tree.pdf}
    \caption{CbCでのRed Black Tree}
    \label{fig:rb_Tree}
\end{figure}
\section{GPGPU}
 GPGPUとは画像処理に使われるGPUを画像処理以外で利用する技術である。
GPUはCPUに比べコア数が圧倒的に多く、単純な計算しかできないが並列処理において一度に大量の計算ができるため利用されている。
Gears OS は Code Gear に分割され処理の依存関係が明確になるので、並列な処理を書きやすい。またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に変数が書き変わる事がない。
\begin{figure}[ht]
    \centering
    \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf}
    \caption{Gears OS による GPGPU}
    \label{fig:gpgpu}
\end{figure}
\section{今後の課題}
 今回、Gears OS のGPGPU処理についての基本的な設計と必要な機能の一部を紹介した。
今後の課題としては、Gears OS による GPGPU処理を実装する。並列化処理に最適な Mappingをほどこす。Cerium、GearsでのMany CPU の並列化処理と比較しながら、GPGPU処理の測定、評価を行う。


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