# HG changeset patch
# User ikkun
# Date 1477063719 -32400
# Node ID 1b5ee04a7b4f963fcfb951f722e0c18cf248d3e4
# Parent  ece8fc16ff1d64220541733f3767e45630f188cb
rewarit

diff -r ece8fc16ff1d -r 1b5ee04a7b4f midterm.tex
--- a/midterm.tex	Fri Oct 21 23:09:43 2016 +0900
+++ b/midterm.tex	Sat Oct 22 00:28:39 2016 +0900
@@ -26,38 +26,24 @@
 \thispagestyle{fancy} 
 
 \section{Gears OS}
-本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散フレームワーク Alice\cite{alice} の開発を行なってきた。
-
-Cerium と Alice を開発して得られた知見から、並列分散処理の信頼性を向上させるにはCodeの分割だけでなくDataの分割も必要であることがわかった。それををふまえ Gears OS\cite{gears}を設計、実装している。\\
-Alice では処理の単位である Code Segment、 データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
 Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
-Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
-これは Alice の Code Segment、 Data Segment にそれぞれ対応する\\
+Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear
+に細かく分割する。
+Gearで表現される計算はメタ計算により実行される。例えば、
 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
-Meta Computationは本論のComputationを支えるComputationのことである。
-関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
-Gears OS では、Meta Code Gear, Meta Data Gear を Monadとして定義し、Meta Computationを実現する。\\
-また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性\
-、Monad に基づくメタ計算による並行制御を用いた信頼性の確保を目的とする。
+接続する Gear を変更することでプログラムの振る舞いを変更することを可能
+にする柔軟性、メタ計算による並行制御,モデル検査を用いた信頼性の確保を目的とする。
+本研究では現状のGears OS のマルチCPUサポートに加えてGPGPUサポートを行
+う。
+GPGPUはCUDAまたはOpeCLで制御される。Gears OSからCide Gear Data Gearを
+これらに正しく渡す必要がある。
 
-\section{Continuation based C}
-CbC のプログラムでは C の関数の代わりに Code Segment を用いて処理を記述している。
-Code Segment は C の関数と異なり戻り値を持たない。
-Code Segment の宣言はCの関数の構文と同様に行い、型に \_\_code を使うことで宣言できる。
-
-Code SegmentからCode Segmentへの移動は goto の後にCode Segment 名と引数を並べて記述するという CbC独自の構文で行う。
-この goto による処理の遷移を継続と呼ぶ。 
-図\ref{fig:codesegment}はCode Segment 間の継続関係を表している。
-
-C では関数呼び出しを繰り返し行う場合、呼びだされた関数の引数の数だけスタックに値が積まれていくが、戻り値を持たない Code Segment ではスタックに値を積んでいく必要が無くスタックを変更する必要が無い。
-このようなスタックに値を積まない継続、つまり呼び出し元の環境を持たない継続を軽量継続と呼び、軽量継続による並列化、ループ制御、関数コールとスタックの意識した最適化がソースコードで行えるようになる。
-
-\begin{figure}[ht]
-    \centering
-    \includegraphics[width=65mm]{pic/codesegment.pdf}
-    \caption{goto による Code Segment 間の継続}
-    \label{fig:codesegment}
-\end{figure}
+Gears OS上のTaskはRed Black Tree上に格納される。rb\_treeはCbCで記述さ
+れており、木をたどるためのStackを一つ持つ。
+アルゴリズム全体はCode Gearの有向グラフで表される。実際にこの有向グラ
+フを作成した。これは一種のフローチャートになっている。木とStackに格納
+されるのはData Gearである。この木を用いて GPGPUを実行するエンジンに
+Taskを渡す。
 
 
 \section{Code Gear と Data Gear}
@@ -70,18 +56,21 @@
 Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
 その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
 
-Data Gear には、int や文字列などの Primitive Data Type が入る。
+Data Gear は、int や文字列などの Primitive Data Type の組み合わせ
+（struct）である。
+Data Gearは様々な型を持つunionとして定義される。
 
 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
 
 \section{Context}
-ある Code Gear から継続するときには、次に実行する Code Gear を名前で指定する。
+ある Code Gear は次に実行する Code Gear を名前で指定する。これを継続と
+いう。
 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
 この Meta Data Gear を Context と呼ぶことにする。
-これは従来の OS の Process や Thread に対応する。
+これは従来の OS の Process や Thread を表す構造体に対応する。
 
 Context には以下のようなものが格納される。
 \begin{itemize}
@@ -92,7 +81,7 @@
 \end{itemize}
 
 \section{Red Black Tree}
- Red Black Tree(赤黒木)は平衡二分木の一種で、主に連想配列の実装に使われる。Red Black Tree の Stack Pop,Stack Push している部分に Stub を仲介させることによって、Stack pop と Stack psuh を Data Segment に分けることで CbC による記述に直した。
+ Red Black Tree(赤黒木)は平衡二分木の一種で、主に連想配列の実装に使われる。Red Black Tree の Stack Pop,Stack Push している部分に Stub を仲介させることによって、Stack pop と Stack psuh を Data Gear に分けることで CbC による記述に直した。
 \begin{figure}[ht]
     \centering
     \includegraphics[width=70mm]{pic/rb_tree.pdf}