\chapter{Ceriumの改良}
本章では、本研究で Cerium に行った改良について説明する。
Cerium のレンダリングの例題として ball\_bound と panel を使用し、それを元に改良の効果を示していく。まず、改良前の 計測結果を示す。(\tabref{ball_bound_flat}) (\tabref{panel_flat})

\begin{table}[!htb]
  \begin{center}
    \caption{Cerium 改良前 (ball bound)} \label{tab:ball_bound_flat}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|} \hline
         FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
         30.2 & 1.8\% & 74.3\% & 23.7\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[!htb]
  \begin{center}
    \caption{Cerium 改良前 (panel)} \label{tab:panel_flat}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|} \hline
         FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
         4.0 & 21.3\% & 11.1.\% & 67.6\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}


特に ball bound では Mail の待ち時間が 約70\%あり、処理時間の大部分を占めている。この Mail の待ち時間を削減するために Task をグルーピングする TaskArray, ソフトウェアMailQueue の実装を行った。また RenderinEngine の Task 内には、明示的な DMAロードが記述されており、アーキテクチャ依存となっている。そこでアーキテクチャ依存の記述を避けるために、MemorySegment を実装した。

\section{TaskArray}
本研究では新しい Task として Task Array を実装した。 Cerium では Task と TaskList 毎に Mail を通知し、SPE の Mail の待ち時間が発生する問題があった。PPE 側で実行される Task もあるなかで、SPE側の Task を一つ一つ Task 毎に依存関係を処理しており、SPE への TaskList 要求や、次の Mail 書き込み待ちなど、Mail 通知の対応が遅れることが考えられる。Mail 通知の対応が遅れた分 SPE はアイドル状態となってしまい、稼働率が下がってしまう。この問題を解決するために、我々は Task Array を提案、実装した。 Task Array を使用することで、複数の Task をまとめる Task のグルーピングが行える。複数の Task を ひとつの Task Array として登録すると、依存関係の処理が Task Array ひとつ分で収まる。依存関係の処理には Mail 通知を行なっていたので 依存関係の処理が減少する分、 Mail 通知の回数も少なくなる。これによって、Mail 待ちによる SPE のアイドル状態の時間を減少させることができると考える。例えば TaskArray のサイズが4、TaskList のサイズが4、処理するべき Task の数が16の場合だとする。この時に TaskArray を使用すると、4つ必要だった TaskList が1つで済み、さらに16Task分の依存関係の解決が4つのTaskArray分で済む。(\figref{taskarray}) これによって Task 毎の Mail通知と TaskList 毎のMail通知の回数が合わせて 四分の一となる。このようにTaskArrayを用い Mail 自体の回数を減らし、待ち時間を削減できると考える。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{./images/taskarray.pdf}
  \end{center}
  \caption{task array flow}
  \label{fig:taskarray}
\end{figure}

以下に Task Array を用いた記述例を示す。このプログラムは Task Array に複数の同一 Task を
登録して、まとめて実行するというプログラムである。

\begin{verbatim}                                                                                                        
void                                                                                                                    
hello_init(TaskManager *manager)                                                                                        
{                                                                                                                       
                                                                                                                        
    /* task id/task num/param/inData/outData の数を指定する*/                                                                   HTask *twice_main = manager->create_task_array(Hello,task_num,data_count,                                           
                                                   data_count,data_count);                                              
    Task *t = 0;                                                                                                        
                                                                                                                        
    for(int i = 0;i<task_num;i++) {                                                                                     
        t = twice_main->next_task_array(Hello, t);                                                                      
    }                                                                                                                   
    twice_main->spawn_task_array(t->next());                                                                            
    twice_main->set_cpu(SPE_ANY);                                                                                       
    twice_main->spawn();                                                                                                
}                                                                                                                       
                                                                                                                        
static int                                                                                                              
run(SchedTask *s,void *rbuf, void *wbuf)                                                                                
{                                                                                                                       
    s->printf("Hello World\n");                                                                                         
    return 0;                                                                                                           
}                                              

// 実行結果                                                                                                             
% ./hello -task 6                                                                                                       
Hello World                                                                                                             
Hello World                                                                                                             
Hello World                                                                                                             
Hello World                                                                                                             
Hello World                                                                                                             
Hello World                                                                                                             
                                                                                                                        
\end{verbatim}

