\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\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{はじめに}
プロセッサメーカは, 消費電力, 発熱及びクロックの限界という観点から, 
マルチコア構成の路線を打ち出しており, 今後ますますマルチコアプロセッサが主流になると想像できる.

マルチコアプロセッサ上で, リソースを有効活用するためには, 並列プログラミングを行う必要があるが, 
効率の良い並列プログラムを書くことは難しい.

そこで, 本研究室で作成した Cerium Task Manager\cite{gongo:2008a} をマルチコアプロセッサに対応させることで,
マルチコアプロセッサ上での Task 単位による並列プログラミングをサポートする.

今まで, Cerium Task Manager は, PlayStation 3/Cell\cite{cell} 上でのみ, 並列実行を可能にしていたが,
今回新たに Mac OS X, Linux 上での並列実行に対応した.

本論文では, まず既存の Cerium Task Manager の実装について説明する. 
その後, 新たに実装した並列実行の機構について説明する.

\section{Cerium Task Manager}\label{section:cerium}
Cerium Task Manager は, Cell 用に開発されたゲームフレームワークであり, 
Rendering Engine を含む.

Cerium Task Manager では, 並列処理を Task 単位で記述する.
関数やサブルーチンを Task として扱い,
Task には, input データ, output データ及び依存関係を設定する.
Cerium Task Manager によってそれらの Task は管理され, 実行される.

Cerium Task Manager は, PlayStation 3/Cell, Mac OS X 及び Linux 上で利用することができ,
それぞれのプラットフォームで同じプログラムを動作させることができる.
これにより, アーキテクチャに依存しないプログラムを記述することが可能である.

Cerium Task Manager では, プログラムの様々なレベルでパイプラインが構成されるので,
プログラムの性能向上が見込める (図\ref{fig:scheduler}) .

また, Task 自体は入力データから, 出力データを計算するだけなので非常に単純だが,
その入出力データをダブルバッファリングとして切り替えたり, 
適切な並列度が得られるように徐々に生成するのは非常に煩雑となる.
さらに, これらのデータ管理は, 並列実行を行うアーキテクチャに特化した処理が必要となる\cite{yutaka:2011b}.
Cerium Task Manager を利用することで, このような処理を代わりに行ってくれるため, 
並列計算の実装に集中することができる.

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