\chapter{Task を用いたパイプラインの改良} \label{chapter:implement}

\section{CPU スレッドの実装}

各 CPU では、メインスレッドで生成された Task を受け取り、その情報を元に Task を実行する。ここでは、Task を
扱う Scheduler の実装と、Task の本体となる部分についての説明と改良された点についての説明を行う。

\subsection{Scheduler} \label{sec:scheduler}

生成された Task に従って実際の Task を実行するのが Scheduler である。Scheduler は、メインスレッドで
生成された Task List を受け取り、その中にある Task をパイプラインに沿って、ステージを遷移
しながら実行していく(\figref{scheduler})。現在は処理する Task の種類に Task Array が追加されている。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.70]{./images/scheduler.pdf}
  \end{center}
  \caption{Scheduler}
  \label{fig:scheduler}
\end{figure}

以下が Task ごとのパイプラインの記述である。

\begin{verbatim}
void
Scheduler::run(SchedTaskBase* task1)
{
    do {
        task1->read();
        task2->exec();
        task3->write();

        delete task3;

        task3 = task2;
        task2 = task1;
        task1 = task1->next(this, 0);
    } while (task1);
}
\end{verbatim}

メインメモリからの DMA 転送待ち時間に exec() を行うことで、
待ち時間を隠蔽することができる。しかし、Task の処理や
各ステージの終了タイミングによっては待ち時間(mail\_wait)が
発生してしまう場合がある(\ref{sec:task_dma})。 \\

\subsubsection{SchedTaskBase}
TaskList にある Task が全て終了し、メインスレッドから終了のメッセージ
を受け取ったら、 task1 は NULL となり、while 文を抜ける。

SchedTaskBase クラスは、Scheduler によって実行されるインターフェースである。
新たに Task Array を追加したので、SchedTaskBase を継承したクラスには
Task Array 関連のクラスが追加されている。

\begin{itemize}

\item SchedMail \\
メインスレッドからメッセージ(Mailbox)を取得する

\item SchedTaskList \\
TaskList を取得する

\item SchedTask, SchedTaskArrayLoad\\
受け取った TaskList の中の Task が 単一 Task か、Task Array なのかを判別する \\
Task Array の時は Task Array をメインメモリから転送する(SchedTaskArrayLoad)

\item SchedTaskArray, SchedTaskArrayLoad\\
TaskList から取得した Task Array を実行する

\item SchedExit \\
SPE の実行を終了する

\item SchedNop, SchedTaskArrayNop, SchedNop2Ready \\
何も行わない。パイプラインステージの待ち合わせ用

\end{itemize}

現在 Cerium では、単一 Task も Task Array も Task Array として処理している。

Scheduler (\ref{sec:scheduler}) によって上記のクラスは以下のように遷移する
( \figref{stb-state} )。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.80]{./images/stb-state.pdf}
  \end{center}
  \caption{ScheTaskBase クラスの状態遷移}
  \label{fig:stb-state}
\end{figure}

\subsection{DMA 命令} \label{sec:task_dma}

Task の入力データや結果の出力データの操作は、TaskManager がパイプラインに沿って
 DMA を行って操作している。しかし、Task 内でメインメモリ上の新たなデータが必要に
なる可能性がある。この時、Task 内で明示的に DMA 転送命令を出すことができる。

\begin{description}
\item[dma\_load(ls, mm, size, tag) :] メインメモリ上のデータ mm から、SPE の
Local Store 上の領域 ls に size byte の DMA 転送を行う。Cell の DMA 転送ではタグ
を使用することになっており、指定したタグ毎に DMA 転送の完了待ちを行うことができる。
タグは Cell の仕様では 0 ~ 31 を使用することができる。

\item[dma\_store(ls, mm, size, tag) :] SPE から PPE への DMA 転送を行う。

\item[dma\_wait(tag) :] tag を元に DMA 転送の完了を待つ。

\end{description}

dma\_load() や dma\_store() は DMA 命令の発行だけなので、DMA 転送を行っている
データを使用する場合は dma\_wait() を用いて、転送完了を待たなければならない。
転送完了を待っている間は Task が一時ストップしてしまう(\figref{mail_wait})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.80]{./images/mailtime.pdf}
  \end{center}
  \caption{DMA 転送待ち時間の発生}
  \label{fig:mail_time}
\end{figure}

\figref{mail_time} では、task\_a の処理の途中で必要になったデータが SPE 上に
存在しない場合、Task の処理内でメインメモリからデータ(a\_2)を要求している。
a\_2 の転送完了を task\_a\_2  が待っているのでこの間、Task が一時ストップしてしまう。

