\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}
\usepackage{caption}
\captionsetup[lstlisting]{font={small,tt}}

\input{dummy.tex} %% Font 

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

\begin{document}

% 和文表題
\title{Gears OS のモジュール化と並列 API}
% 英文表題
\etitle{}

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

% 和文著者名
\author{
  宮城 光希\affiref{1}
  \and
  桃原 優 \affiref{1}
  \and
  河野 真治\affiref{2}
}

% 英文著者名
\eauthor{
  Mitsuki MIYAGI\affiref{1}
  \and
  Yu TOBARU\affiref{1}
  \and
  Shinji KONO\affiref{2}
}

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

% 和文概要
\begin{abstract}
    現代の OS では拡張性と信頼性を両立させることが要求されている。
    信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
    Gears OS は Continuation based C によってアプリケーションと OS そのものを記述する。
    CbC はこの Code Gear と Data Gear の単位でプログラムを記述する。
    システムやアプリケーションを記述するためにCode Gear と Data Gear を柔軟に再利用する必要がある。
    このときに機能を接続するAPIと実装の分離が可能であることが望ましい。
    Gears OS の信頼性を保証するために、形式化されたモジュールシステムを提供する必要がある。
    本論文では、Interface を用いたモジュールシステムの説明とその応用としての並列 API について考察する。
    並列APIは継続を基本とした関数型プログラミングと両立する必要がある。
    ここでは、CbC の goto 文を拡張したpar goto 文を導入する。
    par goto では並列実行のための実行 Context を生成し、TaskScheduler に登録する。
    Gears OS での同期機構はData Gear  の待ち合わせとして定義する。
    メタレベルではこれらの同期機能はCASとそれを用いて実装した Synchronized Queue になる。
    これらの Queue も Interface を用いてモジュール化されている。
    モジュール化の詳細と、有効性について考察する。
\end{abstract}

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

% 表題などの出力
\maketitle

% 本文はここから始まる

\section{OS の拡張性と信頼性の両立}

さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。OS の信頼性を保証する事自体が難しいが、時代とともに進歩する
ハードウェア、サービスに対応して OS 自体が拡張される必要がある。
OS は非決定的な実行を持ち、その信頼性を保証するには、従来のテストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。
これに対処するためには、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。
モデル検査は無限の状態ではなくても巨大な状態を調べることになり、状態を有限に制限したり状態を抽象化したりする方法が用いられている
図\ref{fig:verification}。
\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/verification.pdf}
 \end{center}
 \caption{証明とモデル検査によるOSの検証}
 \label{fig:verification}
\end{figure}

証明やモデル検査を用いて OS を検証する方法はさまざまなものが検討されている。
検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。
つまり信頼性と拡張性を両立させることが重要である。

コンピュータの計算はプログラミング言語で記述されるが、その言語の実行は操作的意味論の定義などで規定される。
プログラミング言語で記述される部分をノーマルレベルの計算と呼ぶ。
コードが実行される時には、処理系の詳細や使用する資源、あるいは、コードの仕様や型などの言語以外の部分が服属する。
これをメタレベルの計算という。
この二つのレベルを同じ言語で記述できるようにして、ノーマルレベルの計算の信頼性をメタレベルから保証できるようにしたい。
ノーマルレベルでの正当性を保証しつつ、新しく付け加えられたデバイスやプログラムを含む正当性を検証したい。

ノーマルレベルとメタレベルを共通して表現できる言語として Continuation based C(以下CbC)\cite{cbc}を用いる。
CbC は関数呼出時の暗黙の環境(Environment)を使わずに、コードの単位を行き来できる引数付き goto 文(parametarized goto)を持つ C と互換性のある言語である。
これを用いて、Code Gear と Data Gear、さらにそのメタ構造を導入する。
これらを用いて、検証された Gears OS を構築したい。
図\ref{fig:MetaGear}。
検証には定理証明支援系である Agda を用いる。
Gears の記述をモジュール化するために Interface を導入した。
さらに並列処理の記述用にpar goto 構文を導入する。
これらの機能は Agda 上で継続を用いた関数型プログラムに対応するようになっている。
\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/MetaGear.pdf}
 \end{center}
 \caption{Gearsのメタ計算}
 \label{fig:MetaGear}
