# HG changeset patch # User gongo@gendarme.cr.ie.u-ryukyu.ac.jp # Date 1233737211 -32400 # Node ID ea6802db8b12bacce621ea4f1097338d42f5c8cb # Parent 63cbf02d3c9ea05dffc4ab9ce60206ccb725430b ３章と４章もう少し diff -r 63cbf02d3c9e -r ea6802db8b12 paper/cell.tex --- a/paper/cell.tex Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/cell.tex Wed Feb 04 17:46:51 2009 +0900 @@ -132,7 +132,7 @@ この様な計算の場合でも 128 ビット同士の演算を行うため、無駄が生じる。 -\subsection{Mailbox} +\subsection{Mailbox} \label{sec:cell_mailbox} Mailbox とは SPE の MFC 内の FIFO キューであり、PPE と SPE 間の 32 ビット メッセージの交換に用いられる。Mailbox では 3 つの振る舞いが @@ -179,7 +179,8 @@ \end{enumerate} \subsection{SPU C/C++ 言語拡張} -SPE では基本的な C 言語の機能の他に、Cell 特有の拡張が行われている。 +SPE では基本的な C 言語の機能の他に、Cell 特有の拡張が行われている +\cite{cell_cpp} 。 \tabref{cell_cpp} に主な API を記す。 \begin{table}[htb] diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/amdahl.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/amdahl.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./amdahl.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 360 252 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/amdahl.pdf Binary file paper/images/amdahl.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_arch.bb --- a/paper/images/cell_arch.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_arch.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_arch.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 505 339 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_mailbox.bb --- a/paper/images/cell_mailbox.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_mailbox.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_mailbox.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 514 342 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_ppe.bb --- a/paper/images/cell_ppe.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_ppe.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_ppe.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 370 327 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_simd.bb --- a/paper/images/cell_simd.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_simd.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_simd.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 402 261 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_spe.bb --- a/paper/images/cell_spe.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_spe.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spe.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 380 340 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_spurs_pipeline.bb --- a/paper/images/cell_spurs_pipeline.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_spurs_pipeline.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spurs_pipeline.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 533 187 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/cell_spurs_task.bb --- a/paper/images/cell_spurs_task.bb Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/images/cell_spurs_task.bb Wed Feb 04 17:46:51 2009 +0900 @@ -1,5 +1,5 @@ %%Title: ./cell_spurs_task.pdf %%Creator: ebb Version 0.5.2 (+ArtBox) %%BoundingBox: 0 0 507 229 -%%CreationDate: Tue Feb 3 18:48:04 2009 +%%CreationDate: Wed Feb 4 17:44:49 2009 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_data_split.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/manycore_data_split.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./manycore_data_split.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 587 154 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_data_split.graffle Binary file paper/images/manycore_data_split.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_data_split.pdf Binary file paper/images/manycore_data_split.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_step.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/manycore_step.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./manycore_step.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 549 335 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_step.graffle Binary file paper/images/manycore_step.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/manycore_step.pdf Binary file paper/images/manycore_step.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_scheduler.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_scheduler.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_scheduler.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 517 492 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_scheduler.graffle Binary file paper/images/tm_scheduler.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_scheduler.pdf Binary file paper/images/tm_scheduler.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_rbuf.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sm_rbuf.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_sm_rbuf.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 405 225 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_rbuf.graffle Binary file paper/images/tm_sm_rbuf.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_rbuf.pdf Binary file paper/images/tm_sm_rbuf.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_wbuf.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sm_wbuf.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_sm_wbuf.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 505 487 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_wbuf.graffle Binary file paper/images/tm_sm_wbuf.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sm_wbuf.pdf Binary file paper/images/tm_sm_wbuf.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sync.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_sync.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_sync.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 577 554 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sync.graffle Binary file paper/images/tm_sync.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_sync.pdf Binary file paper/images/tm_sync.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_post.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_task_post.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_task_post.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 335 388 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_post.graffle Binary file paper/images/tm_task_post.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_post.pdf Binary file paper/images/tm_task_post.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_struct.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/tm_task_struct.bb Wed Feb 04 17:46:51 2009 +0900 @@ -0,0 +1,5 @@ +%%Title: ./tm_task_struct.pdf +%%Creator: ebb Version 0.5.2 (+ArtBox) +%%BoundingBox: 0 0 591 364 +%%CreationDate: Wed Feb 4 17:44:49 2009 + diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_struct.graffle Binary file paper/images/tm_task_struct.graffle has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/images/tm_task_struct.pdf Binary file paper/images/tm_task_struct.pdf has changed diff -r 63cbf02d3c9e -r ea6802db8b12 paper/manycore.tex --- a/paper/manycore.tex Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/manycore.tex Wed Feb 04 17:46:51 2009 +0900 @@ -1,1 +1,153 @@ \chapter{Many Core Architecture 上でのプログラミング} \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 は、 +以上の開発行程をサポートしたフレームワークとなる。 diff -r 63cbf02d3c9e -r ea6802db8b12 paper/master_paper.bib --- a/paper/master_paper.bib Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/master_paper.bib Wed Feb 04 17:46:51 2009 +0900 @@ -5,6 +5,12 @@ year = 2008 } +@manual{cell_cpp, +author = "{International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation}", +title = "{C/C++ Language Extensions for Cell Broadband Engine Architecture Version 2.6}", +year = 2008 +} + @misc{osmesa, author = "", title = "{The Mesa 3D Graphics Library}", @@ -49,10 +55,16 @@ year = 2006 } +@manual{cell_sdk, +author = "{International Business Machines Corporation}", +title = "{Software Development Kit for Multicore Acceleration Version 3.1}", +year = 2008 +} + @manual{libspe2, author = "{International Business Machines Corporation, Sony Computer Entertainment Incorporated, Toshiba Corporation}", -title = "{SPE Runtime Management Library}", -year = 2006 +title = "{SPE Runtime Management Library Version 2.3}", +year = 2008 } @article{gongo2, diff -r 63cbf02d3c9e -r ea6802db8b12 paper/taskmanager.tex --- a/paper/taskmanager.tex Tue Feb 03 18:51:06 2009 +0900 +++ b/paper/taskmanager.tex Wed Feb 04 17:46:51 2009 +0900 @@ -1,1 +1,533 @@ \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 の定義と、 +Task のオプション設定について説明する。 + +\subsection{Task の定義} \label{sec:tm_task} + +以下は実行されるタスクの情報となるデータ構造である。 +このデータは PPE、SPE の両方で使用される。 + +\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} + +このタスクに渡す入力として、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 へ格納される。 +各 CPU は、タスクが終了したらメインスレッド(PPE) へタスク終了のコマンドを +発行する。メインスレッドはそれを受け取り、WaitQueue のタスクを調べ、 +タスク依存を満たしたタスクを ActiveQueue に移し替える。 + +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{Task (CPUスレッド)} +各 CPU では、メインスレッドで生成された Task を受け取り、 +その情報を元に、タスクを実行する。 +ここでは、Task を扱うスケジューラの実装と、 +タスクの本体となる部分の記述について説明する。 + +\subsection{スケジューラ} \label{sec:tm_scheduler} + +生成された Task にしたがって、実際のタスクを実行するのがスケジューラである。 +スケジューラは、メインスレッドで生成された TaskList を受け取り、 +その中にある Task をパイプラインに沿って実行していく (\figref{tm_scheduler}) 。 + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=0.8]{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 の待ち時間を隠蔽することを目的としている。 + +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} + +\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 +#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}{c|l} \hline \hline + create\_task & Task を生成する \\ \hline + run & 実行 Task Queue の実行 \\ \hline + allocate & 環境のアライメントを考慮した allocater \\ \hline + \hline + get\_input & add\_inData で指定したデータを取得する \\ \hline + get\_output & add\_outData で指定した領域に書き込むバッファを取得する \\ \hline + get\_param & add\_param で指定した 32 bit データを取得する \\ \hline + \end{tabular}\hfil} +\end{table} + +\subsection{Input Data の取得} + +\ref{sec:stask_code} 節の コードの rbuf には、 +メインスレッドで \verb+add_inData()+ により指定したデータの実体が入っている +(\figref{tm_sm_rbuf}) 。 + +\begin{figure}[htb] + \begin{center} + \includegraphics[scale=0.8]{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\_onData による rbuf の構造} + \label{fig:tm_sm_wbuf} + \end{center} +\end{figure} + +wbuf から対応するバッファを取得するには以下の様に記述する。 + +\begin{verbatim} +int *out = (int*)smanager->get_output(id); + +for (int i = 0 ; i < size; i++) { + out[i] = i; +} +\end{verbatim} + +タスク終了後、out に該当するメインメモリの領域が +out と同じ値になっている。 + +\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.8]{images/tm_sync.pdf} + \caption{PPE, SPE threads} + \label{fig:tm_sync} + \end{center} +\end{figure} + + +\section{学生による TaskManager を用いた開発}