Mercurial > hg > Papers > 2010 > kent-master

comparison recital-slide/slide.html @ 15:67544736317e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add slides for recital.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 17:25:21 +0900
parents
children d9b85f041908
comparison
equal deleted inserted replaced
14:064c4bd99db0 15:67544736317e
1 <?xml version="1.0" encoding="utf-8"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja">
5 <head>
6 <title>Continuation based C</title>
7 <meta name="copyright" content="Copyright &#169; 2009 KSL: Yogi KENT" />
8 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
9 <meta name="font-size-adjustment" content="1" />
10 <link rel="stylesheet" href="slidy.css"
11 type="text/css" media="screen, projection, print" />
12 <link rel="stylesheet" href="slide.css"
13 type="text/css" media="screen" />
14 <!--link rel="stylesheet" href="../Slidy/w3c-blue2.css"
15 type="text/css" media="screen, projection, print" /-->
16 <style type="text/css">
17 .right {
18 float: right;
19 width: 40%;
20 }
21 .left {
22 float: left;
23 width: 40%;
24 }
25 div.slide {
26 vertical-align: middle;
27 }
28 div.top h1 {
29 width: 70%;
30 padding: 0 1em 0;
31 text-align: center;
32 }
33 #frame {
34 position: fixed;
35 left: -1px;
36 top: -1px;
37 width: 800px;
38 height: 600px;
39 border: solid 1px red;
40 visibility: visible;
41 }
42 .speak {
43
44 visibility: hidden;
45
46 font-size: 80%;
47 line-height: 1.0;
48 position: fixed;
49 right: 0.5em;
50 bottom: 1.5em;
51 max-width: 60%;
52 background-color: green;
53 opacity: 0.90;
54 color: black;
55 -moz-border-radius: 8px;
56 -webkit-border-radius: 8px;
57 }
58 ul.narrow li {
59 margin-right: 0;
60 }
61 table {
62 border-collapse: collapse;
63 border: solid 1px black;
64 }
65 table td {
66 border: solid 1px black;
67 }
68 table th {
69 text-align: center;
70 border: solid 1px black;
71 }
72 </style>
73 <script src="slidy.js"
74 charset="utf-8" type="text/javascript">
75 </script>
76 <script type="text/javascript">
77 sizes = new Array("14pt", "15pt", "16pt", "17pt", "18pt", "19pt", "20pt", "21pt", "22pt","23pt", "24pt", "26pt", "28pt", "30pt", "32pt");
78 sizeIndex = 1;
79 mouseClickEnabled = false;
80 </script>
81 </head>
82 <body>
83 <!-- this defines the slide background -->
84 <div id="frame"></div>
85
86 <div class="background">
87 <div class="header">
88 <!-- sized and colored via CSS -->
89 </div>
90
91 <!--img id="head-icon" alt="graphic with four colored squares"
92 src="../Slidy/icon-blue.png" /-->
93
94 <div class="footer">
95 <object id="w3c-logo" data="kent-logo2.svg" type="image/svg+xml" title="KENT logo">
96 <a href="http://www.w3.org/">
97 <img alt="W3C logo" id="w3c-logo-fallback" src="kent-logo2.png" />
98 </a>
99 </object>
100
101 <!-- modify the following text as appropriate -->
102 組み込み向け言語CbCのGCC上の実装 <span style="font-size:70%;">http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html</span><br />
103 <!--Event, Location, Month Year-->
104 </div>
105 </div>
106
107 <div class="slide top">
108 <h1>組み込み向け言語Continuation based CのGCC上の実装</h1>
109 <p>
110 与儀健人 (並列信頼研究室)
111 &lt;<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>&gt;
112 </p>
113 <!--img src="../Slidy/keys.jpg" class="cover"
114 alt="W3C as letters on 3 plastic buttons from a keyboard" /-->
115 <!--h2>ゼミ, 河野研, Sep, 2009</h2-->
116 </div>
117
118 <div class="slide">
119 <h1>研究の背景</h1>
120 <ul>
121 <li>ソフトウェアは今も大規模・複雑化が続いている</li>
122 <li>しかし、ソフトウェアのバグを発見するのは難しい</li>
123 <li style="marker:none;"/>
124 <li>組込みやReal-time処理の需要も増大してる</li>
125 <li>高速な応答が要求される組込み処理にはハードウェアに近い言語が適している</li>
126 </ul>
127 <p class="subtitle">なにが問題になるのか？</p>
128 <ul>
129 <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
130 <li>現存する記述言語は状態遷移の記述に向いていない</li>
131 <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
132 </ul>
133 </div>
134
135 <div class="slide" style="font-size:95%">
136 <h1>研究目的</h1>
137 <p class="subtitle">
138 状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する
139 </p>
140 <ul>
141 <li>組込み、通信プロトコル、Real-time処理などの記述に向いている</li>
142 <li>状態遷移を直接記述するため、タブロー法での検証に有利</li>
143 <li>関数より細かく、ステートメントより大きい処理単位</li>
144 <li>細かい単位でソースコードレベルの最適化を可能にする</li>
145 </ul>
146 <p class="subtitle">条件</p>
147 <ul>
148 <li>既存のソフトウェアは膨大であり、無駄にはできない</li>
149 <li>互換性が必須条件</li>
150 <li>Cからの変換、Cへの変換ができる事が望ましい</li>
151 </ul>
152 </div>
153
154 <div class="slide">
155 <h1>Continuation based Cの提案</h1>
156 <p class="subtitle">継続を基本とする記述言語CbC</p>
157 <ul>
158 <li>環境を保持しない継続、<dfn>軽量継続</dfn>を導入</li>
159 <li>軽量継続で<em class="weak">状態遷移が明確</em>になる</li>
160 <li>関数の代わりとなる処理単位<dfn>コードセグメント</dfn></li>
161 <li>関数 &gt; コードセグメント &gt; ステートメント</li>
162 <li>for, whileなどのループも軽量継続で実現できる</li>
163 <li>Cとの相互利用のための構文<dfn>環境付き継続</dfn>
164 <ul>
165 <li>このCとの相互利用可能なCbCは<em>C with Continuation</em>と呼ばれる</li>
166 </ul>
167 </li>
168 </ul>
169 <p class="subtitle"></p>
170 </div>
171
172 <div class="slide" style="font-size:95%;">
173 <h1>コードセグメントと軽量継続の記述</h1>
174 <pre style="float:right; width-max:45%">
175 <code>typedef code (*NEXT)(int);
176 int main(int argc, char **argv) {
177 int i;
178 i = atoi(argv[1]);
179 goto factor(i, print_fact);
180 }
181 <em>code factor(int x, NEXT next)</em> {
182 goto factor0(1, x, next);
183 }
184 code factor0(int prod,int x,NEXT next) {
185 if (x &gt;= 1) {
186 goto factor0(prod*x, x-1, next);
187 } else {
188 <em>goto (*next)(prod);</em>
189 }
190 }
191 code print_fact(int value) {
192 printf("factorial = %d\n", value);
193 exit(0);
194 } </code></pre>
195 <p class="subtitle">実際のプログラム記述は？</p>
196 <ul>
197 <li>コードセグメント定義
198 <ul>
199 <li><code>codeキーワードで宣言</code></li>
200 <li>書式は関数と同じ</li>
201 </ul>
202 </li>
203 <li>軽量継続制御
204 <ul>
205 <li><code>goto</code>キーワードと引数</li>
206 <li>コードセグメントの最初に飛ぶ</li>
207 <li>コードセグメントポインタによる間接継続も可能</li>
208 </ul>
209 </li>
210 </ul>
211 </div>
212
213 <div class="slide">
214 <h1>これまでのCbC</h1>
215 <p class="subtitle"></p>
216 <dl>
217 <dt>2000</dt>
218 <dd>micro-cをベースとしたコンパイラの完成<br/>
219 x86, PowerPC, ARM, MIPS.
220 </dd>
221 <dt>2002</dt>
222 <dd>CbCを用いた分散計算</dd>
223 <dt>2005</dt>
224 <dd>CbCを用いたプログラム分割手法</dd>
225 <dt>2006</dt>
226 <dd>CbCによるSPUマシンのシミュレータ</dd>
227 <dt>2007</dt>
228 <dd>時相論理をベースとしたCbCプログラムの検証</dd>
229 <dt>2008</dt>
230 <dd>GCCをベースとしたコンパイラが開発される</dd>
231 <dt>2010</dt>
232 <dd>GCCベースコンパイラを実用レベルに拡張</dd>
233 </dl>
234 </div>
235
236 <div class="slide">
237 <h1>本研究での取り組み</h1>
238 <p class="subtitle">取り組み</p>
239 <dl>
240 <dt>First</dt>
241 <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
242 <ul>
243 <li>軽量継続の実装、これまでの制限の除去</li>
244 <li>x86アーキテクチャにて高速化を行った</li>
245 <li>PowerPCアーキテクチャでの間接継続の追加</li>
246 </ul>
247 </dd>
248 <dt>Second</dt>
249 <dd>C言語との相互利用を可能にした</dd>
250 <dt>Third</dt>
251 <dd>ソースコードメンテナンス性の向上</dd>
252 </dl>
253 </div>
254
255
256
257 <div class="slide">
258 <h1>GNU コンパイラコレクション (GCC)</h1>
259 <div style="width:50%;float:right;">
260 <p class="subtitle">GCCでのコンパイルの流れ</p>
261 <ul style="padding-left:3em">
262 <li>フロントエンド</li>
263 <li>ミドルエンド</li>
264 <li>バックエンド</li>
265 </ul>
266 </div>
267 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
268 </div>
269
270 <div class="slide">
271 <h1>GNU コンパイラコレクション (GCC)</h1>
272 <div style="width:50%;float:right;">
273 <p class="subtitle">GCCでのコンパイルの流れ</p>
274 <ul style="padding-left:3em">
275 <li>フロントエンド</li>
276 <li>ミドルエンド</li>
277 <li>バックエンド</li>
278 </ul>
279 </div>
280 <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
281 </div>
282
283
284 <div class="slide">
285 <h1>First: 軽量継続の実装</h1>
286 <p class="subtitle">軽量継続を実装するには？</p>
287 <ul>
288 <li>河野先生の作ったmicro-cは元より軽量継続を考慮して良く設計されている</li>
289 <li>micro-Cと同じ命令列を出力させるのは難しい</li>
290 <li>関数コール(call命令)ではもちろんダメ</li>
291 <li>必ず<em>jmp命令</em>を出力しないといけない</li>
292 <li>スタックを拡張してはいけない</li>
293 <li>しかしGCCでは<em>関数をベース</em>にしなければならない</li>
294 </ul>
295 <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
296 </div>
297
298 <div class="slide">
299 <h1>First: 軽量継続の実装</h1>
300 <p class="subtitle">末尾呼出ってなに？</p>
301 <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
302 <ul>
303 <li>リターンの直前の関数呼び出しのこと</li>
304 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
305 <li>元の関数に戻らないため少し高速に</li>
306 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
307 </ul>
308 </div>
309
310 <div class="slide">
311 <h1>First: 軽量継続の実装</h1>
312 <p class="subtitle">末尾呼出ってなに？</p>
313 <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
314 <ul>
315 <li>リターンの直前の関数呼び出しのこと</li>
316 <li>GCCが最適化してくれる (<em>TCE</em>)</li>
317 <li>元の関数に戻らないため少し高速に</li>
318 <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
319 </ul>
320 <p class="subtitle incremental">この末尾呼出(TCE)を強制して軽量継続を実装！</p>
321 </div>
322
323 <div class="slide">
324 <h1>First: x86における高速化</h1>
325 <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
326 <ul>
327 <li>特にx86アーキテクチャ</li>
328 <li><em class="weak">あくまで関数がベース</em>なので</li>
329 <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
330 <li>これをレジスタにすれば高速化が可能</li>
331 </ul>
332 <p class="subtitle">fastcallの導入</p>
333 <ul>
334 <li>GCCの独自拡張機能</li>
335 <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
336 </ul>
337 </div>
338
339 <div class="slide">
340 <h1>First: x86における高速化</h1>
341 <p class="subtitle">fastcallの強制</p>
342 <ul>
343 <li>通常は以下の様に定義される
344 <pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
345 </code></pre></li>
346 <li>しかしこれを毎回ユーザが書くのは変</li>
347 <li>やはりフロントエンドにて、強制するべき</li>
348 <li>型の構文木を生成した際にfastcall属性を付加</li>
349 </ul>
350 <p class="subtitle incremental">これで軽量継続制御が高速化される！</p>
351 </div>
352
353 <div class="slide">
354 <h1>First: CbCコンパイラ実装の評価</h1>
355 <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
356 <ul>
357 <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
358 <li>コンパイラの出力した実行ファイルを比較</li>
359 <li>CbCでのquicksort例題を用意</li>
360 <li>実行速度、ファイルサイズ</li>
361 <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
362 </ul>
363 <p class="subtitle">実行環境</p>
364 <ul>
365 <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
366 <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
367 <li>OSはLinuxとOS Xを使用する</li>
368 </ul>
369 </div>
370
371 <div class="slide">
372 <h1>First: 性能評価（速度比較） vs.旧ver</h1>
373 <p class="subtitle">速度測定結果(単位:秒)</p>
374 <table>
375 <tr>
376 <th></th>
377 <th colspan="2">新CbCGCC</th>
378 <th colspan="2">旧CbCGCC</th>
379 </tr>
380 <tr>
381 <td></td>
382 <th>最適化無し</th>
383 <th>最適化有り</th>
384 <th>最適化無し</th>
385 <th>最適化有り</th>
386 </tr>
387 <tr>
388 <td>x86/OS X</td>
389 <td>5.907</td>
390 <td>2.434</td>
391 <td>4.668</td>
392 <td>3.048</td>
393 </tr>
394 <tr>
395 <td>x86/Linux</td>
396 <td>5.715</td>
397 <td>2.401</td>
398 <td>4.525</td>
399 <td>2.851</td>
400 </tr>
401 </table>
402 <p class="subtitle">評価</p>
403 <ul>
404 <li>最適化無の場合は遅くなった </li>
405 <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
406 <li>fastcallの効果が十分に出ている</li>
407 </ul>
408 </div>
409
410
411 <div class="slide">
412 <h1>First: 性能評価（速度比較）</h1>
413 <p class="subtitle">速度測定結果(単位:秒)</p>
414 <table>
415 <tr>
416 <td></td>
417 <td>最適化なしのGCC</td>
418 <td>最適化付きのGCC</td>
419 <td>micro-c</td>
420 </tr>
421 <tr>
422 <td>x86/OS X</td>
423 <td>5.901</td>
424 <td>2.434</td>
425 <td>2.857</td>
426 </tr>
427 <tr>
428 <td>x86/Linux</td>
429 <td>5.732</td>
430 <td>2.401</td>
431 <td>2.254</td>
432 </tr>
433 <tr>
434 <td>ppc/OS X</td>
435 <td>14.875</td>
436 <td>2.146</td>
437 <td>4.811</td>
438 </tr>
439 <tr>
440 <td>ppc/Linux</td>
441 <td>19.793</td>
442 <td>3.955</td>
443 <td>6.454</td>
444 </tr>
445 <tr>
446 <td>ppc/PS3</td>
447 <td>39.176</td>
448 <td>5.874</td>
449 <td>11.121</td>
450 </tr>
451 </table>
452 <p class="subtitle">結果(micro-cとの比較)</p>
453 <ul>
454 <li>x86では速度にあまり差が出なかった</li>
455 <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
456 <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
457 </ul>
458 <p class="subtitle">この違いはどこから？</p>
459 <ul style="font-size:95%;">
460 <li>実際にアセンブラを出力して比較、その結果</li>
461 <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
462 <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
463 <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
464 <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
465 </ul>
466 </div>
467
468
469 <div class="slide">
470 <h1>Second: Cとの相互利用</h1>
471 <p class="subtitle">なぜそれが必要か</p>
472 <ul>
473 <li>既存のソフトウェアを無駄にはできない</li>
474 <li></li>
475 <li>ソースコード上での互換性がある事が望ましい</li>
476 <li>CbCからCの関数を呼び出すのは問題ない</li>
477 <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
478 </ul>
479 <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
480 <ul>
481 <li>軽量継続に、スタックの情報を加える</li>
482 <li>関数からのみ使用可能</li>
483 </ul>
484 </div>
485
486 <div class="slide" style="font-size:95%;">
487 <h1>Second: Cとの相互利用</h1>
488 <pre style="float:right; width-max:45%">
489 <code>typedef code (*NEXT)(int);
490 int main(int argc, char **argv) {
491 int i,a;
492 i = atoi(argv[1]);
493 <em>a = factor(i);</em>
494 printf("%d! = %d\n", a);
495 }
496 int factor(int x) {
497 NEXT ret = <em>__return</em>;
498 goto factor0(1, x, ret);
499 }
500 code
501 factor0(int prod,int x,NEXT next) {
502 if (x &gt;= 1) {
503 goto factor0(prod*x, x-1, next);
504 } else {
505 <em>goto (*next)(prod);</em>
506 }
507 }
508 </code></pre>
509 <p class="subtitle">環境付き継続の使用例</p>
510 <ul>
511 <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li>
512 <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
513 <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
514 </ul>
515 </div>
516
517 <div class="slide" style="font-size:95%;">
518 <h1>Second: Cとの相互利用</h1>
519 <p class="subtitle">内部関数を用いた実装</p>
520 <ul>
521 <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
522 <li>内部関数の中からは外の関数にgotoして脱出</li>
523 </ul>
524 <pre><code>int factor(int x) {
525 int retval;
526
527 <em class="weak">code __return(int val) {
528 retval = val;
529 goto label;
530 }
531 if (0) {
532 label:
533 return retval;
534 }</em>
535
536 NEXT ret = <em>__return</em>;
537 goto factor0(1, x, ret);
538 } </code></pre>
539 </div>
540
541
542 <div class="slide" style="font-size:95%;">
543 <h1>Second: Cとの相互利用・評価</h1>
544 <p class="subtitle">この取り組みにより</p>
545 <ul>
546 <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li>
547 <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
548 </ul>
549 </div>
550
551
552
553 <div class="slide">
554 <h1>まとめ</h1>
555 <p class="subtitle">本研究での取り組み</p>
556 <dl>
557 <dt>First</dt>
558 <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
559 <ul>
560 <li><em>軽量継続における引数順序の制限を取り除いた</em></li>
561 <li>PowerPCでの間接継続の制限を取り除いた</li>
562 <li><em>x86アーキテクチャにて高速化を行った</em></li>
563 </ul>
564 </dd>
565 <dt>Second</dt>
566 <dd><em>Cとの相互利用性の向上</em></dd>
567 <dt>Third</dt>
568 <dd>ソースコードメンテナンス性の向上</dd>
569 </dl>
570 </div>
571
572 <div class="slide" style="font-size:95%;">
573 <h1>まとめ</h1>
574 <p class="subtitle">本研究での成果</p>
575 <dl>
576 <dt>成果1</dt>
577 <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
578 <dt>成果2</dt>
579 <dd>CbCが多数のアーキテクチャに対応
580 <ul>
581 <li>20以上のアーキテクチャ</li>
582 <li>特に64bitのx86, SPUがうれしい</li>
583 </ul> </dd>
584 <dt>成果3</dt>
585 <dd>CbCの高速化
586 <ul>
587 <li>x86においてmicro-cと互角の速度を達成</li>
588 <li>PowerPCでは2倍の速度</li>
589 </ul></dd>
590 </dl>
591 </div>
592
593 <div class="slide">
594 <h1>今後の課題</h1>
595 <p class="subtitle"></p>
596 <ul>
597 <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li>
598 <li>タブロー方を用いた検証</li>
599 <li>TaskManagerのCbC実装</li>
600 </ul>
601 <p class="subtitle">CbC言語の今後</p>
602 <ul>
603 <li>オブジェクティブなCbCの設計</li>
604 <li>データセグメントの導入</li>
605 <li>スケジューラのためのリフレクション</li>
606 </ul>
607 </div>
608
609
610 <div class="slide">
611 <h1>おわり</h1>
612 <p class="subtitle">ありがとうございました</p>
613 </div>
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634 <div class="slide">
635 <h1>Continuation based C</h1>
636 <ul>
637 <li>言語仕様</li>
638 <li>return-callから軽量継続へ</li>
639 <li>コードセグメント</li>
640 <li>状態遷移に適した言語</li>
641 <li>Cとの互換性</li>
642 </ul>
643 </div>
644
645
646 <div class="slide">
647 <h1></h1>
648 <p class="subtitle"></p>
649 <ul>
650 <li></li>
651 <li></li>
652 </ul>
653 </div>
654 <div class="slide">
655 <h1></h1>
656 <p class="subtitle"></p>
657 <ul>
658 <li></li>
659 <li></li>
660 </ul>
661 </div>
662
663 <div class="slide">
664 <h1></h1>
665 <p class="subtitle"></p>
666 <ul>
667 <li></li>
668 <li></li>
669 </ul>
670 </div>
671
672
673 <div class="slide">
674 <h1>First: PowerPCでの間接継続</h1>
675 <p class="subtitle"></p>
676 <ul>
677 <li></li>
678 </ul>
679 <p class="subtitle"></p>
680 <div style="width:70%;margin:1em auto 0;">
681 <pre><code>
682 </code></pre>
683 </div>
684 </div>
685
686 <div class="slide">
687 <h1>継続制御での並列代入</h1>
688 <p class="subtitle" style="margin:0 1em 0.1em;">
689 本当に最適化で余分なコードが消えるのか？
690 </p>
691 <div style="width:45%;float:left;margin-left:1em;">
692 最適化しない場合
693 <pre style="margin-top:0"><code> _test:
694 stwu r1,-64(r1)
695 mr r30,r1
696 stw r3,88(r30)
697 stw r4,92(r30)
698 stw r5,96(r30)
699 lwz r0,92(r30)
700 stw r0,32(r30)
701 lwz r0,96(r30)
702 addic r0,r0,1
703 stw r0,28(r30)
704 lwz r0,88(r30)
705 stw r0,24(r30)
706 lwz r3,32(r30)
707 lwz r4,28(r30)
708 lwz r5,24(r30)
709 addi r1,r30,64
710 lwz r30,-8(r1)
711 lwz r31,-4(r1)
712 b L_next$stub
713 </code></pre>
714 </div>
715 <div style="width:45%;float:right;margin-right:1em;">
716 最適化した場合
717 <pre><code>
718 _test:
719 mr r0,r3
720 mr r3,r4
721 mr r4,r5
722 mr r5,r0
723 b L_next$stub
724 </code></pre>
725 </div>
726 <div style="width:50%;float:right">
727 <ul>
728 <li>r3:=a, r4:=b, r5:=c</li>
729 <li>最適化しないとload, storeが満載</li>
730 <li>最適化すると無駄なload, store命令が消えている</li>
731 <li>実際はr0を使って4命令で入れ替えられる!</li>
732 </ul>
733 </div>
734 </div>
735
736
737 <div class="slide">
738 <h1>継続とはなんなのか？</h1>
739 <p class="subtitle">継続</p>
740 <ul>
741 <li>現在の処理を続行するための情報
742 <ul>
743 <li>Cならば続く命令のアドレスや</li>
744 <li>命令に必要な値、</li>
745 <li>スタックなど、その環境全てを含む</li>
746 </ul>
747 </li>
748 </ul>
749 <p class="subtitle">CbCでの軽量継続</p>
750 <ul>
751 <li>継続からスタックに関する情報を落とす</li>
752 <li>続く命令とデータのみのシンプルな継続</li>
753 <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
754 </ul>
755 </div>
756
757 <div class="slide" style="font-size:95%;">
758 <h1>コードセグメントと軽量継続の記述</h1>
759 <pre style="float:right; width-max:45%">
760 <code>typedef code (*NEXT)(int);
761 int main(int argc, char **argv) {
762 int i;
763 i = atoi(argv[1]);
764 goto factor(i, print_fact);
765 }
766 <em>code factor(int x, NEXT next)</em> {
767 goto factor0(1, x, next);
768 }
769 code factor0(int prod,int x,NEXT next) {
770 if (x &gt;= 1) {
771 goto factor0(prod*x, x-1, next);
772 } else {
773 <em>goto (*next)(prod);</em>
774 }
775 }
776 code print_fact(int value) {
777 printf("factorial = %d\n", value);
778 exit(0);
779 } </code></pre>
780 <p class="subtitle">実際のプログラム記述は？</p>
781 <ul>
782 <li>コードセグメント定義
783 <ul>
784 <li><code>codeキーワードで宣言</code></li>
785 <li>書式は関数と同じ</li>
786 </ul>
787 </li>
788 <li>軽量継続制御
789 <ul>
790 <li><code>goto</code>キーワードと引数</li>
791 <li>コードセグメントの最初に飛ぶ</li>
792 <li>コードセグメントポインタによる間接継続も可能</li>
793 </ul>
794 </li>
795 </ul>
796 </div>
797
798 <div class="slide">
799 <h1>Cとの比較について</h1>
800 <p class="subtitle">quicksort例題をCと比較すると</p>
801 <ul>
802 <li>現在のところ、遅くなる</li>
803 <li>問題はquicksortという例題では必ずスタックが必要だということ</li>
804 <li>例題ではスタックを自前の構造体で用意している</li>
805 <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li>
806 <li>状態遷移ベースの例題を作りたい</li>
807 </ul>
808 </div>
809
810
811 <div class="slide" style="font-size:95%;">
812 <h1>fastcall</h1>
813 <p class="subtitle">実際の出力アセンブラ</p>
814 <div style="width:50%;float:left;margin-left:auto;">
815 <p style="margin:0;text-align:center">fastcallにした場合</p>
816 <pre><code>current:
817 subl $12, %esp
818 movl $30, 16(%esp)
819 movl $20, %edx
820 movl $10, %ecx
821 addl $12, %esp
822 jmp next
823 </code></pre>
824 </div>
825 <div style="width:50%;float:right;margin-right:auto;">
826 <p style="margin:0;text-align:center">normalcallの場合</p>
827 <pre><code>current:
828 pushl %ebp
829 movl %esp, %ebp
830 movl $30, 16(%ebp)
831 movl $20, 12(%ebp)
832 movl $10, 8(%ebp)
833 leave
834 jmp next
835 </code></pre>
836 </div>
837 <br clear="all" />
838 <ul>
839 <li>命令数ではほとんど変化はない</li>
840 <li>引数2つがレジスタecxとedxに格納されるようになった</li>
841 <li>そのためメモリアクセスが減る</li>
842 <li>これで高速化されるはず</li>
843 </ul>
844 </div>
845
846 <div class="slide">
847 <h1>First: 性能評価（サイズ比較）</h1>
848 <p class="subtitle">ファイルサイズの比較</p>
849 <ul>
850 <li>組み込み系ではメモリ使用量が肝心</li>
851 <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
852 <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
853 </ul>
854 <p class="subtitle">結果</p>
855 <table>
856 <tr>
857 <td></td>
858 <th>CbCGCC<br/>速度最適化</th>
859 <th>CbCGCC<br/>サイズ最適化</th>
860 <th>micro-c</th>
861 </tr>
862 <tr>
863 <td>x86/OS X</td>
864 <td>9176</td>
865 <td>9176</td>
866 <td>9172</td>
867 </tr>
868 <tr>
869 <td>x86/Linux</td>
870 <td>5752</td>
871 <td>5752</td>
872 <td>5796</td>
873 </tr>
874 <tr>
875 <td>ppc/OS X</td>
876 <td>8576</td>
877 <td>8576</td>
878 <td>12664</td>
879 </tr>
880 <tr>
881 <td>ppc/Linux</td>
882 <td>10068</td>
883 <td>10068</td>
884 <td>9876</td>
885 </tr>
886 <tr>
887 <td>ppc/PS3</td>
888 <td>6960</td>
889 <td>6728</td>
890 <td>8636</td>
891 </tr>
892 </table>
893 <p class="subtitle">結果考察</p>
894 <ul>
895 <li>x86ではファイルサイズの差がない</li>
896 <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
897 <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
898 </ul>
899 </div>
900
901 <div class="slide">
902 <h1>並列代入</h1>
903 <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
904 <ol>
905 <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
906 <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
907 </ol>
908 <p class="subtitle">問題となる例</p>
909 <pre><code>code somesegment(int a, int b, int c) {
910 /∗ do something ∗/
911 goto nextsegment(b, c, a);
912 }
913 </code></pre>
914 <ul>
915 <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
916 <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
917 <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
918 </ul>
919 <p class="subtitle">次の様に構文木を変更する</p>
920 <pre><code>code somesegment(int a, int b, int c) {
921 int a1, b1, c1;
922 /∗ do something ∗/
923 a1=a; b1=b; c1=c;
924 goto nextsegment(b1, c1, a1);
925 }
926 </code></pre>
927 <ul>
928 <li>これにより、引数順序を考える必要はなくなる</li>
929 <li>代わりに、メモリアクセスが大量に発生</li>
930 <li>しかし、これはGCCの最適化で除去される</li>
931 </ul>
932 </div>
933
934
935
936 </body>
937 </html>
938