Mercurial > hg > Papers > 2008 > kent-dsw

comparison slide.tex @ 4:448fb638bfa0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add tex for slide.
author kent
date Tue, 01 Jul 2008 16:51:39 +0900
parents
children 3436da54f678
comparison
equal deleted inserted replaced
3:e35e566b9983 4:448fb638bfa0
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