\chapter{Task Manager} \label{chapter:taskmanager}

Task Manager は、Task と呼ばれる、分割された各プログラムを管理する。
Task の単位はサブルーチンまたは関数とし、Task 同士の依存関係を考慮しながら
実行していく。

現在実装されている TaskManager の API を \tabref{taskmanager_api} に示す。

\begin{table}[htb]
  \caption{Task Manager API} \label{tab:taskmanager_api}
  \hbox to\hsize{\hfil
  \begin{tabular}{c|l} \hline \hline
    create\_task  & Task を生成する \\ \hline
    run           & 実行 Task Queue の実行 \\ \hline
    allocate      & 環境のアライメントを考慮した allocater \\ \hline
    \hline
    add\_inData   & Task への入力データのアドレスを追加 \\ \hline
    add\_outData  & Task からのデータ出力先アドレスを追加 \\ \hline
    add\_param    & Task のパラメータ (32 bits) \\ \hline
    wait\_for     & Task の依存関係の考慮 \\\hline
    set\_cpu      & Task を実行する CPU の設定 \\ \hline
    set\_post     & Task が終了したら PPE 側で実行される関数の登録 \\ \hline
    spawn         & Task を実行 Task Queue に登録する \\ \hline
  \end{tabular}\hfil}
\end{table}

以下に Task Manager を使った記述例を示す。
このプログラムは、PPE にある文字列データを、SPE が受け取って
データを改変し、PPEに戻すというプログラムである。
各 API の詳細は後述する。

\begin{verbatim}
#define STRSIZE 256
char sendStr[STRSIZE] = "Hello, World";

int
main(void)
{
    TaskManager *manager;
    HTask *task;
    int length = sizeof(char)*STRSIZE;

    // CPU_NUM: 使用する CPU の数
    manager = new TaskManager(CPUNUM);

    // TASK_RUN = TaskRun::run に対応する ID
    task = create_task(TASK_RUN);

    /**
     * タスクの入出力データの設定
     * @param[1]: address of data
     * @param[2]: size of data
     */
    task->add_inData(sendStr,length);
    task->add_outData(sendStr,length);
    
    task->spawn();
    manager->run();

    return 0;
}

TaskRun::run(void *rbuf, void *wbuf)
{
    // add_inData で指定したアドレスのデータを取得
    // recvStr = "Hello, World"
    char *recvStr = (char*)get_input(rbuf, 0);

    // fixStr にあるデータが、
    // Task 終了後、add_outData で指定した
    // sendStr に書き込まれる
    char *fixStr = (char*)get_input(wbuf, 0);

    strcpy(fixStr, recvStr);
    fixStr[0] = 'D'; // 文字列データを変換
    fixStr[3] = 'E'; // 
}

// 実行結果
before: Hello, World
after: DelEo, World

\end{verbatim}


ここからは、Task Manager の実装や API の詳細を述べる。

\section{TaskManager クラス}

TaskManager API を使用するには、まず TaskManager オブジェクトを生成する。

\begin{verbatim}
TaskManager *manager = new TaskManager(CPU_NUM);
\end{verbatim}

CPU\_NUM は、このプログラムで使用する CPU の数になる。
生成した manager からは以下の API が使用可能になる。

\begin{itemize}
  \item create\_task(int TASK\_ID);
  \item allocate(int size);
  \item run(void);
\end{itemize}

create\_task は、指定した ID に対応する Task オブジェクト
(\ref{sec:tm_task} 節) を生成する (\ref{sec:tm_task_create} 節) 。

allocate は、動作環境のアライメントを考慮したアロケートを行う。
Cell の DMA で転送するデータのアライメントは 16 byte が基本で、
ユーザはそれをできるだけ意識しないように memory allocate が行える。

create\_task で生成したタスクは、spawn() されることにより
ActiveQueue に格納される。run は、その ActiveQueue にあるタスクを
SPE に送信することを命令する関数である。
ActiveQueue が空になったら、run を抜ける。


\section{メインスレッドの実装}
メインスレッドでは、主にタスクの起動と、タスクに渡すオプションの設定を行う。
ここでは、タスクの情報オブジェクトとなる Task の定義と、
Task のオプション設定について説明する。

\subsection{Task の定義} \label{sec:tm_task}

以下は実行されるタスクの情報となるデータ構造である。
このデータはメインスレッド、CPUスレッドの両方で使用される。