プログラムに用いられてる新しい API について説明する。\\
\begin{description}
\item[create\_task\_array: ] 同一の Task を複数持つことのできる Task Array を生成する。この際に、登録する Task のID, Task の数、設定する param, input data, output data の数を指定する。
\item[next\_task\_array: ] Task Array に Task を実行順序を定める。実行順序は next\_task\_array
を行った順になる。
\item[spawn\_task\_array: ] Task Array の中のすべての Task が書きこまれたかどうかをチェックする。TaskArray では指定された Task の数と、実際に登録された Task の数が同一か計算し、異なってた場合にはエラー文を返す。これは DMA ロードの際のサイズを合わせる為、正確に数を合わせなければならない。
\end{description}

この TaskArray を RenderingEngine の DrawSpanTask に適応させた。レンダリングの例題は ball bound と panel を用いた。TaskArray の大きさは 8 である。その効果を示す。(\tabref{taskarray_ballbound}) (\tabref{taskarray_panel})

\begin{table}[!htb]
  \begin{center}
    \caption{Effect of Task Array(ball bound)} \label{tab:taskarray_ballbound}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        TaskArray & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
        未使用 & 30.0 & 1.8\% & 76.2\% & 22.0\% \\ \hline
        使用 & 32.2 & 2.5\% & 66.7\% & 30.8\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

mail の待ち時間が 約10\% 削減され、FPSの向上があり、TaskArray による効果が見られた。

\begin{table}[!htb]
  \begin{center}
    \caption{Effect of Task Array(panel)} \label{tab:taskarray_panel}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        TaskArray & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
        未使用 & 4.0 & 21.3\% & 11.1\% & 67.6\% \\ \hline
        使用 & 4.2 & 22.5\% & 5.7\% & 71.8\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\section{MailQueue}
Task の完了通知や、アイドル状態の SPE に Task のリストの情報を通知するために Mail を使用している。Cell の設計では、その通知に使われる SPE からの書き出しMailのQueueのサイズは1である。ハードウェアの設計として、Mailを書き出す場合、前回のMailがPPE側から読み込まれていない場合に、PPE側の読み出しでMailboxが空き状態になるまで、SPEはアイドル状態となる。するとPPE側のMail読み出し処理が追いつかない場合には、SPE側に余計な待ち時間が入ってしまう。そこで、ソフトウェアMailQueue を実装した。ハードウェアのMailboxへの書き込みができない場合には、ソフトウェアMailQueueへ書き出し、Mail の書き出し待ちをなくす。(\figref{mailqueue_flow})

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.6]{./images/mailqueue1.pdf}
  \end{center}
  \caption{mailqueue flow}
  \label{fig:mailqueue_flow}
\end{figure}

MailQueueの大きさはメモリ容量の限り自動で拡張される。以下に ball bound と panelの例題での MailQueue の有無における測定結果を示す(\tabref{mail_ball})(\tabref{mail_panel})。

\begin{table}[!htb]
  \begin{center}
    \caption{Effect of MailQueue(ball bound)} \label{tab:mail_ball}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        MailQueue & FPS & DMA転送待ち時間 &  mailの待ち時間 & SPE稼働率\\ \hline
        なし & 32.2 & 2.5\% & 66.7\% & 30.8\% \\ \hline
        あり & 41.7 & 3.3\% & 56.8\% & 40.0\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[!htb]
  \begin{center}
    \caption{Effect of use MailQueue(panel)} \label{tab:mail_panel}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        MailQueue & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
        なし & 4.2 & 22.5\% & 5.7\% & 71.8\% \\ \hline
        あり & 4.2 & 23.7\% & 4.1.\% & 72.3\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}


ball bound では Mail の待ち時間の割合が減少し、 8FPSの向上がみられた。ソフトウェア MailQueue によって Mail の書き出しタイミングを変更することで、Mail の待ち時間を削減することができた。PPE 側では、SPEからの Mail の確認は一度の ループ文で行なっている。Mail を確認しおえ、そのループ文を抜けてしまうと、次に Mail を確認するまでに PPE 側の Task 処理が挟まれる。よって、SPE 側の Mail 通知は一度に多く行った方が、PPE側の Mail 確認がスムーズに行われ、結果 SPE の稼働率向上に繋がると言える。ソフトウェアMailQueue では Mail をキューイングし一度に書き出すので、この点でも効果がある。panel では描画の処理に時間がかかるので、稼働率は70\%を超えている。mail 待ちは5.7\%と全体の比率からは低い値となっているため、MailQueueの効果はあまり見られない。

