% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2010}

% ここに，使用するパッケージを列挙する．
\usepackage[dvipdfm]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Fine Grain Task Manager Cerium のチューニング}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{金城 裕 \and 河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Tuning of Fine Grain Task Manager Cerium}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Yutaka Kinjyo, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
{Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
現在Cell/PS3またはMac OS X上で動作するFine Grain Task Manager であるCeirumを開発中である。
Cerium Task Managerは、Cell/PS3またはMac OS X上で動作するOpen CL 的なFine Grain	Task Manager である。
ソフトウェアレンダリングエンジンとWord countを例題として、Task Manager の実装時の問題を洗い出している。
メインメモリ上のTaskを各Coreに転送し、その終了を通知する際に生じる待ち時間がWord countの場合には
ネックであることがわかった。それを削減するTask arrayを提案し実装した。その効果について報告する。
}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{概要}

近年CPUの処理速度の向上ためのクロック周波数の増加は、
発熱や消費電力の増大により難しくなっている。そのため、クロック周波数を上げる代わりに、CPUコア数を増やす傾向になった。
マルチコアなCPUの性能を発揮するには、処理をできるだけ並列化しなければならない。それはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。つまり処理速度の性能向上は、ハードウェアだけでなく、ソフトウェアを並列処理に適したように実装することにもかかっている。そのためにはプログラミングの支援をするフレームワークが必要になってくる。そこでFine Grain Task Manager であるCeirumを開発中である。現在Ceriumは、マルチコアCPUの例題としてCellに対応している。また、支援するプログラミングの対象の１つとしてゲームを選択し、PS3,Mac OS X上でのゲームフレームワークとしても動作する。
そのCerium のチューニングをするうちに、各Coreにおいて、割り当てられたTaskが終わり、次のTaskを待つ時間がネックになり、処理速度を遅くしていることがわかった。そこで待ち時間を削減するために、各Task生成のスケジューリング方法や、複数のTaskをまとめて扱うTaskArrayを提案し実装した。その効果について報告する。


\section{Cell Broadband Engine}

Cell Broadband Engine は、ソニー・コンピュータエンタテインメント、ソニー、IBM, 東芝によって開発されたマルチコアCPUである。
Cellは、1基の制御系プロセッサコア (PPE:PowerPc Processor ELement) と8基の演算系プロセッサコア (SPE:Synergistic Processor Element) で構成される。各プロセッサコアは、EIB (Element Interconnect Bus) と呼ばれる高速なバスで接続されている。また、EIBはメインメモリや外部入出力デバイスとも接続されていて、各プロセッサコアはEIBを経由してデータアクセスをおこなう。

このPPEとSPEの2種類のCPUを、プログラマ自身が用途に合わせて適切に使い分けるように考慮する必要がある。

\begin{figure}[htbp]
  \begin{center}
    \scalebox{0.3}{\includegraphics{pic/cell_arch.pdf}}　　　　
    \caption{Cell Broadband Engine Architecture} \label{cell}
  \end{center}
\end{figure}

\subsection{PPE}
PPEはCell BroadbandEngineのメインプロセッサで、複数のSPEをコアプロセッ 
サとして使用することができる汎用プロセッサである。メインメモリや外部デバイスへ 
の入出力、SPEを制御する役割を担っている。PPU(PowerPCProcessorUnit)は、PPE 
の演算処理を行うユニットで、PowerPCアーキテクチャをベースとした命令セットを持 
つ。

\subsection{SPE}
SPEには256KBのLocal Store(LS)と呼ばれる、SPEから唯一、直接参照できるメ 
モリ領域があり、バスに負担をかける事無く並列に計算を進めることが出来る。SPEか 
らメインメモリへは、直接アクセスすることは出来ず、SPEを構成する一つであるMFC 
(MemoryFlowController)へ、チャネルを介してDMA(DirectMemoryAccess)命令を 
送ることで行われる

\subsection{DMA}
SPEはLS以外のメモリに直接アクセスすることができず、PPE 
が利用するメインメモリ上のデータにアクセスするにはDMAを用いる。DMA(Direct 
MemoryAccess)転送とは、CPUを介さずに周辺装置とメモリとの間でデータ転送こと 
で、Cell の場合はメインメモリとLS間でデータの転送を行う。手順としては以下の様に 
なる。 

{\small
\begin{enumerate}
 \item SPEプログラムがMFC(MemoryFlowController)に対してDMA転送命令を発行
 \item MFCがDMAControllerを介してDMA転送を開始。この間、SPEプログラムは 
停止しない。
 \item DMA転送の終了を待つ場合、SPEプログラム内で転送の完了を待つ
\end{enumerate}
}