\begin{verbatim}
#define MAX_PARAMS 8
#define MAX_LIST_DMA_SIZE 8

class Task {
public:
    int command;
    ListDataPtr inData;
    ListDataPtr outData;
    uint32 self;

    int param_size;
    int param[MAX_PARAMS];
};

class ListElement {
public:
    int size;
    unsigned int addr;
};

class ListData {
public:
    int length;
    int size;
    int bound[MAX_LIST_DMA_SIZE];
    ListElement element[MAX_LIST_DMA_SIZE];
};
\end{verbatim}

Task クラスは、各 CPU が実行するタスクの単位オブジェクトである。
以下は、SPE が Task を参照し実行するステップである (\figref{tm_task_struct}) 。

\begin{enumerate}
\item inListData にあるアドレス(メインメモリ空間)を参照し、
  DMA でメインメモリからデータを取得する
\item command を見て、どのタスク(関数)を実行するか決定する
\item DMA read した値をタスクに渡し、実行する
\item 演算結果の DMA 転送先を、outListDataを参照して決定する
\item DMA write する
\end{enumerate}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/tm_task_struct.pdf}
  \end{center}
  \caption{Task の構造と、SPE での参照の仕方}
  \label{fig:tm_task_struct}
\end{figure}

複数のタスクが以上の処理を行うとき、パイプラインに沿って動作する
(\ref{sec:tm_scheduler} 節) 。

Task クラスの他に、PPE でのみ管理される HTask クラスがある。

\begin{verbatim}
class HTask : public Task {
public:
    TaskQueuePtr wait_me;  // List of task waiting for me
    TaskQueuePtr wait_i;   // List of task for which I am waiting
    void (*post_func)(void *);
    void *post_arg;
    CPU_TYPE cpu_type;
};
\end{verbatim}

HTask クラスは、Task クラスを継承したもので、wait\_me、wait\_i は
タスク依存の条件に (\ref{sec:tm_depend} 節) 、
cpu\_type はタスクが実行される CPU の切り替えに (\ref{sec:tm_cpu} 節) 、
post\_func と post\_arg は、タスク終了時に PPE で実行される
関数と引数 (\ref{sec:tm_post} 節) に用いられる。

以上のことからわかるように、Task そのものにはコードの記述はなく、
SPE にロードしてあるタスクの配列から、command に沿って取得し、
実行するだけである。したがって、
予めコード部分を SPE にロードしておく必要がある。

\subsection{Task の生成} \label{sec:tm_task_create}

Task を生成するには、TaskManager の API である create\_task() を実行する。

\begin{verbatim}
HTask* TaskManager::create_task(TASK_ID);

// 記述例
HTask *task = manager->create_task(ID);
\end{verbatim}

Task ID とは、各タスクに割り振られたグローバルIDである。
通常の逐次型プログラムでは、タスクを選択して実行する場合、
その関数ポインタを指定して実行すればいい。
しかし Cell の場合、PPE と SPE 上ではアドレス空間が異なるため、
SPE 上で実行されるタスクをメインスレッドから直接アドレス指定
することはできない。
そこで、タスク毎に ID を割り振り、その ID から、
SPE 上にある Task が格納された配列を参照して実行する。
この処理が \figref{tm_task_struct} の (2) にあたる。


\subsection{Task の入出力}

タスクに渡す入力として、add\_inData と add\_param がある。

\verb+add_inData(addr, size)+ は、タスクに渡すデータのアドレスと、
そのデータのサイズを引数として入力する。
このデータは DMA 転送されるため、addr は 16 バイトアライメントが取れており、
size は 16 バイト倍数である必要がある。

\verb+add_param(param)+ は、タスクに 32bit のデータを渡す。
add\_inData で渡すには小さいデータを送るのに適している。
param は アドレスとしてではなく、値を Task オブジェクトが直接持っているので、
DMA 転送は行わない。

タスクの出力先は add\_outData を使用する。
使用方法は add\_inData と同じで、アライメント、
バイト数にも気をつける必要がある。

\subsection{Task の依存関係} \label{sec:tm_depend}

TaskManager はタスク依存を解決する機能を持っている。以下は記述例である。

\begin{verbatim}
// task2 は task1 が終了してから開始する
task2->wait_for(task1);
\end{verbatim}