\section{MemorySegment}
CreateSpanTask 内では明示的に DMA転送命令を行なっている。これは処理するデータ構造上の理由である。しかし、DMA転送は Cell のアーキテクチャに依存した機能である。また Task に登録された input data と output data は自動的に TaskManager によってパイプライン化されるが、明示的にDMA転送を行う場合には、手動でのパイプライン処理を行う必要がある。そこで、Task 内でのデータの入出力の機能を 抽象化する MemorySegment を実装した。MemorySegment によって DAM転送は隠蔽され、アーキテクチャ依存の記述を避けることができる。またメモリ操作も抽象化される。

CreateSpanTask 内の明示的なDMA転送の例を示す。

\begin{verbatim}
create_span() {

   loop() {

     tmp_spack = spack;
     spack = send_spack;
     send_spack = tmp_spack;

     smanager->dma_wait(SPAN_PACK_STORE);
     smanager->dma_store(send_spack, (memaddr)spackList[prev_index],
                         sizeof(SpanPack), SPAN_PACK_STORE);

     smanager->dma_load(spack, (memaddr)spackList[index],
                         sizeof(SpanPack), SPAN_PACK_LOAD);

     prev_index = index;
     smanager->dma_wait(SPAN_PACK_LOAD);

     span_calc(spack);

  }

}

\end{verbatim}

CreateSpanTask では SpanPack というデータ構造を扱う。MainMemory から SpanPack をDMAロードし、ロードした SpanPack に span\_calc() で計算した Span を格納し また MainMemory へと書きだす。変数 tmp\_spack, spack, send\_spack はそれぞれ SpanPack へのポインタであり、それを入れ替えながらDMA転送行うことで、メモリを節約を行なっている。それぞれのAPIの説明を行う。

\begin{description}
\item[dma\_wait: ] 指定されたdmaタグの dma転送の完了を待つ。
\item[dma\_store: ] 指定された LS のアドレスから、指定された サイズ分 の領域を MainMemory に書き出す。その際にdma\_wait で用いる dma タグも指定する。例の場合では SPAN\_PACK\_STORE である。
\item[dma\_load: ] 指定された MainMmory のアドレスから 指定された サイズ分のデータを LS へDMAロードを行う。その際に dma\_wait で用いる dma タグも指定する。 例の場合では SPAN\_PACK\_LOAD である。
\end{description}
dma タグは、enum によって整数が定義されている。次に上記のコードを MemorySegment API に変更した例を示す。

\begin{verbatim}
create_span() {

   loop() {

     smanager->wait_segment(span_put_ms);

     span_put_ms = span_get_ms;
     smanager->put_segment(span_put_ms);

     span_get_ms = smanager->get_segment((memaddr)spackList[index], span_ml);
     smanager->wait_segment(span_get_ms);

     prev_index = index;
     spack = (SpanPackPtr)span_get_ms->data;

     span_calc(spack);

   }

}
\end{verbatim}

変数 span\_get\_ms, span\_put\_ms はそれぞれ MemorySegment のデータ構造を指すポインタである。この MemorySegment というデータ構造で Task 内部での 必要なデータのやり取りを行う。MemorySegment のAPIの説明を行う

\begin{description}
\item[wait\_segment: ] 指定された MemorySegment の処理完了を待つ。それは書き出し、読み込みどちらも当てはまる。dma\_wait に相当する。
\item[put\_segment: ] 指定された MemorySegment を書きだす。書き出し先のアドレスは、MemorySegment の生成時に登録されている。
\item[get\_segment: ] 指定されたアドレス への書き出しを目的とした、MemorySegment を取得する。MemorySegment は予め MemorySegmentList によって管理されており、その List から使用可能な Segment を得ることができる。
\end{description}

SPE の LS は 256KB となっていて、一般的なCPUのメモリ容量と比べると小さい。LS 内部での頻繁な メモリのアロケーションなどは LS を圧迫することになる。そこで、一度確保したメモリを使いまわすことが必要である。MemorySegment は必要な構造体をはじめに List として登録する。List は LRU で管理し、指定されたメモリ容量を超えた場合には 最もアクセスされた時間が古いデータから順に開放され、新たなデータを List に加える。以下にそのコードを示す

\begin{verbatim}

    ml = smanager->createMemList(sizeof(SpanPack), SPANPACK_SEGMENT_NUM);
    smanager->global_set(GLOBAL_SPANPACK_LIST, (void *)ml);

\end{verbatim}

コード上にあるAPIの説明を行う。

