Binary file prepaper/2015_final_pre.pdf has changed

--- a/prepaper/Benchmark.tex	Tue Feb 17 12:32:12 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-\section{Benchmark}
-本研究で実装した GpuScheduler および CudaScheduler を用いて、WordCountを測定する。
-
-実験環境
-\begin{itemize}
-\item OS : MacOS 10.9.1
-\item CPU : 2*2.66GHz 6-Core Intel Xeon
-\item GPU : NVIDIA Quadro K5000 4096MB
-\item Memory : 16GB 1333MHz DDR3
-\item Compiler : Apple LLVM version 5.0 (clang-500.2.79) (based on LLVM 3.3svn)
-\end{itemize}
-
-表:\ref{table:wc}は100MB のテキストファイルに対して WordCount を行なった場合の実行時間である。
-\begin{table}[!h]
-  \begin{center}
-    \small
-    \begin{tabular}[t]{c||r} \hline
-      & Run Time \\ \hline
-      1 CPU & 0.69s \\ \hline
-      2 CPU & 0.35s \\ \hline
-      4 CPU & 0.18s \\ \hline
-      8 CPU & 0.09s \\ \hline
-      12 CPU & 0.07s \\ \hline
-      OpenCL(no pipeline) & 48.32s \\ \hline
-      OpenCL(pipeline) & 46.74s \\ \hline
-      OpenCL Data Parallel & 0.50s \\ \hline
-      CUDA(no pipeline) & 55.71s \\ \hline
-      CUDA(pipeline) & 53.30s \\ \hline
-      CUDA Data Parallel & 0.73s \\ \hline
-    \end{tabular}
-  \end{center}
-  \label{table:wc}
-  \caption{WordCount}
-\end{table}
-
-パイプラインありの方が少しだけ実行結果が向上している。しかし、期待するほどの効果が出ていない。
-これは図:\ref{fig:parallel_exec}のように綺麗なパイプラインで実行されていないことが考えられる。
-綺麗なパイプラインで実行するためにはデータ転送と kernel の実行が同じ時間で終了することが望ましい。
-また、まだ各 Operation の待ち方がおかしく待つ必要がない部分を待っている可能性もある。

--- a/prepaper/Cerium.tex	Tue Feb 17 12:32:12 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,21 +0,0 @@
-\section{Cerium Task Manager}
-Cerium Task Manager では、並列処理を Task 単位で記述する。関数やサブルーチンを Task として扱い、Task には input data, output data および依存関係を設定する。
-Cerium Task Manager によって、それらの Task は管理され、実行される。図:\ref{fig:createTask}は Task を生成/実行する場合のクラス構成である。
-
-\begin{figure}[!ht]
-  \begin{center}
-    \includegraphics[scale=0.35]{./images/createTask.pdf}
-  \end{center}
-  \caption{Task Manager}
-  \label{fig:createTask}
-\end{figure}
-
-Scheduler と CpuThreads に対応させる形で、GpuScheduler, CudaSchduler および GpuThreads, CudaThreads を実装した。
-TaskList から device 上での memory 領域を確保し、host から device へのデータ転送、kernel の実行、device から host へのデータ転送の順序で device に Operation を投入していく。
-
-Commqnd Queue および Stream を複数用意することでパイプライン実行を実現している。
-これらは任意の数に変更することができる。デフォルトでは8個生成しているので8段のパイプラインとして実行される。
-Task Manager 間の通信を担当する同期キューである mail を使用し Task の完了を通知する。
-
-各 Scheduler 内で初期化、メモリ管理、データ転送のオーバーラップを行なっている。
-Task は Multi Core CPU, OpenCL, CUDA でほぼ同じ記述であるが、修飾子など若干形式が異なる。これらは将来的に自動変換などを行うことが望ましい。

--- a/prepaper/Conclusion.tex	Tue Feb 17 12:32:12 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,5 +0,0 @@
-\section{まとめ}
-本研究では Cerium 上で自動でデータ転送をオーバラップし GPU で実行するように改良を行なった。
-また、Multi Core CPU でのデータ並列による実行も可能にした。
-しかし、まだ十分に GPU の性能を活かしきれているとは言えない。
-今後、GPU の性能をより引き出すためにデータ転送や Task の粒度の見直し、パイプライン実行の妥当性などを調査する必要がある。

