\chapter{Many Core プログラミング} \label{chapter:manycore}

Many Core プログラミングは、一つのマシン内で複数のコアを扱う
プログラミングである。
本章では、Many Core プログラミングの要素や難しさを考察し、
並列プログラムの性能や信頼性を確保するための開発行程を述べる。

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

並列実行には Amdahl 則 \cite{amdahl} があり、使用する CPU を増やしても、
元のプログラムの並列化率が低ければ、
その性能を生かすことは出来ないとされている。
例えば、プログラムの8割を並列化したとしても、6 CPU で 3 倍程度の
性能向上しか得られない (\figref{amdahl}) 。

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

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

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

プログラムの中の並列度は、主に二つの形で取り出すことができる。

\begin{itemize}
\item データ並列 \\
  配列や木の中の個々の要素に対して並列に実行する (\figref{manycore_data_split})
\item パイプライン処理 \\
  複数の逐次処理の隣通しを重ねて実行する
\end{itemize}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.7]{./images/manycore_data_split.pdf}
  \end{center}
  \caption{データ並列}
  \label{fig:manycore_data_split}
\end{figure}

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

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

\subsection{Cell に置けるデータ分割}
分割されたデータは、通常メインメモリ上に置かれるが、
Cell の場合は、SPE の LS 上に置かれることになる。
メインメモリ上で計算を行う逐次型プログラムと異なり、
コピーのコストを払ってでもデータを分割し、
複数の CPU で独立に処理する必要がある。特に、DMA 中心のアクセスになる
Cell の場合は、コピーしやすいように、数 K byte 毎の配列にする方が
良い。

さらに、Cell は SPE Program コードも LS 上に置かれるため、
コードをロードする仕組みも必要になる。
256KB という SPE の少ないメモリ領域を補うため、
Cell には SPE コードのオーバーレイ機能 \cite{cell_sdk} がある。
オーバーレイとは、メモリ上の実行プログラムの一部を他のコードと
置き換えながら実行する手法だが、
コードを置き換える時に SPE 自体が止まってしまうので、好ましくない。
そのため、明示的に DMA でコードをロードする必要がある。

\section{同期}
ここで言う同期とは、複数の CPU がデータの待ち合わせ、または、
整合性を維持するために、他の CPU との待ち合わせを行うことである。

Many Core では、待ち合わせを行うと並列度が下がってしまうので、
同期自体を減らす必要がある。
そのためには、各 CPU が独立に (ロック無し) でデータにアクセス
できる様にデータを分割すれば良い。
Cell の場合は SPE の LS 上 にコピーすることになる。
しかし、SPE はメインメモリからデータを取得する必要があるので、
取得の際には同期を取る必要がある。
Cell の場合は PPE と SPE 間の同期に関しては、
\ref{sec:cell_mailbox} 節で述べた Mailbox を使用する。
メッセージ交換なので、待ち合わせを避けることが可能である。

\section{デバッグ}
並列プログラムの特徴として、デバッグが難しいことも挙げられる。
実行が非決定的 (同じ状態で実行しても結果が異なる) な場合があり、
バグの状態を再現することが難しい。
また、個々の Core 上のデータを調べる必要があり、
デバッガが複数の Core を取り扱えることが必須である。
Cell の場合、動作している複数 の SPE の一つに対して
gdb で breakpoint を掛ければ、PPE や他の SPE も同時にストップするが、
それら全ての CPU を手動で管理するのは厳しい。
また、PPE と SPE ではメモリ空間が違うため、
SPE から直接 PPE のデータを見ることができない。


\section{並列プログラムの開発行程} \label{sec:manycore_step}
並列プログラミングでは、以下の段階において、
それぞれ実装とテストを行う (\figref{manycore_step}) 。

\begin{enumerate}
\item C によるシーケンシャルな実装 \label{step1}
\item 並列実行を考慮したデータ構造を持つ実装 \label{step2}
\item コードを分割し、シーケンシャルに実行する実装 \label{step3}
\item 分割したコードを並列実行する実装 \label{step4}
\end{enumerate}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[scale=0.8]{./images/manycore_step.pdf}
  \end{center}
  \caption{並列プログラムの開発行程}
  \label{fig:manycore_step}
\end{figure}

段階 \ref{step1} の実装では、プログラムのアルゴリズムの信頼性を確認するために
用いる。

段階 \ref{step2} の実装では、コードを分割した際、そのコードが使用できるような
データ構造への変換が必要になり、段階 \ref{step1} と同じ結果が
得られるかどうかを検証する。

段階 \ref{step3} の実装では、並列実行を意識したコードの分割を行う。
この段階まではアーキテクチャに依存しないので、
ターゲットが開発途中の段階でも記述することが可能である。
また、実行が決定的 (入力に対して出力が一意に決まる) であるため、
テストは容易である。
シーケンシャルな実装であるため、デバッグも二分法により容易に行うことが出来る。

段階 \ref{step4} の実装では、段階 \ref{step3} で分割したコードを
実際に並列に動かす。段階 \ref{step3} までが動いていれば
問題なくそのまま動作すると期待される。問題が発生した場合、
その原因と思われる部分を見つけ、一度段階 \ref{step3} に戻した後、
前後のコードと合わせて
入出力データのチェックなどのテストをしていくことが必要となる。
これにより、問題がプログラムのアルゴリズムなのか、
並列実行したことによるデータの整合性の問題(同期、データ送受信のずれなど)か
などを判定することができる。

並列プログラミングでは、以上の段階毎に
信頼性を確かめながら開発を行っていくことになる。

第 \ref{chapter:taskmanager} 章から説明する TaskManager は、
以上の開発行程をサポートしたフレームワークとなる。