また、Task が止まってしまう例として各ステージの終了タイミングのずれがある。 
\figref{mail_time} の Step 2 において、task\_b の 転送が完了しなければ 
Step 3 の task\_b の exec を開始することはできない。すると、task\_a の exec 
終了から、task\_b の exec 開始までの間は Task が止まってしまうことになる。\\

この話に関連して、PPE が SPE から、DMA 命令を受け取ってそれを処理するには、PPE 
が命令をチェックするまで待たなければ行われないという問題がある。SPE が動作している
間も PPE は Task を消化しているので、SPE からの要求にすぐに答えられるわけではない。
この問題の解決策として、DMA 命令を fifo queue に格納し、PPE が命令をチェックする際に
まとめてチェックするように改良した。

\section{Cerium のパイプラインの改良}

Cerium は Task を用いて動作が記述することができる。Task で記述することにより、
Scheduler(\ref{sec:scheduler}) によってパイプラインが構成されるので、プログラム
の性能向上が見込める。Task 化を行う際、以下のことに注意しなければならない。

\begin{itemize}
\item Task が扱うデータの構造(\ref{sec:input_output})
\item 他の Task との依存関係(\ref{sec:task_depandency})
\end{itemize}

データ構造は DMA 転送を行うため、データのアドレスは 16 byte alignment 
が取れておりsize は 16 byte の倍数である必要があるということ、
依存関係は Task\_A で扱うデータが 他の Task\_B でも継続して使用される場合、
Task\_A ー＞ Task\_B という実行順序になるように依存関係を付けなければならないと
いうものである。

\subsection{パイプラインの改良を行う上で考慮する点} \label{sec:pipeline-point}

Task 化において注意することを踏まえた上で、Cerium のパイプラインの改良を行う際に
は、以下のことを考慮する必要がある。

\begin{enumerate}
\item Cerium の処理の Task 化
\item 想定していた処理とパイプラインで実際に行われている処理とのチェック
\item SPE が常時稼動している
\end{enumerate}

今回は Cerium 内で最も処理時間の長い Rendering Engine(\ref{sec:cerium_renderingengine}) 
部分の改良を行う。

\subsection{Rendering Engine 処理の Task 化} \label{sec:rend-task}

Rendering Engine (\ref{sec:cerium_renderingengine}) は、SceneGraph や
ユーザが記述したプログラムを実行する部分 (mainexec) と 描画に係わる部分 (renderng) 
に分けられる。これまでの Cerium は mainexec に rendering の計算部分の処理も含めており 
mainexec と 実際に描画する run\_draw の部分に分けられていた。そして、その２つを交互に
実行する逐次処理の体系を取っていた。
さらに、Task の終了後に Task 同士を繋ぐ関数を用いて依存関係を構築していた。\\

そこで我々は、これまで依存関係に用いていた関数の Task 化を行うことにした。
以下に変更前 \ref{sec:old-rend} と変更後 \ref{sec:new-rend} の 
Rendering Engine のコードを示す。

\subsubsection{変更前の Rendering Engine} \label{sec:old-rend}
\begin{verbatim}
/* PPE Task */
Task TASK_DUMMY {} // 何もしない

/* Function */
/* Start */
void run_init {
  task_next = TASK_DUMMY; // TASK_DUMMY を元に task_next を生成
  task_next->set_post(post2runLoop); // task_next->post2runLoop の順に実行
  task_next->spawn(); // task_next を実行
}

void post2runLoop {
  run_loop();
}

void run_loop {
  task_next = TASK_DUMMY; // task_next を生成

  main_exec {
    task_next->wait_for(A); // A->task_next の順に実行
    task_next->wait_for(B); // B->task_next の順に実行
  }
  common_rendering{
    task_next->wait_for(C); // C->task_next の順に実行
  }

  task_next->set_post(post2runDraw); task_next->post2runDraw の順に実行
  task_next->spawn(); // A,B,C の処理が終了したら task_next タスク を実行
}

void post2runDraw {
  run_draw();
}

void run_draw {
  task_next = TASK_DUMMY; // task_next を生成
  common_draw{
    task_next->wait_for(D); // D->task_next の順に実行
  }
  
  task_next->set_post(post2runLoop); task_next->post2runLoop の順に実行
  task_next->spawn(); // D の処理が終了したら task_next タスクを実行
}
\end{verbatim}

\subsubsection{変更後の Rendering Engine} \label{sec:new-rend}

\begin{verbatim}
/* PPE Task */
Task run_loop_task {
  Task rend = rendering_task; // rendering_task を元に rend を生成
  run_loop(rend);
}

Task rendering_task {
  Task loop = run_loop_task; // run_loop_task を元に loop を生成
  run_draw(loop);
}

/* Function */
/* Start */
void init_loop() {
  Task loop = run_loop_task; // run_loop_task を元に loop を生成
  loop->spawn(); // loop タスクを実行する
}

