Mercurial > hg > Papers > 2015 > parusu-midterm

Binary file midterm.pdf has changed
--- a/midterm.tex	Thu Oct 29 15:17:04 2015 +0900
+++ b/midterm.tex	Thu Oct 29 22:19:31 2015 +0900
@@ -35,29 +35,20 @@
 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
 これは Alice の Code Segment、 Data Segment にそれぞれ対応する。

-Ceriumは初め、Cell\cite{cell} 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行形式が異なっている。
-Gears OSでは Many Core CPU、GPUをはじめとする様々なプロセッサを同等な実行機構でサポートする。
-
-Cerium は C++で実装されているが、オブジェクトと並列処理が直接対応していないのでオブジェクト指向で記述する利点が少ない。
-Alice は Javaで実装されており、実効速度が遅いという問題がある。
-Gears OS は本研究室で開発している CbC(Continutaion based C)\cite{cbc-llvm} を用いて実装を行う。
-CbC は処理を Code Segment で記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。
-
 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
 Meta Computationは本論のComputationを支えるComputationのことである。
 関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
 Gears OS では、Meta Code Gear, Meta Data Gear を Monadとして定義し、Meta Computationを実現する。

-Gears OS は並列実行をサポートするだけでなく、 信頼性も確保する。
-そのために Gears OSを用いて作成されたプログラムに対する Model Checkingを行う機能\cite{model-check}を提供する。
-並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。
-これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
-Model Checking の実現には Meta Code Gear, Meta Data Gearを用いる。
+Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
+また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御を用いた信頼性の確保を目的とする。

-Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
-また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
+今回基本的な設計と Gears で Cerium 同等の機能を実装するため DB の実装の中で扱う AVL Tree、並列で Data や Taskを振り分けるための Synchronized Queue を実装した。

 \section{Continuation based C}
+Gears OS は本研究室で開発している CbC(Continuation based C)\cite{cbc-llvm} を用いて実装を行う。
+CbC は処理を Code Segment で記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。
+
 CbC のプログラムでは C の関数の代わりに Code Segment を用いて処理を記述している。
 Code Segment は C の関数と異なり戻り値を持たない。
 Code Segment の宣言はCの関数の構文と同様に行い、型に \_\_code を使うことで宣言できる。
@@ -94,26 +85,6 @@
 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。
 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。

-Code Gear, Data Gear はポインタを直接には扱わない。
-これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフローを防止する。
-
-Code Gear, Data Gear はそれぞれ関係を持っている。
-例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ Data Gear などである。
-Gear の関連付けは Meta Gear を通して行う。
-Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当する。
-なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
-
-図\ref{fig:list} は 通常の List の表現と Code Gear, Data Gear を使った List の表現である。
-通常の List は要素と次へのポインタをもつ構造体で表現される。
-Code Gear, Data Gear を使った List  の場合、 Meta レベル以外でポインタを扱わないため、任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。
-
-\begin{figure}[ht]
-    \centering
-    \includegraphics[width=70mm]{pic/List.pdf}
-    \caption{List の表現}
-    \label{fig:list}
-\end{figure}
-
 \section{Context}
 ある Code Gear から継続するときには、次に実行する Code Gear を名前で指定する。
 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
@@ -130,13 +101,26 @@
     \item Data Gear に格納される Data Type の情報
 \end{itemize}

+\section{List}
+List は Synchronized Queue を実装するために必要なデータ構造である。
+通常の List は要素と次へのポインタをもつ構造体で表現される。
+Gears OS の場合はMeta レベルでポインタを扱うため、 図\ref{fig:list} のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。
+
+\begin{figure}[ht]
+    \centering
+    \includegraphics[width=70mm]{pic/List.pdf}
+    \caption{List の表現}
+    \label{fig:list}
+\end{figure}
+
 \section{Synchronized Queue}
 Synchronized Queue は Gear OS 内の Task を配るために必要なデータ構造である。
 Gears OS では List を表現する Code Gear, Data Gear に CAS(Compare and Swap) を行う Meta Code Gear, Meta Data Gear を接続することで Synchronized Queue を実現する。
 Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。
 この図を GearBox と呼ぶことにする。
-図\ref{fig:sync}は Synchronized Queue の GearBox である。
-M:get/put が CAS を行う Meta Code Gear となる。
+図\ref{fig:sync}は Synchronized Queue の Get 処理の GearBox である。
+M:get が CAS で データの取り出しの際の書き換えを行う Meta Code Gear となる。
+Put 処理を行う場合はこの Get 処理の流れはそのままに Put の処理を記述することになる。
 今回は CAS で実装しているが、接続する Meta Code Gear を変更することで通常のQueueやMutexを使用したsynchronizedQueueなど仕様変更にも対応できる。

 \begin{figure}[ht]
@@ -169,17 +153,9 @@
         河野真治，杉本　優：Code Segment と Data Segment
         によるプログラミング手法，第54回プログラミング・シンポジウム (2013).

-    \bibitem{cell}
-        {Sony Corporation}: {Cell broadband engine architecture} (2005).
-
     \bibitem{monad}
         Eugenio Moggi, Notion of Computation and Monads(1991)

-    \bibitem{model-check}
-        下地篤樹，河野真治：線形時相論理によるContinuation based
-        Cプログラムの検証，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
-        (2007).
-
     \bibitem{cbc-llvm}
         徳森海斗，河野真治：Continuation based C の LLVM/clang 3.5
         上の実装について，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
--- a/pic/synchronizedQueue.bb	Thu Oct 29 15:17:04 2015 +0900
+++ b/pic/synchronizedQueue.bb	Thu Oct 29 22:19:31 2015 +0900
@@ -1,5 +1,5 @@
 %%Title: synchronizedQueue.pdf
 %%Creator: extractbb 20150315
-%%BoundingBox: 0 0 505 821
-%%CreationDate: Sun Oct 25 04:25:56 2015
+%%BoundingBox: 0 0 503 413
+%%CreationDate: Thu Oct 29 22:04:53 2015
Binary file pic/synchronizedQueue.pdf has changed
--- a/pic/synchronizedQueue.xbb	Thu Oct 29 15:17:04 2015 +0900
+++ b/pic/synchronizedQueue.xbb	Thu Oct 29 22:19:31 2015 +0900
@@ -1,8 +1,8 @@
 %%Title: synchronizedQueue.pdf
 %%Creator: extractbb 20150315
-%%BoundingBox: 0 0 505 821
-%%HiResBoundingBox: 0.000000 0.000000 505.000000 821.000000
-%%PDFVersion: 1.4
+%%BoundingBox: 0 0 503 413
+%%HiResBoundingBox: 0.000000 0.000000 503.000000 413.000000
+%%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Oct 25 04:25:48 2015
+%%CreationDate: Thu Oct 29 22:04:50 2015