\end{figure}

本論文では Interface と par goto の実装の詳細を記述し評価を行った。
マルチ CPU と GPU 上での par goto 文の実行を確認した。
%Go言語に比べて並列構文 par goto が遅いことがわかった。

\section{Gears におけるメタ計算}
Gears OS ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を用いる。
Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。図\ref{fig:metaCS}

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/metaCS.pdf}
 \end{center}
 \caption{Gears でのメタ計算}
 \label{fig:metaCS}
\end{figure}

CbC は軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
CbC は LLVM\cite{llvm} と GCC\cite{gcc} 上で実装されている。
メタレベルの記述は Perl スクリプトによって生成される stub と goto meta によって Code Gear で記述される。

Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。
Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。
一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Meta Data Gear に格納される。
この Meta Data Gear を Context という。
ノーマルレベルでは Context を直接見ることはできない。

Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。
これを記述するために継続に不定長引数を追加する構文をスクプリトの変換機能として用意した。Code \ref{varargnext}
メタ計算側ではこれらの Context を常に持ち歩いているので goto 文で引数を用いることはなく、
行き先は Code Gear の番号のみで指定される。

\lstinputlisting[label=varargnext, caption=不定長引数を持つ継続]{./src/varargnext.cbc}

これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。
Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。
呼び出された Code Gear は必要な引数を Context から取り出す必要がある。
これは スクリプトで生成された stub Meta Code Gear で行われる。
Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。

Context を複製して複数の CPU に割り当てることにより並列実行を可能になる。
これによりメタ計算として並列処理を記述したことになる。
Gears のスレッド生成は Agda の関数型プログラミングに対応して行われるのが望ましい。
そこで、par goto 構文を導入し、Agda の継続呼び出しに対応させることにした。
par goto では Context の複製、入力の同期、タスクスケジューラーへの Context の登録などが行われる。
par goto 文の継続として、スレッドの join に相当する \_\_exit を用意した。
\_\_exit により par goto で分岐した Code Gear の出力を元のスレッドで受け取ることができる。 

関数型プログラムではメモリ管理は GC などを通して暗黙に行われる。
Gears OS ではメモリ管理は stub などのメタ計算部分で処理される。
例えば、寿命の短いスレッドでは使い捨ての線形アロケーションを用いる。 

%Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。
%これを図示したものが図\ref{fig:metaCS}である。

\section{Gears OS の構成}
Gears OS は以下の要素で構成される。

\begin{itemize}
    \item Context
    \item TaskQueue
    \item TaskManager
    \item Worker
\end{itemize}

図\ref{fig:gearsos} に Gears OS の構成図を示す。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/gears_structure}
 \end{center}
 \caption{Gears OS の構成図}
 \label{fig:gearsos}
\end{figure}

Data Gear は union と struct によって表現される。
Context には Data Gear の Data Type の情報が格納されている。
この情報から確保する Data Gear のサイズなどを決定する。

Context は Task でもあり、Taskは通常のOSのスレッドに対応する。
Task は実行する Code Gear と Data Gear をすべて持っている。
TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。
Gears OS における Task Queue は Synchronized Queue で実現される。
Worker は TaskQueue から Task である Context を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。
Input/Output Data Gear の依存関係が解決されたものから並列実行される。

\section{Interface}
Interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
呼び出される Code Gear の引数となる Data Gear はここで全て定義される。

Code\ref{interface}は stack の Interface である。
Code Gear、Data Gear に参照するために Context を通す必要があるが、
Interface を記述することでデータ構造の api と Data Gear を結びつけることが出来る。

\lstinputlisting[label=interface, caption=StackのInterface]{./src/Stack.cbc}

Code\ref{implement}は stack の実装の例である。
createImpl は関数呼び出しで呼び出され、初期化と Code Gear のスロットに対応する Code Gear の番号を入れる。

\lstinputlisting[label=implement, caption=SingleLinkedStackの実装]{./src/stackimpl.cbc}

