|
15
|
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 © 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 <<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>>
|
|
|
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>関数 > コードセグメント > ステートメント</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 >= 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 >= 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 >= 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
|
