--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gearsos.tex	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,102 @@
+\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 はヒープサイズを示す heap\_limit, ヒープの初期位置を示す heap\_start, ヒープの現在位置を示す heap を持っている。
+必要な Data Gear のサイズに応じて heap の位置を動かすことで Allocation を実現する。
+
+allocate を行うには allocate に必要な Data Gear に情報を書き込む必要がある。
+この Data Gear は Context 生成時に生成する必要がある。
+
+Temporal Data Gear にある Data Gear は基本的には破棄可能なものなので heap\_limit を超えたら heap を heap\_start の位置に戻し、ヒープ領域を再利用する(図:\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 を行うコードはソースコード:\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}
+
+\section{List}
+\section{Synchronized Queue}
+\section{Red-Black Tree}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/allocation.bb	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/allocation.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 1064 396
+%%CreationDate: Tue Feb  9 03:13:52 2016
+

Binary file images/allocation.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/gearsos.bb	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/gearsos.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 1312 427
+%%CreationDate: Tue Feb  9 03:18:30 2016
+

Binary file images/gearsos.pdf has changed

Binary file images/images.graffle has changed

--- a/master_paper.tex	Fri Feb 05 04:17:47 2016 +0900
+++ b/master_paper.tex	Tue Feb 09 04:21:34 2016 +0900
@@ -49,8 +49,9 @@
   aboveskip=1zw,
   numberstyle={\scriptsize},%
   stepnumber=1,
-  numbersep=1zw,%
-  lineskip=-0.5ex%
+  numbersep=0.5zw,%
+  lineskip=-0.5ex,
+  numbers=left
 }
 
 %%% 索引のために以下の2行を追加
@@ -84,27 +85,7 @@
 \chapter{並列分散環境下におけるプログラミング}
 \input{cerium.tex}
 \chapter{CbC}
-\chapter{GearsOS}
-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 以外にアクセスできない。
-
-\section{GearsOS の構成}
-Gears OS は
-\section{Allocator}
-\section{List}
-\section{Synchronized Queue}
-\section{Red-Black Tree}
-
+\input{gearsos.tex}
 \chapter{比較}
 \section{Cerium}
 \section{従来の OS}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/allocate.c	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,47 @@
+// Code Gear
+__code start_code(struct Context* context) {
+    // start processing
+    goto meta(context, context->next);
+}
+
+// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Code Gear
+__code code1(struct Context* context, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Data1);
+    context->next  = Code2;
+    
+    goto meta(context, Allocator);
+}
+
+// Meta Code Gear(stub)
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Allocate]->allocate);
+}
+
+// Meta Code Gear
+__code allocator(struct Context* context, struct Allocate* allocate) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap                    += allocate->size;
+
+    goto meta(context, context->next);
+}
+
+// Meta Code Gear(stub)
+__code allocator_stub(struct Context* context) {
+    goto allocator(context, &context->data[Allocate]->allcate);
+}
+
+// Code Gear
+__code code2(struct Context* context, struct Data1* data1) {
+    // processing
+}
+
+// Meta Code Gear(stub)
+__code code2_stub(struct Context* context) {
+    goto code2(context, &context->data[context->dataNum]->data1);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/context.h	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,37 @@
+/* Context definition example */
+#define ALLOCATE_SIZE 1000
+
+enum Code {
+    Code1,
+    Code2,
+    Allocator,
+    Exit,
+};
+
+enum UniqueData {
+    Allocate,
+};
+
+struct Context {
+    enum Code next;
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+
+union Data {
+    struct Data1 {
+        int i;
+    } data1;
+    struct Data2 {
+        int i;
+        char c;
+    } data2;
+    struct Allocate {
+        long size;
+    } allocate;
+};

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/initContext.c	Tue Feb 09 04:21:34 2016 +0900
@@ -0,0 +1,28 @@
+#include <stdlib.h>
+
+#include "context.h"
+
+extern __code code1_stub(struct Context*);
+extern __code code2_stub(struct Context*);
+extern __code allocator_stub(struct Context*);
+extern __code exit_code(struct Context*);
+
+__code initContext(struct Context* context, int num) {
+    context->heapLimit        = sizeof(union Data)*ALLOCATE_SIZE;
+    context->heapStart        = malloc(context->heapLimit);
+    context->heap             = context->heapStart;
+    context->codeNum          = Exit;
+    
+    context->code             = malloc(sizeof(__code*)*ALLOCATE_SIZE);
+    context->data             = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
+
+    context->code[Code1]      = code1_stub;
+    context->code[Code2]      = code2_stub;
+    context->code[Allocator]  = allocator_stub;
+    context->code[Exit]       = exit_code;
+    
+    context->data[Allocate]   = context->heap;
+    context->heap            += sizeof(struct Allocate);
+    
+    context->dataNum          = Allocate;
+}