\section{stub Code Gear の生成}

stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
stub Code Gear を 自動生成する generate stub を Perl スクリプトで作成することによって Code Gear の記述量を約半分にすることができる。

stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
また、この時既に stub Code Gear が記述されている Code Gear は無視される。

cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(Code\ref{stack_c})

\lstinputlisting[label=stack_c, caption=stub Code Gear を加えたコード]{./src/ex_stub}

\section{Context の生成}
generate\_context は Context.h、Interface.cbc、generate\_stub で生成されたImpl.cbc を見て Context を生成する Perl スクリプトである。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/generate_context3.pdf}
 \end{center}
 \caption{generate\_context による Context の生成}
 \label{fig:gc}
\end{figure}

Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。

generate\_context は context の定義 (Code\ref{context}) を読み宣言されている Data Gear を取得する。
Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。
取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。

Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
また、generate context は取得した Code/Data Gear から initContext の生成も行う。

Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
Code Gear は Context を通して Data Gear へアクセスする。
Data Gear の Allocation を行うコードは dataGearInit.cに生成される。


\section{Gears OS の並列処理}
Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。
Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。
Gears OS では 並列実行する Task を Context で表現する。
Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている
Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を Worker に送信する。
Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。

\section{SynchronizedQueue}
SynchronizedQueue は Worker の Queue として使用される。
Worker の Queue は TaskManager を経由して Task を送信するスレッドと Task を取得する Worker 自身のスレッドで扱われる。
そのため SynchronizedQueue はマルチスレッドでもデータの一貫性を保証する Queue を実装する必要がある。

データの一貫性を保証する解決例としての 1 つとしてロックを使った解決方法がある。
しかし、ロックを行ってデータを更新した場合、同じ Queue に対して操作を行う際に待ち合わせが発生し、全体の並列度が下がってしまう。
そこで、Gears OS ではデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue を実装している。
CAS は値の比較、更新をアトミックに行う命令である。
CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。
異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。

Gears OS ではこの CAS を行うための Interface を定義している(Code\ref{atomicInterface})。
この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義して
いる(Code\ref{atomicInterface} 6行目)。

\lstinputlisting[label=atomicInterface, caption=AtomicInterface]{./src/atomicInterface.h}

