Mercurial > hg > Papers > 2011 > koba-master
view paper/early.tex @ 14:19be75493fbb
fix.
author | koba <koba@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 15 Feb 2011 18:04:22 +0900 |
parents | f953f01c58bf |
children |
line wrap: on
line source
\chapter{Cell BE と Cerium} \label{chapter:early} ここでは Cerium がターゲットとしている Cell Broadband Engine の説明と Game Framework Cerium の実装、および同じ並列プログラミングのフレームワーク である OpenCL について説明する。 \section{Cell Broadband Engine}\label{sec:cell} Cell Broadband Engine は SCEI と IBM によって開発された CPU である。 2 thread の PPE(PowerPC Processor Element)と、8個の SPE (Synergistic Processor Element)からなる非対称なマルチコアプロセッサであり、 高速リングパスであるEIB(Element Interface Bus)で構成されている。 Cerium の動作環境である PS3 Linux では PPE と 6個の SPE が使用できる。 (図\ref{fig:cell}) \subsection{PPE (PowerPC Processor Element)}\label{sec:ppe} PPE は Cell Broadband Engine のメインプロセッサで、複数の SPE を コアプロセッサとして使用することができる汎用プロセッサである。 メインメモリや外部デバイスへの入出力、SPE を制御する役割を担っている。 \subsection{SPE (Synergistic Processor Element)}\label{sec:spe} SPE には 256KB の Local Store(LS) と呼ばれる、SPE から唯一、直接参照できる メモリ領域があり、バスに負担をかける事なく並列に計算を進めることができる。 SPE からメインメモリへは、直接アクセスすることはできず、SPE を構成する一つ である MFC(Memory Flow Controller)へ、チャネルを介して DMA(Direct Memory Access) 命令を送ることで行われる。 \newpage \begin{figure}[htbp] \begin{center} \includegraphics[scale=0.8]{images/cell.eps} \end{center} \caption{Cell Broadband Engine} \label{fig:cell} \end{figure} \section{Game Framework Cerium}\label{sec:cerium} Cerium は我々が提案したゲーム開発フレームワークで、独自の Rendering Engine を持つ。ゲーム中のオブジェクトの振る舞いやルールは SceneGraph で管理し、 それらの動きやレンダリングの処理を動的に SPE に割り振るカーネルとして Task Manager が用いられる。Cerium は C++ で実装されており、画像の読み込みや 入力デバイスは SDL を用いて行っている。 \subsection{SceneGraph}\label{sec:scenegraph} ゲームを構成するオブジェクトやその振る舞いを格納したノードの集合を SceneGraph とする。SceneGraph のノードは親子関係を持つ tree で構成される。 親子関係とは、親オブジェクトの回転や平行移動などの行列計算による 頂点座標の変更が、子オブジェクトにも反映する関係のことである。これは子に 対してスタックに積まれた親の変換行列を掛けることで実現できる。 \begin{figure}[h] \begin{center} \includegraphics[scale=0.6]{images/sgtree.pdf} \end{center} \caption{SceneGraph Tree} \label{fig:sgtree} \end{figure} \newpage \subsection{Rendering Engine}\label{sec:rendering} Cerium の Rendering Engine は主に以下の 3 つの Task を持つ。 \begin{itemize} \item CreatePolygonFromSceneGraph: SceneGraph が持つ Polygon の座標から、 実際に画面に表示する座標の計算を行い、PolygonPackを生成する \item CreateSpan: PolygonPack から同じ Y 座標を持つ線分の集合である SpanPack を生成する \item DrawSpan: SpanPack を Texture を読み込みながら Z Buffer を用いて 描画する \end{itemize} Rendering Engine における描画処理は、SceneGraph から、実際に表示する ポリゴンを抽出、ポリゴンから Span の生成、Span に RGB をマッピングし 描画する、といった 3 つの行程に分けることができる。そして各行程が Task として 定義され、Cerium に組み込まれている。 ここでいう Span とは、ポリゴンに対するある特定の Y 座標に関する データを抜き出したものである。 \section{Task Manager}\label{sec:taskmanager} Task Manager は、Cerium における並列処理を可能とするフレームワークであり、 Task と呼ばれる分割された各プログラムを管理する。Task の単位はサブルーチン または関数とし、Task 同士の依存関係を考慮しながら実行していく。 現在実装されている基本的な TaskManager の API の実装を表 \ref{tb:tm_api} に 示す。また、本研究で使用した API の詳細については \ref{sec:tm_api} 節にて 述べる。 \begin{table} \caption{Task Manager の API} \begin{tabular}{c|l} \hline \hline create\_task & Task を生成する \\ \hline run & 実行 Task Queue の実行\\ \hline allocate & 環境のアライメントを考慮したメモリアロケータ\\ \hline \hline set\_inData & Task への入力データのアドレスを追加 \\ \hline set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline set\_param & Task に 32 bit の情報を追加 \\ \hline wait\_for & Task 同士の依存関係をセット \\ \hline set\_cpu & Task を実行する CPU(PPE,SPE0〜5) の設定 \\ \hline set\_post & Task が終了した後 PPE 側で実行される関数の登録 \\ \hline spawn & Task を実行 Task Queue に登録する \\ \hline \end{tabular} \label{tb:tm_api} \end{table} \section{メインスレッドの実装}\label{sec:main_thread} メインスレッドでは、主に Task の起動と、Task に渡すオプションの設定を行う。 ここでは、Task の定義と、Task のオプション設定について説明する。 \subsection{Task の定義}\ref{task_struct} 実行される Task のデータ構造は以下のようになる。このデータは PPE、SPE の 各スレッドで使用される \begin{verbatim} class Task { public: // variables int task_size; int command; int param_count; int inData_count; int outData_count; int inData_offset; int outData_offset; void *data[] __attribute__ ((aligned (DEFAULT_ALIGNMENT))); ... } class ListElement { int size; memaddr addr; \end{verbatim} Task クラスは、各 CPU が実行する Task の単位オブジェクトである。 Task のサイズを示す task\_size や Task ID を格納する command といった パラメータの他、後述する set\_param や set\_inData、set\_outData でセットした 値を格納する data というバッファを持つ。 以下は SPE が Task に格納された各種パラメータを用いて 処理を実行する ステップである。(図\ref{fig:task_struct}) \begin{enumerate} \item inDataElement にあるアドレス(メインメモリ空間)を参照し、DMA で メインメモリからデータを取得する \item command を見て、どの Task を実行するか決定する \item DMA read した値を Task に渡し、実行する \item 演算結果の DMA 転送先を、outDataElement を参照して決定する \item DMA write する \end{enumerate} \begin{figure}[h] \begin{center} \includegraphics[scale=0.7]{images/task_struct.pdf} \end{center} \caption{Task の構造と SPE からのデータの参照} \label{fig:task_struct} \end{figure} \newpage また、PPE では Task クラスの他に HTask クラスが存在する。 \begin{verbatim} class HTask : public SimpleTask { QueueInfo<TaskQueue> *wait_me; // List of task waiting for me QueueInfo<TaskQueue> *wait_i; // List of task for which I am waiting PostFunction post_func; void *post_arg1; void *post_arg2; CPU_TYPE cpu_type; ... \end{verbatim} HTask は wait\_me、wait\_i というキューを持ち、Task の依存関係を記録する。 また、cpu\_type は Task が実行される CPU の切り替えに、post\_func と post\_arg は、Task 終了時に PPE で実行される関数と引数になる。 以上のことからわかるように、Task そのものにはコードの記述はなく、SPE にロード してある Task の配列から、command に格納してある Task ID に従ってコードを 取得し、実行するだけである。よって、予めコード部分を SPE にロードしておく 必要がある。 \subsection{Task Manager の API}\label{sec:tm_api} Task で並列処理をさせる時、ユーザはまず PPE 側で Task の生成、初期化を行う 必要がある。ここではその際に使用する Task Manager の API を紹介する。 \subsubsection*{create\_task}\label{sec:task_make} Task を生成するには、TaskManager の API である {\bf create\_task } を実行する。 \begin{verbatim} HTaskPtr task = manager->create_task(ID); \end{verbatim} ID とは、各 Task に割り振られたグローバル ID である。通常の逐次型プログラム では、Task を選択して実行する場合、その関数ポインタを指定して実行すれば良い。 しかし Cell の場合、PPE と SPE 上ではアドレス空間が異なるため、SPE 上で 実行される Task をメインスレッドから直接アドレス指定することはできない。 そこで、Task 毎に ID を割り振り、その ID から、SPE 上にある Task が 格納された配列を参照して実行する。(図\ref{fig:task_struct} の (2) を参照) \subsubsection*{set\_cpu}\label{sec:set_cpu} TaskManager の{\bf set\_cpu }により、Task をどの CPU で実行させるかを 選択する事ができる。 \begin{verbatim} //SPE 1 で実行 task1->set_cpu(SPE_1); //SPE のどれかで実行 task1->set_cpu(SPE_ANY); //PPE で実行 task1->set_cpu(PPE); \end{verbatim} \subsubsection*{set\_inData set\_outData set\_param}\label{sec:task_io} Task に入力と出力先を渡す API として、{\bf set\_inData }と {\bf set\_outData }、そして{\bf set\_param }がある。 \begin{verbatim} int a; Data *addr; task->set_param(0, (memaddr)a); task->set_inData(0, addr, sizeof(Data)); task->set_outData(0, addr, sizeof(Data)); \end{verbatim} set\_inData は格納する場所の番号と Task に渡すデータのアドレス、 そのデータのサイズを引数として入力する。このアドレスに格納されているデータは DMA 転送によって SPE に送られる為、16 バイトアライメントが取れており、 データサイズは 16 バイト倍数である必要がある。 set\_param は、Task に 32 bit のデータを DMA 転送ではなく、直接渡す。 このため set\_inData で渡すには小さいデータを送るのに適している。 Task の出力先は set\_outData で指定する。使用方法は set\_inData と 同じである。 \subsubsection*{wait\_for}\label{sec:dependency} TaskManager は Task 依存を解決する機能を持っている。 \begin{verbatim} task1->wait_for(task2); task1->wait_for(task3); \end{verbatim} この例では task1 が task2、task3 の終了を待つ。task2、task3 が終了すると task1 が SPE に割り振られる。 \if0 この時、task1 は TaskManager の持つ waitTaskQueue へ、task2、3 は activeTaskQueue へ格納される。activeTaskQueue から各 CPU へ Task が 割り振られ、Task が終了したらメインスレッドへ Task 終了のメールを発行する。 メインスレッドはそれを受け取り、waitTaskQueue の Task を調べ、Task 依存を 満たした Task を activeTaskQueue に移し替える。 (図\ref{fig:dependency}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.8]{images/dependency.pdf} \end{center} \caption{Task の依存関係の解決} \label{fig:dependency} \end{figure} \fi \subsubsection*{set\_post}\label{sec:set_post} Task が終了した時、{\bf set\_post }を使うことでメインスレッドで実行される 関数と、その引数を指定できる。また、set\_post が実行されるタイミングで ユーザが Task が終了したことを検知することができる。 \section{CPU スレッドの実装}\label{sec:cpu_thread} 各 CPU(PPE、SPE) では、メインスレッドで生成された Task を受け取り、その情報を 元に、Task を実行する。ここでは Task 処理の詳細と Task の本体部分の記述、 そして 本研究で使用した API について説明する。 \subsection{Task の処理}\label{sec:task_exec} Task 本体の記述例は以下のようになっている。 \begin{verbatim} static int state(SchedTask *smanager, void *rbuf, void *wbuf) { CHARACTER *p = (CHARACTER*)smanager->get_input(rbuf, 0); CHARACTER *q = (CHARACTER*)smanager->get_output(wbuf, 0); player *jiki = (player*)smanager->get_input(rbuf, 1); p->y += p->vy; p->x += p->vx; if ((p->y < jiki->y) && (p->y + 16 > jiki->y)) { p->vy = -2; p->vx = ((jiki->x > p->x) ? 4 : -4); } *q = *p; return 0; } \end{verbatim} これは図\ref{fig:task_struct} の (3) にあたる処理である。 \ref{sec:task_io} 節でセットしたデータを get\_input で受け取り、 get\_output で書き出し用のバッファのアドレスを受け取っている。 上記の例では、セットしたデータを用いて処理した後で書き出し用のバッファに 書き込んでいる。 \newpage \subsection{SchedTask}\label{sec:schedtask} SchedTask とは、Task の処理中に Task に関する処理を行うことができる オブジェクトで、Task の引数として与えられている。SchedTask の API を 表 \ref{tb:st_api} に示す。 \begin{table}[h] \caption{SchedTask の API} \begin{tabular}{c|l} \hline \hline create\_task & Task を生成する \\ \hline allocate & 環境のアライメントを考慮したメモリアロケータ\\ \hline \hline get\_input & set\_inData で指定したデータを取得する \\ \hline get\_output & set\_outData で指定した領域に書きこむバッファを取得する \\ \hline get\_param & set\_param で指定した 32 ビットデータを取得する \\ \hline \hline global\_alloc & Task 間で共用するデータの allocate \\ \hline global\_get & global\_alloc した領域のアドレスを取得 \\ \hline global\_free & global\_alloc した領域の free \\ \hline \hline mainMem\_alloc & メインメモリ上の allocate \\ \hline mainMem\_get & mainMem\_alloc した領域のアドレス(メインメモリ空間)を取得 \\ \hline mainMem\_wait & mainMem\_alloc が完了するまで待つ \\ \hline \end{tabular} \label{tb:st_api} \end{table} \subsubsection*{Input Data の取得}\label{sec:indata} \ref{sec:task_exec} 節のコードの rbuf にはメインスレッドで set\_inData により 指定したデータの実体が入っている。(図\ref{fig:rbuf}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.8]{images/rbuf.pdf} \end{center} \caption{set\_inData による rbuf の構造} \label{fig:rbuf} \end{figure} \newpage このデータを扱う場合、直接 rbuf を見るのではなく \begin{verbatim} int *data = (int*)smanager->get_input(rbuf, index); \end{verbatim} というようにして取得する。index は set\_inData で指定した番号になる。 同様に set\_param で設定した値は、get\_param(index) で得られる。ここの index も get\_input と同じく、指定した番号である。 \subsubsection*{Output Data の取得}\label{sec:outdata} Task が出力を行う場合、Task 生成時に set\_outData を行い、出力先のアドレスと データサイズが指定されている。wbuf は rbuf 同様、指定したサイズ分の バッファで、Task の処理を行う前に生成時に設定したデータサイズを元にバッファを allocate する。wbuf はこの時点ではただのバッファで、中には何も入っていない (不定)。Task 処理の終了時、wbuf の値を set\_outData で指定したアドレスに DMA 転送する。(図\ref{fig:wbuf}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.6]{images/wbuf.pdf} \end{center} \caption{set\_outData による wbuf の構造} \label{fig:wbuf} \end{figure} \subsubsection*{Task 間の共用空間}\label{sec:global} 各 Task は独立して動作するため、使用するメモリ領域も他の Task と干渉すること はない。しかし、処理によっては Task 間で同じデータを使用する場合がある。 共用領域を allocate するには global\_alloc を使う。 allocate した領域のアドレスは global\_get で取得できる。 global\_alloc した領域はユーザが global\_free で解放する必要がある。 共用領域は各 SPE に置かれるので、違う SPE の領域を参照する事はできない。 従って、同じデータを使う可能性の Task を同じ SPE 上で実行させることにより、 メモリ領域も軽減できる。(図\ref{fig:global}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.6]{images/global.pdf} \end{center} \caption{Task 間の共用領域} \label{fig:global} \end{figure} \section{OpenCL}\label{sec:opencl} OpenCL(Open Computing Language) とは、マルチコア CPU や GPU、その他の プロセッサによる、ヘテロジニアスコンピューティングのフレームワークである。 OpenCL のプラットフォームモデルは Host と複数の OpenCL Device で 構成されている。OpenCL devices の中では Compute Units(CUs) として分割され、 その中でさらに Processing Elements(PEs) として分割される。 \if0 (図\ref{fig:opencl}) \begin{figure}[h] \begin{center} \includegraphics[scale=0.8]{images/opencl.pdf} \end{center} \caption{OpenCL Platform} \label{fig:opencl} \end{figure} \fi また、OpenCL Device は 4 つの違うメモリ領域 (Global Memory, Constant Memory, Local Memory, Private Memory) を持ち、それぞれ Host や CUs、PEs からの アクセス権限が異なる(アドレス空間が異なる)。プログラミングモデルとしては、 データ並列、タスク並列をサポートしている。OpenCL は Host や各 device に kernel があることや、device 毎にメモリアドレス空間が違う、 プログラミングモデル等、TaskManager とよく似ている。