Mercurial > hg > Papers > 2010 > jsst-yutaka

changeset 5:eafd4bf0f73b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
aa
author Yutaka_Kinjyo
date Fri, 27 Aug 2010 08:43:00 +0900
parents 71595d65cf4a
children 4f0503e35925
files jssst.tex
diffstat 1 files changed, 103 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
--- a/jssst.tex	Tue Aug 17 17:50:29 2010 +0900
+++ b/jssst.tex	Fri Aug 27 08:43:00 2010 +0900
@@ -62,8 +62,8 @@
 現在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を提案し実装した。その効果について報告する。
+メインメモリ上のTaskを各Coreが受け取る際や、その終了を通知する際に待ち時間が生じる。
+その待ち時間を削減するために、Task arrayを提案し実装した。その効果について報告する。
 }
 %
 % 英文アブストラクト（大会論文には必要なし)
@@ -73,10 +73,10 @@
 
 \section{概要}
 
-近年CPUの処理速度の向上ためのクロック周波数の増加は、
+CPUの処理速度の向上ためのクロック周波数の増加は、
 発熱や消費電力の増大により難しくなっている。そのため、クロック周波数を上げる代わりに、CPUコア数を増やす傾向になった。
 マルチコアなCPUの性能を発揮するには、処理をできるだけ並列化しなければならない。それはアムダールの法則により、並列化できない部分が並列化による性能向上を制限することから言える。つまり処理速度の性能向上は、ハードウェアだけでなく、ソフトウェアを並列処理に適したように実装することにもかかっている。そのためにはプログラミングの支援をするフレームワークが必要になってくる。そこでFine Grain Task Manager であるCeirumを開発中である。現在Ceriumは、マルチコアCPUの例題としてCellに対応している。また、支援するプログラミングの対象の１つとしてゲームを選択し、PS3,Mac OS X上でのゲームフレームワークとしても動作する。
-そのCerium のチューニングをするうちに、各Coreにおいて、割り当てられたTaskが終わり、次のTaskを待つ時間がネックになり、処理速度を遅くしていることがわかった。そこで待ち時間を削減するために、各Task生成のスケジューリング方法や、複数のTaskをまとめて扱うTaskArrayを提案し実装した。その効果について報告する。
+そのCerium のチューニングをするうちに、各Coreにおいて、割り当てられたTaskが終わり、次のTaskを待つ時間が処理速度を遅くしていることがわかった。そこで待ち時間を削減するために、各Task生成方法、スケジュールリング方法の変更、複数のTaskをまとめて扱うTaskArrayを提案し実装した。その効果について報告する。
 
 
 \section{Cell Broadband Engine}
@@ -123,6 +123,28 @@
 \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つの要素から構成されており、
@@ -155,10 +177,29 @@
 }
 
 input,output data, paramaterは関数でいうところの引数にあたいする。cpu typeはTaskがPPE,または6基あるSPEのどれかで実行されるかを示すもの。
-dependencyは他のTaskとの依存関係を示す。以下にWordCountとレンダリングエンジンにおいてのTaskを紹介する。
+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
@@ -170,7 +211,7 @@
 
 WordCountTaskは、inputで与えられたdataをword countし、output dataに書き出すTaskである。
 PrintTaskはすべてのWordCountTaskの実行完了を待ち、outputへ書き出された値を集計し出力するTaskである。
-一度にSPEに渡せるdataはDMAの仕様上16Kbyteまでである。さらに転送する際には16byteの倍数である必要がある。
+一度にSPEに渡せるデータ容量はDMAの仕様上16Kbyteまでである。さらに転送する際には16の倍数byteである必要がある。
 
 \subsection{WordCountのTask設定}
 
@@ -179,22 +220,71 @@
 
 \begin{figure}[htbp]
   \begin{center}
-    \scalebox{0.3}{\includegraphics{pic/wc_graf1.png}}　　　　
+    \scalebox{0.3}{\includegraphics{pic/wc_graf1.png}}
     \caption{WordCountにおけるTaskの流れ} \label{wordcoutntask1}
   \end{center}
 \end{figure}
 
-PrintTaskのdependencyにはすべてのWordCountTaskが設定さており、WordCountがすべて終わらないと、
-実行されないようになっている。
+PrintTaskはWordCountTaskを待ちTaskと設定し、WordCountがすべて終わらないと、
+実行されない。
+
+\subsection{WordCountTaskのTaskArray化}
+WordCountTaskをTaskArray化した。TaskArray１つに、64個のTaskが入るようにし、WordCount対象は166Mのテキストファイルとした。TaskArrayを適応した場合と、そうで
+ない場合で比較する。
+SPEは6個使用した。timeは実行にかかった時間、dma waitはデータをPPEからSPEまたは、SPEからPPEにdma転送している時間、mail wait はSPEが次のTaskListを待っている時間である。以下に、表にして示す。dma,mailそれぞれのwait時間に関してはspe6個の平均を示しており、数値はDMAのデクリメンタを用いてカウントした値を10万で割って、簡略化した値である。この時の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  & 286 & 212 \\ \hline
+        mail wait  & 93 & 120 \\ \hline
+      \end{tabular}\hfil}
+    \label{tb:lightspeed}
+  \end{center}
+\end{table}
+\vspace{-5mm}
+
+TaskArrayの効果は見られなかった。その原因はおそらくWordCountの場合はPPE側のTaskがないので、依存関係の解決にあまり待ち時間が発生しないからだと考える。また、WordCountにおいてはファイルをメモリにマッピングするので、ファイルの容量が大きい場合に大量にメモリを消費してしまう。その結果スワップが起きやすくなり、dma転送の待ち時間が長くなっている可能性がある。この解決として、一度にファイル全てをマッピングするのではなく、何回かに切り分けてマッピンするのがよいと考える。ある程度のWordCountし終わった領域に、次のWordCount領域を入れ替えて使うことでメモリを節約でき、スワップを減らすことができるはずである。その結果メモリアクセスが高速になり、dma転送の待ち時間も削減できると考える。
 
 
-\subsection{TaskのTaskArray化}
+
+\subsection{レンダリングエンジンのTaskArray化}
+
+レンダリングエンジンは、PPE側で座標の計算や
 
-
-\subsection{レンダリングエンジンのTask}
+\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}
 
 \section{まとめと今後の課題}
-
+PPE側がTaskを実行して忙しいときに、mailの待ち時間の削減にTaskArrayが有効なことがわかった。
 
 
 {\bf 謝辞}\