AtomicInterface での CAS の実際の実装を Code\ref{atomicImpl} に示す。
実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(Code\ref{atomicImpl} 2行目)。
この関数は第一引数に渡されたアドレスに対して第二引数の値から第三引数の値ヘ CAS を行う。
CAS に成功した場合、true を返し、失敗した場合は false を返す。
Code\ref{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。

\lstinputlisting[caption=CAS の実装, label=atomicImpl]{./src/atomicImpl.cbc}

SynchronizedQueue の Data Gear の定義を Code\ref{synchronizedQueue} に示す。
SynchronizedQueue はデータのリストの先頭と、終端のポインタを持っている。
Queue を操作する際はこのポインタに対して CAS をすることでデータの挿入と取り出しを行う。

\lstinputlisting[caption=SynchronizedQueue の定義, label=synchronizedQueue]{./src/synchronizedQueue.h}

\section{並列構文}
Gears OS の並列構文は par goto文で用意されている(Code\ref{pargoto})。
\lstinputlisting[caption=par goto による並列実行, label=pargoto]{./src/parGotoCreateTask.cbc}
par goto の引数には Input/Output Data Gear と 実行後に継続する \_\_exit を渡す。
par goto で生成された Task は \_\_exit に継続することで終了する。
par goto文でも 通常の goto 分と同様にメタへの goto 文へ置き換えられるが、par goto 文では通常の goto 文とは異なるメタへと継続する。
Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、
Output Data Gear への書き出し処理(Commit)に継続される。

Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。
Code Gear の引数である\_\_next が持つ引数の Data Gear が Output Data Gear となる。

書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。
参照した Task が持つ実行に必要な Input Data Gear カウンタのデクリメントを行う。
カウンタが0になると Task が待っている Input Data Gear が揃ったことになり、
その Task を TaskManager 経由で 実行される Worker に送信する。

この par goto 文は通常のプログラミングの関数呼び出しのように扱うことができる。


%\section{比較}
%
%従来のプログラミングスタイルとの比較。
%Gears のプログラミングは関数呼出を中心とするプログラミングとはかなり異なる。
%Gears は関数呼出を禁止しているわけではなく、使用する資源の制御に問題がないなら普通に関数呼出して良い。
%%Linux kernel などでは関数呼出の大半はインライン展開されることを期待してプログラミングされており、
%関数呼出で予測できないスタックの爆発やCPU資源の浪費が起きないようにプログラミングされている。
%Gears では Gears 間のプログラミングは戻り先や使用する資源を明示する必要がある。
%
%goto 文での引数は通常の関数呼出と異なり、スタック(環境)に積むことができない。引数に必要な情報を含むData Gearを
%持ち歩くスタイルとなる。一つのインタフェース内部では、これらは共通している。実際、これらはメタレベルでは、
%Context というMeta Data Gear にすべて格納されている。メタレベルは、Data Gear の詳細な型は使用されない。
%ノーマルレベルに移行する際に stub Code Gear を通して詳細な型が接続される。
%
%インタフェースを再利用する際には、呼び出すインタフェースが持つ引数は保存される必要がある。これらは、実際には
%Context 内にあるので自動的に保存されている。ノーマルレベルの記述では、... の部分にその意味が込めれている。
%これは、可変長引数の...と同じ意味だと考えても良い。ただ、LLVM/GCC レベルでそれを実装するのは比較的難しい。
%なので、今回はScriptによる変換を採用している。
%
%ノーマルレベルの記述と関数型プログラミングの記述の比較。Gear は必ず継続を渡す必要がある。これは一段の
%関数呼出を許しているのと同等である。70年代の Fortan の関数呼出は決まった場所に戻り先を格納するので
%再起呼出ができなかったのと同じである。例えば Code Gears 以下のような型を持つ。ここで t は継続の型である。
%Stack は Stack を受けとる Stack \verb|->| t という Code Gear を継続として引数で受けとる。popStack はこの引数を
%呼び出す。
%
%\verb|popStack : {a t : Set} -> Stack |
%
%\verb|           -> (Stack -> t) -> t|
%
%つまり、Code Gear は制限された関数の形式を持っている。Data Gear は、関数型言語の直積や排他的論理和(Sum)を含むデータ型に
%対応する。しかし、一つの Context で実行される Data Gear は、一つの巨大なSumに含まれるようになっている。これを
%メタレベルでは、中の型の詳細に立ち入ることなく実行する。
%
%%Context はノーマルレベル のData Gear の他に様々なメタ情報を持つ。例えば、メモリ管理情報や実行される CPU 、あるいは、Task の
%状態、待ち合わせている Data Gear などである。これらの情報は C やアセンブラのレベルで実装されるのと同時に、通常の Gear の
%プログラミングにも対応する。例えば、CPU をかそうてきに Gears で記述すればソフトウェア的な並列実行を実現し、実際の
%GPU を用いれば GPU による並列実行となる。この実行をモデル検査的な状態数え上げに対応させればモデル検査を実行できる。
%
%Haskell などを実行可能仕様記述として用いる OS の検証\cite{Klein:2009:SFV:1629575.1629596,Chen:2015:UCH:2815400.2815402}と、Code Gear を用いる手法は類似>しているが、Code Gear の場合は、
%記述を制限し、Code と仕様の対応、さらにCodeと資源の対応が明確になる利点がある。
%
%型つきアセンブラ\cite{Yang:2010:SLI:1806596.1806610}は、より低レベルの関数型の記述であると言える。アセンブラの記述自体は小さく扱いやすいが、
%OS レベルあるいはアプリケーションレベルからの距離が大きい。型の整合性を保証するだけでは OS の検証としては
%不十分なので、証明やモデル検査を用いることになるが、記述量が多いのが、その際に欠点となる。
%Code Gear は、より大きな単位であり、プログラミングレベルの抽象化が可能になっているので、これらの記述の
%大きさの欠点をカバーできる可能性がある。
%
%証明手法は、従来では Hoare Logic \cite{Chen:2015:UCH:2815400.2815402}のような Post Condition / Pre Condition を用いる方法が使われている。
%現在のGearsは、Agda への変換は考えているが、その上の具体的な証明方法はまだ用意されていない。
%

\section{Gears OS の評価}

\subsection{実験環境}
今回 Twice、 BitonicSort をそれぞれ CPU、GPU環境で Gears OS の測定を行う。

使用する実験環境を表\ref{tab:powerEdge}、 GPU 環境を表\ref{tab:gtx1070} に示す。
また、今回は LLVM/Clang で実装した CbC コンパイラを用いて Gears OS をコンパイルする。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l|l|} \hline
            Model & Dell PowerEdgeR630 \\ \hline
            OS    & CentOS 7.4.1708 \\ \hline
            Memory & 768GB \\ \hline
            CPU & 2 x 18-Core Intel Xeon 2.30GHz \\ \hline
        \end{tabular}
         \caption{実行環境}
         \label{tab:powerEdge}
    \end{center}