このとき、task1 は ActiveQueue へ、task2 は WaitQueue へ格納される。
ActiveQueue から 各 CPU へタスクが割り振られ、
タスクが終了したらメインスレッドへタスク終了のコマンドを
発行する。メインスレッドはそれを受け取り、WaitQueue のタスクを調べ、
タスク依存を満たしたタスクを ActiveQueue に移し替える
(\figref{tm_task_depend})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/tm_task_depend.pdf}
  \end{center}
  \caption{Task の依存関係の解決}
  \label{fig:tm_task_depend}
\end{figure}

wait\_for は複数のタスクを指定でき、以下の場合は、
task3 が task1、task2 の二つのタスク終了を待つ形となる。

\begin{verbatim}
task3->wait_for(task1);
task3->wait_for(task2);
\end{verbatim}

\subsection{Task を実行させる CPU の選択} \label{sec:tm_cpu}

TaskManager の set\_cpu() により、タスクをどの CPU で
実行するか選択することが出来る。

\begin{verbatim}
// SPE 1 で実行する
task1->set_cpu(SPE_1);

// SPE のどれかで実行する 
task2->set_cpu(SPE_ANY);

// PPE で実行する
task3->set_cpu(PPE);
\end{verbatim}

これにより、メインスレッド内でもタスクを実行することが可能になるため、
環境依存によるプログラム変換はタスクの部分だけとなる。よって、
\figref{manycore_step} の段階(3) と 段階 (4) のタスク単位での
相互変換が容易になる。

\subsection{Task 終了時に実行される関数} \label{sec:tm_post}

タスクが終了した際、メインスレッドで実行される関数と、その引数を指定できる。

\begin{verbatim}
int data = 3;
task->set_post(func1, (void*)data);

void
func1(void *data)
{
    printf("func1: data = %d\n", (int)data);
}

// 実行出力結果
func1: data = 3
\end{verbatim}

set\_post により、ユーザ側でもタスクが終了したということを検知できる。

また、大量のタスクに依存関係を設定する際、一度に create\_task で生成し
wait\_for で繋げるというのは難しい。
その場合、ある一定数のタスクだけ生成しておき、set\_post を使って
終了したことを確認して、その中で新たにタスクを生成していく方が望ましい
(\figref{tm_task_post}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/tm_task_post.pdf}
  \end{center}
  \caption{Task set\_post}
  \label{fig:tm_task_post}
\end{figure}

\figref{tm_task_post} では、Func0 で task1 から task50 を生成し、
それらに set\_post(Func1) を実行する。
Func1() で、task1 から task50 までが終了したことを確認したら、
今度は task51 から task70 まで生成し、set\_post(Func2) を設定する。
このように、set\_post と wait\_for を組み合わせることで、
複雑で大量なタスクの依存関係も設定することが可能となっている。


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

各 CPU では、メインスレッドで生成された Task を受け取り、
その情報を元に、タスクを実行する。
ここでは、Task を扱うスケジューラの実装と、
タスクの本体となる部分の記述について説明する。

\subsection{スケジューラ} \label{sec:tm_scheduler}

生成された Task にしたがって、実際のタスクを実行するのがスケジューラである。
スケジューラは、メインスレッドで生成された TaskList を受け取り、
その中にある Task をパイプラインに沿って、ステージを遷移しながら
実行していく。(\figref{tm_scheduler}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.72]{images/tm_scheduler.pdf}
    \caption{スケジューラ}
    \label{fig:tm_scheduler}
  \end{center}
\end{figure}

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

\begin{verbatim}
SchedTaskBase *task1, *task2, *task3;

do {
    task3->write();
    task2->exec();
    task1->read();

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

%このパイプラインでは、実際に三つの task が同時に動作しているわけではない。

read() や write() での DMA 待ちの間に、exec() を行うことで
DMA の待ち時間を隠蔽することができる。
しかし、各ステージの終了のタイミングによっては
待ちが入ってしまう場合がある (\figref{tm_sm_pipeline_wait})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.9]{images/tm_sm_pipeline_wait.pdf}
    \caption{パイプラインの待ち時間の発生}
    \label{fig:tm_sm_pipeline_wait}
  \end{center}
\end{figure}

step 1 では全てのステージが同じタイミングで終了しているが、
step 2 では、read() 以外は早く終わり、step 3 では
exec() 以外が早く終わっている。このことにより、早くに終了したステージには
待ち時間が入ってしまい、結果として並列度が下がってしまう。

