Mercurial > hg > Papers > 2008 > kent-sigos

comparison slide.tex @ 8:0cca1c3a062d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
slide $B40@.(B?
author kent
date Wed, 23 Apr 2008 03:59:06 +0900
parents f8cf4a3ac7a8
children 5915da9d55db
comparison
equal deleted inserted replaced
7:f8cf4a3ac7a8 8:0cca1c3a062d
1 % File: slide.tex 1 % File: slide.tex
2 % Created: 月 4 21 08:00 PM 2008 J 2 % Created: 月 4 21 08:00 PM 2008 J
3 % Last Change: 月 4 21 08:00 PM 2008 J 3 % Last Change: 月 4 22 17:18 PM 2008 J
4 % 4 %
5 \documentclass[mathserif]{beamer} 5 \documentclass[mathserif]{beamer}
6 \usepackage{graphicx} 6 \usepackage{graphicx}
7 \usepackage{verbatim} 7 \usepackage{verbatim}
8 \usepackage{beamerthemesplit} 8 %\usepackage{beamerthemesplit}
9 %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf 9 %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf
10 10
11 \title{Continuation based CコンパイラのGCC-4.2による実装} 11 \title[CbC on GCC]{Continuation based CコンパイラのGCC-4.2による実装}
12 \author{与儀 健人} 12 \author{与儀 健人 \and 河野真治}
13 \institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻}
13 \date{\today} 14 \date{\today}
14 15
15 \usetheme{Boadilla} 16 \usetheme{Boadilla}
17 %\usetheme{default}
18 %\useoutertheme[subsection=false]{smoothbars}
19 %\useoutertheme{infolines}
20 \renewcommand{\kanjifamilydefault}{gt}
16 21
17 \begin{document} 22 \begin{document}
23
24 \begin{frame}
25 \titlepage
26 \end{frame}
18 27
19 \section{背景} 28 \section{背景}
20 \begin{frame} 29 \begin{frame}
21 \frametitle{研究背景} 30 \frametitle{研究背景}
22 \begin{itemize} 31 \begin{itemize}
23 \item Continuation based C (CbC) 32 \item Continuation based C (CbC)
24 \item Micro-CによるCbCコンパイラの実装 33 \item Micro-CによるCbCコンパイラの実装
25 \item 以前の論文により、GCCでコンパイラを実装する方法が示された 34 \item GCCでCbCコンパイラを実装する方法が分かっている
26 \end{itemize} 35 \end{itemize}
27 \end{frame} 36 \end{frame}
28 \begin{comment} 37 \begin{comment}
29 私たちの研究室ではCbCという言語を提案しています。 38 私たちの研究室ではCbCという言語を提案しています。
30 CbCはCから関数の概念を取り払って、代わりに継続という概念を追加したもので、.. 39 CbCはCから関数の概念を取り払って、
40 代わりにコードセグメントという処理単位を追加したものです。詳しくは
31 41
32 CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの 42 CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの
33 つかってコンパイルしていました。 43 つかってコンパイルしていました。
34 このMicro-CによるコンパイラもGCCとくらべて遜色ないほど、良いコードをはくのですが\ldots 44 このMicro-CもGCCとくらべて遜色ないほど、良いコードをはくのですが
35 細かな最適化などを比べると及ばない。 45 はやり、UNIXの標準的なコンパイラであるGCCでコンパイルしたい
36 対応アーキテクチャ 46
37 47 また、以前の論文によりTail callを使ったGCCへの実装方法がしめされた。
38 そこでGCCに移植する 48 そこで、本研究ではCbCのGCCへの実装を行いましたので、
39 以前の論文によりGCCへの実装方法がしめされた。 49 その評価と合わせて報告したいと思います
40 そこで、本研究ではGCCへの実装を行いました。
41 \end{comment} 50 \end{comment}
42 51
43 52
44 \section{CbC} 53 \section{CbC}
45 \begin{frame} 54 \begin{frame}
46 \frametitle{Continuation based Cについて} 55 \frametitle{Continuation based Cについて}
47 \begin{itemize} 56 \begin{exampleblock}{What is it?}
48 \item 57 \begin{itemize}
49 \end{itemize} 58 \item 琉球大学 並列信頼研究室で開発
50 \end{frame} 59 \item 構文はC言語とほぼ同じ
60 \item 関数の除去、コードセグメントの追加
61 \item コードセグメントを繋ぐ``継続''を導入
62 \end{itemize}
63 \end{exampleblock}
64 \end{frame}
65 \begin{comment}
66 まずは、本研究室が提案しているCbCについて少し説明します
67 構文はC言語とほぼ同じです
68 ただし Cから関数や、while,forなどのloopを除去し
69 code segmentという処理の単位を追加しています
70 また、code segmentどうしの移動(これを継続と呼びます)
71 をgotoを使って表します
72 ...聴いても分かりにくいと思うので、コード例をみましょう
73 \end{comment}
51 74
52 \begin{frame}[fragile] 75 \begin{frame}[fragile]
53 \frametitle{CbCコード例} 76 \frametitle{CbCコード例}
54 \begin{columns} 77 \begin{columns}
55 \column{.4\textwidth} 78 \column{.4\textwidth}
75 \column{.3\textwidth} 98 \column{.3\textwidth}
76 \flushright 99 \flushright
77 \includegraphics[width=\textwidth]{figures/CbC-loop.eps} 100 \includegraphics[width=\textwidth]{figures/CbC-loop.eps}
78 \end{columns} 101 \end{columns}
79 \end{frame} 102 \end{frame}
103 \begin{comment}
104 見にくい？
105 これはCのwhile文をcode segmentにしたものです
106 みての通り、_ _codeという関数の様なものが三つあります
107 この一つずつがコードセグメントです
108 最初に while_condが実行されます これは条件判定ですね
109 .. .
110 簡単でしたが、少し分かっていただけたでしょうか？
111 \end{comment}
80 112
81 \begin{frame}[fragile] 113 \begin{frame}[fragile]
82 \frametitle{実装に必要な構文} 114 \frametitle{実装に必要な構文}
83 \begin{itemize} 115 \begin{itemize}
84 \large 116 \large
85 \item コードセグメント宣言 \hfill\verb|__ code cs(int a, char *b)| 117 \item \verb|__code cs(int a, char *b)|
86 \item 継続 \hfill\verb|goto cs(10, "abc");| 118 \item \verb|goto cs(10, "abc");|
87 \end{itemize} 119 \end{itemize}
88 \end{frame} 120 \end{frame}
121 \begin{comment}
122 実装に必要な構文を説明します
123 まずはcode segmentの定義です コード例にもあったように、
124 コードセグメントの定義や宣言、コードセグメントポインタの宣言などをこの構文で行えます
125 つぎにgoto.
126 この二つを実装することでCbCを動作させることができます
127 \end{comment}
89 128
90 \section{GCC} 129 \section{GCC}
91 \begin{frame} 130 \begin{frame}
92 \frametitle{GNU Compiler Collection} 131 \frametitle{GNU Compiler Collection}
93 \begin{itemize} 132 \begin{itemize}
96 \item i386, PowerPC, MIPS, SPARC .. 135 \item i386, PowerPC, MIPS, SPARC ..
97 \item 強力な最適化機構 136 \item 強力な最適化機構
98 \item コンパイルだけでなくas, ldなどの統合環境 137 \item コンパイルだけでなくas, ldなどの統合環境
99 \end{itemize} 138 \end{itemize}
100 \end{frame} 139 \end{frame}
140 \begin{comment}
141 GNU Compiler Collection
142 .. . ですが、皆さん良くご存知だと思いますので、
143 ここではGCCの内部構造について簡単に説明します
144 \end{comment}
101 145
102 \begin{frame} 146 \begin{frame}
103 \frametitle{GCCコンパイルパス} 147 \frametitle{GCCコンパイルパス}
104 \begin{columns} 148 \begin{columns}
105 \column{.5\textwidth} 149 \column{.5\textwidth}
111 \item[RTL] 中間コード 155 \item[RTL] 中間コード
112 \end{description} 156 \end{description}
113 \end{columns} 157 \end{columns}
114 \end{frame} 158 \end{frame}
115 \begin{comment} 159 \begin{comment}
160 図は GCCがどのようにコンパイルを進めるかを表したものです
116 パーサによってGenericに変換 161 パーサによってGenericに変換
117 一般的にいう構文木、言語の構造をそのままツリーにしている 162 一般的にいう構文木、言語の構造をそのままツリーにしている
118 163
119 Static Single Assignment であるGIMPLEに変換 164 次にGEnericはGimplifyというpassによってGIMPLEに変換されます
120 ここで、ほとんど言語の違いがなくなる 165 Static Single Assignment
166 データ構造自体はGenericとかわりまりませんが、いろいろ制約が加わります
121 167
122 RTLに変換 168 RTLに変換
123 アーキテクチャに依存しないアセンブラ 169 アーキテクチャに依存しないアセンブラ
124 170
125 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる 171 * 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる
172 今回の実装でどの部分を変更したのか
173 コードセグメントや継続のパースのためにParserを修正
174 それらの構文を表すGeneric Treeを作る
175 そのTreeをRTLに変換するRTLGenerator を修正
176
177 そこで、Tailcalleliminationについて説明します
126 \end{comment} 178 \end{comment}
127 179
128 180
129 \section{Tail call} 181 \section{Tail call}
130 \begin{frame} 182 \begin{frame}
131 \frametitle{Tail call elimination} 183 \frametitle{Tail call elimination}
132 \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps} 184 \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps}
133 \end{frame} 185 \end{frame}
186 \begin{comment}
187 このTail call EliminationはGCCの最適化の一つで、
188 「関数の最後に別の関数を呼び出してる場合は、
189 callじゃなくてjmpでいいじゃないか」
190 というアイデアをもとに設計されてます
191
192 図を見ていただくと分かるとおり、ここでは関数main, A, B
193 を定義しています
194 そして関数Aでは最後に関数Bを呼び出しています
195 この場合、mainからAをよび、AからBをよび、
196 Bが終わるとAに戻り、すぐにret命令でmainにもどるという処理になります
197
198 ですが、明らかにAに戻るのは無駄でしょう
199 この無駄はAからBを呼ぶ際にcallでなくjmpを使うことで回避できます
200 これが単純なTail callの例です
201
202 ですが、たった1命令で最適化と言えるのか?
203 \end{comment}
134 204
135 \begin{frame}[fragile] 205 \begin{frame}[fragile]
136 \begin{columns}[t] 206 \begin{columns}[t]
137 \column{.5\textwidth} 207 \column{.5\textwidth}
138 \begin{verbatim} 208 \begin{verbatim}
170 \item 関数コールがreturnの直前にある 240 \item 関数コールがreturnの直前にある
171 \item 関数の返す型がcallerとcalleeで一致している 241 \item 関数の返す型がcallerとcalleeで一致している
172 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい 242 \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
173 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない 243 \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
174 \end{enumerate} 244 \end{enumerate}
175 \end{frame} 245 \center
176 246 \visible<2>{引数をすべて固定数とすることで対応}
177 \begin{frame}
178 \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
179 \end{frame} 247 \end{frame}
180 248
181 \section{実装} 249 \section{実装}
182 \begin{frame} 250 \begin{frame}
183 \frametitle{実装} 251 \frametitle{実装}
184 \begin{itemize} 252 \begin{itemize}
185 \item \_\_code トークンの追加 253 \item \_\_code トークンの追加
186 \item code segmentのパース 254 \item code segmentのパース \hfill Parser \hspace{5em}
187 \item gotoのパース 255 \item gotoのパース \hfill Parser \hspace{5em}
188 \item \alert<2>{tree/RTL変換 (expand\_call)} 256 \item code segment/goto を表すGeneric Tree
257 \item \alert<2>{tree/RTL変換 (expand\_call)} \hfill RTL Generator \hspace{5em}
189 \item その他(エラー検出など) 258 \item その他(エラー検出など)
190 \end{itemize} 259 \end{itemize}
191 \end{frame} 260 \end{frame}
261 \begin{comment}
262 トークン
263 パーサ recursive Decent
264 expand_call
265 expand_cbc_goto
266 \end{comment}
192 267
193 \begin{frame} 268 \begin{frame}
194 \frametitle{expand\_call} 269 \frametitle{expand\_call}
195 \begin{itemize} 270 \begin{exampleblock}{What is the function?}
196 \item 関数呼び出しのtreeからRTLへ変換する 271 \begin{itemize}
197 \item Tail callが可能ならその最適化を行う 272 \item 関数呼び出しのtreeからRTLへ変換する
198 \item この関数のみで1200行もある 273 \item Tail callが可能ならその最適化を行う
199 \item そのほとんどがTail call可否の判定 274 \item この関数のみで1200行もある
200 \item そして読みづらい 275 \item そのほとんどがTail call可否の判定
201 \end{itemize} 276 \item そして読みづらい
277 \end{itemize}
278 \end{exampleblock}
202 \end{frame} 279 \end{frame}
203 280
204 \begin{frame} 281 \begin{frame}
205 \frametitle{expand\_cbc\_goto} 282 \frametitle{expand\_cbc\_goto}
206 \begin{itemize} 283 \begin{exampleblock}{What is it doing?}
207 \item code segmentへのgotoを表したtreeを受け取る 284 \begin{itemize}
208 \item 確実にTail callでcode segmentにgoto 285 \item code segmentへのgotoを表したtreeをRTLに変換
209 \item 無駄なTail call可否判定を削除 286 \item 無駄なTail call可否判定を削除
210 \end{itemize} 287 \item Tail callの条件を強制
288 \item 確実にTail callを適用
289 \item 500行程度
290 \end{itemize}
291 \end{exampleblock}
211 \end{frame} 292 \end{frame}
212 293
213 294
214 \section{評価} 295 \section{評価}
215 \begin{frame}[fragile] 296 \begin{frame}[fragile]
232 \item[+fastcall] \verb|__attribute__ ((fastcall))|を付加 313 \item[+fastcall] \verb|__attribute__ ((fastcall))|を付加
233 \end{description} 314 \end{description}
234 \end{frame} 315 \end{frame}
235 316
236 \begin{frame} 317 \begin{frame}
318 \frametitle{考察}
319 \end{frame}
320
321 \begin{frame}
237 \frametitle{まとめ} 322 \frametitle{まとめ}
238 \begin{itemize} 323 \begin{block}{まとめ}
239 \item GCCにCbCコンパイラを実装 324 \begin{itemize}
240 \item そのベンチマーク 325 \item GCCにCbCコンパイラを実装
241 \end{itemize} 326 \item そのベンチマーク
242 327 \item 性能向上を確認
243 328 \end{itemize}
244 \begin{itemize} 329 \end{block}
245 \item environment 330
246 \item PPCのRTL変換不能 331 \begin{block}{TO DO}
247 \item オプションの強制 332 \begin{itemize}
248 \item SPU対応とGCCのversion 333 \item environment
249 \end{itemize} 334 \item PPCのRTL変換不能
335 \item オプションの強制
336 \item SPU対応とGCCのversion
337 \end{itemize}
338 \end{block}
339 \end{frame}
340
341 \appendix
342 \begin{frame}
343 \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
250 \end{frame} 344 \end{frame}
251 345
252 \end{document} 346 \end{document}
253 347
254 348