Binary file paper/pic/gearsos.graffle has changed

Binary file paper/pic/gearsos.pdf has changed

Binary file paper/pic/persistent_date_tree.graffle has changed

Binary file paper/pic/persistent_date_tree.pdf has changed

Binary file paper/pic/twice_640.pdf has changed

Binary file paper/sigos.pdf has changed

--- a/paper/sigos.tex	Fri May 06 19:00:48 2016 +0900
+++ b/paper/sigos.tex	Sun May 08 02:41:43 2016 +0900
@@ -5,26 +5,27 @@
 \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=1zw,%
-  lineskip=-0.5ex%
+    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}
 
 \input{dummy.tex} %% Font 
 
@@ -89,6 +90,7 @@
 % Introduce
 \section{GearsOS}
 
+
 \section{Code Gear と Data Gear}
 Gears OS はプログラムの単位として Gear を用いる。
 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。
@@ -151,18 +153,154 @@
 
 \begin{figure}[ht]
     \begin{center}
-        \includegraphics[width=80mm]{./pic/gearsos.pdf}
+        \includegraphics[width=70mm]{./pic/gearsos.pdf}
     \end{center}
     \caption{gotoによる Code Segment 間の接続}
     \label{fig:gearsos}
 \end{figure}
 
 \section{Context}
+Context は接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、 Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。
+Gears OS では必要な Code/Data Gear に参照したい場合、このContext を通す必要がある。
+
+メインとなる Context と Worker 用 Context があり、 TaskQueue と Persistent Data Tree は共有される。
+Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することは出来ない。
+Worker 間の相互作用は Persistent Data Tree への読み書きのみで行う。
+
 \section{TaskQueue}
+Gears OS における Task Queue は Synchronized Queue で実現される。
+メインとなる Context と Worker 用 の Context で共有され、 Worker が TaskQueue から Task を取得し、実行することで並列処理を行う。
+
+Gears OS の Queue は Queue を表す Data Gear と List を表現する Element という名前の Data Gear を組み合わせて表現する。
+Queue を表す Data Gear には List 構造の先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。
+Element を表す Data Gear は、Task を示す task、 次の Element を示す next が格納される。
+
+Queue に対して操作を行う場合、 Queue 自体の Data Gear を書き換える。
+Task を 挿入する場合、 新しく Element を生成し、 Queue の last から List 構造の末尾に新しい Element を追加し、 Queue の last を書き換える。
+Task を 取得する場合、 Queue の first から List 構造を最初の要素を取り出し、 取り出した要素の次の要素の参照を Queue の first に書き込む。
+
+Gears OS の TaskQueue はマルチスレッドでの操作を想定しているため、データの一貫性を保証する必要がある。
+そのため、データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行っている。
+CAS はデータの比較・置換をアトミックに行う命令である。 
+メモリからデータの読みだし、変更、メモリへのデータの書き出しという一連の処理を CAS を利用することで処理の間に他のスレッドがメモリに変更を加えないことを保証することができる。
+CAS に失敗した場合は置換を行わず、再びデータの呼び出しから始める。
+
+Code \ref{src:sync_enqueue} に CAS を使用した Task 挿入を示している。
+Code \ref{src:sync_enqueue} は 2つのCode Gear を定義しており、 putQueue3 は要素がある場合、 putQueue4 は要素がない場合の Task 挿入を示している。
+
+\lstinputlisting[label=src:sync_enqueue, caption=Enqueue]{./src/sync_enqueue.c}
+
+\section{Persistent Data Tree}
+Gears OS は Persistent Data Gear の管理に木構造を用いる。
+この木構造は非破壊的で構成される。
+非破壊木構造とは図\ref{fig:persistent_data_tree}のように一度構築した木構造を破壊すること無く新しい木構造を構築することで、木構造を編集する方法である。
+非破壊木構造は木構造を書き換えることなく編集を行うため、読み書きを平行して行うことが可能である。
+
+\begin{figure}[ht]
+    \begin{center}
+        \includegraphics[width=80mm]{./pic/persistent_date_tree.pdf}
+    \end{center}
+    \caption{木構造の非破壊的編集}
+    \label{fig:persistent_data_tree}
+\end{figure}
+
+Gears OS では Data Tree として木構造を利用する。
+その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。 
+最悪なケースでは線形リストになり、計算量が O(n) となる。
+
+そのため、挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。
+Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。
+
+\begin{itemize}
+\item 各ノードは赤または黒の色を持つ。
+\item ルートの色は黒である。
+\item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。
+\item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。
+\end{itemize}
+
+これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。
+
+\section{Worker}
+Worker は TaskQueue から Task を取得し、実行する。
+Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。
+実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。
+
+各 Worker は個別の Context を参照しており、 メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。
+ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。
+
+Worker が Task の取得を行う Code Gear を Code \ref{src:sync_dequeue} に示す。
+Task Queue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。
+
+\lstinputlisting[label=src:sync_dequeue, caption=GetTask]{./src/sync_dequeue.c}
+
+Worker から取得された Task の Code Gear は並列実行される。
+並列実行される Code Gear と言っても他の Code Gear と同じである。
+これは Gears OS 自体が Code Gear によって構成されていることに起因する。
+つまり、 Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないとき、全て並列に実行することができる。
+
 \section{TaskManager}
