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