void run_loop(Task rend) {
  main_exec {
    rend->wait_for(A); // A->rend の順に実行する
    rend->wait_for(B); // B->rend の順に実行する
  }
  rendering(rend);
}

void rendering(Task rend) {
  common_rendering{
    rend->wait_for(C); // C->rend の順に実行する
  }
  rend->spawn(); // A,B,C の処理が終了したら rend タスクを実行する
}

void run_draw(loop) {
  common_draw{
    loop->wait_for(D); //D->loop の順に実行する
  }
  loop->spawn(); // D の処理が終了したら loop タスクを実行する
}
\end{verbatim}

変更前と変更後から TASK\_DUMMY を排除していることが分かる。
TASK\_DUMMY は何もしない Task で、SPE で処理する Task と PPE 上
の関数の待ち合わせに使用していた。変更後では SPE の Task 
を PPE の Task が直接待ち合わせている。\\

この旧 Cerium から TASK\_DUMMY を排除し、処理全体を Task で書きなおした
状態の Rendering Engine を本研究における改良前の Rendering Engine とする。

\subsection{Rendering Engine の動作の確認}

Cerium のパイプラインの改良をする上で、\ref{sec:pipeline-point} 
でも述べたとおり SPE が常時稼動が重要である。そこで、改良前の Rendering 
Engine で SPE が停止している箇所が無いか調べてみた。以下にその
コードを示す。

\subsubsection{check\_spe\_idle} \label{sec:check_idle}
\begin{verbatim} 
void debug_check_spe_idle()
{
  // SPE が停止しているときに残っている実行可能な Task の数
  printf("spu_idle! : activeTaskQueue->length = %d \n"
         , activeTaskQueue->length());
  HTaskPtr task = activeTaskQueue->getFirst();  // 残っている Task の先頭を取得
  int tmp_i = 0;
  do { // 残っている Task を 順に表示していく
        printf("task_name = %s ,",ppeManager->get_task_name(task));
        printf("cpu = [%d], count = %d", task->cpu_type, tmp_i);
        tmp_i++;
     } while ((task = activeTaskQueue->getNext(task)) != 0);
      printf("\n");
}

/* 出力結果 */

spu_idle!: activeTaskQueue->length = 1 
task_name = RUN_LOOP_TASK ,cpu = [0]
spu_idle!: activeTaskQueue->length = 1 
task_name = (C) ,cpu = [0]
spu_idle!: activeTaskQueue->length = 1 
task_name = RENDERING_TASK ,cpu = [0]
spu_idle!: activeTaskQueue->length = 1 
task_name = (C) ,cpu = [0]
spu_idle!: activeTaskQueue->length = 1 
task_name = RENDERING_TASK ,cpu = [0]

\end{verbatim}

この結果から分かることは、task\_name で表示されている Task の前で SPE の処理が
止まっているということである。実行開始時の RUN\_LOOP\_TASK は、まだ SPE に仕事を
何も割り振っていない状態なので、表示されている。しかし、その後に表示されている 
Task は本来表示されてはいけないものである。(C) Task は common\_rendering 内で
作られている PPE 上で動作する Task 、RENDERING\_TASK は、run\_draw を行う
PPE 上で動作する Task である。\\

これらの結果から、Rendering Engine の動作内で、SPE の動作が停止している可能性がある
ことが分かる。そこで、(C) Task と RENDERING\_TASK を中心に Rendering Engine の動作を
確認したところ、想定とは違う依存関係を付けている箇所を発見することができた。その
依存関係を直しつつ、さらにTask を追加した 改良後の Rendering Engine を以下に示す。

\subsubsection{改良後の Rendering Engine の パイプライン}

\begin{verbatim}

/* PPE Task */
Task run_loop_task {
  Task rend = rendering_task; // rendering_task を元に rend を生成
  run_loop(rend);
}

Task rendering_task {
  Task draw = draw_task; // draw_task を元に draw を生成
  rengering(draw);
}

Task draw_task {
  Task loop = run_loop_task; // run_loop_task を元に loop を生成
  run_draw(loop);  
}

/* Function */
/* Start */
void init_loop() {
  Task loop = run_loop_task; // run_loop_task を元に loop を生成
  loop->spawn(); // loop タスクを実行する
}

void run_loop(Task rend) {
  main_exec {
    rend->wait_for(A); // A->rend の順に実行する
    rend->wait_for(B); // B->rend の順に実行する
  }
  rendering(rend);
}

void rendering(Task draw) {
  common_rendering{
    draw->wait_for(C); // C->rend の順に実行する
  }
  draw->spawn(); // A,B,C の処理が終了したら rend タスクを実行する
}