\end{table}

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            GPU & GeForce GTX 1070 \\ \hline
            Cores & 1920 \\ \hline
            Clock Speed & 1683MHz \\ \hline
            Memory Size & 8GB GDDR5 \\ \hline
            Memory Bandwidth & 256GB/s \\ \hline
        \end{tabular}
        \caption{GPU 環境}
        \label{tab:gtx1070}
    \end{center}
\end{table}

\subsection{Twice}
Twice は与えられた整数配列のすべての要素を2倍にする例題である。

Twice の Task は Gears OS のデータ並列で実行される。
CPU の場合は配列ある程度の範囲に分割してTaskを生成する。
これは要素毎に Task を生成するとその分の Context を生成するために時間を取ってしまうからである。

Twice は並列実行の依存関係もなく、データ並列での実行に適した課題である。
そのため、 通信時間を考慮しなければ CPU よりコア数が多い GPU が有利となる。

要素数$2^{27}$ のデータに対する Twice の実行結果を 表\ref{tab:wice}、図\ref{fig:twice}に示す。
CPU 実行の際は $2^{27}$ のデータを 64個のTask に分割して並列実行を行っている。
GPU では1次元の block 数を $2^{15}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。
ここでの ``GPU`` は CPU、GPU 間のデータの通信時間も含めた時間、 ``GPU(kernel only)`` は kernel のみの実行時間である。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            Processor & Time(ms) \\ \hline
            1 CPU   & 1181.215 \\ \hline
            2 CPUs  & 627.914 \\ \hline
            4 CPUs  & 324.059 \\ \hline
            8 CPUs  & 159.932 \\ \hline
            16 CPUs & 85.518\\ \hline
            32 CPUs & 43.496 \\ \hline
            GPU & 127.018\\ \hline
            GPU(kernel only)& 6.018 \\ \hline
        \end{tabular}
        \caption{$2^{27}$ のデータに対する Twice}
        \label{tab:twice}
    \end{center}
\end{table}

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=70mm]{./pic/twice.pdf}
    \end{center}
    \caption{$2^{27}$ のデータに対する Twice}
    \label{fig:twice}
\end{figure}

ある程度の台数効果があると考えられる。

GPU での実行は kernel のみの実行時間は 32 CPU に比べて 約 7.2 倍の速度向上が見られた。
しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。
CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。

\subsection{BitonicSort}
BitonicSort は並列処理向けのソートアルゴリズムである。
代表的なソートアルゴリズムである Quick Sort も並列処理 を行うことが可能であるが、 QuickSort では ソートの過程で並列度が変動するため、台数効果が出づらい。
一方でBitonic Sort は最初から最後まで並列度が変わらずに並列処理を行う。
図\ref{fig:bitonicNetwork} は要素数8のデータに対する BitonicSort のソートネットワークである。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=70mm]{./pic/bitonicNetwork.pdf}
    \end{center}
    \caption{要素数8の BitonicNetwork}
    \label{fig:bitonicNetwork}
\end{figure}

