Mercurial > hg > Papers > 2015 > nozomi-sigos

annotate paper/cerium.tex @ 2:74e97b9a4caf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
edit
author Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
date Tue, 05 May 2015 16:55:08 +0900
parents 0127effb8fcd
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \section{Cerium}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 Cerium は、当初 Cell 用の Fine-Grain Task Manager\cite{gongo:2008a} として当研究室で開発された。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 TaskManager, SceneGraph, Rendering Engine の3つの要素から構成されており、今では、PS3 および Linux, MacOS X 上で動作する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 GPGPU の Data Parallel を含めて、同じ形式で並列プログラムを記述することができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \subsection{Cerium TaskManager}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 TaskManager は、Task と呼ばれる分割されたプログラムを管理する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 関数やサブルーチンを Task として扱い、Task 同士の依存関係を考慮しながら実行される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 Task は TaskManager を使って生成する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 Task を生成する際に、以下のような要素を設定することができる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \begin{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 \item input data
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \item output data
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 \item parameter
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 \item cpu type
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \item dependency
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \end{itemize}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 input, output, parameter は関数でいうところの引数に相当する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 cpy type は Task がどのようなの Device の組み合わせで実行されるかを示す。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 dependency は他の Task との依存関係を示している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
2
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
24 \begin{figure}[htbp]
0
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 \includegraphics[scale=0.4]{./images/createTask.pdf}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 \caption{Task Manager}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 \label{fig:createTask}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 \end{figure}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 図:\ref{fig:createTask}は Cerium が Task を生成/実行する場合のクラスの構成である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に移される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 ActiveTaskList に移された Task は依存関係が存在しないのでどのような順序で実行されても問題ない。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 Task は Scheduler に転送しやすい TaskList に変換してから cpy type に対応する Scheduler に Synchronized Queue である mail を通して転送される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 Scheduler ではパイプラインで task が処理される(図:\ref{fig:task_scheduler})。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 Task が終了すると Scheduler から TaskManager に mail を通して通知される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 その通知に従って依存関係が処理され、再び TaskManager から Scheduler に Task が転送される。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
2
Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
40 \begin{figure}[htbp]
0
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 \includegraphics[scale=0.4]{./images/scheduler.pdf}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 \caption{Task Scheduler}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \label{fig:task_scheduler}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 \end{figure}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 以下に Task を生成する例題を示す。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 表:\ref{table:TaskManager_api}は Task を生成に用いる API を示している。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 input データを2つ用意し、input データの各要素同士を乗算し、output に格納する multiply という例題である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 \lstinputlisting[caption=multiply,label=test]{./source/multiply.cc}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 \begin{table}[htpb]
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 \small
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 \begin{tabular}[htpb]{|c|l|} \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 create\_task & Task を生成する \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 set\_inData & Task への入力データのアドレスを追加 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 set\_outData & Task からのデータ出力先アドレスを追加 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 set\_param & Task のパラメータ \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 wait\_for & Task の依存関係 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 set\_cpu & Task を実行する Device の設定 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 spawn & Task を登録する \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 iterate & データ並列で実行する Task として登録する \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 \end{tabular}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 \caption{Task 生成に用いる API}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 \label{table:TaskManager_api}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 \end{table}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 CPU で実行される Task(OpenCL, CUDA でいう kernel) の記述は以下のようになる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 表:\ref{table:taskAPI}は Task 側で使用する API である。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 \lstinputlisting[caption=task,label=test]{./source/multiply_task.cc}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 \begin{table}[ht]
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 \small
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 \begin{tabular}[t]{|c|l|} \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 get\_input & 入力データのアドレスを取得 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 get\_output & データ出力先のアドレスを取得 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 get\_param & パラメータを取得 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 \end{tabular}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 \caption{ Task 側で使用する API }
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 \label{table:taskAPI}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 \end{table}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 \subsection{Cerium におけるデータ並列}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 Cerium でデータ並列による実行をサポートするために、OpenCL の API に合わせた iterate という API を用意した。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 iterate は length を引数として受け取り、Scheduler で length の値と受け取った引数の個数を次元数として Task 数を計算し、データ並列で実行する Task として生成する。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 例として、CPU 数4、一次元で10個のデータに対してデータ並列実行を行なった場合、各 CPU が担当する index は表:\ref{table:dpi}のようになる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 \begin{table}[h]
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 \begin{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 \small
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 \begin{tabular}[t]{c||c|c|c|c} \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 &CPU0& CPU1&CPU2&CPU3 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 1&0&1&2&3 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 2&4&5&6&7 \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 3&8&9& & \\ \hline
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 \end{tabular}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 \caption{Data 並列実行時の index の割り当て}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 \label{table:dpi}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 \end{center}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 \end{table}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 各 CPU が担当する index は SchedTask に格納してある。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 データ並列で実行する Task の記述は以下のようになる。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 \lstinputlisting[caption=example,label=test]{./source/multiply_task_dp.cc}
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 並列プログラムでは、並列化する Task が全部同一であるということは少なくない。
0127effb8fcd first commit
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 iterate を実装したことで、Task を生成する部分をループで回す必要はなくなり、OpenCL と同様に1つの記述で異なる index を持つ Task を Multi Core CPU 上で実行することが可能になった。