--- a/prepaper/Introduction.tex	Tue Feb 17 12:32:12 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,16 +0,0 @@
-\section{研究目的}
-PS3 および Linux、Mac OS X 上で動く並列プログラミングフレームワーク、Cerium Task Manager\cite{gongo:2008a}の開発・完了を行なっている。
-
-Cell だけでなく、GPU のような異なるアーキテクチャを搭載した CPU、つまりヘテロジニアスな CPU が増えてきた。
-GPU の普及と高性能化にともない、GPU の演算資源を画像処理以外の目的にも利用する GPGPU(GPU による汎目的計算)が注目されている\cite{FFTonGPU}。
-
-特定の計算に特化した Task の生成やスケジューリングを行い、高い並列度を出すという研究は様々な分野で行われている。
-特定の計算に限らず、GPU を用いて汎用計算できるフレームワークを Cerium Task Manager は目指している。
-
-GPU のみで計算を行った場合、Task によっては並列度が出ない場合がある。
-GPU はデータ並列による実行が推奨されている。
-データ並列とは多次元のデータ構造に対して、それを分割して各要素に対して処理を行うことを指す
-OpenCL および CUDA にはそのための API が存在する。
-また GPU は CPU とメモリ空間が異なるため、データにアクセスするためにはメモリ空間ごとコピーする必要がある。
-このデータ転送部分が大きなオーバーヘッドになる。
-この問題を解決するために OpenCL および CUDA を用いて、自動でデータ転送をオーバーラップし、パイプライン実行を行うよう Cerium を改良した。

--- a/prepaper/Parallel.tex	Tue Feb 17 12:32:12 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,49 +0,0 @@
-\section{Parallel Computing Platform}
-OpenCL および CUDA では、オペレーティングシステムなどが処理されるメイン CPU のことを host、GPGPU を行うグラフィックボードのことを device と定義している。
-この device 上で動作するプログラムのことを特別に kernel と呼ぶ。
-
-今回、実装に用いた OpenCL には Command Queue、CUDA には Stream という device に Operation を渡す仕組みがそれぞれ存在する。
-Command Queue は clCreateCommandQueue という OpenCL の API に所属する Context と実行対象となる device を指定することで生成される。
-Stream は cuStreamCreate という CUDA の API で生成される。
-この関数には Context や device を指定する必要がないが、Context を生成したスレッドと同一のスレッドでないと Stream を生成できないという制約がある。
-これらに投入された Operation は投入された順序で device 上で逐次実行される。
-複数ある場合、異なる Command Queue および Stream に投入されている Operation は並列に実行される。
-複数の Stream をある場合の実行の様子は図:\ref{fig:parallel_exec}のようになる。
-HtoD は host から device へのデータ転送、kernel は kernel の実行、DtoH は device から host へのデータ転送を示している。
-
-\begin{figure}[!htpd]
-  \begin{center}
-    \includegraphics[scale=0.35]{./images/paralle_exec.pdf}
-  \end{center}
-  \caption{Parallel Execution}
-  \label{fig:parallel_exec}
-\end{figure}
-
-OpenCL では Task の最小単位を WorkItem、CUDA では Thread と定義している。
-また、WorkItem をまとめたものを WorkGroup、Thread をまとめたものを Block と呼ぶ。
-OpenCL および CUDA にはデータ並列よる実行を行う API がそれぞれ存在する。
-OpenCL および CUDA でデータ並列実行すると、一つの記述から index の異なる複数の kernel を自動生成する。
-この index を元に自分が担当するデータの範囲が決定される。
-OpenCL では clEnqueueNDRangeKernel という API を用いることでデータ並列よる実行を行うことができる。
-clEnqueueNDRangeKernel の引数として WorkItem の数と次元数を指定することで全体の Task 数が決定する。
-CUDA では cuLaunchKernel という API を用いる。
-引数として各次元の Block 数と各次元の Block 一つ当たりの Thread 数を指定することで全体の Task 数を決定する。
-実行される各 kernel では index 取得する必要がある。
-OpenCL では index の取得に get\_global\_id という API を用いる。
-CUDA では kernel に組み込み変数が準備されており、それらから index を算出することができる(図:\ref{fig:index})。
-
-\begin{figure}[!h]
-  \begin{center}
-    \includegraphics[scale=0.4]{./images/culculate_index.pdf}
-  \end{center}
-  \caption{Calculate Index}
-  \label{fig:index}
-\end{figure}
-
-INRIA が提供する StarPU というものがある。
-CPU と GPU といったヘテロジニアスな環境下でのタスクベースなプログラミングモデルをサポートしている。
-メモリ管理や Task のスケジューリングなど管理するリソースが多く、プログラマに大きな負担がかかる。
-
-GPU Programming の問題点として host 側のリソースだけでなく、device 側のリソースまで管理する必要があるという点が上げられる。
-また、利用する Platform よって記述が大きくことなることも GPU Programming の難易度を上げている。
-Cerium ではプログラマの負担を減らすため、同一のコードで OpenCL および CUDA で動作し、スケジューリングやリソースの管理等を自動で行うようになっている。