% 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が受け取る際や、その終了を通知する際に待ち時間が生じる。
その待ち時間を削減するために、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}
}

\subsection{Mailbox} \label{sec:cell_mailbox}

Mailbox とは PPE と SPE 間の 32 ビット
メッセージの交換に用いられる。Mailbox では 3 つの振る舞いが
出来る様に設計されている。

\begin{enumerate}
\item SPU Inbound Mailbox \\
  PPE から SPE へデータを渡すためのキュー。キューのエントリ数は
  実装依存による が、研究環境では最大4個までのデータを蓄積できる。
  このキューが空の場合は、SPE は、データがメールボックスに書き込まれるまでは、
  命令でストールする。読み出すデータの順番は書き込んだ順番に保証されている。
\item SPU Outbound Mailbox \\
  SPE から PPE へのデータを渡すためのキュー。研究環境では最大1個までしか
  データが蓄積できない。
\item SPU Outbound interrupt Mailbox \\
  SPU Outbound Mailbox とほとんど同じだが、このキューでは SPE から
  キューにデータが書き込まれると、PPE に対して割り込みイベントが
  発生し、データの読み出しタイミングを通知する事が出来る。
\end{enumerate}


\section{Ceriumとは}

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

%% \begin{itemize}
%% \item SceneGraph
%% \item Rendering Engine
%% \item Task Manager
%% \end{itemize}

\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との依存関係を示す。依存関係の情報はPPE側が持っている。SPEからPPEへ実行し終わったTaskが通知され、PPE側ではその通知に沿って
依存関係を処理していく。例えば、Task A が Task B の実行完了をまって、実行可能状態になるとする。はじめTask B はどのTaskも待つ必要がないので、
SPEに送られ、実行される。Task Bの実行が完了すると、SPEからTask B の完了通知がMailでPPE側へ通知される。Task Bが実行完了の通知がきたので、Task Aの待ちTask
から、Task BがはずされTask AはSPEに送られる。以上のようにSPEからのMailを使った通知によって、Taskの依存関係を解決している。
待ちTaskを持っているTaskはwait queueと呼ばれるキューに、待ちTaskのないTaskはactive queueと呼ばれるキューに入れられる。active queueにあるTaskをSPEに送る。()

\begin{figure}[htbp]
  \begin{center}
    \scalebox{0.4}{\includegraphics{pic/dependency.pdf}}　　　　
    \caption{依存関係の解決} \label{fig:dependency}
  \end{center}
\end{figure}

\subsection{Taskのスケジューリング}
SPEは、Taskを一つずつ受け取るのではなく、ある程度まとめて受け取る。それをTaskListと呼んでいる。TaskListに沿ってTaskを実行していき、Task毎に実行完了のMailを
送る。TaskListのTaskを全て実行すると、次のTaskListを要求するMailをPPE側に送る。

\section{TaskArray}
WordCountの場合,　対象となるファイルによって大量のTaskが生成される。レンダリングエンジンの場合、PPE側で実行すべきTaskがある。その時に、PPEが自分のTaskを完了し、Taskの依存関係を解決するのに時間がかかってしまう。そうなるとSPEからのTaskList要求への反応が送れ、SPEの待ち時間が生じるはずである。それを解決するためにTaskArrayを提案、実装した。TaskArrayは、複数のTaskをまとめて扱うことができる。それによって依存関係を解決すべきTaskの数が減り、解決の手間が省け、SPEからのTaskList要求に応答しやすくなる。また、一度にTaskListに多くのTaskを登録できるため、SPE側からのTaskList要求の回数が減り、待ち時間が生じる可能性が減る。さらにTaskArrayの長さによっては、パイプラインが長くなり、DMAの転送時間を多く隠すことができる。WordCountとレンダリングエンジンのおいて、TaskをTaskArrayにし、効果を検証した。

\subsection{WordCountのTask}

まずは例題の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に渡せるデータ容量はDMAの仕様上16Kbyteまでである。さらに転送する際には16の倍数byteである必要がある。

\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はWordCountTaskを待ちTaskと設定し、WordCountがすべて終わらないと、
実行されない。

\subsection{WordCountTaskのTaskArray化}
WordCountTaskをTaskArray化した。TaskArray１つに、64個のTaskが入るようにし、WordCount対象は166Mのテキストファイルとした。TaskArrayを適応した場合と、そうで
ない場合で比較する。
SPEは6個使用した。timeは実行にかかった時間、dma waitは、SPEが起動していた時間においての、dma転送の待ち時間の割合。
mail wait はSPEが起動していた時間においての、次のTaskListのmailを待っている時間の割合である。以下に、表にして示す。dma,mailそれぞれのwait割合に関してはspe6個の平均を示しており、この時のTaskの数は約一万個である。

\vspace{5mm}
\begin{table}[htb]
  \begin{center}
    \vskip -\lastskip \vskip -20pt
    \caption{WordCountTaskのTaskArray化による比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l|l} \hline \hline
         & Task & TaskArray\\ \hline
        \hline
        %Mac OSX & 7.0 & 8.5\\ \hline
        time  & 2.184s & 2.109s \\ \hline
        %dma wait  & 28685142 & 21266467 \\ \hline
        %mail wait  & 9302079 & 12025955 \\ \hline
        dma wait  & 18\% & 12\% \\ \hline
        mail wait  & 5\% & 8\% \\ \hline
      \end{tabular}\hfil}
    \label{tb:lightspeed}
  \end{center}
\end{table}
\vspace{-5mm}

