--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/2014_final_pre.bib	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,157 @@
+@article{kono:2008a,
+	author = "河野真治",
+	title = "検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用",
+	journal = "電子情報通信学会VLSI設計技術研究会",
+	month = "March",
+	year = 2008
+}
+
+@article{akira:2008a,
+	author = "神里 晃 and 宮國 渡 and 杉山 千秋 and 河野 真治",
+	title = "CからCellアーキテクチャを利用したCbCへの変換",
+	journal = "電子情報通信学会VLSI設計技術研究会",
+	month = "March",
+	year = 2008
+}
+
+@article{akira:2006a,
+	author = "神里 晃 and 河野 真治",
+	title = "Continuation based CによるPS3 Cell のシミュレーション",
+	journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会",
+	month = "May",
+	year = 2006
+}
+
+@mastersthesis{akira:master,
+	author = "神里 晃",
+	title = "Cell を用いたゲームフレームワークの提案",
+	school = "琉球大学理工学研究科情報工学専攻",
+	month = "Feb",
+	year = 2008
+}
+
+@mastersthesis{gongo:master,
+	author = "宮國 渡",
+	title = "Cell用の Fine-Grain Task Manager の実装",
+	school = "琉球大学理工学研究科情報工学専攻",
+	month = "Feb",
+	year = 2009
+}
+
+@article{gongo:2008a,
+	author = "宮國 渡 and 河野 真治 and 神里 晃 and 杉山 千秋",
+	title = "Cell 用の Fine-grain Task Manager の実装",
+	journal = "情報処理学会 システムソフトウェアとオペレーティング・システム研究会",
+	month = "April",
+	year = 2008
+}
+
+@article{chiaki:thesis,
+	author = "杉山 千秋",
+	title = "SceneGraph と StatePattern を用いたゲームフレームワークの設計と実装",
+	journal = "琉球大学工学部情報工学科 平成19年度卒業論文",
+	year = 2008
+}
+
+@article{akamine:2010a,
+	author = "赤嶺 一樹 and 河野 真治",
+	title = "Meta Engine を用いた Federated Linda の実験",
+	journal = "日本ソフトウェア科学会第 27 会大会(2010 年度)",
+	month = "Sep",
+	year = 2010
+}
+
+@mastersthesis{kaito:master,
+	author = "多賀野 海人",
+	title = "Cell Task Manager Cerium における Task を用いたパイプラインの改良",
+	school = "琉球大学理工学研究科情報工学専攻",
+	month = "Feb",
+	year = 2011
+}
+
+@article{yutaka:2010a,
+	author = "金城 裕 and 河野 真治",
+	title = "Fine Grain Task Manager Cerium  のチューニング",
+	journal = "日本ソフトウェア科学会第 27 会大会",
+	month = "Sep",
+	year = 2010
+}
+
+@article{yutaka:2011a,
+	author = "金城 裕 and 河野 真治",
+	title = "ゲームフレームワーク Cerium TaskManager の改良",
+	journal = "情報処理学会システムソフトウェアとオペレーティング・システム研究会",
+	month = "Apr",
+	year = 2011
+}
+
+@article{yutaka:2011b,
+	author = "金城 裕 and 河野 真治",
+	title = "Cerium におけるDataSegment APIの設計",
+	journal = "日本ソフトウェア科学会第 28 会大会",
+	month = "Sep",
+	year = 2011
+}
+
+@article{Jaeschke93,
+	author={G. Jaeschke},
+	title={On Strong Pseudoprimes to Several Bases},
+	journal= MC,
+	volume= 61,
+	year= 1993,
+	pages={915-926},
+	mrnumber={94d:11004},
+	annote={Greatly extends the computations of \cite{PSW80} useful for \href{http://primes.utm.edu/prove/prove2_3.html}{testing
+		small numbers}.}
+}
+
+@article{takayama,
+	author = "高山 征大",
+	title = "「CELL REGZA」が搭載する並列化技術「Molatominum」",
+	journal = "",
+	month = "Dec",
+	year = 2009
+}
+
+@misc{ydl,
+author = "",
+title = "{Yellow Dog Linux for PowerPC Computers}",
+howpublished = "{http://us.fixstars.com/products/ydl/}"
+}
+
+@misc{cerium,
+author = "",
+title = "{SourceForge.JP: Cerium Rendering Engine}",
+howpublished = "{https//sourceforge.jp/projects/cerium/}"
+}
+
+@manual{cell,
+author = "{Sony Corporation}",
+title = "{Cell BroadbandEngine \texttrademark アーキテクチャ}",
+year = 2006
+}
+
+@manual{cell_cpp,
+author = "{International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation}",
+title = "{C/C++ Language Extensions for Cell Broadband Engine Architecture Version 2.6}",
+year = 2008
+}
+
+
+@misc{blender,
+title = "{blender.org}",
+howpublished = "{http://blender.org/}"
+}
+
+@misc{opengl,
+title = "{opengl}",
+howpublished = "{http://www.opengl.org/}"
+}
+
+@article{akamine,
+author = "{赤嶺一樹, 河野真治}",
+title = "{Meta Engine を用いた Federated Linda の実験}",
+journal = "{日本ソフトウェア科学会第 27 会大会(2010 年度)}",
+month = "{Sep}",
+year = 2010
+}

