\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} はシングルスレッドでは正常に動作するが、マルチスレッドでは期待した動作を達成できない可能性がある。
並列実行すると同じメモリ位置にアクセスされる可能性があり、データの一貫性が保証できないからである。
データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行うように変更する必要がある。
CAS はデータの比較・置換をアトミックに行う命令である。
メモリからのデータの読み出し、変更、メモリへのデータの書き出しという一連の処理を、CAS を利用することで処理の間に他のスレッドがメモリに変更を加えていないということを保証することができる。
CAS に失敗した場合は置換は行わず、再びデータの読み出しから始める。

ソースコード:\ref{enqueue} 44行目の putQueue3, 51行目の putQueue4, ソースコード:\ref{dequeue} 2行目の getQueue が実際に Queue を操作している Code Gear である。
これらの Code Gear から CAS を利用したソースコード:\ref{sync_enqueue}, ソースコード:\ref{sync_dequeue} の Code Gear に接続を変更することでスレッドセーフな Queue として扱うことが可能になる。
Code Gear は Gears OS における最小の処理単位となっており、接続を変更することでプログラムの振る舞いを柔軟に変更することができる。

\lstinputlisting[label=sync_enqueue, caption=Enqueue using CAS]{src/sync_enqueue.c}
\lstinputlisting[label=sync_dequeue, caption=Dequeue using CAS]{src/sync_dequeue.c}

\section{Worker}

\section{Red-Black Tree}
Gears OS では Persistent Data Gear の管理に木構造を用いる。

\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 へ移動させる。

TaskManager は Worker の管理も行う。
メインとなる Context には Worker の情報が格納されており、TaskManager はこの Context を参照して Worker の起動・停止を行う。
ソースコード\ref{init_worker}は Worker を起動する Code Gear である。