void run_draw(loop) {
  common_draw{
    D->spawn();
  }
  loop->spawn(); // loop タスクを実行する
}
\end{verbatim}

改良点は、draw\_task の追加、(D) Task と loop タスクの依存関係の変更である。
(D) Task では実際に画面上に描画する処理を行なっている。そして、描画に必要な
データの計算は main\_exec, rendering で行っている。画面の描画のために必要な
データの格納場所とそのデータを計算して格納する場所は別で用意しておき、描画が
終了した時点で切り替えるようにする(double buffering)。そうすることで、描画を
行っている間に次の描画のためのデータを別の Task で計算することができる。

改良前の Rendering Engine では、次の描画のためのデータを計算するための Task が
前の描画処理が終了するのを待っていた。そのため、(C) Task の前の RUN\_LOOP\_TASK 
で SPE  が停止してしまい、(C) Task が表示されてしまったと考えられる。

この変更によって (C) Task が \ref{sec:check_idle} の出力結果に表示されることは
なくなった。\\

また、draw\_task を追加した理由は、\ref{sec:check_idle} の出力結果から SPE の
停止している箇所を絞り込めるからである。draw\_task を追加したこと
によって \ref{sec:check_idle} の出力結果 は DRAW\_TASK を表示するようになった。
これは RENDERING\_TASK 内の処理を行なっているときに SPE が停止していることを
表している。 

\subsection{改良による性能評価}

次に、Rendering Engine のパイプラインの改良によって、どの程度性能が向上したのか
を調べる。性能評価の指標を以下に示す。

\begin{itemize}
\item mail\_time \\
  DMA 転送 の待ち時間の割合を表している。少ないほど良い。
\item busy\_ratio \\
  SPE が動作している時間の割合を表している。多いほど良い。
\item Frame Per Second (FPS) \\
  １秒間にRendering Engine 全体の処理が何回行われているかを表している。\\
  多いほど良い
\end{itemize}

\subsubsection{性能評価に用いる例題}
\begin{enumerate}

\item ball\_bound \\
オブジェクトが 1 つで使用している画像のサイズが最小の例題

\item planets \\
オブジェクトが複数あり、使用している画像のサイズも大きな例題

\end{enumerate}

\newpage

\begin{figure}[!htb]
  \begin{center}
    \begin{tabular}{cc}
      \begin{minipage}[t]{.45\hsize}
        \includegraphics[scale=0.30]{images/ball_bound.pdf}
      \end{minipage}
      \begin{minipage}[t]{.45\hsize}
        \includegraphics[scale=0.30]{images/planets.pdf}
      \end{minipage}
    \end{tabular}
    \caption{左：ball\_bound、右：planets}
    \label{fig:performance_test}
  \end{center}
\end{figure}


これらの例題を SPE を 6 個用いて処理させている。
mail\_time, busy\_ratio のデータは 6 個の SPE のデータの平均とする。

改良前と改良後の Rendering Engine の性能を以下に示す。
(\tabref{mail_time}), (\tabref{busy_ratio}), (\tabref{FPS})。\\

\begin{table}[!htb]
  \begin{center}
    \caption{mail\_time} \label{tab:mail_time}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|l|l|} \hline
         & 改良前 & 改良後 \\ \hline
        ball\_bound & 21.56\% & 9.13\% \\ \hline
        planets & 27.16\% & 13.65\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[!htb]
  \begin{center}
    \caption{busy\_ratio} \label{tab:busy_ratio}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|l|l|} \hline
         & 改良前 & 改良後 \\ \hline
        ball\_bound & 77.88\% &  90.38\% \\ \hline
        planets & 71.30\% & 85.48\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

\begin{table}[!htb]
  \begin{center}
    \caption{Frame Per Second} \label{tab:FPS}
    \hbox to\hsize{\hfil
      \begin{tabular}{|c|l|l|c|} \hline
         & 改良前 & 改良後 & 向上率\\ \hline
        ball\_bound & 5.291577 FPS & 7.012021 FPS & 32.5\% \\ \hline
        planets & 2.781246 FPS & 4.108326 FPS & 47.7\% \\ \hline
      \end{tabular}\hfil}
  \end{center}
\end{table}

以上の結果より、Rendering Engine のパイプラインの改良によって Cerium の
性能が向上したことが分かる。

\section{考察}

\begin{comment}
処理を Task に分割して行き、細分化していくことで、パイプラインによって処理速度
が向上したり、SPE が停止している箇所を見つけることが容易なるというような利点が
生まれる。しかし、現在の Cerium の仕様上、Task が扱うデータの管理、Task の依存
関係の記述はユーザが行う必要があり、Task の数が増えるとプログラミングの難易度が
格段に上がってしまうという問題がある。
\end{comment}