Mercurial > hg > Papers > 2015 > yuhi-master
annotate paper/chapter2.tex @ 79:7990a2abbf05 default tip
add file
| author | Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 02 Mar 2015 11:21:40 +0900 |
| parents | 48db1f674a83 |
| children |
| rev | line source |
|---|---|
| 55 | 1 \chapter{並列プログラミング\\フレームワーク Cerium} |
| 4 | 2 Cerium は、当初 Cell 用の Fine-Grain TaskManager として当研究室で開発された。 |
| 3 本章では Cerium の実装について説明する。 | |
| 4 | |
| 5 \section{Cerium の概要} | |
| 54 | 6 Cerium は当初 Cell 用であったが、現在では Linux、 MacOS X上で動作する。 |
| 4 | 7 GPGPU の Data Parallel を含めて同じ形式で記述できる。 |
| 8 | |
| 9 CeriumはTaskManager、 SceneGraph、Rendering Engine の3つの要素から構成される。 | |
| 32 | 10 本研究では Cerium の TaskManager を汎用計算フレームワークとして改良を行った。 |
| 11 | |
| 4 | 12 \section{Cerium TaskManager} |
| 13 Cerium TaskManager では、処理の単位を Task としてプログラムを記述していく。 | |
| 14 関数やサブルーチンを Task として扱い、 Task 間の依存関係を考慮しながら実行される。 | |
| 15 | |
| 32 | 16 ソースコード:\ref{src:createTask}に Host 側で Task を生成する例題を示す。 |
| 4 | 17 input data を2つ用意し、 input data の各要素同士を乗算し、 |
| 18 output に格納する multiply という例題である。 | |
| 19 | |
| 20 \begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] | |
| 21 void | |
| 22 multiply_init(TaskManager *manager, float *i_data1, float *i_data2, float *o_data) { | |
| 23 | |
| 24 // create task | |
| 25 HTask* multiply = manager->create_task(MULTIPLY_TASK); | |
| 26 multiply->set_cpu(spe_cpu); | |
| 27 | |
| 28 // set indata | |
| 29 multiply->set_inData(0, i_data1, sizeof(float) * length); | |
| 30 multiply->set_inData(1, i_data2, sizeof(float) * length); | |
| 31 | |
| 32 // set outdata | |
| 33 multiply->set_outData(0, o_data, sizeof(float) * length); | |
| 34 | |
| 35 // set parameter | |
| 36 multiply−>set_param(0,(long)length); | |
| 37 | |
| 38 // set device | |
| 39 multiply->set_cpu(SPE_ANY); | |
| 40 | |
| 41 // spawn task | |
| 42 multiply−>spawn(); | |
| 43 } | |
| 44 \end{lstlisting} | |
| 45 | |
| 46 表:\ref{table:task_create_api}は Task 生成時に用いる API の一覧である。 | |
| 32 | 47 create された Task は Input Data や 依存関係を設定し、 |
| 48 spawn することで TaskManager に登録される。 | |
| 0 | 49 |
| 4 | 50 \begin{tiny} |
| 51 \begin{table}[htpb] | |
| 52 \begin{center} | |
| 53 \small | |
| 54 \begin{tabular}[htpb]{c|l} | |
| 55 \hline | |
| 56 create\_task & Task を生成する \\ | |
| 57 \hline | |
| 58 set\_inData & Task への入力データのアドレスを追加 \\ | |
| 59 \hline | |
| 60 set\_outData & Task からの出力データのアドレスを追加 \\ | |
| 61 \hline | |
| 62 set\_param & Task へ値を一つ渡す。ここではlengthを渡している \\ | |
| 63 \hline | |
| 64 set\_cpu & Task を実行する Device の設定 \\ | |
| 65 \hline | |
| 66 spawn & 生成した Task を ActiveTaskList に登録する \\ | |
| 67 \hline | |
| 68 \end{tabular} | |
| 69 \caption{Task 生成おける API} | |
| 70 \label{table:task_create_api} | |
| 71 \end{center} | |
| 72 \end{table} | |
| 73 \end{tiny} | |
| 0 | 74 |
| 32 | 75 次に、ソースコード:\ref{src:task} に Device 側で実行される Task (OpenCL、CUDA でいう kernel) の記述を示す。 |
| 0 | 76 |
| 4 | 77 \begin{lstlisting}[frame=lrbt,label=src:task,caption=Task,numbers=left] |
| 78 static int | |
| 79 run(SchedTask *s) { | |
| 80 // get input | |
| 81 float *i_data1 = (float*)s->get_input(0); | |
| 82 float *i_data2 = (float*)s->get_input(1); | |
| 83 // get output | |
| 84 float *o_data = (float*)s->get_output(0); | |
| 85 // get parameter | |
| 86 long length = (long)s->get_param(0); | |
| 87 | |
| 88 // calculate | |
| 89 for (int i=0; i<length; i++) { | |
| 90 o_data[i] = i_data1[i] * i_data2[i]; | |
| 91 } | |
| 92 return 0; | |
| 93 } | |
| 94 \end{lstlisting} | |
| 95 | |
| 96 表:\ref{table:task_api}は Task 側で使用する API である。 | |
| 32 | 97 Host 側で設定した Input Data やパラメタを取得することができる。 |
| 4 | 98 |
| 99 \begin{tiny} | |
| 100 \begin{table}[htpb] | |
| 101 \begin{center} | |
| 102 \small | |
| 103 \begin{tabular}[htpb]{c|l} | |
| 104 \hline | |
| 105 get\_input & 入力データのアドレスを取得 \\ | |
| 106 \hline | |
| 7 | 107 set\_output & 出力先データのアドレスを取得 \\ |
| 4 | 108 \hline |
| 7 | 109 set\_param & パラメータを取得 \\ |
| 4 | 110 \hline |
| 111 \end{tabular} | |
| 112 \caption{Task 側で使用する API} | |
| 113 \label{table:task_api} | |
| 114 \end{center} | |
| 115 \end{table} | |
| 116 \end{tiny} | |
| 32 | 117 |
| 118 Task を生成する際に設定できる要素は以下の通りとなる。 | |
| 119 | |
| 120 \begin{itemize} | |
| 121 \item Input Data | |
| 122 \item Output Data | |
| 123 \item Parameter | |
| 124 \item CpuType | |
| 125 \item Dependency | |
| 126 \end{itemize} | |
| 127 | |
| 128 Input/Output Data, Parameter は関数で言うところの引数に相当する。 | |
| 129 CpuType は Task が動作する Device を示し、 Dependency は他の Task との依存関係を表す。 | |
| 130 | |
| 131 \section{Cerium における Task} | |
| 132 図:\ref{fig:taskmanager}は Cerium が Task を生成/実行する場合のクラスの構成図である。 | |
| 133 TaskManager で依存関係が解消され、実行可能になった Task は ActiveTaskList に移される。 | |
| 134 ActiveTaskList に移された Task は依存関係が存在しないのでどのような順番で実行されても良い。 | |
| 135 Task は転送を行いやすい TaskList に変換され、CpuType に対応した Scheduler に転送される。 | |
| 136 なお、転送はSynchronozed Queue である mail を通して行われる。 | |
| 137 | |
| 138 \begin{figure}[htpb] | |
| 139 \begin{center} | |
| 140 \includegraphics[scale=0.7]{./images/createTask.pdf} | |
| 141 \end{center} | |
| 142 \caption{Task Manager} | |
| 143 \label{fig:taskmanager} | |
| 144 \end{figure} | |
| 145 | |
| 146 \section{Task の Scheduling} | |
| 147 GPU や Cell のような Shared Memory でない環境でのプログラミングを行う場合、 | |
| 148 Task の入出力となるデータを転送し、転送が終わってから Task を起動しなければならない。 | |
| 149 転送処理がボトルネックとなり、並列度が低下してしまう。 | |
| 150 そのため、Cerium はパイプライン実行をサポートしている。 | |
| 151 | |
| 152 Scheduler に転送された Task はパイプラインで処理される(図:\ref{fig:scheduler})。 | |
| 153 Task が全て終了すると Scheduler から TaskManager に mail を通して通知される。 | |
| 154 通知に従い依存関係を解決した Task が再び TaskManager から Scheduler に転送される。 | |
| 155 | |
| 156 \begin{figure}[htpb] | |
| 157 \begin{center} | |
| 158 \includegraphics[scale=0.7]{./images/scheduler.pdf} | |
| 159 \end{center} | |
| 160 \caption{Scheduler} | |
| 161 \label{fig:scheduler} | |
| 162 \end{figure} | |
|
48
8d6a0f047d5a
create task in sort bench example
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
163 |
|
49
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
164 Cerium の Task は SchedTask と呼ばれるデータ構造で表現されている。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
165 SchedTask は input/output data の length や合計 size を持っており、 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
166 これらのパラメタから自分の data が格納されているアドレスを算出し、read/write を実行する。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
167 SchedTask を利用することで容易にパイプラインを構築できる。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
168 Task をパイプライニングにより Scheduling している部分をソースコード:\ref{src:pipeline_multicore}に示す。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
169 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
170 \begin{lstlisting}[frame=lrbt,label=src:pipeline_multicore,caption=Task,numbers=left] |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
171 void |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
172 Scheduler::run(SchedTaskBase* task1) |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
173 { |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
174 // Pipeline Stage |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
175 SchedTaskBase* task2 = new SchedNop(); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
176 SchedTaskBase* task3 = new SchedNop(); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
177 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
178 // main loop |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
179 do { |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
180 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
181 task1->read(); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
182 task2->exec(); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
183 task3->write(); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
184 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
185 delete task3; |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
186 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
187 task3 = task2; |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
188 task2 = task1; |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
189 task1 = task1->next(this, 0); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
190 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
191 } while (task1); |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
192 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
193 delete task3; |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
194 delete task2; |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
195 } |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
196 \end{lstlisting} |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
197 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
198 引数として受け取っている task1 は Task のリストである。このリストがなくなるまでパイプライン実行のループを回す。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
199 task1 が read、task2 が exec、task3 が write を担当している。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
200 つまり task3 には read と exec が終わった Task が来るため、write が終わったら delete して良い。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
201 各 Task はそれぞれの処理を行い、task2 は task3 に、task1 は task2 に自分の Task を渡していく。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
202 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
203 このメインループを回すことで Cerium の Scheduler はパイプラインによる実行を可能にしている。 |
|
c7678996940c
add pipeline in multicore
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents:
48
diff
changeset
|
204 |