\section{ Many Core 上のプログラムの特徴}

従来の逐次型のプログラムでは、Many Coreの性能を十分に引き出す
ことは出来ない。ここでは、その性能を活かすMany Core プログラム
の特徴について考察する。ここでは、{\tt 定常的な並列度の必要性、
データ並列、パイプライン実行、
プログラムとデータの分割、
同期の問題、
マルチスレッド、
デバッグ}に関して考察を行う。

\subsection{ 定常的な並列度の必要性}

並列実行にはAmdahl則\cite{java-conncurrecy}があり、プログラムの並列化率が
低ければ、その性能を活かすことは出来ない。0.8 程度の並列化
率では、6CPUでも3倍程度の性能向上しか得られない(\ref{amdahl})。

\begin{figure}[htb]
\begin{center}
\includegraphics[width=6cm]{fig/amdahl.eps}
\caption{amdahl}
\end{center}
\label{amdahl}
\end{figure}


高い並列
度ではなくとも、恒常的に並列度を維持する必要がある。このため、

{\small
\begin{verbatim}
   逐次型のプログラムの一部を並列化する

\end{verbatim}
}

という手法では不十分である。LSIなどのハードウェア場合は演算の
対象がもともと多量の演算とデータパスを持つので並列計算の効果を
定常的に得られることが多いが、C等で記述されたプログラムでは、
for 文や配列のアクセスなどに並列性が隠されてしまい、それを引き出す
ことが難しい。

プログラムの中の並列度は、主に二つの形で取り出すことが出来る。
一つは、配列や木の中の個々の要素に対して並列に実行する

{\small
\begin{verbatim}
    データ並列

\end{verbatim}
}

である。もう一つは、複数の逐次処理の隣同士を重ねて実行する

{\small
\begin{verbatim}
    パイプライン処理

\end{verbatim}
}

である。この二つを同時に用いることで定常的な並列度を維持することが
可能となることがある。パイプライン処理は、プログラム中で階層的に
使われることが多い。

\subsection{ プログラムとデータの分割}

データ並列とパイプライン処理を可能にするためには、プログラムと
データの適切な分割を行う必要がある。for文、あるいは、木をだとって
処理する個々のステートメントがプログラムの分割の対象となる。
データは自明に分割できるわけではなく、分割できるデータ構造を採用し、
必要ならばコピーを行う。

分割されたデータは、メモリ上に置かれるが、Cellの場合はSPUのローカル
メモリ上に置かれることになる。共有メモリベースの場合でもキャッシュを
考慮した配置をする必要がある。具体的には、データのアライメントをそろ
える必要がある。メインメモリ上で計算を行う逐次型プログラムと異なり、
コピーのコストを払ってでもデータを分割し、複数のCPUで独立に処理する
必要がある。特に、DMA中心のアクセスになるCellの場合は、
コピーしやすいように、数Kbyte毎の配列にする方が良い。

Cellの場合はさらにコードもローカルメモリ上に置かれるために、
コードをロードする仕組みも必要になる。

\subsection{ 同期の問題}

ここで言う同期は、複数のCPUがデータの待ち合わせ、または、整合性を
維持するために、他のCPUとの待ち合わせを行うことである。従来の
マルチCPUでは、並列度が低いために同期は希であり、キャッシュ上の
Spin lock を用いることが多かった。これは、メモリの特定の場所を
test and set 等の特殊な命令で繰り返しアクセスして待ち合わせる手法
である。Unix OSのkernel、POSIX Thread など同期機構の実装に使われている。

Many Core では、待ち合わせを行うと並列度が下がってしまうので、
同期自体を減らす必要がある。そのためには、各CPUが独立に(Lock無しに)
データにアクセス出来るようにデータを分割すれば良い。Cell では、
SPUがローカルメモリを持っているので、そちらにコピーすることになる。
しかし、SPUはメインメモリからデータを取得する必要があるので、その
取得の際には同期を取る必要がある。
Cellでは、SPUとPPU間の同期にはMail box というFIFOメッセージ
キューが用意されていて、readch,writech という命令でSPUから
アクセスする。Spin lock と違って、メッセージ交換なので待ち合わせを
避けることが可能である。

共有メモリベースのシステムの場合でも、同じ場所をアクセスする場合は
キャッシュの競合が生じるので、コピーなどを用いて領域の分割を
行う必要がある。Thread local などを用いる場合もある。

複数のCPUが出力する結果を一つのキューに挿入するようなことをすると、
挿入時に必ず同期が必要になるので同期のコストが高い。

\subsection{ マルチスレッド}

従来の共有メモリ型のマルチCPUでは、POSIX Thread を用いて並列実行
を実現することが多い。特にHyper Thread では、複数の命令ストリーム
を使って、メモリアクセス時等のの命令実行パイプラインのストールを
スレッドを切替えて隠すことが出来る。しかし、Many Core の場合に、
個々のCoreに複数のThreadを割り当てるとワーキングセット(Threadが
使用するデータ)の大きさが大きくなりキャッシュやローカルメモリに
入らなくなる場合がある。

スレッド(Hyper Thread)は本来、I/O待ちやメインメモリアクセス等に対して
有効であり、ほとんどのデータがキャッシュやローカルメモリにあると
考えられるMany Coreには向いていない。個々のタスクを実行するCPU
上で複数のスレッドを使用するメリットはほとんどないと思われる。
一方で、個々のCPUは細分化されたタスクを十分に持っていなければ
恒常的な並列度を維持できない。

一方で、同期機構で待ち合わせを行う場合に、Spin lockを避けるとすれば、
条件付変数などのスレッドのタスクの待ち合わせ機構が必要となる。

Many Core の台数にも寄るが、実行するタスクの管理を行うマネージャー
を複数スレッドで構成し、そのうちの一つが、ポーリングベースで
複数のCoreに対する待ち合わせを行うようにするのが良いと思われる。
Cellでは、SPURS\cite{spurs}という仕組みが提案されている。

\subsection{ デバッグ}

複数のCoreを走らせた状態でのデバッグは難しい。並列プログラムの
特徴として、実行が非決定的(同じ状態で実行しても結果が異なる)こと
があり、バグの状態を再現することが難しいことがある。また、個々の
Core上のデータを調べる必要があり、デバッガが複数のCoreを取り扱える
ことが必須である。