待ち時間を減らすには、早く終わったステージの余った時間を
他のタスクに割り当てたり、終了するタイミングが同じタスクが
同時に実行されるようなスケジューリングが必要となる。
現在の TaskManager には実装されていない。

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

SchedTaskBase クラスは、スケジューラによって実行されるインターフェースである。
SchedTaskBase を継承したクラスは以下のようなものがある。

\begin{itemize}
\item SchedMail \\
  メインスレッドからのメッセージ (Mailbox) を取得する
\item SchedTaskList \\
  TaskList を取得する
\item SchedTask \\
  TasKList から取得した Task を実行する
\item SchedExit \\
  SPE の実行を終了する
\item SchedNop \\
  何も行わない
\end{itemize}

各クラスからは、次に呼び出す SchedTaskBase を予測できる
(\figref{tm_sm_state}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{images/tm_sm_state.pdf}
    \caption{SchedTaskBase クラスの状態遷移}
    \label{fig:tm_sm_state}
  \end{center}
\end{figure}


\subsection{タスクの記述} \label{sec:stask_code}

ユーザがタスクを記述する場合、SchedTask を継承し、
パイプラインの exec 内で呼ばれている run() にタスクの処理を記述する。

\begin{verbatim}
// Hello.h
#include "SchedTask.h"

class Hello : public SchedTask {
public:
    // read,exec,write は SchedTask で記述されている
    int run(void *r, void *w);
};

// Hello.cc
#include <stdio.h>
#include "Hello.h"

int
Hello::run(void *rbuf, void *wbuf)
{
    int task_id = smanager->get_param(0);

    printf("[%d] Hello, World!!\n", task_id);

    return 0;
}
\end{verbatim}

\subsection{STaskManager}

上記の smanager とは、CPU 内で Task に関する処理を行う際に使用する
オブジェクトで、SchedTask を継承していれば、自動的に使えるようになる。

\begin{verbatim}
STaskManager *smanager;
\end{verbatim}

Task に関する処理の場合、メインスレッドの TaskManager と
同じようなアクセスが出来る方がユーザに理解しやすいと考え、このように実装した。

\tabref{sm_api} に STaskManager の API を示す。

\begin{table}[htb]
  \caption{STaskManager API} \label{tab:sm_api}
  \hbox to\hsize{\hfil
  \begin{tabular}{l|l} \hline \hline
    create\_task  & Task を生成する \\ \hline
    allocate      & 環境のアライメントを考慮した allocater \\ \hline
    \hline
    get\_input    & add\_inData で指定したデータを取得する \\ \hline
    get\_output   & add\_outData で指定した領域に書き込むバッファを取得する \\ \hline
    get\_param    & add\_param で指定した 32 bit データを取得する \\ \hline
    \hline
    global\_alloc & タスク間で共用する領域のアロケート \\ \hline
    global\_get   & global\_alloc した領域のアドレスを取得 \\ \hline
    global\_free  & global\_alloc した領域の free()  \\ \hline
    \hline
    dma\_store    & DMA 送信 \\ \hline
    dma\_load     & DMA 受信 \\ \hline
    dma\_wait     & DMA 転送完了を待つ \\\hline
    \hline
    mainMem\_alloc & メインメモリ上のアロケート \\ \hline
    mainMem\_get   & mainMem\_alloc した領域のアドレス(メインメモリ空間) \\ \hline
    mainMem\_wait  & mainMem\_alloc が完了するまで待つ \\ \hline
  \end{tabular}\hfil}
\end{table}

ここからは、\tabref{sm_api} に挙げた CPU スレッド上の機能を説明する。


\subsection{Input Data の取得}

\ref{sec:stask_code} 節の コードの rbuf には、
メインスレッドで \verb+add_inData()+ により指定したデータの実体が入っている
(\figref{tm_sm_rbuf}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{images/tm_sm_rbuf.pdf}
    \caption{add\_inData による rbuf の構造}
    \label{fig:tm_sm_rbuf}
  \end{center}
\end{figure}

このデータを扱う場合、直接 rbuf を見るのではなく

\begin{verbatim}
int *data = (int*)smanager->get_input(id);
\end{verbatim}

というようにして取得する。id は、add\_inData で指定した順番 (0〜N-1) になる。
この場合、\verb+smanager->get_input(1)+ とすれば、data2 が得られる。

同様に、\verb+add_param()+ で指定した値は \verb+get_param(id)+ で得られる。
ここの id も、\verb+get_input+ と同じく、設定した順番によって指定する。

\subsection{Output Data の扱い}

タスクが出力を行う場合、タスク生成時に \verb+add_outData+ を行い、
出力先のアドレスと、データサイズが指定されている。
wbuf は、rbuf 同様、指定したサイズ分のバッファである。
しかし、wbuf はこの時点ではただのバッファで、中には何も入っていない(不定)。
タスク終了時、スケジューラの write() で、
wbuf の値を \verb+add_outData+ で指定したアドレスに DMA 転送する
(\figref{tm_sm_wbuf}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{images/tm_sm_wbuf.pdf}
    \caption{add\_outData による rbuf の構造}
    \label{fig:tm_sm_wbuf}
  \end{center}
\end{figure}

wbuf から対応するバッファを取得し、add\_outData で指定した領域に
書き込むには以下の様に記述する。

\begin{verbatim}
// メインスレッド
int *data = new data[10];

task->add_outData(data, sizeof(int)*10);
task->add_param(10);

// CPU スレッド
int *out = (int*)smanager->get_output(0); // data
int size = smanager->get_param(0); // 10

for (int i = 0 ; i < size; i++) {
    out[i] = i*i;
}

// 実行結果
% ./a.out
data[0] = 0;
data[1] = 1;
data[2] = 4;
data[3] = 9;
data[4] = 16;
data[5] = 25;
data[6] = 36;
data[7] = 49;
data[8] = 64;
data[9] = 81;
\end{verbatim}

タスク終了後、out に書き込まれた値が、out に対応する
メインメモリの data に DMA 転送される。

\subsection{タスク間の共用領域} \label{sec:tm_sm_global}

各タスクは独立して動作するため、使用するメモリ領域も
他のタスクと干渉することは無い。
しかし、処理によってはタスク間で同じデータを使用する場合がある。

例えば、\ref{sec:cerium_rendering_draw_span} 節で後述するが、
ポリゴンのレンダリング時はテクスチャイメージが必要となり、
そのデータは SPE の LS 上に置かなければならない。
このとき、各タスクで同じテクスチャイメージを使うことがあり、
その場合、タスク毎に同じデータを持つよりも、LS 上に一つロードして
そのデータを各タスクが参照することが望ましい (\figref{tm_sm_global})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/tm_sm_global.pdf}
  \end{center}
  \caption{タスク間の共用領域とそのアクセス方法}
  \label{fig:tm_sm_global}
\end{figure}

共用領域をアロケートするには、\verb+global_alloc(int id, int size)+ を使う。
id は、アロケートした領域に割り振る番号で、
size がアロケートするバイト数を表す。
アロケートした領域のアドレスは \verb+global_get(int id)+ で、
\verb+global_alloc()+ 時に指定した id を渡すことで取得できる。
\verb+global_alloc()+ した領域は、TaskManager 側で解放することは無いので
ユーザが \verb+global_free(int id)+ を実行する必要がある。

共用領域は、各 SPE 上に置かれるので、違う SPE の領域を参照することはできない。
したがって、同じデータを使う可能性のタスクを
同じ SPE 上で実行させることにより、メモリ使用量も軽減できる。


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

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

dma\_load(unsigned int ls, unsigned int ea, int size, int tag)
はメインメモリ上のデータ ea から、SPE の LS 上の領域 ls に
size バイトの DMA 転送を行う。
Cell の DMA 転送ではタグを使用することになっており、
指定したタグ毎に DMA 転送完了待ちを行うことができる。
タグは Cell の仕様では 0 〜 31 を使用することが出来る。

同じ様に、\verb+dma_store(ls, ea, size, tag)+
では SPE から PPE への DMA 送信を行う。

DMA 送受信の完了を待つのが \verb+dma_wait(int tag)+ ある。

\verb+dma_load()+ や \verb+dma_store()+ は DMA 命令の発行だけだが、
\verb+dma_wait()+ では転送を待たなくてはならず、そこでタスクが一時ストップ
してしまう。これは並列度を下げてしまう要因である。
対処法としては、load や store を発行した後、すぐに wait には入らず
別の処理を行う。こうすることにより、DMA 転送の開始から終了までの
待ち時間を隠蔽することができ、並列度を下げることはなくなる。

\subsection{メインメモリ上のアロケート}

SPE 上でデータを操作しているとき、例えばリストや木構造の場合は
新しい要素が生成される場合がある。
このとき、SPE 上で生成されたデータはそのままではメインメモリには反映されない。
反映させるには、メインメモリ上の領域をアロケートし、そこに
DMA でデータを転送すればよい。

STaskManager では、メインメモリ上のアロケートを行う
\verb+mainMem_alloc(id, size)+ が実装されている。
id は領域に割り振る番号で、size バイト分アロケートする。
SPE からメインメモリへのアロケート命令は Mailbox を用いており、
\verb+mainMem_alloc()+ を実行後すぐにアロケートされるわけではない。
\verb+mainMem_wait(int id)+ で、指定した id の領域のアロケート完了の
メールが来るのを待ち、
\verb+mainMem_ger(int id)+ で、領域のアドレスが得られる。
このときのアドレスはメインメモリ空間であることに気をつける必要がある。

ちなみに、Cell には Callback 機能があり、PPE 上で関数を実行し、
その値を SPE に渡すということができる \cite{cell_abi} 。
SPE 上での printf() といったシステムコールも、Callback 機能で
実装されている。

Callback を使えば、malloc() を PPE 上で実行し、その返り値であるアドレスを
SPE に渡すという手法で、この \verb+mainMem_alloc()+ 実装できる。
しかし、Callback は一度 SPE そのものを停止させるため、並列度の観点から
\verb+mainMem_alloc()+ を実装することになった。

\subsection{CPU スレッドでのタスク生成}

各 CPU 内でも、メインスレッドと同じ様にタスクを生成することができる。

\begin{verbatim}
Task *task = smanager->create_task(TASK_ID);
\end{verbatim}

現在の実装でメインスレッドと違う点は、
依存関係が設定できないことと、実行する CPU を選択できない(現在のCPUで実行する)
、set\_post が使用できないことである。
基本的に、タスクの生成はメインスレッドで行うが、
状況によっては CPU 内でタスクを再起動したいということがある。
例えば、タスクのある地点で DMA 待ちを行う必要が出て来た場合、
その間他の処理する部分がなければ、一旦このタスクを終了し、後続のタスクを
実行させてから再びこのタスクを実行するという使い方ができる。

\section{メインスレッドと各 CPU スレッド間との同期}

メインスレッドと各 CPU 間では、Mailbox (\ref{sec:cell_mailbox}節) を用いた
32ビットメッセージの交換により同期を行っている。
通常、スレッド間で待ち合わせを行うと処理が止まってしまい、
並列度が下がってしまうがことがあるが、Mailbox は
メッセージ交換なので待ち合わせを避けることが可能である。

\figref{tm_sync} は、PPE-SPE 間のメッセージのやりとりを表している。
メインスレッドでは、各 SPE の起動と終了、そしてタスクの管理を行っている。
そして Outbound Mailbox (SPE $\rightarrow$ PPE メッセージ) を見て、
その内容に対応する処理を PPE 上で行う。
対処した結果を Inbound Mailbox (PPE $\rightarrow$ SPE メッセージ) で伝え、
受け取った SPE はタスクを再実行する。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{images/tm_sync.pdf}
    \caption{PPE, SPE threads}
    \label{fig:tm_sync}
  \end{center}
\end{figure}


\section{評価}

TaskManager は、第 \ref{chapter:cerium} 章で述べる Cerium を構築するもので、
特にユーザが触れることが一番多い機能である。

ここでは、実際に TaskManager を用いて学生に並列プログラミングを行ってもらい、
その結果と学生からの評価、さらにパイプライン実行による効果を検証し、
TaskManager の評価を述べる。

\subsection{並列ソーティングプログラム} \label{tm_sort}

今回は整数のデータをソートするプログラムを学生に記述してもらった。
SPE のメモリ領域(LS) は 256KB と少ないため、
データ全てを SPE に送った場合、領域が足りない可能性がある。
そこで、データを複数のブロックに分割して、
それらのブロック毎に SPE に送ってソートする。
ブロック内ではクイックソートを行う。
その後、ソートし終わったブロックの隣同士でソートを行う。
この作業を分割回数だけ繰り返せば全体のデータのソートが完了となる
(\figref{tm_sort}) 。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{images/tm_sort.pdf}
    \caption{Sort}
    \label{fig:tm_sort}
  \end{center}
\end{figure}

ブロックのサイズは 一回の DMA の制限である 16KB に設定した。
この手法では、各ブロックのソートを独立して行えるため、
他タスクとの待ち合わせの回数を最小限に抑えることが出来る。

このプログラムを、使用する SPE の個数を 1から6に変化させ、それぞれ
実行速度を計測した (\figref{tm_sort_calc}) 。
今回はソートする整数の数は 100 万とした。
横軸が使用した SPE の数、左縦軸が、SPE 1個の時の実行結果を 1 をしたときの
台数効果、右縦軸が実行時間(sec) である。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=1.2]{images/tm_sort_calc1m.pdf}
    \caption{Sort 実験結果}
    \label{fig:tm_sort_calc}
  \end{center}
\end{figure}

SPE 6個の台数効果が 5.1 となり、理論値にはおよばないものの、
充分な台数効果が出ていると言える。

\subsection{パイプライン実行による並列度の検証}

\figref{tm_sm_pipeline_wait} で示したように、CPU スレッドでは
read()、exec()、write() のステージをパイプラインで実行している。
この時、exec() を read() や write() の DMA 転送中に実行せず、
転送完了後に実行すればパイプライン実行による効果は現れない
(\figref{tm_sm_pipeline_wait2})。

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{images/tm_sm_pipeline_wait2.pdf}
    \caption{\figref{tm_sm_pipeline_wait} でパイプライン実行を行わない場合のCPU スレッド 処理}
    \label{fig:tm_sm_pipeline_wait2}
  \end{center}
\end{figure}

そこで、\ref{tm_sort} 節の Sort プログラムを用いて、
パイプライン実行を行った場合とそうでない場合の実行速度を比較した。
SPE の数は 1 個とし、ソートする整数は 100 万とした。
結果を \tabref{tm_sm_pipeline_wait2} に示す。

\begin{table}[htb]
  \begin{center}
    \caption{パイプライン実行の有無による速度の比較} \label{tab:tm_sm_pipeline_wait2}
    \hbox to\hsize{\hfil
      \begin{tabular}{c|c} \hline \hline
        環境 & 実行速度 (sec) \\ \hline \hline
        パイプライン実行 & 1079.885128 \\ \hline
        パイプライン非実行 & 1084.194156 \\ \hline
        \hline
      \end{tabular}
%      \begin{tabular}{c|c} \hline \hline
%        速度差 & 参考 (16KB DMA 実行時間)\\ \hline \hline
%        4.309028 sec &  0.204330 (msec) \\ \hline
%        \hline
%      \end{tabular}\hfil}
        \hfil}
  \end{center}
