|
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 </ul>
|
|
|
49 </article>
|
|
|
50 </slide>
|
|
|
51
|
|
|
52 <slide>
|
|
|
53 <hgroup>
|
|
11
|
54 <h2>分散ネットフレームワーク Alice</h2>
|
|
|
55 </hgroup>
|
|
|
56 <article>
|
|
|
57 <ul>
|
|
|
58 <li>本研究室で開発を行なっている分散管理フレームワーク</li>
|
|
12
|
59 <li>並列フレームワーク Ceriumに似たタスク管理機構と先行研究であるFederated Lindaに似たData Segmentの通信構造</li>
|
|
|
60 <li>データとタスクを細かく分割したDataSegment、CodeSegmentでプログラム記述することで高い並列処理</li>
|
|
|
61 <li>Aliceの並列性能を確認するためbitonic Sortを実装したが、期待した結果を出すことが出来なかった</li>
|
|
|
62 <li><FONT Color="red">本論文ではAliceの実行速度の改善を行い、約10% の速度改善に成功した</FONT></li>
|
|
11
|
63 </ul>
|
|
|
64 </article>
|
|
|
65 </slide>
|
|
|
66
|
|
10
|
67
|
|
|
68 <slide>
|
|
|
69 <hgroup>
|
|
11
|
70 <h2>Code Segment</h2>
|
|
|
71 </hgroup>
|
|
|
72 <article>
|
|
|
73 <ul>
|
|
|
74 <li>AliceではCode Segmentと呼ばれる単位でタスクを生成する</li>
|
|
|
75 <li>Code Segmentは依存するData Segmentが全て揃うとActiveになる</li>
|
|
|
76 <li>Input/Output Data SegmentがCode Segment間の依存関係を自動的に記述する</li>
|
|
|
77 </ul>
|
|
12
|
78 <table width="100%">
|
|
|
79 <tr>
|
|
|
80 <td width="50%"><Div Align="Center"><image src="images/dsandcs2.png" width="600"></Div></td>
|
|
|
81 </tr>
|
|
|
82 </table>
|
|
11
|
83 </article>
|
|
|
84 </slide>
|
|
|
85
|
|
12
|
86 <slide>
|
|
|
87 <hgroup>
|
|
|
88 <h2>Data Segment</h2>
|
|
|
89 </hgroup>
|
|
|
90 <article>
|
|
|
91 <p>Data Segmentは数値や文字列を構造体的に保持する<br>
|
|
|
92 Aliceではデータベース的に扱うが、通常とは異なりKey毎にQueueを持つ<br>
|
|
|
93 以下のAPIでデータの送受信を行う</p>
|
|
|
94 <table width="100%">
|
|
|
95 <tr>
|
|
|
96 <td width="70%">
|
|
|
97 <FONT size="6"><ul><li>put : DataSegmentの追加</li></ul></font>
|
|
|
98 <FONT size="6"><ul><li>update : DataSegmentの更新</li></ul></font>
|
|
|
99 <FONT size="6"><ul><li>peek : DataSegmentの取得</li></ul></font>
|
|
|
100 <FONT size="6"><ul><li>take : DataSegmentの取得及び削除</li></ul></font>
|
|
|
101 </td>
|
|
|
102 <td width="30%"><Div Align="center"><image src="images/datasegment_key.png"></Div></td>
|
|
|
103 </tr>
|
|
|
104 </table>
|
|
|
105 <FONT Color="red">これらのAPIで分散プログラムが記述できる</FONT>
|
|
|
106 </article>
|
|
|
107 </slide>
|
|
11
|
108
|
|
|
109 <slide>
|
|
|
110 <hgroup>
|
|
10
|
111 <h2>実行速度の問題</h2>
|
|
|
112 </hgroup>
|
|
|
113 <article>
|
|
12
|
114 <p>Aliceの並列性能は問題がある<br>
|
|
|
115 作成した例題により以下のoverheadが見つかっている</p>
|
|
10
|
116 <ul>
|
|
|
117 <li>SEDA Architecture</li>
|
|
|
118 <li>Output Data Segmentの作成時のコピー</li>
|
|
|
119 </ul>
|
|
|
120 </article>
|
|
|
121 </slide>
|
|
|
122
|
|
|
123 <slide>
|
|
|
124 <hgroup>
|
|
|
125 <h2>SEDA Architecture</h2>
|
|
|
126 </hgroup>
|
|
|
127 <article>
|
|
|
128 <p>マルチコアを活かすためにAliceではSEDA Architectureを採用している。
|
|
|
129 <br>SEDAとはマルチコアスレッドを用いて大量の接続を管理し、<br>
|
|
|
130 データを処理毎に分けられたステージと呼ばれるスレッドで処理を行う。</p>
|
|
|
131 Aliceでは
|
|
|
132 <ul>
|
|
12
|
133 <Div Align="Center"><image src="images/seda.png"></Div>
|
|
10
|
134 </ul>
|
|
12
|
135 の3つのステージで構成されている。
|
|
10
|
136 </article>
|
|
|
137 </slide>
|
|
|
138
|
|
|
139 <slide>
|
|
|
140 <hgroup>
|
|
12
|
141 <h2>SEDA Architectureの実装</h2>
|
|
10
|
142 </hgroup>
|
|
|
143 <article>
|
|
12
|
144 <ul>
|
|
|
145 <code><pre>
|
|
|
146 while(ture){
|
|
|
147 Command cmd = linkedBlockingQueue.take()
|
|
|
148 Command result = runCommand(cmd);
|
|
|
149 nextLinkedBlockingQueue.put(result);
|
|
|
150 }
|
|
|
151 </pre></code>
|
|
14
|
152 <p>今回SEDAは上記のソースコードのように実装されている</p>
|
|
|
153 <p>LinkedBlockingQueueにCommandが次々と投げられる<br>
|
|
12
|
154 各ステージでQueueからCommandが取得され、Commandが実行され、<br>
|
|
14
|
155 その結果が次のステージのQueueに投げられる<br>
|
|
|
156 もし、Queueが空の場合にはブロッキングされenqueueされるまで待つ</p>
|
|
|
157 上記のコードを複数作成することでSEDAを形成している
|
|
|
158
|
|
12
|
159 </ul>
|
|
10
|
160 </article>
|
|
|
161 </slide>
|
|
|
162
|
|
|
163 <slide>
|
|
|
164 <hgroup>
|
|
|
165 <h2>LinkedBlockingQueue</h2>
|
|
|
166 </hgroup>
|
|
|
167 <article>
|
|
11
|
168 <p>SEDA Architectureを実装するにあたり、LinkedBlockingQueueを使用している。</p>
|
|
|
169 特徴として
|
|
10
|
170 <ul>
|
|
|
171 <li>LinkedBlockingQueueは片方向の連結リストを使用したQueue</li>
|
|
|
172 <li>enqueue/dequeueの操作時は排他制御は別々のlockで管理</li>
|
|
|
173 <li>enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)</li>
|
|
|
174 </ul>
|
|
11
|
175 ただし、enqueue時にNodeオブジェクトの生成操作が発生するため、<br>
|
|
|
176 enqueue操作の処理コストが特に高い。
|
|
10
|
177 </article>
|
|
|
178 </slide>
|
|
|
179
|
|
|
180 <slide>
|
|
|
181 <hgroup>
|
|
12
|
182 <h2>SEDAの問題点</h2>
|
|
10
|
183 </hgroup>
|
|
|
184 <article>
|
|
12
|
185 <p>SEDAは多段のパイプラインによって構成されるためレスポンスが遅れる。<br>
|
|
|
186 スループット重視の実装であるため、レスポンスが要求される<br>
|
|
|
187 Sortのようなプログラムに向いていない。<br>
|
|
|
188 非力なマシーンでは、スレッドを切り替えが頻繁に起こり、<br>
|
|
|
189 レスポンスを下げる要因になる。</p>
|
|
|
190 </article>
|
|
|
191 <hgroup>
|
|
|
192 <h2>改善案</h2>
|
|
|
193 </hgroup>
|
|
|
194 <article>
|
|
|
195 Sortのようなにレスポンスが必要なプログラムのために、
|
|
|
196 SEDAのステージ上ではなく、直接Commandを実行するようなAPIを提供する
|
|
|
197
|
|
10
|
198 </article>
|
|
|
199 </slide>
|
|
|
200
|
|
|
201 <slide>
|
|
|
202 <hgroup>
|
|
12
|
203 <h2>Output Data Segment作成時のコピー</h2>
|
|
10
|
204 </hgroup>
|
|
|
205 <article>
|
|
12
|
206 Input Data SegmentはCodeSegmentによって変更され、Output Data Segmentとして出力される。<br>
|
|
|
207 この際、変更されたDataSegmentをコピーし、新しくDataSegmentを作成する。<br>
|
|
|
208 このコピーにかかる時間がoverheadとなっている。
|
|
|
209 <Div Align="Center"><image src="images/put.png"></Div>
|
|
|
210 putはInput Data SegmentをコピーしてOutput Data Segmentを作成する
|
|
11
|
211 </article>
|
|
|
212 </slide>
|
|
|
213
|
|
12
|
214
|
|
11
|
215 <slide>
|
|
|
216 <hgroup>
|
|
|
217 <h2>問題に対する改善案</h2>
|
|
|
218 </hgroup>
|
|
|
219 <article>
|
|
12
|
220
|
|
|
221 <p>並列タスク管理フレームワークCeriumでもコピーによるoverheadがあり、Input Data SegmentとOutput Data Segmentをswapすることで解決している。<br>Aliceでも同様の方法で解決する。</p>
|
|
|
222 <Div Align="Center"><image src="images/flip.png"></Div>
|
|
|
223 flipではInput Data SegmentとOutput Data Segmentを入れ替え、必要な部分だけ変更を加えるので無駄なコピーを抑える事ができる
|
|
10
|
224
|
|
12
|
225 </ul>
|
|
10
|
226 </article>
|
|
|
227 </slide>
|
|
|
228
|
|
|
229 <slide>
|
|
|
230 <hgroup>
|
|
11
|
231 <h2>実験概要</h2>
|
|
10
|
232 </hgroup>
|
|
|
233 <article>
|
|
12
|
234 <p>今回行った改善による効果を調べるために3つの実験を行った。<br>
|
|
|
235 実験はSEDAの効果が出るようにメニコアのマシンで行った</p>
|
|
11
|
236 <ul>
|
|
|
237 <li>SEDAの有無</li>
|
|
|
238 <p>Data Segmentを取得するCode Segmentが10000回実行されるまでの時間を測定</p>
|
|
|
239 <li>flipとputの比較</li>
|
|
12
|
240 <p>既存のAPIの<em>put</em>と新しく追加したAPIである<em>flip</em>を使用して10000回、Data Segmentを追加されるまでの時間を測定</p>
|
|
11
|
241 <li>Bitonic Sortによる比較</li>
|
|
12
|
242 <p>今回行った改善でBitonic Sortがどの程度速度が改善されたか測定する。<br>
|
|
|
243 要素は100万個、10個に分割して実験した</p>
|
|
11
|
244 </ul>
|
|
|
245 </article>
|
|
|
246 </slide>
|
|
|
247
|
|
|
248
|
|
|
249 <slide>
|
|
|
250 <hgroup>
|
|
|
251 <h2>実験結果</h2>
|
|
|
252 </hgroup>
|
|
|
253 <article>
|
|
12
|
254 <p>実験結果は100回行った平均</p>
|
|
11
|
255 <ul>
|
|
|
256 <table>
|
|
12
|
257 <tr width="100%">
|
|
|
258 <th width="50%">SEDA</th><th width="25%">あり</th><th width="25%">なし</th>
|
|
10
|
259 </tr>
|
|
|
260 <tr>
|
|
11
|
261 <td>実行時間(ms)</td><td>27.72</td><td>7.53</td>
|
|
10
|
262 </tr>
|
|
11
|
263 </table>
|
|
|
264 </ul>
|
|
|
265 <ul>
|
|
|
266 <table>
|
|
12
|
267 <tr width="100%">
|
|
|
268 <th width="50%">API</th><th width="25%">flip</th><th width="25%">put</th>
|
|
10
|
269 </tr>
|
|
|
270 <tr>
|
|
11
|
271 <td>実行時間(ms)</td><td>61.12</td><td>65.24</td>
|
|
|
272 </tr>
|
|
|
273 </table>
|
|
|
274 </ul>
|
|
|
275 <ul>
|
|
|
276 <table>
|
|
12
|
277 <tr width="100%">
|
|
|
278 <th width="50%"></th><th width="25%">改善前</th><th width="25%">改善後</th>
|
|
10
|
279 </tr>
|
|
|
280 <tr>
|
|
11
|
281 <td>実行時間(ms)</td><td>199.38</td><td>184.64</td>
|
|
10
|
282 </tr>
|
|
|
283 </table>
|
|
11
|
284 Bitonic Sortの例題では約10％程度改善された
|
|
|
285 </ul>
|
|
10
|
286 </article>
|
|
|
287 </slide>
|
|
|
288
|
|
|
289 <slide>
|
|
|
290 <hgroup>
|
|
11
|
291 <h2>まとめ</h2>
|
|
10
|
292 </hgroup>
|
|
11
|
293 <article>
|
|
|
294 <ul>
|
|
14
|
295 <li>今回行った改善により、<FONT color="red">最大4倍程度速度を期待することが出来る</FONT></li>
|
|
|
296 <li>Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度</li>
|
|
|
297 <li>分散環境下ではFederated Lindaと同じ速度を目標としている</li>
|
|
|
298 <li>今回の実験からSEDAに問題があることが明らかになったのでRemoteにおいてもSEDAの使用を選択できるようにする</li>
|
|
11
|
299 <li>また、Aliceが抱える問題は速度だけではない</li>
|
|
|
300 <li>信頼性の問題や永続性の問題についても改善をしなければならない</li>
|
|
|
301 </ul>
|
|
10
|
302 </article>
|
|
|
303 </slide>
|
|
|
304
|
|
12
|
305
|
|
10
|
306 <slide class="backdrop"></slide>
|
|
|
307
|
|
|
308 </slides>
|
|
|
309
|
|
|
310 <script>
|
|
|
311 var _gaq = _gaq || [];
|
|
|
312 _gaq.push(['_setAccount', 'UA-XXXXXXXX-1']);
|
|
|
313 _gaq.push(['_trackPageview']);
|
|
|
314
|
|
|
315 (function() {
|
|
|
316 var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
|
|
|
317 ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
|
|
|
318 var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
|
|
|
319 })();
|
|
|
320 </script>
|
|
|
321
|
|
|
322 <!--[if IE]>
|
|
|
323 <script src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js"></script>
|
|
|
324 <script>CFInstall.check({mode: 'overlay'});</script>
|
|
|
325 <![endif]-->
|
|
|
326 </body>
|
|
|
327 </html>
|
