\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}

% Cell の説明いれる

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

\section{mechanism of parallel execution on multi-core}\label{section:impl}

If on a PlayStation 3, Task is assigned to each SPE, then to be executed in parallel.
Cerium Task Manager possible to be executed in parallel on Mac OSX and Linux anew.

We implement a synchronized queue on Mac OS X and Linux.
The synchronized queue corresponds to the Mailbox on Playstation 3.
For only one thread use the synchronized queue, that was managed by a binary semaphore.
Each threads has two synchronized queues for input and output,
be able to execute in parallel tasks was received under managment thread.

Furthermore, because multicore available the same memory space in comparison with Playstation 3,
we modified to pass the pointer a spots that were using the transfer DMA, aimed to improve the speed.

\section{Benchmark}

Performance was measured using the example of Word Count, Sort and Prime Counter.
Word Count is to count number of words in the 100MBtext file.
Sort is to sort in one hundred thousand pieces of numeric.
Prime Counter is to enumerate all the prime numbers in the range of up to one million.
for comparsion performance was measured using the same example in PlayStation 3.
Both the optimization level is at the maximum.

The results are shown in Table \ref{table:benchmark}.

{\bf Experiment environment}

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

We use 6 CPU on CentOS, as compared with the case using 1 CPU, 
about 5.1 times the speed improvement in the example of WordCount,
about 5.2 times the speed improvement in the example of Sort,
about 5.3 times the speed improvement in the example of Prime Counter.
If we use 24 CPU, the speed is rising as compared with the case using 12 CPU, however, the speed improvement rate is down.
This is probably concurrency is low, and that seems to be grinding to a halt speed improvement from Amdahl's law\cite{amdahl}.
Improvement of parallelization rate is a challenge for the future.

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

\section{Conclusions}
In this paper, we describe a new mechanism of parallel execution and implementation of existing Cerium Task Manager.
By using a new implementation mechanism of parallel execution, You can correspond to a multi-core processor environment on Mac OSX and Linux.

To improve the rate of speed as future work when the number of processors has increased.
In addition, Cerium Task Manager has many type of task, is a drawback of such description.
This can be solved by the system description the dependency of the task rather than on the user side.

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

\end{document}