Mercurial > hg > Papers > 2012 > nobu-thesis

comparison presen/cbc.md @ 29:24ef9b912739 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 27 Feb 2012 14:11:40 +0900
parents 1ff691fb558e
children 5ec4d6ecebd1
comparison
equal deleted inserted replaced
28:1ff691fb558e 29:24ef9b912739
154 <li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li> 154 <li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</font>により実装されている.</li>
155 155
156 Tail Call Elimination 156 Tail Call Elimination
157 --------- 157 ---------
158 <li>関数呼び出しを call ではなく jmp 命令で行う最適化</li> 158 <li>関数呼び出しを call ではなく jmp 命令で行う最適化</li>
159 <li>例えば, 如何の場合関数 f は jmp 命令で処理が移る</li> 159 <li>例えば, 如何の場合関数 g は jmp 命令で関数 f へと処理が移る</li>
160 160
161 <table width=100%> 161 <table width=100%>
162 <tr> 162 <tr>
163 <td width=50%> 163 <td width=50%>
164 <pre> 164 <pre>
218 --------- 218 ---------
219 - 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。 219 - 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。
220 - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく 220 - この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
221 必要があった。 221 必要があった。
222 - しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。 222 - しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。
223 - 専用関数がなくなったことでより今後より楽なアップデートを行なっていくことができるようになった。 223 - 専用関数がなくなったことで今後より楽なアップデートを行なっていくことができるようになった。
224 224
225 225
226 --- 226 ---
227 227
228 228
229 229
230 性能評価 230 性能評価
231 ======== 231 ========
232 232
233 <li>conv1:演算と継続を交互に繰り返すプログラム</li> 233 <li>conv1: 演算と継続を交互に繰り返すプログラム</li>
234 234
235 <table width=100%> 235 <table width=100%>
236 <caption>各コンパイラにより生成されたコードの速度比較</caption> 236 <caption>各コンパイラにより生成されたコードの速度比較</caption>
237 <td style="margin:auto; text-align:center;"> 237 <td style="margin:auto; text-align:center;">
238 <img src="./pix/conv1_for_resume.png" style="height:15em"> 238 <img src="./pix/conv1_for_resume.png" style="height:15em">
240 <td> 240 <td>
241 <img src="./pix/conv1_mac_for_presen.png" style="height:15em"> 241 <img src="./pix/conv1_mac_for_presen.png" style="height:15em">
242 </td> 242 </td>
243 </table> 243 </table>
244 244
245 <li>引数 2,3 の結果はほぼ同じだが, 引数 1 の結果には差がでている.</li> 245 <li>引数 2、3 の結果はほぼ同じ</li>
246 246 <li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早</li>
247 引数 1 の時のプログラム 247
248 --------- 248 ---
249 <li>引数が 1 の時は, 関数ポインタとして構造体に保存していたコードセグメントへと継続を行なっている</li>
250
251
252 ---
253
254 249
255 250
256 最適化の比較 251 最適化の比較
257 ======== 252 ========
258 <table width=100% border=1> 253 <table width=100% border=1>
259 <caption>それぞれの最適化にかかったプログラムの挙動</caption> 254 <caption>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</caption>
260 <tr> 255 <tr>
261 <td>最適化</td> 256 <td>最適化</td>
262 <td style="text-align:center;">状態遷移</td> 257 <td style="text-align:center;">状態遷移</td>
263 </tr> 258 </tr>
264 <tr> 259 <tr>
280 </tr> 275 </tr>
281 </table> 276 </table>
282 277
283 --- 278 ---
284 279
285 最適化の比較 280
286 ======== 281 GCC の最適化
287 <table width=100% border=1> 282 ========
288 <caption>それぞれの最適化により吐かれたアセンブラコード</caption> 283 - 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</l>
289 <tr> 284 - これは、最適化の 1 つ『インライン展開』により各コードセグメントの計算がまとめて行われる為、
290 <td width=50% style="text-align:center;">CbC-GCC-4.5</td> 285 継続する数を減らすことができるから。
291 <td width=50% style="text-align:center;">CbC-GCC-4.6</td> 286 - GCC-4.5 でもインライン展開はされていたが、GCC-4.6 はより良い最適化がかけられている。
292 </tr> 287
293 288
294 <tr> 289
295 <td> 290
296 <pre> 291 ---
297 main: 292
298 call f 293
299 : 294
300 jmp f_g0 295 GCC のアップデートに合わせる事の重要性
301 : 296 ========
302 movq $f_g1, -24(%rdx) 297 - 今回の『インライン展開』のように GCC の最適化は日々改良されていく。
303 addl $10, %edi 298 - また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。
304 movq $g_h1, -48(%rdx) 299 - それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。
305 jmp g_h1 300
306 : 301
307 movq 24(%rsi), %rdx 302
308 movq %rax, %rsi 303 ---
309 :
310 jmp *%rdx
311 :
312 movq 24(%rsi), %rdx
313 :
314 jmp *%rdx
315 </pre>
316 </td>
317 <td>
318 <pre>
319 main:
320 movq $f_g1, main_stack+2000(%rip)
321 :
322 call g_h1
323 :
324 movq 24(%rax), %rdx
325 :
326 jmp *%rdx
327 :
328 movq 24(%rax), %rdx
329 :
330 jmp *%rdx
331 </pre>
332 </td>
333 </tr>
334 <!--
335 <tr>
336 <td></td>
337 <td></td>
338 </tr>
339 -->
340
341 </table>
342 <li>関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる</li>
343 <!--
344 <li>保存していた関数ポインタへの継続はインライン展開は行われない</li>
345 -->
346
347 ---
348
349
350
351 GCC の最適化について
352 ========
353 - インライン展開の最適化がより良くなっていることができた.
354 - また, GCC では新たな最適化もアップデートが行われていく.
355
356
357 ---
358
359 304
360 305
361 306
362 まとめ 307 まとめ
363 ======== 308 ========
364 - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った. 309 - 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
365 - アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った. 310 - アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った。
366 - アップデートにかけたことで, より良い最適化がかかることを確認できた. 311 - アップデートにかけたことで, より良い最適化がかかることを確認できた。
367 - GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる. 312 - GCC ベースの CbC コンパイラは今後 GCC のアップデートに合わせていくだけとなる。
368 313
369 314
370 今後の課題 315 今後の課題
371 --------- 316 ---------
372 - LLVM ベースの CbC コンパイラの開発 317 - LLVM ベースの CbC コンパイラの開発
432 <li>CbC の実装では Parser と RTL の生成部分に手が加えられている。</li> 377 <li>CbC の実装では Parser と RTL の生成部分に手が加えられている。</li>
433 378
434 --- 379 ---
435 380
436 381
437 382 最適化の比較
438 383 ========
439 384 <table width=100% border=1>
440 385 <caption>それぞれの最適化により吐かれたアセンブラコード</caption>
441 386 <tr>
442 387 <td width=50% style="text-align:center;">CbC-GCC-4.5</td>
443 388 <td width=50% style="text-align:center;">CbC-GCC-4.6</td>
444 389 </tr>
445 390
446 391 <tr>
447 392 <td>
393 <pre>
394 main:
395 call f
396 :
397 jmp f_g0
398 :
399 movq $f_g1, -24(%rdx)
400 addl $10, %edi
401 movq $g_h1, -48(%rdx)
402 jmp g_h1
403 :
404 movq 24(%rsi), %rdx
405 movq %rax, %rsi
406 :
407 jmp *%rdx
408 :
409 movq 24(%rsi), %rdx
410 :
411 jmp *%rdx
412 </pre>
413 </td>
414 <td>
415 <pre>
416 main:
417 movq $f_g1, main_stack+2000(%rip)
418 :
419 call g_h1
420 :
421 movq 24(%rax), %rdx
422 :
423 jmp *%rdx
424 :
425 movq 24(%rax), %rdx
426 :
427 jmp *%rdx
428 </pre>
429 </td>
430 </tr>
431 <!--
432 <tr>
433 <td></td>
434 <td></td>
435 </tr>
436 -->
437
438 </table>
439 <li>関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる</li>
440 <!--
441 <li>保存していた関数ポインタへの継続はインライン展開は行われない</li>
442 -->
443
444 ---
445
446
447
448
449
450
451
452
453
454
455