BitonicSort はステージ毎に決まった2点間の要素の入れ替えを並列に実行することによってソートを行う。
Gears OS ではこのステージ毎に Output Data Gear を書き出し、 次のステージの Code Gear の Input Data Gear として記述することで BitonicSort を実現する。

要素数$2^{24}$ のデータに対する BitonicSort の実行結果を 表\ref{tab:bitonicSort}、図\ref{fig:bitonicSort}に示す。
こちらも Twice と同じくCPU 実行の際は $2^{24}$ のデータを 64個のTask に分割して並列実行を行っている。
つまり生成される Task は 64 * ステージ数 となる。
GPU では1次元の block 数を $2^{14}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。

\begin{table}[htbp]
    \begin{center}
        \begin{tabular}{|l||l|} \hline
            Processor & Time(s) \\ \hline
            1 CPU &  41.416 \\ \hline
            2 CPUs & 23.340\\ \hline
            4 CPUs & 11.952\\ \hline
            8 CPUs & 6.320\\ \hline
            16 CPUs & 3.336\\ \hline
            32 CPUs & 1.872\\ \hline
            GPU & 5.420\\ \hline
            GPU(kernel only)& 0.163\\ \hline
        \end{tabular}
        \caption{$2^{24}$ のデータに対する BitonicSort}
        \label{tab:bitonicSort}
    \end{center}
\end{table}

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=70mm]{./pic/bitonicSort.pdf}
    \end{center}
    \caption{$2^{24}$ のデータに対する BitonicSort}
    \label{fig:bitonicSort}
\end{figure}

1 CPU と 32 CPU で 約22.12 倍 の速度向上が見られた。
GPU では通信時間を含めると 8 CPU の約1.16倍となり、 kernel のみの実行では 32 CPU の約11.48倍となった。
現在の Gears OS の CUDA 実装では、 Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の実行結果の書き出しを行っており、その処理の時間で差が出たと考えられ
る。
GPU で実行される Task 同士の依存関係の解決の際はCuDevicePtr などのGPU のメモリへのポインタを渡し、CPU でデータが必要になったときに初めて GPU から CPU へデータの通
信を行うメタ計算の実装が必要となる。

\subsection{OpenMP との比較}
OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。
アノテーションを Code \ref{code:openMP} のように for 文の前につけることで、ループの並列化を行う。

\lstinputlisting[caption=OpenMP での Twice, label=code:openMP]{./src/openMP.c}

OpenMP は既存のコードにアノテーションを付けるだけで並列化を行えるため、変更が少なくて済む。
しかし、 ループのみの並列化ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになってしまう。
OpenMP はループの並列化 ではなくブロック単位での並列実行もサポートしているが、アノテーションの記述が増えてしまう。
また、 OpenMPはコードとデータを厳密に分離していないため、データの待ち合わせ処理をバリア等のアノテーションで記述する。

Gears OS では Input Data Gear が揃った Code Gear は並列に実行されるため、プログラム全体の並列度を高めることが出来る。
また 並列処理のコードとデータの依存関係を par goto 文で簡潔に記述することが出来る。

Gears OS と OpenMP で実装した Twice の実行結果の比較を図\ref{fig:vsopenmp} に示す。
実行環境は 表\ref{tab:powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。
static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=70mm]{./pic/vsopenmp.pdf}
    \end{center}
    \caption{vs OpenMP}
    \label{fig:vsopenmp}
\end{figure}

実行結果として OpenMP は 1CPUと 32CPU で約10.8 倍の速度向上がみられた。
一方 Gears OS では約 27.1 倍の速度向上のため、台数効果が高くなっている。
しかし、Gears OS は 1CPU での実行時間がOpenMP に比べて大幅に遅くなっている。

\subsection{Go 言語との比較}
Go 言語 は Google社が開発しているプログラミング言語である。
Go 言語によるTwice の実装例を code \ref{code:go}に示す。

\lstinputlisting[caption=Go 言語での Twice, label=code:go]{./src/go.go}

Go 言語は並列実行を ``go function(argv)'' のような構文で行う。
この並列実行を goroutine と呼ぶ。