表に示した結果より、著しいTaskArrayの効果は見られなかった。この結果はWordCountにおいては誤差の範囲内である。効果が見られなかった原因はおそらくWordCountの場合はPPE側のTaskがないので、依存関係の解決にあまり待ち時間が発生しないからだと考えられる。また、WordCountにおいてはファイルをメモリにマッピングするので、ファイルの容量が大きい場合に大量にメモリを消費してしまう。その結果スワップが起きやすくなり、dma転送の待ち時間が長くなっている可能性がある。この解決として、一度にファイル全てをマッピングするのではなく、何回かに切り分けてマッピンするのがよい。ある程度のWordCountし終わった領域に、次のWordCount領域を入れ替えて使うことでメモリを節約でき、スワップを減らすことができるはずである。その結果メモリアクセスが高速になり、dma転送の待ち時間も削減できる。

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

レンダリングエンジンは主に、CreatePolygon、CreateSpan、DrawSpanという3つのTaskから構成されている。
それぞれのTaskの動作とレンダリングの流れを示す。

{\small
\begin{enumerate}
 \item CreatePolygonTaskによってSceneGraphをもとにモデリングデータから、実際に表示するポリゴンを生成する。
 \item CreateSpanTaskで生成したポリゴンからSpanの生成する。
 \item DrawSpanTaskでSpanをRGBにマッピングし描画する。
ここでいうSpanとは、ポリゴンに対するある特定のY座標に関するデータを抜き出したものである。
\end{enumerate}
}

\begin{figure}[htbp]
  \begin{center}
    \scalebox{0.3}{\includegraphics{pic/rendering3.pdf}}
    \caption{レンダリングエンジンの流れ} \label{rendering}
  \end{center}
\end{figure}


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

レンダリングエンジンの中で、もっとも数が多く生成されるDrawSpanTaskをTaskArray化した。
地球と月を表示する例題を対象に効果を検証した。FPS(Frame Per Second)は、一秒間に表示できる
Frame数のことである。

\begin{figure}[htbp]
  \begin{center}
    \scalebox{0.5}{\includegraphics{pic/lightearth.pdf}}
    \caption{地球と月を表示する例題} \label{rendering}
  \end{center}
\end{figure}


\vspace{5mm}
\begin{table}[htb]
  \begin{center}
    \vskip -\lastskip \vskip -20pt
    \caption{レンダリングTaskのTaskArray化による比較}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|l|l|l} \hline \hline
         & Task & TaskArray\\ \hline
        \hline
        %Mac OSX & 7.0 & 8.5\\ \hline
        FPS  & 3.94 & 4.32 \\ \hline
        %dma wait  & 28685142 & 21266467 \\ \hline
        %mail wait  & 9302079 & 12025955 \\ \hline
        dma wait  & 0.06\% & 0.07\% \\ \hline
        mail wait  & 55\% & 42\% \\ \hline
      \end{tabular}\hfil}
    \label{tb:lightspeed}
  \end{center}
\end{table}
\vspace{-5mm}

結果からDrawSpanTaskをTaskArray化すると、FPSが多くなり、mailのwait時間が減ったことがわかる。レンダリングエンジンでは、PPE側でも
処理すべきTaskがあり、常にPPEが忙しい状態になっている。そのためmailを処理する時間が送れSPEのmail待ちが発生していると考えられる。
TaskArray化でTaskをまとめることでSPEが１つのTaskListで多くのTaskを実行できるようになったため、TaskListを要求する回数が減って、待ち時間が発生する
回数も減少した。またそれはSPEからのmailの数が減ったということなので、PPE側のmail処理の時間短縮になったと考えられる。


\section{まとめ}
今回はTaskを複数にまとめるTaskArrayを提案、実装し効果を測った。
TaskArrayの効果があるのは、PPE側にも実行すべきTaskがありPPEが忙しい場合ということがわかった。WordCountでは、PPE側のTask
がなく、mail待ちがネックではなく、TaskArrayの効果がなかった。大量のファイルをマッピングし、メモリを多く消費するのでメモリアクセス、
dma転送に待ち時間があると考えられ、TaskArrayを用いてもうまくdma転送が隠れてないようだ。dma転送をスケジュールリングによって
うまく隠す、またはメモリ領域の節約をすることができれば、今回のWordCountのような大量のデータを用いる場合の速度向上が期待できる。

\subsection{メインメモリアクセス}
WordCountを実装している際に極端に処理速度が遅くなる時があった。
それは複数のSPEが同時にメインメモリにアクセスする際に、それぞれ離れたメモリにアクセスする時である。Taskにはそれぞれアクセスすべき
メインメモリのアドレスを持っており、そのTaskがうまくSPEに割り振られてなかったため、そのようなことがおこった。TaskをSPEに割り振る際には
なるべく複数のSPEが近くのメモリをアクセスするようにした方がよい。また一定周期でSPEを同期させ、特定のSPEのTask実行が遅くなりすぎたり、速くなり
すぎたりするのを防ぐことでも、メモリアクセス先が離れることを回避できる。



%{\bf 謝辞}\
%
 \begin{adjustvboxheight} % needed only when Appendix follows
 \begin{thebibliography}{99}
 \bibitem{} 宮國渡 "Implementation of Fine-grain Task Manager for Cell" 平成20年度 学位論文(修士)
 \bibitem{} fixstars:http://cell.fixstars.com/ps3linux/index.php/メインページ
 \bibitem{} 高山 征大「CELL REGZA」が搭載する並列化技術「Molatomium」
 \bibitem{} OpenCL:http://www.khronos.org/opencl/
 \bibitem{} Mark Deloura "Game Programming Gems"

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