|
4
|
1 % File: slide.tex
|
|
|
2 % Created: 火 6 24 12:51 PM 2008 J
|
|
|
3 % Last Change: 火 6 24 12:51 PM 2008 J
|
|
|
4 %
|
|
|
5 \documentclass[mathserif]{beamer}
|
|
|
6 \usepackage{graphicx}
|
|
|
7 \usepackage{verbatim}
|
|
6
|
8 \usepackage{ulem}
|
|
4
|
9 %\usepackage{beamerthemesplit}
|
|
|
10 %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf
|
|
|
11
|
|
|
12 \title[CbC on GCC]{組み込み向け低レベル言語 CbC の GCC による実装}
|
|
|
13 \author{与儀 健人 \and 河野真治}
|
|
|
14 \institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻}
|
|
|
15 \date{\today}
|
|
|
16
|
|
|
17 \usetheme{Boadilla}
|
|
|
18 %\usetheme{default}
|
|
|
19 %\useoutertheme[subsection=false]{smoothbars}
|
|
|
20 %\useoutertheme{infolines}
|
|
|
21 \renewcommand{\kanjifamilydefault}{gt}
|
|
|
22
|
|
|
23 %
|
|
|
24 %
|
|
|
25 % 研究内容
|
|
|
26 % CbC例
|
|
|
27 % GCC
|
|
|
28 % Tailcall
|
|
|
29 % 評価
|
|
|
30 % 環境付きgoto
|
|
|
31 % 今後の研究内容( 検証? REP マージャーの検証、タブロー法等 )
|
|
|
32 %
|
|
|
33 %
|
|
|
34
|
|
|
35 \begin{document}
|
|
|
36
|
|
|
37 \begin{frame}
|
|
|
38 \titlepage
|
|
|
39 \end{frame}
|
|
|
40
|
|
|
41 \section{背景}
|
|
|
42 \begin{frame}
|
|
|
43 \frametitle{研究背景}
|
|
|
44 \begin{exampleblock}{Background}
|
|
|
45 \begin{itemize}
|
|
|
46 \item 近年、情報技術の発展により、ソフトウェアは大規模
|
|
|
47 かつ複雑化する傾向にある。
|
|
|
48 \item また、日常にあふれる様々な家電にもコンピュータが使われるようになり、
|
|
|
49 組み込みソフトウェアの需要が拡大している。
|
|
|
50 % 近年、情報技術の発展により、
|
|
|
51 % ソフトウェアは大規模かつ複雑化する傾向にあります。
|
|
|
52 % おなじ理由で、市場に出回る家電には冷蔵庫や洗濯機、電子ジャーやコーヒーメーカーに
|
|
|
53 % いたるまで組み込み系のソフトおよびOSが使われるようになりました。
|
|
|
54 \end{itemize}
|
|
|
55 \end{exampleblock}
|
|
|
56 %\begin{exampleblock}{Problem}
|
|
|
57 \begin{Problem}
|
|
|
58 \begin{itemize}
|
|
|
59 \item 複雑化したソフトウェアの正当性(Validity)を保証できるか?
|
|
|
60 \item 組み込みソフトやOSの記述に最適な言語とは?
|
|
|
61 %
|
|
|
62 %
|
|
|
63 %
|
|
|
64 \end{itemize}
|
|
|
65 \end{Problem}
|
|
|
66 %\end{exampleblock}
|
|
|
67 \end{frame}
|
|
|
68
|
|
|
69 \begin{frame}
|
|
|
70 \frametitle{研究内容}
|
|
|
71 \begin{exampleblock}{Continuation based C (CbC)}
|
|
|
72 \begin{itemize}
|
|
|
73 \item Cよりも下位、アセンブラより上位の言語
|
|
|
74 \item 入力、出力インターフェイスの組み合わせから、検証を自身で表現できる
|
|
|
75 \item OS、デバイスドライバ、ハードウェアの記述が可能
|
|
|
76 \end{itemize}
|
|
|
77 \end{exampleblock}
|
|
6
|
78 \begin{exampleblock}{Recent works}
|
|
4
|
79 \begin{itemize}
|
|
|
80 \item Micro-Cによる実装 (i386,PPC,mips,spu,arm)
|
|
|
81 \item タブロー法によるCbCプログラムの検証
|
|
|
82 %タブロー法を用いたContinuation based Cプログラムの検証, 下地 篤樹, 河野 真治(琉球大学) 日本ソフトウェア科学会第23回大会論文集, Sep, 2006
|
|
|
83 \item CbCによるハードウェア記述
|
|
|
84 %検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用 , 河野 真治 (琉球大学), 電子情報通信学会VLSI設計技術研究会, March, 2008
|
|
|
85 \item 組み込みソフトウェアへの適用
|
|
|
86 %継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
|
|
|
87 \end{itemize}
|
|
|
88 \end{exampleblock}
|
|
|
89 \end{frame}
|
|
|
90
|
|
|
91 \begin{frame}
|
|
|
92 \frametitle{GCCによるCbCコンパイラの実装}
|
|
|
93 \begin{exampleblock}{Why is it needed?}
|
|
|
94 \begin{itemize}
|
|
|
95 \item 十数種のアーキテクチャへの対応が可能
|
|
|
96 \item 構文木、RTLレベルでの高度な最適化
|
|
|
97 \item
|
|
|
98 \item Tailcallを使った実装方法が示されている
|
|
|
99 \end{itemize}
|
|
|
100 \end{exampleblock}
|
|
|
101 \end{frame}
|
|
|
102
|
|
|
103 \begin{comment}
|
|
|
104 \frametitle{目標}
|
|
|
105 \begin{exampleblock}{Purposes}
|
|
|
106 \begin{itemize}
|
|
|
107 \item アセンブラとC言語の中間にあたる
|
|
|
108 \item 組み込み、OS、デバイスドライバの記述に適した、
|
|
|
109 \item 検証を自身で表現できる
|
|
|
110 \end{itemize}
|
|
|
111 \end{exampleblock}
|
|
|
112 \begin{exampleblock}{past Research}
|
|
|
113 \begin{itemize}
|
|
|
114 \item Micro-Cによる Continuation based C の開発 [Sep,2000]
|
|
|
115 \item C言語からContinuation based Cへの変換 [Jul,2001]
|
|
|
116 \item タブロー法を用いたContinuation based Cプログラムの検証 [Sep,2006]
|
|
|
117 \end{itemize}
|
|
|
118 \end{exampleblock}
|
|
|
119 \end{comment}
|
|
|
120
|
|
|
121 \begin{comment}
|
|
|
122 \frametitle{CbCの現状}
|
|
|
123 \begin{exampleblock}{Recent work}
|
|
|
124 \begin{itemize}
|
|
|
125 \item Micro-Cによる実装 (i386,PPC,mips,spu,arm)
|
|
|
126 \item タブロー法によるCbCプログラムの検証
|
|
|
127 %タブロー法を用いたContinuation based Cプログラムの検証, 下地 篤樹, 河野 真治(琉球大学) 日本ソフトウェア科学会第23回大会論文集, Sep, 2006
|
|
|
128 \item CbCによるハードウェア記述
|
|
|
129 %検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用 , 河野 真治 (琉球大学), 電子情報通信学会VLSI設計技術研究会, March, 2008
|
|
|
130 \item 組み込みソフトウェアへの適用
|
|
|
131 %継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
|
|
|
132 \end{itemize}
|
|
|
133 \end{exampleblock}
|
|
|
134 \end{comment}
|
|
|
135
|
|
|
136 \section{CbC}
|
|
|
137 \begin{frame}
|
|
|
138 \frametitle{Continuation based Cについて}
|
|
|
139 \begin{exampleblock}{What is it?}
|
|
|
140 \begin{itemize}
|
|
|
141 \item 琉球大学 並列信頼研究室で開発
|
|
|
142 \item 構文はC言語とほぼ同じ
|
|
|
143 \item 関数の撤廃、コードセグメントの導入
|
|
|
144 \item コードセグメントを繋ぐ``継続''
|
|
|
145 \end{itemize}
|
|
|
146 \end{exampleblock}
|
|
|
147 \end{frame}
|
|
|
148
|
|
|
149 \begin{frame}[fragile]
|
|
|
150 \frametitle{CbCコード例}
|
|
|
151 \begin{columns}
|
|
|
152 \column{.4\textwidth}
|
|
|
153 \flushleft \small
|
|
|
154 \begin{verbatim}
|
|
|
155 __code while_process(int total,int count){
|
|
|
156 total += count;
|
|
|
157 count++;
|
|
|
158 goto while_cond(total, count);
|
|
|
159 }
|
|
|
160 __code while_cond(int total, int count){
|
|
|
161 if ( count <= 100 ){
|
|
|
162 goto while_process(total, count);
|
|
|
163 }else{
|
|
|
164 goto while_end(total);
|
|
|
165 }
|
|
|
166 }
|
|
|
167 __code while_end(int total){
|
|
|
168 goto cs_exit(0);
|
|
|
169 }
|
|
|
170 \end{verbatim}
|
|
|
171 \column{.1\textwidth}
|
|
|
172 \column{.3\textwidth}
|
|
|
173 \flushright
|
|
|
174 a%\includegraphics[width=\textwidth]{figures/CbC-loop.eps}
|
|
|
175 \end{columns}
|
|
|
176 \end{frame}
|
|
|
177
|
|
|
178 \begin{frame}[fragile]
|
|
|
179 \frametitle{実装に必要な構文}
|
|
6
|
180 構文は以下の二つが通れば良い。
|
|
4
|
181 \begin{itemize}
|
|
|
182 \huge
|
|
|
183 \item \verb|__code cs(int a, char *b)|
|
|
|
184 \item \verb|goto cs(10, "abc");|
|
|
|
185 \end{itemize}
|
|
|
186 \end{frame}
|
|
|
187
|
|
|
188 \section{GCC}
|
|
|
189 \begin{frame}
|
|
|
190 \frametitle{GNU Compiler Collection}
|
|
|
191 \begin{itemize}
|
|
|
192 \item UNIXにおける標準的なコンパイラ
|
|
|
193 \item C, C++, java, FORTRAN, Ada ..
|
|
|
194 \item i386, PowerPC, MIPS, SPARC ..
|
|
|
195 \item 強力な最適化機構
|
|
|
196 \item コンパイルだけでなくas, ldなどの統合環境
|
|
|
197 \end{itemize}
|
|
|
198 \end{frame}
|
|
|
199
|
|
|
200 \begin{frame}
|
|
|
201 \frametitle{GCCコンパイルパス}
|
|
|
202 \begin{columns}
|
|
|
203 \column{.5\textwidth}
|
|
|
204 a%\includegraphics[width=\textwidth]{figures/GCC-pass-slide.eps}
|
|
|
205 \column{.4\textwidth}
|
|
|
206 \begin{description}
|
|
|
207 \item[Generic Tree] 構文木
|
|
|
208 \item[GIMPLE] SSA
|
|
|
209 \item[RTL] 中間コード
|
|
|
210 \end{description}
|
|
|
211 \end{columns}
|
|
|
212 \end{frame}
|
|
|
213
|
|
|
214
|
|
|
215 \section{Tail call}
|
|
6
|
216
|
|
|
217 \begin{frame}
|
|
|
218 \frametitle{Tail call elimination}
|
|
|
219 \begin{exampleblock}{Waht is it?}
|
|
|
220 \begin{itemize}
|
|
|
221 \item 関数呼び出しに関する最適化
|
|
|
222 \item call命令じゃなく、jmp命令を使用する (i386)
|
|
|
223 \item スタックを拡張せず、現在のスタックフレームを書き潰す
|
|
|
224 \end{itemize}
|
|
|
225 \end{exampleblock}
|
|
|
226 GCCへの実装ではこの最適化を利用して行う
|
|
|
227 \end{frame}
|
|
|
228
|
|
4
|
229 \begin{frame}
|
|
|
230 \frametitle{Tail call elimination}
|
|
|
231 a%\includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps}
|
|
|
232 \end{frame}
|
|
|
233
|
|
6
|
234 \begin{comment}[fragile]
|
|
4
|
235 \begin{columns}[t]
|
|
|
236 \column{.5\textwidth}
|
|
|
237 \begin{verbatim}
|
|
|
238 A:
|
|
|
239 pushl %ebp
|
|
|
240 movl %esp, %ebp
|
|
|
241 subl $24, %esp
|
|
|
242 movl 20(%ebp), %eax
|
|
|
243 addl 16(%ebp), %eax
|
|
|
244 movl %eax, 8(%esp)
|
|
|
245 movl 12(%ebp), %eax
|
|
|
246 movl %eax, 4(%esp)
|
|
|
247 movl 8(%ebp), %eax
|
|
|
248 movl %eax, (%esp)
|
|
|
249 call B
|
|
|
250 leave
|
|
|
251 ret
|
|
|
252 \end{verbatim}
|
|
|
253 \column{.5\textwidth}
|
|
|
254 \begin{verbatim}
|
|
|
255 A:
|
|
|
256 pushl %ebp
|
|
|
257 movl %esp, %ebp
|
|
|
258 movl 20(%ebp), %eax
|
|
|
259 addl %eax, 16(%ebp)
|
|
|
260 popl %ebp
|
|
|
261 jmp B
|
|
|
262 \end{verbatim}
|
|
|
263 \end{columns}
|
|
6
|
264 \end{comment}
|
|
4
|
265
|
|
|
266 \begin{frame}
|
|
|
267 \frametitle{Tail callの条件}
|
|
|
268 \begin{enumerate}
|
|
|
269 \item 関数コールがreturnの直前にある
|
|
|
270 \item 関数の返す型がcallerとcalleeで一致している
|
|
|
271 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
|
|
|
272 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
|
|
|
273 \end{enumerate}
|
|
6
|
274 %\center
|
|
|
275 %\visible<2>{引数をすべて固定数とすることで対応}
|
|
4
|
276 \end{frame}
|
|
|
277
|
|
|
278 \section{実装}
|
|
|
279 \begin{frame}
|
|
|
280 \frametitle{実装}
|
|
|
281 \begin{itemize}
|
|
|
282 \item \_\_code トークンの追加
|
|
|
283 \item code segmentのパース \hfill Parser \hspace{5em}
|
|
|
284 \item gotoのパース \hfill Parser \hspace{5em}
|
|
|
285 \item code segment/goto を表すGeneric Tree
|
|
|
286 \item \alert<2>{tree/RTL変換 (expand\_call)} \hfill RTL Generator \hspace{5em}
|
|
|
287 \item その他(エラー検出など)
|
|
|
288 \end{itemize}
|
|
|
289 \end{frame}
|
|
|
290
|
|
6
|
291 \begin{comment}
|
|
4
|
292 \frametitle{expand\_call}
|
|
|
293 \begin{exampleblock}{What is the function?}
|
|
|
294 \begin{itemize}
|
|
|
295 \item 関数呼び出しのtreeからRTLへ変換する
|
|
|
296 \item Tail callが可能ならその最適化を行う
|
|
|
297 \item この関数のみで1200行もある
|
|
|
298 \item そのほとんどがTail call可否の判定
|
|
|
299 \item そして読みづらい
|
|
|
300 \end{itemize}
|
|
|
301 \end{exampleblock}
|
|
6
|
302 \end{comment}
|
|
4
|
303
|
|
6
|
304 \begin{comment}
|
|
4
|
305 \frametitle{expand\_cbc\_goto}
|
|
|
306 \begin{exampleblock}{What is it doing?}
|
|
|
307 \begin{itemize}
|
|
|
308 \item code segmentへのgotoを表したtreeをRTLに変換
|
|
|
309 \item 無駄なTail call可否判定を削除
|
|
|
310 \item Tail callの条件を強制
|
|
|
311 \item 確実にTail callを適用
|
|
|
312 \item 500行程度
|
|
|
313 \end{itemize}
|
|
|
314 \end{exampleblock}
|
|
6
|
315 \end{comment}
|
|
4
|
316
|
|
|
317 \section{評価}
|
|
|
318 \begin{frame}[fragile]
|
|
|
319 \frametitle{評価(ベンチマーク)}
|
|
|
320 \begin{itemize}
|
|
|
321 \item 環境 i386 fedora core
|
|
|
322 \item 使用したプログラム conv1
|
|
|
323 \end{itemize}
|
|
|
324 \centering
|
|
|
325 \begin{tabular}{|l|r|r|r|r|} \hline
|
|
|
326 & ./conv1 0 & ./conv1 1 & ./conv1 2 & ./conv1 3 \\ \hline
|
|
|
327 Micro-C & 5.25 & 8.97 & 2.19 & 2.73 \\ \hline \hline
|
|
|
328 GCC & 3.69 & 4.87 & 3.08 & 3.65 \\ \hline
|
|
|
329 GCC (+omit) & 2.74 & 4.20 & 2.25 & 2.76 \\ \hline
|
|
|
330 GCC (+fastcall) & 2.70 & 3.44 & 1.76 & 2.34 \\ \hline \hline
|
|
|
331 TCC & 4.15 &122.28& 84.91&102.59\\ \hline
|
|
|
332 \end{tabular}
|
|
|
333 \begin{description}
|
|
|
334 \item[+omit] -fomit-frame-pointerオプションを付加
|
|
|
335 \item[+fastcall] \verb|__attribute__ ((fastcall))|を付加
|
|
|
336 \end{description}
|
|
|
337 \end{frame}
|
|
|
338
|
|
6
|
339 \renewcommand<>{\sout}[1]{\temporal#2{#1}{\beameroriginal{\sout}{#1}}{#1}}
|
|
|
340 \section{環境付き継続に関する考察}
|
|
|
341 \begin{frame}[fragile]
|
|
|
342 \frametitle{環境付き継続}
|
|
|
343 %\sout<2>{未実装の構文}\\
|
|
|
344 未実装の構文
|
|
|
345 %\uncover<2>{新たに実装された構文}
|
|
|
346 \begin{verbatim}
|
|
|
347 goto cs( 10 ), env;
|
|
|
348 \end{verbatim}
|
|
|
349 %env = malloc(STACKSIZE);
|
|
|
350 \begin{itemize}
|
|
|
351 \item envは現在とは別のスタック空間を表す
|
|
|
352 \begin{itemize}
|
|
|
353 \item mallocで取得
|
|
|
354 \item 中断した別スレッドのスッタクフレーム
|
|
|
355 \item 関数から継続した場合の元のスタックフレーム
|
|
|
356 \end{itemize}
|
|
|
357 \item そのenvで表される環境(スタック)へスタックフレームを変更したあと継続する \\
|
|
|
358 具体的には\verb|%ebp|を変更
|
|
|
359 \end{itemize}
|
|
|
360 \end{frame}
|
|
4
|
361
|
|
6
|
362 \begin{frame}[fragile]
|
|
|
363 \frametitle{環境付き継続}
|
|
|
364 Micro-CでのCbCでは以下の使い方が主となっている
|
|
|
365 \begin{verbatim}
|
|
|
366 int func(void){
|
|
|
367 /* something */
|
|
|
368 goto cs( __environment, __return );
|
|
|
369 }
|
|
|
370 __code cs(void *env, void *ret){
|
|
|
371 /* something */
|
|
|
372 goto ret(20), env;
|
|
|
373 }
|
|
|
374 \end{verbatim}
|
|
|
375 このように、\verb|__environment,__return|を使用して、呼び出し元関数の環境へ戻れる。
|
|
|
376 この使用方法に限れば、GCCでも実装完了。
|
|
|
377 \end{frame}
|
|
|
378
|
|
|
379 \begin{frame}
|
|
|
380 \frametitle{実装方法}
|
|
|
381
|
|
|
382 \end{frame}
|
|
|
383
|
|
|
384 \section{まとめ}
|
|
4
|
385 \begin{frame}
|
|
|
386 \frametitle{まとめ}
|
|
|
387 \begin{block}{Conclusion}
|
|
|
388 \begin{itemize}
|
|
|
389 \item GCCにCbCコンパイラを実装
|
|
|
390 \item そのベンチマークによる性能向上の確認
|
|
6
|
391 \item 環境付き継続の実装及び問題点の考察
|
|
4
|
392 \end{itemize}
|
|
|
393 \end{block}
|
|
|
394
|
|
|
395 \begin{block}{TO DO}
|
|
|
396 \begin{itemize}
|
|
6
|
397 \item environmentの強化
|
|
4
|
398 \item PPCのRTL変換不能
|
|
|
399 \item オプションの強制
|
|
|
400 \item SPU対応とGCCのversion
|
|
|
401 \end{itemize}
|
|
|
402 \end{block}
|
|
|
403 \end{frame}
|
|
|
404
|
|
|
405
|
|
|
406 %\begin{thebibliography}
|
|
|
407 %\item[CbC]{} 河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
|
|
|
408 %\end{thebibliography}
|
|
|
409 %継続を持つCの下位言語によるシステム記述
|
|
|
410 %河野真治 , 日本ソフトウェア科学会第17回大会論文集, September, 2000 (in Japanese)
|
|
|
411 %継続を基本とするプログラム単位を用いた組込みシステム開発 , 河野 真治 (琉球大学), 組み込みソフトウェア工学シンポジウム2003, Oct,2003
|
|
|
412
|
|
6
|
413 %\appendix
|
|
|
414 %\begin{frame}
|
|
|
415 %a%\includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
|
|
|
416 %\end{frame}
|
|
4
|
417
|
|
|
418 \end{document}
|
|
|
419
|
|
|
420
|
|
|
421
|
|
|
422
|