\end{table}

速度差は約 4.3 秒となった。
研究環境では、ソートのブロックサイズである 16KB の DMA 転送時間は
0.204330 msec を示したため、$4.309028 (sec) / 0.204330 (msec) = 21088 回$ の
DMA 転送回数を隠蔽できたことになる。


\subsection{画像の拡大縮小回転、色の変換}

変換を行う画像の読み込みは SDL \cite{sdl} を使用しており、
当初学生は生成された SDL のデータ構造 (SDL\_Surface) を
そのまま SPE に送っていた。しかし、SDL\_Surface が持つ画像データは
メインメモリ空間のアドレスで、SPE 側で参照できないという問題で
つまづく学生が多かった。

その問題を回避するためには、SDL\_Surface ではない新しい構造体を
作成する必要がある。アドレスではなく画像データそのものを持ち
変換タスクに対応するデータ構造への変換を行った。

\subsection{総評}
学生の反応で多かったのは、シーケンシャルプログラムから並列プログラムへ
変換する際に、データやコードの分割を行うのに苦労していたことである。
分割したデータ構造の設計や使用方法がシーケンシャルなプログラミングとは
違うためだと考えられる。
並列処理の経験が浅いプログラマに対しては、コードやデータの分割に際して、
何らかの雛形が必要であると言える。

また、Cell 特有の制限(DMA サイズ制限、アライメント) や、
SPE と PPE でのアドレス空間の違いなど、Cell の使用に関する問題も起きた。
そういった意見を反映し、環境使用は TaskManager 側で意識しない様に
実装している。しかし、アーキテクチャに対応した、タスクの最適化を行う場合、
ユーザ自身がターゲットアーキテクチャの使用を学ぶ必要がある。