Binary file prepaper/2014_final_pre.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/2014_final_pre.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,48 @@
+\documentclass[twocolumn,twoside,7pt]{jarticle}
+\usepackage[dvipdfmx]{graphicx}
+\usepackage{picins}
+\usepackage{fancyhdr}
+\usepackage{setspace}
+
+\pagestyle{fancy}
+\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{images/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
+\rhead{}
+\cfoot{}
+
+\setstretch{0.8}
+\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
+\setlength{\headheight}{0mm}
+\setlength{\headsep}{5mm}
+\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
+\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
+\setlength{\textwidth}{181mm}
+\setlength{\textheight}{261mm}
+\setlength{\footskip}{0mm}
+\pagestyle{empty}
+
+\begin{document}
+\title{Cerium Task Manager の Multi Platform 対応}
+\author{105744J 氏名 小久保 翔平 指導教員 : 河野 真治}
+\maketitle
+\thispagestyle{fancy}
+
+%研究目的
+\input{Introduction.tex}
+
+% parallel computing platform
+\input{Parallel.tex}
+
+%Cerium
+\input{Cerium.tex}
+
+%benchmark
+\input{Benchmark.tex}
+
+%まとめ
+\input{Conclusion.tex}
+
+%参考文献
+\bibliographystyle{ipsjunsrt}
+\input{bibliography.tex}
+
+\end{document}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/Benchmark.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,39 @@
+\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}
+\newpage
+パイプラインありの方が少しだけ実行結果が向上している。しかし、期待するほどの効果が出ていない。
+これは図:\ref{fig:parallel_exec}のように綺麗なパイプラインで実行されていないことが考えられる。
+綺麗なパイプラインで実行するためにはデータ転送と kernel の実行が同じ時間で終了することが望ましい。
+また、まだ各 Operation の待ち方がおかしく待つ必要がない部分を待っている可能性もある。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/Cerium.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,18 @@
+\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 へのデータ転送の順序で Command Queue および Stream に Operation を投入していく。
+Commqnd Queue および Stream は任意の数に変更することができる。デフォルトでは8段のパイプラインとして実行される。
+Task Manager 間の通信を担当する同期キューである mail を使用し Task の完了を通知する。
+各 Scheduler 内で初期化、メモリ管理、データ転送のオーバーラップを行なっている。
+Task は Multi Core CPU, OpenCL, CUDA でほぼ同じ記述であるが、修飾子など若干形式が異なる。これらは将来的に自動変換などを行うことが望ましい。

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

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/Introduction.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,13 @@
+\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 を改良した。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/Makefile	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,19 @@
+TARGET=2014_final_pre
+TEX=platex
+DVIPDF=dvipdfmx
+
+.SUFFIXES: .tex .dvi
+
+all: pdf# $(TARGET).ps
+	open $(TARGET).pdf
+
+dvi:
+	$(TEX) $(TARGET)
+
+pdf: dvi
+	$(DVIPDF) $(TARGET)
+
+
+clean:
+	rm -f $(TARGET).dvi $(TARGET).aux $(TARGET).log
+	rm -f $(TARGET).pdf *~

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/Parallel.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,48 @@
+\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 で生成される。
+cuStreamCreate には Context や device を指定する必要がないが、Context を生成したスレッドと同一のスレッドでないと Stream を生成できないという制約がある。
+Command Queue および Stream に投入された Operation は投入された順序で device 上で逐次実行される。
+複数の Command Queue および Stream がある場合、異なる 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}
+
+3D グラフィックのような多次元のデータ構造がある場合に高い並列度を保って処理を行うには、それを分割して各要素の対して並列に実行する機能が必要である。
+これを OpenCL および CUDA ではデータ並列と呼んでいる。
+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}
+
+Cerium の思想に近いものとして INRIA が提供する StarPU というものがある。
+CPU と GPU といったヘテロジニアスな環境下でのタスクベースなプログラミングモデルをサポートしている。
+メモリ管理や Task のスケジューリングなど管理するリソースが多く、プログラマに大きな負担がかかる。
+一方、Cerium ではプログラマの負担を減らすためスケジューリングやリソースの管理等を自動で行うようになっている。

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/bibliography.tex	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,21 @@
+
+\begin{thebibliography}{10}
+
+\bibitem{FFTonGPU}
+{Yasuhiko OGATA, Toshio Endo, Naoya MARUYAMA, Satoshi MATSUOKA}:性能モデルに基づくCPU及びGPUを併用する効率的なFFTライブラリ，東京工業大学 (2008).
+
+\bibitem{toma:2012a}
+{Daichi TOMA and Shinji KONO}:Cerium Task Manager におけるマルチコア上での並列実行機構の実装(2012)
+
+\bibitem{gongo:2008a}
+{Wataru MIYAGUNI,Shinji KONO}:Cell 用の Fine-grain Task Manager の実装
+
+\bibitem{opencl:ref}
+{Aaftab Munshi, Khronos OpenCL Working Group}:The OpenCL Specification Version 1.0 (2007)
+
+\bibitem{kono}
+{Shinji KONO.}: 検証を自身で表現できるハードウェア、ソフトウェア記述言語
+  Continuation ba sed C と、その Cell
+  への応用，電子情報通信学会VLSI設計技術研究会 (2008).
+
+\end{thebibliography}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/createTask.bb	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/createTask.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 512 391
+%%CreationDate: Tue Feb 25 23:52:44 2014
+

Binary file prepaper/images/createTask.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/createTask.xbb	Wed Feb 26 01:14:10 2014 +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 23:52:52 2014
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/culculate_index.bb	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/culculate_index.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 562 226
+%%CreationDate: Tue Feb 25 23:26:03 2014
+

Binary file prepaper/images/culculate_index.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/culculate_index.xbb	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,8 @@
+%%Title: ./images/culculate_index.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 562 226
+%%HiResBoundingBox: 0.000000 0.000000 562.000000 226.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Feb 25 23:26:10 2014
+

Binary file prepaper/images/emblem-bitmap.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/paralle_exec.bb	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,5 @@
+%%Title: ./images/paralle_exec.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 785 184
+%%CreationDate: Tue Feb 25 23:00:27 2014
+

Binary file prepaper/images/paralle_exec.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/prepaper/images/paralle_exec.xbb	Wed Feb 26 01:14:10 2014 +0900
@@ -0,0 +1,8 @@
+%%Title: ./images/paralle_exec.pdf
+%%Creator: extractbb 20090506
+%%BoundingBox: 0 0 785 184
+%%HiResBoundingBox: 0.000000 0.000000 785.000000 184.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Feb 25 23:00:37 2014
+