\chapter{Gears OSの並列処理}
\section{並列処理の構成}

\section{TaskManager}
Gears OS の TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。
\coderef{taskManagerInterface} に TaskManager の Interface を示す。

\lstinputlisting[caption=TaskManager の Interface, label=code:taskManagerInterface]{./src/taskManagerInterface.cbc}

TaskManager は 以下の API を持っている。

\begin{itemize}
    \item Task の実行(spawn, spawnTasks)
    \item Task の依存関係の設定(setWaitTask)
    \item TaskManager が管理している Task 数のインクリメントとデクリメント(increment/decrementTaskCount)
    \item TaskManager(shutdown)の終了処理
\end{itemize}

\coderef{createTaskManager}  に TaskManager Interface を実装した Data Gear の初期化部分を示す。
TaskManager は初期化の際に、指定した数の Worekr を生成する。
その際CPU、GPU の数を指定することができ、指定した分の CPUWorker と GPUWorker が createWorker 関数 (\coderef{createTaskManager} 27-46行目) で生成される。

\lstinputlisting[caption=TaskManager の初期化, label=code:createTaskManager]{./src/createTaskManager.cbc}

TaskManager は \figref{sendTask}に示すように spawn を呼び出した際、実行する Task の Input Data Gear が用意されているかを判断する。
Input Data Gear が全て用意されている場合、その Task を Worker の Queue に送信する。
 送信する Worker は Task を実行する環境(CPU、GPU) によって決定する。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/sendTask.pdf}
    \end{center}
    \caption{Workerへの Task 送信}
    \label{fig:sendTask}
\end{figure}

\section{Worker}
Worker は自身の Queue から Task を取得し、Task の Code Gear を実行し、 Output Data Gear の書き出しを行っている。

\coderef{createCPUWorker} に Task を CPU で実行する CPUWorker の初期化部分を示す。
CPUWorker は初期化の際に スレッドを生成する(\coderef{createCPUWorker} 10行目)。
生成されたスレッドはまず startWorker 関数(\coderef{createCPUWorker} 14-21行目)を呼び出し、このスレッド用の Context を生成する。
Context をスレッド毎に生成することで、メモリ空間をスレッドごとに持てるため Gearefマクロ で interface の引数を取得する際の競合、メモリ確保の処理での他のスレッドの停止を防ぐ事ができる。

\lstinputlisting[caption=CPUWorker の初期化, label=code:createCPUWorker]{./src/createCPUWorker.cbc}

Context の生成後は Queue から Task を取得する Code Gear へ継続する。
Task は Context なので、 Worker は Context を入れ替えて Task の実行を行う。

CPUWorker での Task の実行を\coderef{workerRun} に示す。
\coderef{workerRun} は Context の入れ替えを行うため、 Meta Code Gear として記述されており、getTaskCPUWorker(\coderef{workerRun} 1-9行目)の引数に Context を記述している。
CPUWorker は中身が NULL の task を取得すると Worker の終了処理を行う(\coderef{workerRun} 2-4 行目)。
Task が取得できた場合 Task の実行後に継続する Code Gear を格納し(\coderef{workerRun} 7行目)、 Task を Context としてCode Gear に継続する(\coderef{workerRun} 8行目)。
Task の実行後に継続する Code Gear は Data Gear の書き出しと依存関係の解決を行う。

\lstinputlisting[caption=CPUWorker でのTaskの実行, label=code:workerRun]{./src/workerRun.cbc}

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

Gears OS では マルチスレッドでもデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue\cite{queue} を実装している。
CAS は値の比較、更新をアトミックに行う命令である。
CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。
異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。

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

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

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

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

SynchornizedQueue では\coderef{atomicImpl} で示した Code Gear を呼び出して実装を行う。

\section{依存関係の解決}
\section{並列処理の記述}
\section{Iterator}
\section{待ち機構}