Go 言語は goroutin 間のデータ送受信をチャネルというデータ構造で行う。
チャネルによるデータの送受信は ``\textless-'' を使って行われる。
例えばチャネルのデータ構造であるchannel に対して ``channel \textless- data'' とすると、 data を channel に送信を行う。
``\textless- channel'' とすると、 channel から送信されたデータを1つ取り出す。
channel にデータが送信されていない場合はchannel にデータが送信されるまで実行をブロックする。
Go 言語はチャネルにより、データの送受信が簡潔に書ける。
しかし、チャネルは複数の goroutine で参照できるためデータの送信元が推測しづらい。

Gears OS では goroutine は par goto 文とほぼ同等に扱うことが出来る。
また、Code Gear は par goto 文で書き出す Output Data Gear を指定して実行するため、Data Gear の書き出し元が推測しやすい。

Go 言語での OpenMP と同様に Twice を実装しGears OS と比較を行う。
こちらも実行環境は 表\ref{tab:powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS、Go 言語両方とも配列を64個のTask、 goroutineに分割して並列実行を行った。

\begin{figure}[ht]
    \begin{center}
        \includegraphics[width=70mm]{./pic/vsgo.pdf}
    \end{center}
    \caption{vs Go}
    \label{fig:vsgo}
\end{figure}

実行結果として Go 言語は 1CPUと32CPU で約4.33 倍の速度向上が見られた。


\section{結論}
本論文では Gears OS のプロトタイプの設計と実装、メタ計算である Context と stub の生成を行う Perl スクリプトの記述、並列実行機構の実装を行った。
Code Gear 、Data Gear を処理とデータの単位として用いて Gears OS を設計した。
Code Gear、Data Gear にはメタ計算を記述するための Meta Code Gear、Meta Data Gear が存在する。
メタ計算を Meta Code Gear、によって行うことでメタ計算を階層化して行うことができる。
Code Gear は関数より細かく分割されてるためメタ計算を柔軟に記述できる。
Gears OS は Code Gear と Input/Output Data Gear の組を Task とし、並列実行を行う。

Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface は複数の実装をもち、Meta Data Gear として定義される。
従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call するが、
Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、操作に対応する Code Gear に goto する。

Context は使用する Code Gear、Data Gear をすべて格納している Meta Data Gear である。
通常の計算から Context を直接扱うことはセキュリティ上好ましくない。
このため Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear である stub Code Gear を定義した。
stub Code Gear は Code Gear 毎に記述され、Code Gear 間の遷移に挿入される。

並列処理を行う際は Context を生成し、 Code Gear と Input/Output Data Gear を Context に設定して TaskManager 経由で各 Worker の SynchronizedQueue に送信される。
Context の設定はメタレベルの記述になるため、ノーマルレベルでは par goto 文という CbC の goto 文に近い記述で並列処理を行える。
この par goto は通常のプログラミングの関数呼び出しのように扱える。

これらのメタ計算の記述は煩雑であるため Perl スクリプトによる自動生成を行なった。
これにより Gears OS のコードの煩雑さは改善され、ユーザーレベルではメタを意識する必要がなくなった。

Twice と BitonicSort の例題の測定結果では 1CPU と 32CPU で Twice では約 27.1 倍、BitonicSort では 約 22.12 倍の速度向上が見られた。
また、GPU 実行の測定も行い、kernel のみの実行時間では 32 CPU より Twice では約 7.2 倍、BitonicSort では約 11.48 倍の速度向上がみられ、
GPU の性能を活かすことができた。

今後の課題は、
Go、OpenMP との比較から、 Gears OS が1CPU での動作が遅いということがわかった。
Gears OS は par goto 文を使用することで Context を生成し、並列処理を行う。
しかし、Context はメモリ空間の確保や使用する全ての Code/Data Gear を設定する必要があり、生成にある程度の時間がかかってしまう。
そこで、 par goto のコンパイルタイミングで実行する Code Gear のフローをモデル検査で解析し、処理が軽い場合はContext を生成せずに、関数呼び出しを行う等の最適化を行>うといったチューニングが必要である。


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

\end{document}