Mercurial > hg > Papers > 2016 > parusu-sigos

--- a/paper/sigos.bib	Sun May 08 02:41:43 2016 +0900
+++ b/paper/sigos.bib	Sun May 08 14:59:00 2016 +0900
@@ -9,11 +9,11 @@

 @article{
     alice,
-    author = "赤嶺 一樹 and 河野 真治",
-    title = "DataSegment API を用いた分散フレームワークの設計",
-    journal = "日本ソフトウェア科学会第28回大会論文集",
-    month = "Sep",
-    year = 2011
+    author = "照屋 のぞみ and 河野 真治",
+    title = "分散フレームワークAliceのPC画面配信システムへの応用",
+    journal = "第57回プログラミング・シンポジウム",
+    month = "Jan",
+    year = 2016
 }

 @misc{cell,
@@ -32,15 +32,6 @@
 }

 @article{
-    cbc,
-    author = "河野 真治 and 島袋 仁",
-    title = "C with Continuation と、そのPlayStationへの応用",
-    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
-    month = "May",
-    year = 2000
-}
-
-@article{
     cbc-llvm,
     author = "徳森 海斗 and 河野 真治",
     title = " Continuation based C の LLVM/clang 3.5 上の実装について",
@@ -57,15 +48,6 @@
     year = 1989
 }

-@article{
-    model-check,
-    author = "下地 篤樹 and 河野 真治",
-    title = "線形時相論理によるContinuation based Cプログラムの検証",
-    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
-    month = "April",
-    year = 2007
-}
-
 @manual{opencl,
 author = "{Aaftab Munshi, Khronos OpenCL Working Group}",
 title ="{The OpenCL Specification Version 1.0}",
@@ -73,12 +55,24 @@
 }

 @misc{cuda,
-title = "{CUDA}",
-howpublished = "{https://developer.nvidia.com/category/zone/cuda-zone/}"
+    title = "{CUDA}",
+    howpublished = "{https://developer.nvidia.com/category/zone/cuda-zone/}"
 }

-@misc{
-   msg,
-   title = "MessagePack",
-   howpublished = "{http://msgpack.org/}"
-}
\ No newline at end of file
+@article{
+    gears,
+    author = "小久保 翔平 and 伊波 立樹 and 河野 真治",
+    title = "Monad に基づくメタ計算を基本とする Gears OS の設計",
+    journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)",
+    month = "May",
+    year = 2015
+}
+
+@article{
+    cbc-lola,
+    author = "Kaito TOKKMORI and Shinji KONO",
+    title = "Implementing Continuation based language in LLVM and Clang",
+    journal = "LOLA 2015",
+    month = "July",
+    year = 2015
+}
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Sun May 08 02:41:43 2016 +0900
+++ b/paper/sigos.tex	Sun May 08 14:59:00 2016 +0900
@@ -88,8 +88,31 @@
 % 本文はここから始まる

 % Introduce
-\section{GearsOS}
+\section{Gears OS}
+CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。
+そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。
+マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
+また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
+並列処理をする上でこれらのリソースを無視することができない。
+しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。
+並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。
+本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS の設計・実装を行う。

+Cerium\cite{cerium} は本研究室で開発していた並列プログラミングフレームワークである。
+Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。
+Cerium では依存関係を Task 間で設定するが、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない。
+また、Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がない。
+そのため、本要ポインタをキャストして利用するしか無く、型の検査を行う事ができない。
+
+Gears OS\cite{gears} は Code Gear と Data Gear によって構成される。
+Code Gear は処理の単位、Data Gear はデータの単位となる。
+Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。
+また、Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する。
+Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される。
+Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する。
+依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。
+Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。
+本論文ではGears OS のプロトタイプとして Data Gear を管理する Persistent Data Tree, Task を管理する TaskQueue, 並列処理を行う Worker を実装し、簡単な例題を用いて Gears OS の評価を行う。

 \section{Code Gear と Data Gear}
 Gears OS はプログラムの単位として Gear を用いる。
@@ -101,13 +124,24 @@

 Data Gear は Data そのものを表しており、int や文字列などの Primitive Data Type が入っている。

+Code Gear、 Data Gear は 本研究室で開発されている Alice\cite{alice} で使われている単位である Code Segment、 Data Segment\cite{segment} それぞれに対応する。
+
 Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。

 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。
 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。

+\section{Meta Computation}
+Gears OS では通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。
+Meta Computation の例として並列処理の依存関係の解決や、 OS が行うネットワーク管理、メモリ管理等の資源制御などが挙げられる。
+
+Gears OS では Meta Computation を Meta Code Gear、 Meta Data Gear で表現する。
+Meta Code Gear は通常の Code Gear 直後に遷移され、 Meta Computation を実行する。
+Meta Computation の実行後は通常の Code Gear で指定した Code Gear を実行する。
+つまり Code Gear の実行後は何かしらの Meta Code Gear を実行する。
+
 \section{Continuation based C}
-Gears OS の実装は本研究室で開発している CbC(Continuation based C)を用いて行う。
+Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行う。
 CbC は処理を Code Segment を用いて記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。

 CbC のプログラムでは C の関数の代わりに Code Segment を用いてい処理を記述している。 Code Segment は C の関数と異なり戻り値を持たない。
@@ -127,6 +161,7 @@
     \caption{gotoによる Code Segment 間の接続}
     \label{fig:cbc_goto}
 \end{figure}
+
 \section{CbC での Gears OS の構文サポート}
 CbC は Gears OS の構文のサポートを行う。

@@ -135,7 +170,7 @@
 そこで Gears OS では Context から必要なデータを取り出して Code Gear に接続する stub を定義する。
 stub は Code Gear から推論することが可能のため、 CbC は自動的に stub の生成を行う。

-また、Code Gear の遷移には meta computation を行うために Meta Code Gear を挟む。
+また、Code Gear の遷移には Meta computation を行うために Meta Code Gear を挟む。
 CbC では Meta Code Gear への接続も自動的に行うようにする。

 \section{Gears OS の構成}
@@ -212,10 +247,10 @@
 Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。

 \begin{itemize}
-\item 各ノードは赤または黒の色を持つ。
-\item ルートの色は黒である。
-\item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。
-\item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。
+    \item 各ノードは赤または黒の色を持つ。
+    \item ルートの色は黒である。
+    \item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。
+    \item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。
 \end{itemize}

 これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。
@@ -240,7 +275,11 @@

 \section{TaskManager}
 Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。
-Task には
+Task には Input/Output Data Gear の情報が格納されている。
+Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。
+Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。
+この Input と Output の関係が依存関係となる。
+TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。

 \section{評価}
 Gears OS の評価として依存関係のない例題の並列実行を行った。
@@ -253,48 +292,48 @@
 以下に今回の処理の流れを示す。

 \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) を実行。
+    \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}
+    \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}
+    \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 倍の速度向上が見られた。
@@ -302,6 +341,7 @@
 Code Gear には実行時間を予想可能なものにするという特徴があるため、タスクが最適な粒度なのかを検査する機能が必要になると考えられる。

 \section{まとめ}
+本論文では Code Gear、 Data Gear  によって構成される Gears OS のプロトタイプの設計、実装を行った。

 \nocite{*}
 \bibliographystyle{ipsjunsrt}