\section{Ceriumとは}

CeriumはTaskManager、レンダリングエンジンとSceneGrpahの3つの要素から構成されており、
PS3、Mac OS X、Linux上でゲームフレームワークとして動作する。ゲーム中のオブジャクトの振る舞いやルールはSceneGraphで管理し、それらの動きやレンダリングの処理を動的にSPEに割り振るカーネルとして、TaskMnagerが用いられる。PS3のGraphics Engineの仕様は公開されておらず、ソフトウェアレンダリングエンジンを実装する必要があった。

\subsection{TaskManager}
TaskManagerは、Taskと呼ばれる、分割された各プログラムを管理する。
Taskの単位はサブルーチンまたは関数とし、Task同士の依存関係を考慮し、実行可能状態になったTaskを各SPEに割り振る。
Taskは通常PPEで生成され、SPEに送られる。SPEでは、受け取ったTaskをパイプラインに沿ってステージを遷移しながら複数のTaskを同時に実行していく。

\section{CeriumにおけるTask}

TaskはTaskManagerを使って生成する。
Taskを生成する際に以下のような要素が設定可能である。

{\small
\begin{enumerate}
 \item input data
 \item output data
 \item paramater
 \item cpu type
 \item dependency
\end{enumerate}
}

input,output data, paramaterは関数でいうところの引数にあたいする。cpu typeはTaskがPPE,または6基あるSPEのどれかで実行されるかを示すもの。
dependencyは他のTaskとの依存関係を示す。以下にWordCountとレンダリングエンジンにおいてのTaskを紹介する。

\subsection{WordCountのTask}

WordCountのTaskは以下の二つである。

{\small
\begin{enumerate}
 \item WordCountTask
 \item PrintTask
\end{enumerate}
}

WordCountTaskは、inputで与えられたdataをword countし、output dataに書き出すTaskである。
PrintTaskはすべてのWordCountTaskの実行完了を待ち、outputへ書き出された値を集計し出力するTaskである。
一度にSPEに渡せるdataはDMAの仕様上16Kbyteまでである。さらに転送する際には16byteの倍数である必要がある。

\subsection{WordCountのTask設定}

wcするfileをメモリへマッピングし、WordCountTask
のinputに、file dataのアドレスを16kbyteごとに指定していく。

\begin{figure}[htbp]
  \begin{center}
    \scalebox{0.3}{\includegraphics{pic/wc_graf1.png}}　　　　
    \caption{WordCountにおけるTaskの流れ} \label{wordcoutntask1}
  \end{center}
\end{figure}

PrintTaskのdependencyにはすべてのWordCountTaskが設定さており、WordCountがすべて終わらないと、
実行されないようになっている。


\subsection{WordCountにおけるTask生成のスケジューリング}

\subsection{TaskのTaskArray化}


\subsection{レンダリングエンジンのTask}



\section{まとめと今後の課題}




{\bf 謝辞}\
%
%% \begin{adjustvboxheight} % needed only when Appendix follows
%% \begin{thebibliography}{99}
%% \bibitem{LS86} Lanin, V. and Shasha, D.：A Symmetric Concurrent B-Tree
%% Algorithm,
%% Proc.\ 1986 Fall Joint Computer Conference, IEEE, 1986, pp.~380--389．

%% \bibitem{ST85} Sleator, D. D. and Tarjan, R. E.：Self-Adjusting Binary Search
%% Trees, {\it J. ACM}, Vol.~32, No.~3 (1985), pp.~652--686．

%% \bibitem{S89} Shapiro E.：The Family of Concurrent Logic Programming Languages.
%% {\it ACM Computing Surveys}, Vol.~21, No.~3 (1989), pp.~413--510．

%% \bibitem{T85} Tarjan, R. E.：Amortized Computational Complexity, {\it
%% SIAM J.\ Alg.\ Disc.\ Math.}, Vol.~6, No.~2 (1985), pp.~306--318.

%% \bibitem{W90} 和田久美子：スプレイ木の並列データ探索, Proc.\ KL1
%% Programming Workshop '90, Tokyo, ICOT, 1990, pp.~42--49．
%% \end{thebibliography}
%% \end{adjustvboxheight} % needed only when Appendix follows

\appendix
\section{付録: \LaTeX による論文作成のガイド} 

ここに，以前の \verb|sample.tex| では，論文作成のガイドがあったが，
その内容は \verb|guide.tex| に移動した．

\end{document}