\begin{description}
\item[createMemList: ] 指定されたサイズの、指定され数だけ メモリを確保し、そのメモリを List を生成する。
\item[global\_set: ] どの Task からでも 指定された アドレスを呼び出すことができる。Task 共通のメモリ空間を扱う時に用いる。
\end{description}
このように MemorySegment はメモリの List を持ち、それを抽象化した API によって LS のメモリを使い回しながら、Task 内でのデータ転送を可能にする。また 明示的なDMA転送API を隠蔽することができるので、他の分散メモリ環境などでの汎用性が期待できる。DrawSpanTask の他に、Texture cache でも使用している。

\subsection{改良のまとめと比較}

本研究で行った改良、TaskArray と MailQueue を加えた計測結果をまとめる。
本研究で行った改良と、Cerium 開発後から先行研究の改良の効果をまとめたものを　ball bound , panel の例題を用いて示す。(\tabref{result_ball_bound})(\tabref{result_panel})
ball bound では Cerium 開発後からの改良の結果、FPS が17上昇し、稼働率が18\%向上した。
panel では Cerium 開発後からの改良の結果、FPS が0.2上昇し、稼働率が約4\%向上した。
Cerium が提案され、これまでの改良の一覧を示す(\tabref{imp_resultp})

\begin{table}[!htb]
  \begin{center}
    \caption{Ceriumの改良効果(ball bound)} \label{tab:result_ball_bound}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        改良時期     & FPS  & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
        Cerium開発時 & 24.6 & 5.5\% & 72.4\% & 22.1\% \\ \hline
        先行研究     & 30.2 & 1.8\% & 74.3\% & 23.7\% \\ \hline
        本研究       & 41.7 & 3.3\% & 56.8\% & 40.0\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}


\begin{table}[!htb]
  \begin{center}
    \caption{Ceriumの改良効果(panel)} \label{tab:result_panel}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|c|c|c|} \hline
        改良時期     & FPS & DMA転送待ち時間 & mail待ちの割合 & SPE稼働率\\ \hline
        Cerium開発時 & 3.9 & 21.1\% & 13.2\% & 65.9\% \\ \hline
        先行研究     & 4.0 & 21.3\% & 11.1.\% & 67.6\% \\ \hline
        本研究       & 4.2 & 23.7\% & 4.1.\% & 72.3\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[!htb]
  \begin{center}
    \caption{Cerium の開発から改良点のまとめ} \label{tab:imp_resultp}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|c|} \hline
        改良時期　& 改良点 \\ \hline
               & DrawSpanTask のパイプライン化  \\\hline
               & TASK\_DUMMY での依存関係の設定を排除 \\ \hline
               & 依存関係の設定を Task 化で実現 \\ \hline
               & プロファイラの導入 \\ \hline
               & Texture cache の実装 \\ \hline
               & Prime Counter の実装 \\ \hline
        本研究 & WordCount の実装 \\ \hline
        本研究 & CreatePolygon部分のTask化 \\ \hline
        本研究 & 光源機能の実装 \\ \hline
        本研究 & Task Array の実装 \\ \hline
        本研究 & ソフトウェアMailQueue の実装 \\ \hline
        本研究 & MemorySegment の実装 \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\subsubsection{OpenGLとの比較}

OpenGL (Open Graphics Library) \cite{opengl} とは、Silicon Graphics 社が開発した、3D グラフィックス
処理のためのプログラミングインターフェースである。
学生実験で作成されたシューティングゲーム SuperDandy(\figref{t_dandy}) を Task を用いない OpneGL 上で動作するバージョンを用意して、Cerium
と性能を比較した。OpenGL は PPE だけで動作している。Cerium は今までの改良をすべて加えたもので、レンダリング部分が Task 化され並列処理される。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.4]{./images/t_dandy.pdf}
  \end{center}
  \caption{SuperDandy実行の様子}
  \label{fig:t_dandy}
\end{figure}

\begin{table}[!htb]
  \begin{center}
    \caption{シューティングゲーム「SuperDandy」の性能比較(OpenGL, Cerium))} \label{tab:dandy-compare}
    \hbox to \hsize{\hfil
      \begin{tabular}{|c|l|l|c|} \hline
         & OpenGL  & Cerium & 性能差\\ \hline
        dandy & 17.5 FPS & 49.5 FPS & 2.9 倍\\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

コアを１つ用いている OpenGL 版に比べて、Cerium では 2.9 倍の性能向上が見られた。
SPEを活用し、改良によって待ち時間の削減ができ、性能の向上ができた。