Mercurial > hg > Papers > 2013 > sugi-sigos

comparison presen/index.html @ 11:57b1c4692d21

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
minor change
author sugi
date Wed, 24 Apr 2013 13:34:58 +0900
parents 5c57e35e19b6
children 85b22f56ef00
comparison
equal deleted inserted replaced
10:5c57e35e19b6 11:57b1c4692d21
53 </article> 53 </article>
54 </slide> 54 </slide>
55 55
56 <slide> 56 <slide>
57 <hgroup> 57 <hgroup>
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>
90 </hgroup>
91 <article>
92 <ul>
93 </ul>
94 </article>
95 </slide>
96
97 <slide>
98 <hgroup>
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>
110 </hgroup>
111 <article>
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>
124 </article>
125 </slide>
126
127 <slide>
128 <hgroup>
58 <h2>Code Segment</h2> 129 <h2>Code Segment</h2>
59 </hgroup> 130 </hgroup>
60 <article> 131 <article>
61 <ul> 132 <ul>
62 </ul> 133 <li>AliceではCode Segmentと呼ばれる単位でタスクを生成する</li>
63 </article> 134 <li>Code Segmentは依存するData Segmentが全て揃うとActiveになる</li>
64 </slide> 135 <li>Input/Output Data SegmentがCode Segment間の依存関係を自動的に記述する</li>
65 136 </ul>
66 <slide> 137 </article>
67 <hgroup> 138 </slide>
68 <h2>Data Segment</h2> 139
69 </hgroup>
70 <article>
71 <p>DataSegmentはデータを細かくしたものであり、以下のAPIで操作を行う</p>
72 </article>
73 </slide>
74 140
75 <slide> 141 <slide>
76 <hgroup> 142 <hgroup>
77 <h2>実行速度の問題</h2> 143 <h2>実行速度の問題</h2>
78 </hgroup> 144 </hgroup>
157 <slide> 223 <slide>
158 <hgroup> 224 <hgroup>
159 <h2>LinkedBlockingQueue</h2> 225 <h2>LinkedBlockingQueue</h2>
160 </hgroup> 226 </hgroup>
161 <article> 227 <article>
162 <p>今回、SEDA Architectureを実装するにあたりJavaのLinkedBlockingQueueを使用している。</p> 228 <p>SEDA Architectureを実装するにあたり、LinkedBlockingQueueを使用している。</p>
163 特徴として 229 特徴として
164 <ul> 230 <ul>
165 <li>LinkedBlockingQueueは片方向の連結リストを使用したQueue</li> 231 <li>LinkedBlockingQueueは片方向の連結リストを使用したQueue</li>
166 <li>enqueue/dequeueの操作時は排他制御は別々のlockで管理</li> 232 <li>enqueue/dequeueの操作時は排他制御は別々のlockで管理</li>
167 <li>enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)</li> 233 <li>enqueueとdequeueの操作を並列に行うことが可能(スループットに優れている)</li>
168 </ul> 234 </ul>
235 ただし、enqueue時にNodeオブジェクトの生成操作が発生するため、<br>
236 enqueue操作の処理コストが特に高い。
169 </article> 237 </article>
170 </slide> 238 </slide>
171 239
172 <slide> 240 <slide>
173 <hgroup> 241 <hgroup>
177 CodeSegmentはDataSegmentを取得するとActiveになる。<br> 245 CodeSegmentはDataSegmentを取得するとActiveになる。<br>
178 取得されたDataSegmentはCodeSegmentによって変更され、<br> 246 取得されたDataSegmentはCodeSegmentによって変更され、<br>
179 Output Data Segmentとして出力される。<br> 247 Output Data Segmentとして出力される。<br>
180 この際、変更されたDataSegmentをコピーし、新しくDataSegmentを作成する。<br> 248 この際、変更されたDataSegmentをコピーし、新しくDataSegmentを作成する。<br>
181 このコピーにかかる時間がオーバーヘッドとなっている。 249 このコピーにかかる時間がオーバーヘッドとなっている。
182 <ul>
183 <li></li>
184 </ul>
185 </article> 250 </article>
186 </slide> 251 </slide>
187 252
188 <slide> 253 <slide>
189 <hgroup> 254 <hgroup>
199 <p></p> 264 <p></p>
200 <li>SEDA Architecture</li> 265 <li>SEDA Architecture</li>
201 Sortのようなにレスポンスが必要なプログラムのために、SEDAのステージ上ではなく、 266 Sortのようなにレスポンスが必要なプログラムのために、SEDAのステージ上ではなく、
202 直接DataSegmentを取得するAPIを用意する 267 直接DataSegmentを取得するAPIを用意する
203 <p></p> 268 <p></p>
269 </ul>
270 </article>
271 </slide>
272
273 <slide>
274 <hgroup>
275 <h2>問題に対する改善案</h2>
276 </hgroup>
277 <article>
278 <ul>
204 <li>Output Data Segment作成時におけるコピー</li> 279 <li>Output Data Segment作成時におけるコピー</li>
205 Data SegmentはCode Segment内ではReceiverという変数が保持している。 280 Ceriumでも同様なコピーの問題があり、Input Data SegmentとOutput Data Segmentを
206 281 Swapすることで解決している。Aliceでも同様の方法で解決する。<br>
207 </ul> 282 Data SegmentはCode Segment内ではReceiverという変数が保持している。<br>
208 </article> 283 このReceiverをOutput Data Segmentにすることで無駄なコピーを減らす。
209 </slide> 284 </ul>
210 285 </article>
211 <slide> 286 </slide>
212 <hgroup> 287
213 <h2>Slide with Image (Centered horz/vert)</h2> 288 <slide>
214 </hgroup> 289 <hgroup>
215 <article class="flexbox vcenter"> 290 <h2>検証</h2>
216 <img src="images/barchart.png" alt="Description" title="Description"> 291 </hgroup>
217 <footer class="source">source: place source info here</footer> 292
218 </article> 293 <article>
219 </slide> 294 <h3>実験環境</h3>
220
221 <slide>
222 <hgroup>
223 <h2>Table Option A</h2>
224 <h3>Subtitle Placeholder</h3>
225 </hgroup>
226 <article>
227 <table> 295 <table>
228 <tr> 296 <tr>
229 <th></th><th>Column 1</th><th>Column 2</th><th>Column 3</th><th>Column 4</th> 297 <td>CPU</td><td>Intel(R) Xeon(R) X5650 @2.67GHz</td>
230 </tr> 298 </tr>
231 <tr> 299 <tr>
232 <td>Row 1</td><td>placeholder</td><td class="highlight">placeholder</td><td>placeholder</td><td>placeholder</td> 300 <td>物理コア数</td><td>12</td>
233 </tr> 301 </tr>
234 <tr> 302 <tr>
235 <td>Row 2</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td> 303 <td>論理コア数</td><td>24</td>
236 </tr> 304 </tr>
237 <tr> 305 <tr>
238 <td>Row 3</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td> 306 <td>CPU キャッシュ</td><td>12MB</td>
239 </tr> 307 </tr>
240 <tr> 308 <tr>
241 <td>Row 4</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td> 309 <td>Memory</td><td>16GB</td>
242 </tr>
243 <tr>
244 <td>Row 5</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td>
245 </tr> 310 </tr>
246 </table> 311 </table>
247 </article> 312 <p></p>
248 </slide> 313 SEDAを活かせるようにメニコア上でテストを行なった。
249 314 </article>
250 <slide> 315 </slide>
251 <hgroup> 316
252 <h2>Table Option A (Smaller Text)</h2> 317 <slide>
253 <h3>Subtitle Placeholder</h3> 318 <hgroup>
254 </hgroup> 319 <h2>実験概要</h2>
255 <article class="smaller"> 320 </hgroup>
321 <article>
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>
256 <table> 343 <table>
257 <tr> 344 <tr>
258 <th></th><th>Column 1</th><th>Column 2</th><th>Column 3</th><th>Column 4</th> 345 <th>SEDA</th><th>あり</th><th>なし</th>
259 </tr> 346 </tr>
260 <tr> 347 <tr>
261 <td>Row 1</td><td>placeholder</td><td class="highlight">placeholder</td><td>placeholder</td><td>placeholder</td> 348 <td>実行時間(ms)</td><td>27.72</td><td>7.53</td>
262 </tr>
263 <tr>
264 <td>Row 2</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td>
265 </tr>
266 <tr>
267 <td>Row 3</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td>
268 </tr>
269 <tr>
270 <td>Row 4</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td>
271 </tr>
272 <tr>
273 <td>Row 5</td><td>placeholder</td><td>placeholder</td><td>placeholder</td><td>placeholder</td>
274 </tr> 349 </tr>
275 </table> 350 </table>
276 </article> 351 </ul>
277 </slide> 352 <ul>
278 353 <table>
279 <slide> 354 <tr>
280 <hgroup> 355 <th>API</th><th>flip</th><th>put</th>
281 <h2>Table Option B</h2> 356 </tr>
282 <h3>Subtitle Placeholder</h3> 357 <tr>
283 </hgroup> 358 <td>実行時間(ms)</td><td>61.12</td><td>65.24</td>
284 <article>
285 <table class="rows">
286 <tr>
287 <th>Header 1</th><td>placeholder</td><td class="highlight">placeholder</td><td>placeholder</td>
288 </tr>
289 <tr>
290 <th>Header 2</th><td>placeholder</td><td>placeholder</td><td>placeholder</td>
291 </tr>
292 <tr>
293 <th>Header 3</th><td>placeholder</td><td>placeholder</td><td>placeholder</td>
294 </tr>
295 <tr>
296 <th>Header 4</th><td>placeholder</td><td>placeholder</td><td>placeholder</td>
297 </tr>
298 <tr>
299 <th>Header 5</th><td>placeholder</td><td>placeholder</td><td>placeholder</td>
300 </tr> 359 </tr>
301 </table> 360 </table>
302 </article> 361 </ul>
303 </slide> 362 <ul>
304 363 <table>
305 <slide> 364 <tr>
306 <hgroup> 365 <th></th><th>改善前</th><th>改善後</th>
307 <h2>Slide Styles</h2> 366 </tr>
308 </hgroup> 367 <tr>
309 <article class="smaller"> 368 <td>実行時間(ms)</td><td>199.38</td><td>184.64</td>
310 <div class="columns-2"> 369 </tr>
311 <ul> 370 </table>
312 <li class="red">class="red"</li> 371 Bitonic Sortの例題では約10％程度改善された
313 <li class="red2">class="red2"</li> 372 </ul>
314 <li class="red3">class="red3"</li> 373 </article>
315 <li class="blue">class="blue"</li> 374 </slide>
316 <li class="blue2">class="blue2"</li> 375
317 <li class="blue3">class="blue3"</li> 376 <slide>
318 <li class="green">class="green"</li> 377 <hgroup>
319 <li class="green2">class="green2"</li> 378 <h2>まとめ</h2>
320 </ul> 379 </hgroup>
321 <ul> 380 <article>
322 <li class="green3">class="green3"</li> 381 <ul>
323 <li class="yellow">class="yellow"</li> 382 <li>今回行った改善により、以前のAliceよりも約10％程度速度が改善した</li>
324 <li class="yellow2">class="yellow2"</li> 383 <li>しかし、Aliceに要求される速度は、少なくともシングルスレッドで書かれたプログラムと同じ程度</li>
325 <li class="yellow3">class="yellow3"</li> 384 <li>分散環境下ではFederated Linda以上の速度が求められる</li>
326 <li class="gray">class="gray"</li> 385 <li>また、Aliceが抱える問題は速度だけではない</li>
327 <li class="gray2">class="gray2"</li> 386 <li>信頼性の問題や永続性の問題についても改善をしなければならない</li>
328 <li class="gray3">class="gray3"</li> 387 </ul>
329 <li class="gray4">class="gray4"</li> 388 </article>
330 </ul> 389 </slide>
331 </div> 390
332 <div class="centered" style="margin-top:2em"> 391 <slide>
333 I am centered text with a <button>Button</button> and <button disabled>Disabled</button> button. 392 <hgroup>
334 </div> 393 <h2>Message Packの型変換にかかる時間</h2>
335 </article> 394 </hgroup>
336 </slide> 395 <article>
337 396 <ul>
338 <slide class="segue dark nobackground"> 397 </ul>
339 <aside class="gdbar"><img src="images/google_developers_icon_128.png"></aside> 398 </article>
340 <hgroup class="auto-fadein"> 399 </slide>
341 <h2>Segue Slide</h2>
342 <h3>Subtitle Placeholder</h3>
343 </hgroup>
344 </slide>
345
346 <slide class="fill nobackground" style="background-image: url(images/sky.jpg)">
347 <hgroup>
348 <h2 class="white">Full Image (with Optional Header)</h2>
349 </hgroup>
350 <footer class="source white">www.flickr.com/photos/25797459@N06/5438799763/</footer>
351 </slide>
352
353 <slide class="segue dark quote nobackground">
354 <aside class="gdbar right bottom"><img src="images/google_developers_icon_128.png"></aside>
355 <article class="flexbox vleft auto-fadein">
356 <q>
357 This is an example of quote text.
358 </q>
359 <div class="author">
360 Name<br>
361 Company
362 </div>
363 </article>
364 </slide>
365
366 <slide>
367 <hgroup>
368 <h2>Slide with Iframe</h2>
369 </hgroup>
370 <article>
371 <iframe data-src="http://www.google.com/doodle4google/history.html"></iframe>
372 </article>
373 </slide>
374
375 <slide>
376 <article>
377 <iframe data-src="http://www.google.com/doodle4google/history.html"></iframe>
378 </article>
379 </slide>
380
381 <slide class="thank-you-slide segue nobackground">
382 <aside class="gdbar right"><img src="images/google_developers_icon_128.png"></aside>
383 <article class="flexbox vleft auto-fadein">
384 <h2>&lt;Thank You!&gt;</h2>
385 <p>Important contact information goes here.</p>
386 </article>
387 <p class="auto-fadein" data-config-contact>
388 <!-- populated from slide_config.json -->
389 </p>
390 </slide>
391
392 <slide class="logoslide dark nobackground">
393 <article class="flexbox vcenter">
394 <span><img src="images/google_developers_logo_white.png"></span>
395 </article>
396 </slide>
397
398 <slide class="backdrop"></slide> 400 <slide class="backdrop"></slide>
399 401
400 </slides> 402 </slides>
401 403
402 <script> 404 <script>