|
20
|
1 <!DOCTYPE html>
|
|
|
2 <html>
|
|
|
3 <head>
|
|
|
4 <meta http-equiv="content-type" content="text/html;charset=utf-8">
|
|
|
5 <title>Gears OS における並列処理</title>
|
|
|
6
|
|
|
7 <meta name="generator" content="Slide Show (S9) v2.5.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16]">
|
|
|
8 <meta name="author" content="Takui Higashionna" >
|
|
|
9
|
|
|
10 <!-- style sheet links -->
|
|
|
11 <link rel="stylesheet" href="s6/themes/projection.css" media="screen,projection">
|
|
|
12 <link rel="stylesheet" href="s6/themes/screen.css" media="screen">
|
|
|
13 <link rel="stylesheet" href="s6/themes/print.css" media="print">
|
|
|
14 <link rel="stylesheet" href="s6/themes/blank.css" media="screen,projection">
|
|
|
15
|
|
|
16 <!-- JS -->
|
|
|
17 <script src="s6/js/jquery-1.11.3.min.js"></script>
|
|
|
18 <script src="s6/js/jquery.slideshow.js"></script>
|
|
|
19 <script src="s6/js/jquery.slideshow.counter.js"></script>
|
|
|
20 <script src="s6/js/jquery.slideshow.controls.js"></script>
|
|
|
21 <script src="s6/js/jquery.slideshow.footer.js"></script>
|
|
|
22 <script src="s6/js/jquery.slideshow.autoplay.js"></script>
|
|
|
23
|
|
|
24 <!-- prettify -->
|
|
|
25 <link rel="stylesheet" href="scripts/prettify.css">
|
|
|
26 <script src="scripts/prettify.js"></script>
|
|
|
27
|
|
|
28 <script>
|
|
|
29 $(document).ready( function() {
|
|
|
30 Slideshow.init();
|
|
|
31
|
|
|
32 $('code').each(function(_, el) {
|
|
|
33 if (!el.classList.contains('noprettyprint')) {
|
|
|
34 el.classList.add('prettyprint');
|
|
|
35 el.style.display = 'block';
|
|
|
36 }
|
|
|
37 });
|
|
|
38 prettyPrint();
|
|
|
39 } );
|
|
|
40
|
|
|
41
|
|
|
42 </script>
|
|
|
43
|
|
|
44 <!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
|
|
|
45 <!--[if IE]>
|
|
|
46 <script src="s6/js/jquery.microsoft.js"></script>
|
|
|
47 <![endif]-->
|
|
|
48
|
|
|
49
|
|
|
50
|
|
|
51 </head>
|
|
|
52 <body>
|
|
|
53
|
|
|
54 <div class="layout">
|
|
|
55 <div id="header"></div>
|
|
|
56 <div id="footer">
|
|
|
57 <div align="right">
|
|
|
58 <img src="s6/images/logo.svg" width="200px">
|
|
|
59 </div>
|
|
|
60 </div>
|
|
|
61 </div>
|
|
|
62
|
|
|
63 <div class="presentation">
|
|
|
64
|
|
|
65 <div class='slide cover'>
|
|
|
66 <table width="90%" height="90%" border="0" align="center">
|
|
|
67 <tr>
|
|
|
68 <td>
|
|
|
69 <div align="center">
|
|
|
70 <h1><font color="#808db5">Gears OS における並列処理</font></h1>
|
|
|
71 </div>
|
|
|
72 </td>
|
|
|
73 </tr>
|
|
|
74 <tr>
|
|
|
75 <td>
|
|
|
76 <div align="left">
|
|
|
77 Takui Higashionna
|
|
|
78
|
|
|
79 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:100%;height:0.2em;">
|
|
|
80 </div>
|
|
|
81 </td>
|
|
|
82 </tr>
|
|
|
83 </table>
|
|
|
84 </div>
|
|
|
85
|
|
|
86 <div class='slide '>
|
|
|
87 <!-- === begin markdown block ===
|
|
|
88
|
|
|
89 generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16]
|
|
|
90 on 2017-05-15 18:13:55 +0900 with Markdown engine kramdown (1.13.2)
|
|
|
91 using options {}
|
|
|
92 -->
|
|
|
93
|
|
|
94 <!-- _S9SLIDE_ -->
|
|
|
95 <h1 id="section">メタ計算を使った並列処理</h1>
|
|
|
96
|
|
|
97 <ul>
|
|
|
98 <li>並列処理のプラグラミングは、処理のパイプライン</li>
|
|
|
99 <li>当研究室ではメタ計算をサポートする言語として Continuation based C (CbC) を開発している</li>
|
|
|
100 <li>CbC は Code Gear と Data Gear という処理とデータの単位を持っており、メタ計算を行うための Meta Code Gear、Meta Data Gear がある。</li>
|
|
|
101 <li>Gears OS は CbC を用いて記述されている。</li>
|
|
|
102 </ul>
|
|
|
103
|
|
|
104
|
|
|
105 </div>
|
|
|
106 <div class='slide '>
|
|
|
107 <!-- _S9SLIDE_ -->
|
|
|
108 <h1 id="code-gear-data-gear">Code Gear Data Gear</h1>
|
|
|
109
|
|
|
110 <ul>
|
|
|
111 <li>Code Gear Data Gear とはプラグラムを分解し、処理の部分を Code Gear int や文字列などの部分を Data Gear という単位で分ける。</li>
|
|
|
112 <li>Code Gearの処理はその処理に必要な Data Gear が揃ってから行われる。</li>
|
|
|
113 <li>Code Gear の処理の移行は goto を使って行い、この移行の仕方を継続という。</li>
|
|
|
114 <li>goto による移行は戻り値を持たないため、スタックを積む必要のない、スタックに積まない継続を軽量継続と呼ぶ。</li>
|
|
|
115 </ul>
|
|
|
116
|
|
|
117
|
|
|
118 </div>
|
|
|
119 <div class='slide '>
|
|
|
120 <!-- _S9SLIDE_ -->
|
|
|
121 <h1 id="code-gear-data-gear-">Code Gear Data Gear を用いた計算</h1>
|
|
|
122
|
|
|
123 <ul>
|
|
|
124 <li>Code Gear の処理の実行は、接続された Data Gear が揃ってから実行される。</li>
|
|
|
125 <li>Data Gear には Output Data Gear と Input Data Gear があり、Code Gear は接続された Data Gear 以外を変更することはない。</li>
|
|
|
126 <li>そのため通常の計算ではポインタを気にすることはなく、ポインタ演算はメタ計算部分で行われる。</li>
|
|
|
127 <li>Code Gear の処理は tail call のみで遷移を行う関数型プログラミングである。</li>
|
|
|
128 <li>agda に変換することができ、プログラムの正しさを証明できる。</li>
|
|
|
129 </ul>
|
|
|
130
|
|
|
131
|
|
|
132 </div>
|
|
|
133 <div class='slide '>
|
|
|
134 <!-- _S9SLIDE_ -->
|
|
|
135 <h1 id="section-1">メタ計算</h1>
|
|
|
136
|
|
|
137 <ul>
|
|
|
138 <li>メタ計算は通常の計算のための計算である</li>
|
|
|
139 <li>並列処理の依存関係の解決、GPUなどのアーキテクチャ実行のための処理を行う。</li>
|
|
|
140 <li>Gears OSではメタ計算は Meta Code Gear、Meta Data Gear で表現される。</li>
|
|
|
141 </ul>
|
|
|
142
|
|
|
143
|
|
|
144 </div>
|
|
|
145 <div class='slide '>
|
|
|
146 <!-- _S9SLIDE_ -->
|
|
|
147 <h1 id="gears-os">Gears OS</h1>
|
|
|
148
|
|
|
149 <ul>
|
|
|
150 <li>Gears OS は Code Gear、Data Gearの単位を用いて開発されており、CbCで記述される。</li>
|
|
|
151 <li>Meta Code Gear は 通常の Code Gear の直後に遷移され、メタ計算を実行する。</li>
|
|
|
152 <li>Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。</li>
|
|
|
153 </ul>
|
|
|
154
|
|
|
155
|
|
|
156 </div>
|
|
|
157 <div class='slide '>
|
|
|
158 <!-- _S9SLIDE_ -->
|
|
|
159 <h1 id="gears-os-">Gears OS の並列性</h1>
|
|
|
160
|
|
|
161 <ul>
|
|
|
162 <li>Code Gear が処理するのに必要なinput Data Gear と処理実行後に出力される Input Data Gear の組を Task と呼ぶ。</li>
|
|
|
163 <li>Code Gear は Task 以外とは依存関係がない</li>
|
|
|
164 <li>依存関係が明確化されている Code Gear Data Gear で記述することで、並列化し易い。</li>
|
|
|
165 </ul>
|
|
|
166
|
|
|
167 <div style="text-align: center;">
|
|
|
168 <img src="./fig/codeGear_dataGear.svg" alt="message" width="800" />
|
|
|
169 </div>
|
|
|
170
|
|
|
171
|
|
|
172 </div>
|
|
|
173 <div class='slide '>
|
|
|
174 <!-- _S9SLIDE_ -->
|
|
|
175 <h1 id="gears-os--1">Gears OS の柔軟性</h1>
|
|
|
176
|
|
|
177 <ul>
|
|
|
178 <li>Gears OS はメタ計算を使用することで
|
|
|
179 – データ拡張や機能の追加
|
|
|
180 – GPU 等の様々なアーキテクチャでも同じプログラムの動作</li>
|
|
|
181 <li>メタ計算は通常の処理と階層を分けて処理を行う。</li>
|
|
|
182 </ul>
|
|
|
183
|
|
|
184 <div style="text-align: center;">
|
|
|
185 <img src="./fig/meta_gear.svg" alt="message" width="800" />
|
|
|
186 </div>
|
|
|
187
|
|
|
188
|
|
|
189 </div>
|
|
|
190 <div class='slide '>
|
|
|
191 <!-- _S9SLIDE_ -->
|
|
|
192 <h1 id="gears-os--2">Gears OS の構成</h1>
|
|
|
193
|
|
|
194 <ul>
|
|
|
195 <li>Gears OS は以下の要素で構成される。</li>
|
|
|
196 </ul>
|
|
|
197
|
|
|
198
|
|
|
199 </div>
|
|
|
200 <div class='slide '>
|
|
|
201 <!-- _S9SLIDE_ -->
|
|
|
202 <h1 id="context">Context</h1>
|
|
|
203
|
|
|
204 <ul>
|
|
|
205 <li>Gears OS は Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear を持つ。</li>
|
|
|
206 <li>Gears OS は必要な Code Gear、Data Gear に参照したい場合、この Context を通す必要がある。</li>
|
|
|
207 <li>Context は 接続に必要な Code/Data Gear のリスト、 Data Gear を確保するためのメモリ空間、実行する Code Gear、Code Gear の実行に必要な Input Data Gear のカウンタ等をもっている。</li>
|
|
|
208 </ul>
|
|
|
209
|
|
|
210
|
|
|
211 </div>
|
|
|
212 <div class='slide '>
|
|
|
213 <!-- _S9SLIDE_ -->
|
|
|
214 <h1 id="taskmanager">TaskManager</h1>
|
|
|
215 <ul>
|
|
|
216 <li>TaskManager は Task、Worker の生成</li>
|
|
|
217 <li>Worker に生成した Task の送信</li>
|
|
|
218 <li>生成した Worker の終了処理等を行う</li>
|
|
|
219 </ul>
|
|
|
220
|
|
|
221
|
|
|
222 </div>
|
|
|
223 <div class='slide '>
|
|
|
224 <!-- _S9SLIDE_ -->
|
|
|
225 <h1 id="worker">Worker</h1>
|
|
|
226 <ul>
|
|
|
227 <li>Worker は thread と実行する Task が入っている Queue を持っている。</li>
|
|
|
228 <li>Worker は TaskManager から送信された Task を Queue から取り出し、Code Gear を実行する。</li>
|
|
|
229 <li>Task は Context なので、Code Gear の実行に必要な Input Data Gear はその Context から参照される。</li>
|
|
|
230 <li>Code Gear を実行した後は出力される Output Data Gear から依存関係を解決する。</li>
|
|
|
231 </ul>
|
|
|
232
|
|
|
233
|
|
|
234 </div>
|
|
|
235 <div class='slide '>
|
|
|
236 <!-- _S9SLIDE_ -->
|
|
|
237 <h1 id="gpgpu">GPGPU</h1>
|
|
|
238 <ul>
|
|
|
239 <li>もともとは画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術のこと。</li>
|
|
|
240 <li>GPUにはCPUに比べ多数のコアがあり、並列に処理することによってCPUよりも高速に処理を行うことができる。</li>
|
|
|
241 <li>CPUに比べ複雑な計算ができない、GPU単体に直接命令を書き込むこともできないなど、問題点も存在する。</li>
|
|
|
242 </ul>
|
|
|
243
|
|
|
244
|
|
|
245 </div>
|
|
|
246 <div class='slide '>
|
|
|
247 <!-- _S9SLIDE_ -->
|
|
|
248 <h1 id="cpuwoker">CPUWoker</h1>
|
|
|
249 <ul>
|
|
|
250 <li>Worker thread で動くTaskスケジューラーである。</li>
|
|
|
251 <li>synchronized queue からTask の List を読み込み実行する。</li>
|
|
|
252 <li>Data Gear の待ち合わせ管理を行う。</li>
|
|
|
253 <li>CPU Worker はreceive Tasl というAPI を持ち、Taskがなくなるまで繰り返す。</li>
|
|
|
254 </ul>
|
|
|
255
|
|
|
256
|
|
|
257 </div>
|
|
|
258 <div class='slide '>
|
|
|
259 <!-- _S9SLIDE_ -->
|
|
|
260 <h1 id="cudawoker">CUDAWoker</h1>
|
|
|
261 <ul>
|
|
|
262 <li>CPUWoker を再利用して作成するTask スケジューラー</li>
|
|
|
263 <li>CUDA ライブラリの初期化を行う以外の動作はCPUWoker と全く同じとなる。</li>
|
|
|
264 <li>GPU へのデータ転送及びGPU側でのTaskの実行はTaskのMeta Code Gear で行われる。</li>
|
|
|
265 </ul>
|
|
|
266
|
|
|
267
|
|
|
268 </div>
|
|
|
269 <div class='slide '>
|
|
|
270 <!-- _S9SLIDE_ -->
|
|
|
271 <h1 id="section-2">依存関係の解決</h1>
|
|
|
272 <ul>
|
|
|
273 <li>Gears での依存関係の解決は Data Gear にQueueをもたせることで行う</li>
|
|
|
274 <li>Queue には その Data Gear を待っている Task が入っている</li>
|
|
|
275 <li>Task は実行に必要な Input Data Gear のカウンタを持っており, Data Gear は書き出されると、依存関係にある Taskのカウンタをデクリメントする</li>
|
|
|
276 <li>全ての Input Data Gear が揃ったら, Taskを Worker に送信する</li>
|
|
|
277 </ul>
|
|
|
278
|
|
|
279 <div style="text-align: center;">
|
|
|
280 <img src="./fig/dependency.svg" alt="message" width="800" />
|
|
|
281 </div>
|
|
|
282
|
|
|
283
|
|
|
284 </div>
|
|
|
285 <div class='slide '>
|
|
|
286 <!-- _S9SLIDE_ -->
|
|
|
287 <h1 id="task-">Task の設定におけるメタ計算の問題</h1>
|
|
|
288 <ul>
|
|
|
289 <li>現在のGears OS では並列実行するTask の設定を以下の用に行っている。</li>
|
|
|
290 <li>実行するCode Gear 揃っていない Input Data Gear の数、Input Data Gear/Output Data Gear への参照等をノーマルレベルで記述している。</li>
|
|
|
291 </ul>
|
|
|
292
|
|
|
293
|
|
|
294 </div>
|
|
|
295 <div class='slide '>
|
|
|
296 <!-- _S9SLIDE_ -->
|
|
|
297 <h1 id="task--1">Task の設定におけるメタ計算の問題</h1>
|
|
|
298 <ul>
|
|
|
299 <li>この記述方法では Meta Data Gearである Task を直接参照しているためノーマルレベルでの記述は好ましくなく、メタレベルでの記述を行いたい。</li>
|
|
|
300 <li>そこで以下のような記述を新たに考案した。</li>
|
|
|
301 <li>par goto は先に上げたCode1 に変換されるきじゅつであり、これによりノーマルレベルでは直接 Taskを参照せずに par goto の引数で Task の設定を行うことができる。</li>
|
|
|
302 <li>この記述を拡張することでCPU GPUでの切り替えを行うことも可能であると考える。</li>
|
|
|
303 </ul>
|
|
|
304 <!-- === end markdown block === -->
|
|
|
305 </div>
|
|
|
306
|
|
|
307
|
|
|
308 </div><!-- presentation -->
|
|
|
309 </body>
|
|
|
310 </html>
|
