\chapter{Gears OS}
Cerium と Alice の開発を通して得られた知見から並列分散処理には Code の分割だけではなく Data の分割も必要であることがわかった。
当研究室で開発している Code Segment を基本的な処理単位とするプログラミング言語 Continuation based C(CbC) を用いて Data Segment を定義し、Gears OS の設計と基本的な機能の実装を行なった。

本章では Gears OS の設計と実装した基本的な機能について説明する。
\section{Code Gear と Data Gear}
Gears OS ではプログラムの単位として Gear を用いる。
Gear は並列実行の単位、データの分割、Gear 間の接続等になる。

Code Gear はプログラムの処理そのものになる。
これは OpenCL/CUDA の kernel, Cerium の Task に相当する。
Code Gear は任意の数の Data Gear を参照し、処理が完了すると 任意の数の Data Gear に書き込む。
Code Gear は接続された Data Gear 以外にアクセスできない。
Code Gear から次の Code Gear への処理の移動は goto の後に Code Gear の名前と引数を指定することで実現できる。
Code Gear は Code Segment そのものである。

Data Gear はデータそのものを表す。
int や文字列などの Primitive Data Type を持っている。

Gear の特徴として処理やデータの構造が Code Gear, Data Gear に閉じていることにある。
これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。

\section{Gears OS の構成}
Gears OS は以下の要素で構成される。
\begin{itemize}
\item Context \\
  接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear のためのメモリ空間等を持っており、Context を通してアクセスすることができる。
  メインとなる Context と Worker 用の Context があり、TaskQueue と Persistent Data Tree は共有される。
  Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
  Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
\item TaskQueue \\
  ActiveTaskQueue と WaitTaskQueue の2つの TaskQueue を持つ。
  先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。
  Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。
  Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。
\item TaskManager \\
  Task には Input Data Gear, Output Data Gear が存在する。
  Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。
  依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。
  TaskManager はメインとなる Context を参照する。
\item Persistent Data Tree \\
  非破壊木構造で構成された Lock-free なデータストアである。
  Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。
\item Worker \\
  TaskQueue から Task の取得・実行を行う。
  Task の処理に必要なデータは Persistent Data Tree から取得する。
  処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。
\end{itemize}

図:\ref{fig:gearsos} は Gears OS の構成図である。

\begin{figure}[!ht]
  \begin{center}
    \includegraphics[scale=0.35]{./images/gearsos.pdf}
  \end{center}
  \caption{Gears OS}
  \label{fig:gearsos}
\end{figure}

\newpage

\section{Allocator}
Gears OS では Context の生成時にある程度の大きさのメモリ領域を確保する。
Context には確保したメモリ領域を指す情報が格納される。
このメモリ領域を利用して Task の実行に必要な Data Gear を生成する。

Context の定義と生成はソースコード:\ref{context},ソースコード:\ref{initcontext} の通りである。

\lstinputlisting[label=context, caption=Context]{src/context.h}
\lstinputlisting[label=initcontext, caption=initContext]{src/initContext.c}

Context はヒープサイズを示す heapLimit, ヒープの初期位置を示す heapStart, ヒープの現在位置を示す heap を持っている。
必要な Data Gear のサイズに応じて heap の位置を動かすことで Allocation を実現する。

allocate を行うには allocate に必要な Data Gear に情報を書き込む必要がある。
この Data Gear は Context 生成時に生成する必要があり、ソースコード:\ref{context} 14行目の Allocate がそれに当たる。
UniqueData で定義した Data Gear は Context と同時に生成される。

Temporal Data Gear にある Data Gear は基本的には破棄可能なものなので heapLimit を超えたら heap を heapStart の位置に戻し、ヒープ領域を再利用する(図:\ref{fig:allocation})。
必要な Data Gear は Persistent Data Tree に書き出すことで他の Worker からアクセスすることが可能になる。

\begin{figure}[!ht]
  \begin{center}
    \includegraphics[scale=0.4]{./images/allocation.pdf}
  \end{center}
  \caption{Allocation}
  \label{fig:allocation}
\end{figure}

実際に allocate を行う Code Gear はソースコード:\ref{allocate} の通りである。

Context 生成時に実行可能な Code Gear と名前が対応付けられる。
その対応付けられた Code Gear が Context の code に格納される。
この code を介して遷移先の Code Gear を決定する。

Code Gear には Context が接続されるが Context を介して Data Gear にアクセスすることはない。
stub を介して間接的に必要な Data Gear にアクセスする。

\lstinputlisting[label=allocate, caption=allocate]{src/allocate.c}

\newpage

\section{Synchronized Queue}
Gears OS における Synchronized Queue は TaskQueue として利用される。
メインとなる Context と Worker 用の Context で共有され、Woker が TaskQueue から Task を取得し実行することで並列処理を実現する。

Gears OS での Queue を Queue を表す Data Gear と Queue の構成要素である Element によって表現する。
Queue を表す Data Gear には先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。
Element を表す Data Gear には Task を示す task, 次の Element を示す next が格納される。

ソースコード:\ref{queue} は Context の定義(ソースコード:\ref{context})に追加する Queue と Element の定義である。

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

新たに Queue に対する操作を行う Code Gear の名前を追加し、UniqueData には Queue の情報が入る Queue(ソースコード:\ref{queue} 9行目) と Enqueue に必要な情報を書き込む Element(ソースコード:\ref{queue} 10行目) を定義している。

通常の Enqueue, Dequeue を行う Code Gear はソースコード:\ref{enqueue} と ソースコード:\ref{dequeue} の通りである。

\lstinputlisting[label=enqueue, caption=Enqueue]{src/enqueue.c}
\lstinputlisting[label=dequeue, caption=Dequeue]{src/dequeue.c}

ソースコード:\ref{enqueue} とソースコード:\ref{dequeue} はシングルスレッドでは正常に動作するが、並列実行すると期待した値にならない。

\section{Red-Black Tree}