|
10
|
1 <!--
|
|
|
2 Google IO 2012/2013 HTML5 Slide Template
|
|
|
3
|
|
|
4 Authors: Eric Bidelman <ebidel@gmail.com>
|
|
|
5 Luke Mahé <lukem@google.com>
|
|
|
6
|
|
|
7 URL: https://code.google.com/p/io-2012-slides
|
|
|
8 -->
|
|
|
9 <!DOCTYPE html>
|
|
|
10 <html>
|
|
|
11 <head>
|
|
|
12 <title></title>
|
|
|
13 <meta charset="utf-8">
|
|
|
14 <meta http-equiv="X-UA-Compatible" content="chrome=1">
|
|
|
15 <!--<meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0">-->
|
|
|
16 <!--<meta name="viewport" content="width=device-width, initial-scale=1.0">-->
|
|
|
17 <!--This one seems to work all the time, but really small on ipad-->
|
|
|
18 <!--<meta name="viewport" content="initial-scale=0.4">-->
|
|
|
19 <meta name="apple-mobile-web-app-capable" content="yes">
|
|
|
20 <link rel="stylesheet" media="all" href="theme/css/default.css">
|
|
|
21 <link rel="stylesheet" media="only screen and (max-device-width: 480px)" href="theme/css/phone.css">
|
|
|
22 <base target="_blank"> <!-- This amazingness opens all links in a new tab. -->
|
|
|
23 <script data-main="js/slides" src="js/require-1.0.8.min.js"></script>
|
|
|
24 </head>
|
|
|
25 <body style="opacity: 0">
|
|
|
26
|
|
|
27 <slides class="layout-widescreen">
|
|
|
28
|
|
|
29 <slide class="title-slide segue nobackground">
|
|
|
30 <!--<aside class="gdbar"><img src="images/google_developers_icon_128.png"></aside>
|
|
|
31 The content of this hgroup is replaced programmatically through the slide_config.json. -->
|
|
|
32 <hgroup>
|
|
|
33 <h1 data-config-title><!-- populated from slide_config.json --></h1>
|
|
|
34 <h2 data-config-subtitle><!-- populated from slide_config.json --></h2>
|
|
|
35 <p data-config-presenter><!-- populated from slide_config.json --></p>
|
|
|
36 </hgroup>
|
|
|
37 </slide>
|
|
|
38
|
|
|
39 <slide>
|
|
|
40 <hgroup>
|
|
|
41 <h2>研究背景</h2>
|
|
|
42 </hgroup>
|
|
|
43 <article>
|
|
|
44 <ul>
|
|
|
45 <li>分散プログラムには信頼性とスケーラビリティが必要である</li>
|
|
|
46 <li>しかし、両方を兼ね備えたプログラムを作成することは容易ではない</li>
|
|
|
47 <li>そこで、当研究室では信頼性とスケーラビリティの両方をもったプログラムの記述をサポートする、分散フレームワークAliceを開発を行なっている</li>
|
|
|
48 <li>Aliceはデータとタスクを細かく分割したDataSegment、CodeSegmentでプログラム記述する</li>
|
|
|
49 <li>DataSegment、CodeSegmentで記述することにより高い並列処理を行うことができる</li>
|
|
|
50 <li>Aliceの並列性能を確認するためbitonic Sortを実装したが、実行速度に問題があったため、
|
|
|
51 本論文では実行速度の改善を試みた</li>
|
|
|
52 </ul>
|
|
|
53 </article>
|
|
|
54 </slide>
|
|
|
55
|
|
|
56 <slide>
|
|
|
57 <hgroup>
|
|
11
|
58 <h2>分散ネットフレームワーク Alice</h2>
|
|
|
59 </hgroup>
|
|
|
60 <article>
|
|
|
61 <ul>
|
|
|
62 <li>本研究室で開発を行なっている分散管理フレームワーク</li>
|
|
|
63 <li>Data SegmentとCodeSegmentによりプログラムを記述する</li>
|
|
|
64 <li>並列フレームワーク Ceriumに似たタスク管理機構と先行研究であるFederated Lindaに似たData Segmentの通信構造をもつ</li>
|
|
|
65 <li>メニーコアのマシンが主流である背景からSEDA Architectureが採用している</li>
|
|
|
66 </ul>
|
|
|
67 </article>
|
|
|
68 </slide>
|
|
|
69
|
|
|
70 <slide>
|
|
|
71 <hgroup>
|
|
|
72 <h2>Data Segment</h2>
|
|
|
73 </hgroup>
|
|
|
74 <article>
|
|
|
75 <p>Data Segmentは数値や文字列を構造体的に保持する。<br>
|
|
|
76 Aliceではデータベース的に扱うが、通常とは異なりKey毎にQueueを持つ<br>
|
|
|
77 以下のAPIでデータの送受信を行う</p>
|
|
|
78 <ul>
|
|
|
79 <li>put</li>
|
|
|
80 <li>update</li>
|
|
|
81 <li>peek</li>
|
|
|
82 <li>take</li>
|
|
|
83 </ul>
|
|
|
84 </article>
|
|
|
85 </slide>
|
|
|
86
|
|
|
87 <slide>
|
|
|
88 <hgroup>
|
|
|
89 <h2>put</h2>
|
|
10
|
90 </hgroup>
|
|
|
91 <article>
|
|
|
92 <ul>
|
|
|
93 </ul>
|
|
|
94 </article>
|
|
|
95 </slide>
|
|
|
96
|
|
|
97 <slide>
|
|
|
98 <hgroup>
|
|
11
|
99 <h2>update</h2>
|
|
|
100 </hgroup>
|
|
|
101 <article>
|
|
|
102 <ul>
|
|
|
103 </ul>
|
|
|
104 </article>
|
|
|
105 </slide>
|
|
|
106
|
|
|
107 <slide>
|
|
|
108 <hgroup>
|
|
|
109 <h2>peek</h2>
|
|
10
|
110 </hgroup>
|
|
|
111 <article>
|
|
11
|
112 <ul>
|
|
|
113 </ul>
|
|
|
114 </article>
|
|
|
115 </slide>
|
|
|
116
|
|
|
117 <slide>
|
|
|
118 <hgroup>
|
|
|
119 <h2>take</h2>
|
|
|
120 </hgroup>
|
|
|
121 <article>
|
|
|
122 <ul>
|
|
|
123 </ul>
|
|
10
|
124 </article>
|
|
|
125 </slide>
|
|
|
126
|
|
|
127 <slide>
|
|
|
128 <hgroup>
|
|
11
|
129 <h2>Code Segment</h2>
|
|
|
130 </hgroup>
|
|
|
131 <article>
|
|
|
132 <ul>
|
|
|
133 <li>AliceではCode Segmentと呼ばれる単位でタスクを生成する</li>
|
|
|
134 <li>Code Segmentは依存するData Segmentが全て揃うとActiveになる</li>
|
|
|
135 <li>Input/Output Data SegmentがCode Segment間の依存関係を自動的に記述する</li>
|
|
|
136 </ul>
|
|
|
137 </article>
|
|
|
138 </slide>
|
|
|
139
|
|
|
140
|
|
|
141 <slide>
|
|
|
142 <hgroup>
|
|
10
|
143 <h2>実行速度の問題</h2>
|
|
|
144 </hgroup>
|
|
|
145 <article>
|
|
|
146 <p>Aliceは先行研究であるFederated Lindaよりも処理速度が遅い。<br>
|
|
|
147 作成した例題によりOverHeadの原因が見つかっている</p>
|
|
|
148 <ul>
|
|
|
149 <li>Message Packによる型変換</li>
|
|
|
150 <li>SEDA Architecture</li>
|
|
|
151 <li>Output Data Segmentの作成時のコピー</li>
|
|
|
152 </ul>
|
|
|
153 </article>
|
|
|
154 </slide>
|
|
|
155
|
|
|
156 <slide>
|
|
|
157 <hgroup>
|
|
|
158 <h2>Message Pack</h2>
|
|
|
159 </hgroup>
|
|
|
160 <article>
|
|
|
161 <p>シリアライズライブラリの一種。<br>
|
|
|
162 シリアライズされたデータにオブジェクトの型情報を併せて埋め込むため、<br>
|
|
|
163 IDL(インターフェース定義ファイル)を用意する必要がない。<br>
|
|
|
164 異なる言語間でオブジェクトを交換可能<br>
|
|
|
165 MessagePack for Java のVersion 0.6からValue型が追加されており、<br>オブジェクトを動的型付け可能</p>
|
|
|
166 <ul>
|
|
|
167 <li>MessagePackを使用することで他のノードとData Segmentの送受信が高速に行うことができる</li>
|
|
|
168 <li>AliceはData SegmentをQueueに追加する際にValue型に変換</li>
|
|
|
169 <li>アノテーションをつけることにより既存のData Segmentと互換性を保ったまま拡張することができる</li>
|
|
|
170 </ul>
|
|
|
171 </article>
|
|
|
172 </slide>
|
|
|
173
|
|
|
174
|
|
|
175 <slide>
|
|
|
176 <hgroup>
|
|
|
177 <h2>Message Packの問題</h2>
|
|
|
178 </hgroup>
|
|
|
179 <article>
|
|
|
180 <p>分散プログラムにおいて、常にVersionが同じとは限らない。<br>
|
|
|
181 旧Versionとの互換性のため、Value型に変換している。<br>
|
|
|
182 しかし、追加するタイミングで変換を行うと、外部と通信を行わない<br>
|
|
|
183 DataSegmentに対しても型変換を行う</p>
|
|
|
184 Sortなどの配列をValue型に変換する場合は要素の数が増えるほど、<br>
|
|
|
185 変換する時間が増加する。
|
|
|
186 <ul>
|
|
|
187 </ul>
|
|
|
188 </article>
|
|
|
189 </slide>
|
|
|
190
|
|
|
191 <slide>
|
|
|
192 <hgroup>
|
|
|
193 <h2>SEDA Architecture</h2>
|
|
|
194 </hgroup>
|
|
|
195 <article>
|
|
|
196 <p>マルチコアを活かすためにAliceではSEDA Architectureを採用している。
|
|
|
197 <br>SEDAとはマルチコアスレッドを用いて大量の接続を管理し、<br>
|
|
|
198 データを処理毎に分けられたステージと呼ばれるスレッドで処理を行う。</p>
|
|
|
199 Aliceでは
|
|
|
200 <ul>
|
|
|
201 <li>putやtakeなどの要求に沿ったCommandを作成するステージ</li>
|
|
|
202 <li>Commandを処理するステージ</li>
|
|
|
203 <li>DataSegmentをCodeSegmentにセットするステージ</li>
|
|
|
204
|
|
|
205 </ul>
|
|
|
206 の3つのステージで構成されている。
|
|
|
207 </article>
|
|
|
208 </slide>
|
|
|
209
|
|
|
210 <slide>
|
|
|
211 <hgroup>
|
|
|
212 <h2>SEDAの問題点</h2>
|
|
|
213 </hgroup>
|
|
|
214 <article>
|
|
|
215 <p>SEDAは多段のパイプラインによって構成されるためレスポンスが遅れる。<br>
|
|
|
216 スループット重視の実装であるため、レスポンスが要求される<br>
|
|
|
217 Sortのようなプログラムに向いていない。<br>
|
|
|
218 非力なマシーンでは、スレッドを切り替えが頻繁に起こり、<br>
|
|
|
219 レスポンスを下げる要因になる。</p>
|
|
|
220 </article>
|
|
|
221 </slide>
|
|
|
222
|
|
|
223 <slide>
|
|
|
224 <hgroup>
|
|
|
225 <h2>LinkedBlockingQueue</h2>
|
|
|
226 </hgroup>
|
|
|
227 <article>
|
|
11
|
228 <p>SEDA Architectureを実装するにあたり、LinkedBlockingQueueを使用している。</p>
|
|
|
229 特徴として
|
|
10
|
230 <ul>
|
|
|
231 <li>LinkedBlockingQueueは片方向の連結リストを使用したQueue</li>
|
|
|
232 <li>enqueue/dequeueの操作時は排他制御は別々のlockで管理</li>
|
|
|
233 <li>enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)</li>
|
|
|
234 </ul>
|
|
11
|
235 ただし、enqueue時にNodeオブジェクトの生成操作が発生するため、<br>
|
|
|
236 enqueue操作の処理コストが特に高い。
|
|
10
|
237 </article>
|
|
|
238 </slide>
|
|
|
239
|
|
|
240 <slide>
|
|
|
241 <hgroup>
|
|
|
242 <h2>Output Data Segment作成時のコピー</h2>
|
|
|
243 </hgroup>
|
|
|
244 <article>
|
|
|
245 CodeSegmentはDataSegmentを取得するとActiveになる。<br>
|
|
|
246 取得されたDataSegmentはCodeSegmentによって変更され、<br>
|
|
|
247 Output Data Segmentとして出力される。<br>
|
|
|
248 この際、変更されたDataSegmentをコピーし、新しくDataSegmentを作成する。<br>
|
|
|
249 このコピーにかかる時間がオーバーヘッドとなっている。
|
|
|
250 </article>
|
|
|
251 </slide>
|
|
|
252
|
|
|
253 <slide>
|
|
|
254 <hgroup>
|
|
|
255 <h2>問題に対する改善案</h2>
|
|
|
256 </hgroup>
|
|
|
257 <article>
|
|
|
258 <ul>
|
|
|
259 <li>MessagePack</li>
|
|
|
260 MessagePackによるValue型に変換が必要なケースは、<br>
|
|
|
261 他のノードに対してData Segmentを送信する場合である。<br>
|
|
|
262 DataSegmentを追加するタイミングでValue型に変換せず、<br>
|
|
|
263 メッセージを送信する前に変換を行えばよい。
|
|
|
264 <p></p>
|
|
|
265 <li>SEDA Architecture</li>
|
|
|
266 Sortのようなにレスポンスが必要なプログラムのために、SEDAのステージ上ではなく、
|
|
|
267 直接DataSegmentを取得するAPIを用意する
|
|
|
268 <p></p>
|
|
11
|
269 </ul>
|
|
|
270 </article>
|
|
|
271 </slide>
|
|
|
272
|
|
|
273 <slide>
|
|
|
274 <hgroup>
|
|
|
275 <h2>問題に対する改善案</h2>
|
|
|
276 </hgroup>
|
|
|
277 <article>
|
|
|
278 <ul>
|
|
10
|
279 <li>Output Data Segment作成時におけるコピー</li>
|
|
11
|
280 Ceriumでも同様なコピーの問題があり、Input Data SegmentとOutput Data Segmentを
|
|
|
281 Swapすることで解決している。Aliceでも同様の方法で解決する。<br>
|
|
|
282 Data SegmentはCode Segment内ではReceiverという変数が保持している。<br>
|
|
|
283 このReceiverをOutput Data Segmentにすることで無駄なコピーを減らす。
|
|
10
|
284 </ul>
|
|
|
285 </article>
|
|
|
286 </slide>
|
|
|
287
|
|
|
288 <slide>
|
|
|
289 <hgroup>
|
|
11
|
290 <h2>検証</h2>
|
|
10
|
291 </hgroup>
|
|
11
|
292
|
|
10
|
293 <article>
|
|
11
|
294 <h3>実験環境</h3>
|
|
10
|
295 <table>
|
|
|
296 <tr>
|
|
11
|
297 <td>CPU</td><td>Intel(R) Xeon(R) X5650 @2.67GHz</td>
|
|
10
|
298 </tr>
|
|
|
299 <tr>
|
|
11
|
300 <td>物理コア数</td><td>12</td>
|
|
|
301 </tr>
|
|
|
302 <tr>
|
|
|
303 <td>論理コア数</td><td>24</td>
|
|
|
304 </tr>
|
|
|
305 <tr>
|
|
|
306 <td>CPU キャッシュ</td><td>12MB</td>
|
|
|
307 </tr>
|
|
|
308 <tr>
|
|
|
309 <td>Memory</td><td>16GB</td>
|
|
10
|
310 </tr>
|
|
|
311 </table>
|
|
11
|
312 <p></p>
|
|
|
313 SEDAを活かせるようにメニコア上でテストを行なった。
|
|
10
|
314 </article>
|
|
|
315 </slide>
|
|
|
316
|
|
|
317 <slide>
|
|
|
318 <hgroup>
|
|
11
|
319 <h2>実験概要</h2>
|
|
10
|
320 </hgroup>
|
|
|
321 <article>
|
|
11
|
322 <p>今回行った改善による効果を調べるために3つの実験を行った。</p>
|
|
|
323 <ul>
|
|
|
324 <li>SEDAの有無</li>
|
|
|
325 <p>Data Segmentを取得するCode Segmentが10000回実行されるまでの時間を測定</p>
|
|
|
326 <li>flipとputの比較</li>
|
|
|
327 <p>既存のAPIの<em>put</em>と新しく追加したAPIである<em>flip</em>をつかい10000回、Data Segmentを追加されるまでの時間を測定</p>
|
|
|
328 <li>Bitonic Sortによる比較</li>
|
|
|
329 <p>今回行った改善(ただし、MessagePackによる改善を除く)
|
|
|
330 Bitonic Sortで100万の要素をSortされるまでの時間を測定する。分割数は10個で行った</p>
|
|
|
331 </ul>
|
|
|
332 </article>
|
|
|
333 </slide>
|
|
|
334
|
|
|
335
|
|
|
336 <slide>
|
|
|
337 <hgroup>
|
|
|
338 <h2>実験結果</h2>
|
|
|
339 </hgroup>
|
|
|
340 <article>
|
|
|
341 <p>実験結果は100回行った平均である</p>
|
|
|
342 <ul>
|
|
|
343 <table>
|
|
10
|
344 <tr>
|
|
11
|
345 <th>SEDA</th><th>あり</th><th>なし</th>
|
|
10
|
346 </tr>
|
|
|
347 <tr>
|
|
11
|
348 <td>実行時間(ms)</td><td>27.72</td><td>7.53</td>
|
|
10
|
349 </tr>
|
|
11
|
350 </table>
|
|
|
351 </ul>
|
|
|
352 <ul>
|
|
|
353 <table>
|
|
10
|
354 <tr>
|
|
11
|
355 <th>API</th><th>flip</th><th>put</th>
|
|
10
|
356 </tr>
|
|
|
357 <tr>
|
|
11
|
358 <td>実行時間(ms)</td><td>61.12</td><td>65.24</td>
|
|
|
359 </tr>
|
|
|
360 </table>
|
|
|
361 </ul>
|
|
|
362 <ul>
|
|
|
363 <table>
|
|
|
364 <tr>
|
|
|
365 <th></th><th>改善前</th><th>改善後</th>
|
|
10
|
366 </tr>
|
|
|
367 <tr>
|
|
11
|
368 <td>実行時間(ms)</td><td>199.38</td><td>184.64</td>
|
|
10
|
369 </tr>
|
|
|
370 </table>
|
|
11
|
371 Bitonic Sortの例題では約10％程度改善された
|
|
|
372 </ul>
|
|
10
|
373 </article>
|
|
|
374 </slide>
|
|
|
375
|
|
|
376 <slide>
|
|
|
377 <hgroup>
|
|
11
|
378 <h2>まとめ</h2>
|
|
10
|
379 </hgroup>
|
|
11
|
380 <article>
|
|
|
381 <ul>
|
|
|
382 <li>今回行った改善により、以前のAliceよりも約10％程度速度が改善した</li>
|
|
|
383 <li>しかし、Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度</li>
|
|
|
384 <li>分散環境下ではFederated Linda以上の速度が求められる</li>
|
|
|
385 <li>また、Aliceが抱える問題は速度だけではない</li>
|
|
|
386 <li>信頼性の問題や永続性の問題についても改善をしなければならない</li>
|
|
|
387 </ul>
|
|
10
|
388 </article>
|
|
|
389 </slide>
|
|
|
390
|
|
|
391 <slide>
|
|
|
392 <hgroup>
|
|
11
|
393 <h2>Message Packの型変換にかかる時間</h2>
|
|
10
|
394 </hgroup>
|
|
|
395 <article>
|
|
11
|
396 <ul>
|
|
|
397 </ul>
|
|
10
|
398 </article>
|
|
|
399 </slide>
|
|
|
400 <slide class="backdrop"></slide>
|
|
|
401
|
|
|
402 </slides>
|
|
|
403
|
|
|
404 <script>
|
|
|
405 var _gaq = _gaq || [];
|
|
|
406 _gaq.push(['_setAccount', 'UA-XXXXXXXX-1']);
|
|
|
407 _gaq.push(['_trackPageview']);
|
|
|
408
|
|
|
409 (function() {
|
|
|
410 var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
|
|
|
411 ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
|
|
|
412 var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
|
|
|
413 })();
|
|
|
414 </script>
|
|
|
415
|
|
|
416 <!--[if IE]>
|
|
|
417 <script src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js"></script>
|
|
|
418 <script>CFInstall.check({mode: 'overlay'});</script>
|
|
|
419 <![endif]-->
|
|
|
420 </body>
|
|
|
421 </html>
|
