\documentclass[twocolumn,twoside,9.5pt]{article}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{picins}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{pic/emblem-bitmap.eps}}Technical Reading \& Writing}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{15mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{15mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\begin{document}
\title{Implementation of Cerium Parallel Task Manager on Multi-core}
\author{128569G Daichi TOMA}
\date{}
\maketitle
\thispagestyle{fancy}

\section{Introduction}
We have developed Cerium Task Manager\cite{gongo:2008a} that is a Game Framework on the PlayStation 3/Cell\cite{cell}. 
Cerium Task Manager new supporting parallel execution on Mac OS X and Linux. 
In this paper, we described implementation of existing Cerium Task Manager and a new parallel execution. 

\section{Cerium Task Manager}\label{section:cerium}

Cerium Task Manager is a game framework has been developed for the Cell, and include the Rendering Engine.
In Cerium Task Manager, parallel processing is described as a task. 
The task usually consists of a function or subroutine. also the task is setted data inputs, data outputs and dependencies.
Cerium Task Manager managed those tasks, and execute.  

Cerium Task Manager is available on PlayStaiton 3, Linux, Max OSX,
furthermore run the same programs on each platform.
Therefore, to write a programs that does not depend on the architecture is possible.

Cerium Task Manager configure pipeline at various levels of the program,
thus performance improvement. (Figure \ref{fig:scheduler}). 

The task is very simple because only calculate data outputs from data inputs;
nevertheless to switch to those data inputs and outputs as double buffering,
To generate gradually so as to obtain concurrency is very complicate.

Additionally, these data management, it is necessary to the operation that specializes in architecture using parallel execution.\cite{yutaka:2011b}
Cerium Task Manager helps to do to such operation,
therefore be able to concentrate on the implementation of parallel computation.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{./pic/scheduler.pdf}
\end{center}
\caption{Scheduler}
\label{fig:scheduler}
\end{figure}

\section{マルチコア上での並列実行の機構}\label{section:impl}

PlayStation 3/Cell 上の場合, 各 SPE に Task が割り当てられ, 並列に実行される.

今回新たに, Mac OS X, Linux 上でも並列に実行させることを可能にした.
これは, PlayStation 3/Cell の Mailbox に対応させる形で, 
Synchronized Queue を用いて Mac OS X, Linux 側の Cerium Task Manager へ移植したものである.
操作しているスレッドが常に1つになるよう, バイナリセマフォで管理されている.
各スレッドは, input 用と output 用として Synchronized Queue を2つ持っており, 
管理スレッドからタスクを受けて並列に実行するようになっている.

また, PlayStation 3/Cell と違い各 CPU で同じメモリ空間が利用できるため,
DMA転送を用いていた箇所をポインタ渡しをするように修正し, 速度の向上を図った.

% \subsection{Mailbox}
% Mailbox は, Cell の機能の1つである.
% Mailbox は, PPE と SPE の間を双方向で, 32 bit メッセージの受け渡しが可能であり,
% FIFO キュー構造になっている.


\section{ベンチマーク}
Word Count, Sort 及び Prime Counter の例題を用いて, 計測した.
それぞれ入力として, 100MB のテキストファイルの単語数カウント, 10 万入力のソート, 100 万までの範囲の素数を全て数え上げるようになっている.
比較対象として, PlayStation 3/Cell においても同様の例題を用いて計測している.
どちらも, 最適化レベルは最大にしてある.

表\ref{table:benchmark}に結果を示す.

{\bf 実験環境}

CentOS/Xeon
\begin{small}
\begin{itemize}\small
\item OS : CentOS 6.0
\item CPU : Intel\textregistered Xeon\textregistered X5650 @2.67GHz * 2
\item Memory : 128GB
\item Compiler : GCC 4.4.4
\end{itemize}
\end{small}

PlayStation 3/Cell
\begin{small}
\begin{itemize}\small
\item OS : Yellow Dog Linux 6.1
\item CPU : Cell Broadband Engine @ 3.2GHz
\item Memory : 256MB
\item Compiler : GCC 4.1.2
\end{itemize}
\end{small}


\begin{tiny}
\begin{table}[h]
\caption{Benchmark}
\label{table:benchmark}
\small
\begin{tabular}[t]{c||r|r|r}
\hline
& Word Count & Sort & Prime Counter\\
\hline\hline
1 CPU (Cell)& 2381 ms & 6244 ms & 2081 ms \\
\hline
6 CPU (Cell)& 1268 ms & 1111 ms & 604 ms\\
\hline
1 CPU (Xeon)& 354 ms & 846 ms & 266 ms\\
\hline
6 CPU (Xeon)& 70 ms & 163 ms & 50 ms\\
\hline
12 CPU (Xeon)& 48 ms & 127 ms & 36 ms\\
\hline
24 CPU (Xeon)& 40 ms & 100 ms & 31 ms\\
\hline
\end{tabular}
\end{table}
\end{tiny}

% Word Count 	354 / 70 = 5.0571
% Sort		846 / 163 = 5.1901
% Prime Counter 266 / 50 = 5.32
表\ref{table:benchmark}より, CentOS上で 6 CPU を利用した場合, 1 CPU を利用した場合と比較して
Word Count の例題で約 5.1 倍, Sort の例題で約 5.2 倍, Prime Counter の例題で, 約 5.3倍の速度向上が見られる.
しかしながら, 24 CPU を利用した場合, 12 CPU を利用した場合と比較して速度は上がっているものの速度向上率が落ちている.
これは並列化率が低いために性能を活かすことができず, 速度向上が頭打ちになっているとアムダールの法則\cite{amdahl}から考えられる.
並列化率の向上は今後の課題である.

% また, 図\ref{fig:multi_result}より, 台数効果が確認できる.

\section{まとめ}
本稿では, 既存の Cerium Task Manager の実装と新しい並列実行の機構について説明した.
新しく実装した並列実行の機構を用いることによって, Mac OS X, Linux 上でのマルチプロセッサ環境に対応できる. 

今後の課題として, 並列化率を向上させ, プロセッサ数が増えた時の速度向上率を改善する.
また, 現在の Cerium Task Manager は Task の種類が増え, Open CL\cite{opencl} に比べても記述が煩雑であるなどの欠点がある.
これは Task の依存関係を, ユーザ側ではなくシステム側が記述するようにすることで解決できると考える.

\nocite{cell_abi}
% \nocite{yutaka:2010a, cell_abi, cell_cpp, cell_sdk, libspe2, ydl, clay200912, fix200609}
\bibliographystyle{junsrt}
\bibliography{cerium.bib,book.bib}

\end{document}