Mercurial > hg > Papers > 2016 > kkb-master

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cerium.tex	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,100 @@
+\chapter{並列プログラミングフレームワーク Cerium}
+Cerium は PlayStation 3(PS3) に搭載された Cell Broadband Engine(Cell) 向けの Fine-Grain TaskManager として当研究室で設計・開発されたフレームワークである。
+本章では Cerium の実装について説明する。
+
+\section{Cerium の概要}
+Cerium は、TaskManager, SceneGraph, Rendering Engine の3つの要素から構成される。
+Cell 用のゲームフレームワークとして開発されたが、現在では Multi-Core CPU, GPU も計算資源として利用可能な汎用計算フレームワークとなっている。
+
+\section{TaskManager}
+TaskManager は、Task と呼ばれる分割されたプログラムを管理する。
+サブルーチンまたは関数が Task の単位となる。
+TaskManager が提供する API を表:\ref{table:TaskManager_api}に示す。
+
+\begin{table}[htpb]
+  \begin{center}
+    \small
+    \begin{tabular}[htpb]{|c|l|} \hline
+      create\_task & Task の生成 \\ \hline
+      allocate     & 環境のアライメントに考慮した allocator \\ \hline
+      set\_inData  & Task への入力データのアドレスを追加 \\ \hline
+      set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
+      set\_param   & Task のパラメータ(32 bits) \\ \hline
+      wait\_for    & Task の依存関係を設定 \\ \hline
+      set\_cpu     & Task を実行する Device の設定 \\ \hline
+      spawn        & Task を Queue に登録 \\ \hline
+      iterate      & データ並列で実行する Task として Queue に登録 \\ \hline
+    \end{tabular}
+    \caption{TaskManager API}
+    \label{table:TaskManager_api}
+  \end{center}
+\end{table}
+
+TaskManager は ActiveTaskList と WaitTaskList の2種類の Queue を持つ。
+依存関係を解決する必要がある Task は WaitTaskList に入れられる。
+TaskManger によって依存関係が解決されると ActiveTaskList に移され、実行可能な状態となる。
+実行可能な状態となった Task は set\_cpu で指定された Device に対応した Scheduler に転送し実行される。
+図:\ref{fig:createTask}は Cerium が Task を生成/実行する場合のクラスの構成である。
+\begin{figure}[!ht]
+  \begin{center}
+    \includegraphics[scale=0.6]{./images/createTask.pdf}
+  \end{center}
+  \caption{TaskManager}
+  \label{fig:createTask}
+\end{figure}
+
+\section{Cerium における Task}
+Task は TaskManager の API を利用して生成する。
+生成された Task には以下の要素を設定することができる。
+
+\begin{itemize}
+\item input data \\
+  set\_inData を用いて設定する Task が実行する処理に必要なデータの入力元となるアドレス。
+  関数を呼び出す際の引数に相当する。
+  汎用ポインタ(void* 型) なので Task 側で適切なキャストを行う必要がある。
+\item output data \\
+  set\_outData を用いて設定する Task が処理したデータの出力先となるアドレス。
+  関数の戻り値に相当する。
+\item parameter \\
+  set\_param を用いて設定するデータの処理に必要な実数値(index 等)。
+\item cpu type \\
+  set\_cpu を用いて設定する Task が実行される Device の組み合わせ。
+  Cell, Multi-Core CPU, GPU またはこれらの組み合わせを指定することができる。
+\item dependency \\
+  wait\_for を用いて設定する他の Task との依存関係。
+  依存関係が解決された Task は実行可能な状態となる。
+\end{itemize}
+
+\section{Task のパイプライン実行}
+\begin{figure}[htpd]
+  \begin{minipage}[t]{0.5\hsize}
+    \begin{center}
+      \includegraphics[scale=0.4]{./images/cell_arch.pdf}
+    \end{center}
+    \caption{Cell Architecture}
+    \label{fig:cellarch}
+  \end{minipage}
+  \begin{minipage}[t]{0.5\hsize}
+    \begin{center}
+      \includegraphics[scale=0.4]{./images/gpu_arch.pdf}
+    \end{center}
+    \caption{GPU Architecture}
+    \label{fig:gpuarch}
+  \end{minipage}
+\end{figure}
+Cell(図:\ref{fig:cellarch}) や GPU(図:\ref{fig:gpuarch}) のように異なるメモリ空間を持つ Device を計算資源として利用するにはデータの転送が必要になる。
+このデータ転送がボトルネックとなり、並列度が低下してしまう。
+転送処理をオーバーラップし、並列度を維持するために Cerium では Task のパイプライン実行をサポートしている。
+
+TaskManager である程度の Task をまとめた TaskList を生成し、実行する Device に対応した Scheduler に転送する。
+受け取った TaskList に沿ってパイプラインを組み Task を実行していく。
+TaskList でまとめられている Task は依存関係が解決されているので自由にパイプラインを組むことが可能である。
+実行完了は TaskList 毎ではなく、Task 毎に通知される。
+図:\ref{fig:scheduler}は TaskList を受け取り、Task をパイプラインで処理していく様子である。
+\begin{figure}[ht]
+  \begin{center}
+    \includegraphics[scale=0.6]{./images/scheduler.pdf}
+  \end{center}
+  \caption{Scheduler}
+  \label{fig:scheduler}
+\end{figure}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/cell_arch.bb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/cell_arch.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 412 414
+%%CreationDate: Thu Feb  4 02:51:30 2016
+
Binary file images/cell_arch.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/createTask.bb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/createTask.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 512 391
+%%CreationDate: Tue Feb 25 09:13:13 2014
+
Binary file images/createTask.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/createTask.xbb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,8 @@
+%%Title: ./images/createTask.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 512 391
+%%HiResBoundingBox: 0.000000 0.000000 512.000000 391.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Feb 25 09:13:14 2014
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/gpu_arch.bb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/gpu_arch.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 412 414
+%%CreationDate: Thu Feb  4 02:51:35 2016
+
Binary file images/gpu_arch.pdf has changed
Binary file images/images.graffle has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/scheduler.bb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/scheduler.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 532 385
+%%CreationDate: Thu Feb  4 03:40:25 2016
+
Binary file images/scheduler.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/images/scheduler.xbb	Fri Feb 05 04:17:47 2016 +0900
@@ -0,0 +1,8 @@
+%%Title: ./scheduler.pdf
+%%Creator: extractbb 20130405
+%%BoundingBox: 0 0 532 385
+%%HiResBoundingBox: 0.000000 0.000000 532.000000 385.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Jan 13 09:58:53 2015
+
--- a/master_paper.tex	Tue Feb 02 22:08:26 2016 +0900
+++ b/master_paper.tex	Fri Feb 05 04:17:47 2016 +0900
@@ -25,37 +25,40 @@
 \end{minipage}}
 \markleftfoot{% 左下に挿入
   \begin{minipage}{.8\textwidth}
-    Monad に基づくメタ計算を基本とする Gears OS の設計
+    Code Segment と Data Segment によって構成される Gears OS の設計
 \end{minipage}}

 \newcommand\figref[1]{図 \ref{fig:#1}}
 \newcommand\tabref[1]{表 \ref{tab:#1}}

-\lstset{%
- language={Java},
- basicstyle={\footnotesize},%
- identifierstyle={\footnotesize},%
- commentstyle={\footnotesize\itshape},%
- keywordstyle={\footnotesize\bfseries},%
- ndkeywordstyle={\footnotesize},%
- stringstyle={\footnotesize\ttfamily},
- frame={tb},
- breaklines=true,
- columns=[l]{fullflexible},%
- numbers=left,%
- xrightmargin=0zw,%
- xleftmargin=1zw,%
- numberstyle={\scriptsize},%
- stepnumber=1,
- numbersep=0.5zw,%
- lineskip=-0.5ex%
+\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%
 }

-
 %%% 索引のために以下の2行を追加
 \usepackage{makeidx,multicol}
 \makeindex
 \begin{document}
+
+%rome
 \frontmatter

 \maketitle
@@ -74,74 +77,29 @@
 %表目次
 \listoftables

+%arabic
 \mainmatter
+
 %chapters
 \chapter{並列分散環境下におけるプログラミング}
-
-\chapter{並列プログラミングフレームワーク Cerium}
-Cerium は PlayStation 3(PS3) に搭載された Cell Broadband Engine(Cell) 向けの Fine-Grain TaskManager として当研究室で設計・開発されたフレームワークである。
-本章では Cerium の実装について説明する。
-
-\section{Cerium の概要}
-Cerium は、TaskManager, SceneGraph, Rendering Engine の3つの要素から構成される。
-Cell 用のゲームフレームワークとして開発されたが、現在では Multi-Core CPU, GPU も計算資源として利用可能な汎用計算フレームワークとなっている。
-
-\section{TaskManager}
-TaskManager は、Task と呼ばれる分割されたプログラムを管理する。
-サブルーチンまたは関数が Task の単位となる。
-Task には依存関係が設定されており、TaskManager で依存関係が解決されると実行可能な状態になる。
-TaskManager が提供する API を表:\ref{table:TaskManager_api}に示す。
-\begin{table}[htpb]
-  \begin{center}
-    \small
-    \begin{tabular}[htpb]{|c|l|} \hline
-      create\_task & Task の生成 \\ \hline
-      allocate     & 環境のアライメントに考慮した allocator \\ \hline
-      set\_inData  & Task への入力データのアドレスを追加 \\ \hline
-      set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
-      set\_param   & Task のパラメータ(32 bits) \\ \hline
-      wait\_for    & Task の依存関係を設定 \\ \hline
-      set\_cpu     & Task を実行する Device の設定 \\ \hline
-      spawn        & Task を Queue に登録 \\ \hline
-      iterate      & データ並列で実行する Task として Queue に登録 \\ \hline
-    \end{tabular}
-    \caption{TaskManager API}
-    \label{table:TaskManager_api}
-  \end{center}
-\end{table}
+\input{cerium.tex}
+\chapter{CbC}
+\chapter{GearsOS}
+Cerium と Alice の開発を通して得られた知見から並列分散処理には Code の分割だけではなく Data の分割も必要であることがわかった。
+当研究室で開発している Code Segment を基本的な処理単位とするプログラミング言語 Continuation based C(CbC) を用いて Data Segment を定義し、Gears OS の設計と基本的な機能の実装を行なった。

-\section{Cerium における Task}
-Task は TaskManager の API を利用して生成する。
-生成された Task には以下の要素を設定することができる。
+本章では Gears OS の設計と実装した基本的な機能について説明する。
+\section{Code Gear と Data Gear}
+Gears OS ではプログラムの単位として Gear を用いる。
+Gear は並列実行の単位、データの分割、Gear 間の接続等になる。

-\begin{itemize}
-\item input data \\
-  set\_inData を用いて設定する Task が実行する処理に必要なデータの入力元となるアドレス。
-  関数を呼び出す際の引数に相当する。
-  汎用ポインタ(void* 型) なので Task 側で適切なキャストを行う必要がある。
-\item output data \\
-  set\_outData を用いて設定する Task が処理したデータの出力先となるアドレス。
-  関数の戻り値に相当する。
-\item parameter \\
-  set\_param を用いて設定するデータの処理に必要な実数値(index 等)。
-\item cpu type \\
-  set\_cpu を用いて設定する Task が実行される Device の組み合わせ。
-  Cell, Multi-Core CPU, GPU またはこれらの組み合わせを指定することができる。
-\item dependency \\
-  wait\_for を用いて設定する他の Task との依存関係。
-  依存関係が解決された Task は実行可能な状態となる。
-\end{itemize}
+Code Gear はプログラムの処理そのものになる。
+これは OpenCL/CUDA の kernel, Cerium の Task に相当する。
+Code Gear は任意の数の Data Gear を参照し、処理が完了すると 任意の数の Data Gear に書き込む。
+Code Gear は接続された Data Gear 以外にアクセスできない。

-TaskManager は ActiveTaskList と WaitTaskList
-
-\section{Task の Scheduling}
-
-\chapter{CbC}
-
-\chapter{GearsOS}
 \section{GearsOS の構成}
-\section{Monad とメタ計算}
-\section{Code Gear と Data Gear}
+Gears OS は
 \section{Allocator}
 \section{List}
 \section{Synchronized Queue}