-% 依存関係もここに書く
-\section{Persistent Data Tree}
-\section{Worker}
+Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。
+Task には
+
+\section{評価}
+Gears OS の評価として依存関係のない例題の並列実行を行った。
+
+今回使用した例題は Twice という整数配列を2倍にする例題である。
+Code \ref{src:twice} に Twice の処理を行う Code Gear を示す。
+
+\lstinputlisting[label=src:twice, caption=Twice]{./src/twice.c}
+
+以下に今回の処理の流れを示す。
+
+\begin{itemize}
+\item 配列サイズを元に index, alignment, 配列へのポインタを持つ Data Gear に分割。
+\item Data Gear を Persistent Data Tree に挿入。
+\item 実行する Code Gear(Twice) と実行に必要な Data Gear への key を持つ Task を生成。
+\item 生成した Task を TaskQueue に挿入。
+\item Worker の起動。
+\item Worker が TaskQueue から Task を取得。
+\item 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得。
+\item 並列の処理される Code Gear(Twice) を実行。
+\end{itemize}
+
+要素数$2^17$*1000 のデータを640個の Task に分割し、コア数を変更して測定を行った結果を表\ref{table:result}、図\ref{fig:result}に示す。
+
+\begin{table}[ht]
+  \begin{center}
+    \small
+    \begin{tabular}[htpb]{|c||c|c|c|}
+      \hline
+      Processor & Time(ms) \\
+      \hline
+      \hline
+      1 CPU & 1315 \\
+      \hline
+      2 CPUs & 689 \\
+      \hline
+      4 CPUs & 366 \\
+      \hline
+      8 CPUs & 189 \\
+      \hline
+      12 CPUs & 111 \\
+      \hline
+    \end{tabular}
+    \caption{要素数$2^{17}$*1000 のデータに対する Twice}
+    \label{table:result}
+  \end{center}
+\end{table}
+
+\begin{figure}[ht]
+  \begin{center}
+    \includegraphics[width=70mm]{pic/twice_640.pdf}
+  \end{center}
+  \caption{要素数$2^{17}$*1000 のデータに対する Twice}
+  \label{fig:result}
+\end{figure}
+
+結果から、 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた。
+しかし、 タスクの粒度が小さすぎると CAS の失敗が多くなり、性能がでないことがある。
+Code Gear には実行時間を予想可能なものにするという特徴があるため、タスクが最適な粒度なのかを検査する機能が必要になると考えられる。
+
 \section{まとめ}
 
 \nocite{*}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/sync_dequeue.c	Sun May 08 02:41:43 2016 +0900
@@ -0,0 +1,20 @@
+// Dequeue
+__code getQueue(struct Context* context, struct Queue* queue, struct Node* node) {
+    if (queue->first == 0)
+        return;
+
+    struct Element* first = queue->first;
+    if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) {
+        queue->count--;
+
+        context->next = GetQueue;
+        stack_push(context->code_stack, &context->next);
+
+        context->next = first->task->code;
+        node->key = first->task->key;
+
+        goto meta(context, Get);
+    } else {
+        goto meta(context, GetQueue);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/sync_enqueue.c	Sun May 08 02:41:43 2016 +0900
@@ -0,0 +1,25 @@
+// Enqueue(normal)
+__code putQueue3(struct Context* context, struct Queue* queue, struct Element* new_element) {
+    struct Element* last = queue->last;
+
+    if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
+        last->next = new_element;
+        queue->count++;
+        
+        goto meta(context, context->next);
+    } else {
+        goto meta(context, PutQueue3);
+    }
+}
+
+// Enqueue(nothing element)
+__code putQueue4(struct Context* context, struct Queue* queue, struct Element* new_element) {
+    if (__sync_bool_compare_and_swap(&queue->first, 0, new_element)) {
+        queue->last = new_element;
+        queue->count++;
+        
+        goto meta(context, context->next);
+    } else {
+        goto meta(context, PutQueue3);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/twice.c	Sun May 08 02:41:43 2016 +0900
@@ -0,0 +1,16 @@
+// Twice
+__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int alignment, int* array) {
+    int i = loopCounter->i;
+
+    if (i < alignment) {
+        array[i+index*alignment] = array[i+index*alignment]*2;
+        loopCounter->i++;
+
+        goto meta(context, Twice);
+    }
+
+    loopCounter->i = 0;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}