Mercurial > hg > Papers > 2008 > kent-sigos

--- a/Makefile	Tue Apr 22 14:13:29 2008 +0900
+++ b/Makefile	Wed Apr 23 03:59:06 2008 +0900
@@ -28,10 +28,11 @@

 $(SLIDE1).ps: $(SLIDE1).dvi
 	$(DVIPS) $^
-	if [ -x $(BKMK2UNI) ]; then\
-	  mv $@ $@.tmp;\
-	  $(BKMK2UNI) -e < $@.tmp > $@;\
-	fi
+
+	#if [ -x $(BKMK2UNI) ]; then\
+	  #mv $@ $@.tmp;\
+	  #$(BKMK2UNI) -e < $@.tmp > $@;\
+	#fi

 clean:
 	rm -f *.{aux,log,nav,out,snm}
--- a/slide.tex	Tue Apr 22 14:13:29 2008 +0900
+++ b/slide.tex	Wed Apr 23 03:59:06 2008 +0900
@@ -1,53 +1,76 @@
 %        File: slide.tex
 %     Created: 月  4 21 08:00 PM 2008 J
-% Last Change: 月  4 21 08:00 PM 2008 J
+% Last Change: 月  4 22 17:18 PM 2008 J
 %
 \documentclass[mathserif]{beamer}
 \usepackage{graphicx}
 \usepackage{verbatim}
-\usepackage{beamerthemesplit}
+%\usepackage{beamerthemesplit}
 %manual% open /usr/local/ptetex/share/texmf-dist/doc/latex/beamer/beameruserguide.pdf

-\title{Continuation based CコンパイラのGCC-4.2による実装}
-\author{与儀 健人}
+\title[CbC on GCC]{Continuation based CコンパイラのGCC-4.2による実装}
+\author{与儀 健人 \and 河野真治}
+\institute[IE Ryukyu Univ]{琉球大学大学院理工学研究科情報工学専攻}
 \date{\today}

 \usetheme{Boadilla}
+%\usetheme{default}
+%\useoutertheme[subsection=false]{smoothbars}
+%\useoutertheme{infolines}
+\renewcommand{\kanjifamilydefault}{gt}

 \begin{document}

+\begin{frame}
+  \titlepage
+\end{frame}
+
 \section{背景}
 \begin{frame}
   \frametitle{研究背景}
   \begin{itemize}
     \item Continuation based C (CbC)
     \item Micro-CによるCbCコンパイラの実装
-    \item 以前の論文により、GCCでコンパイラを実装する方法が示された
+    \item GCCでCbCコンパイラを実装する方法が分かっている
   \end{itemize}
 \end{frame}
 \begin{comment}
   私たちの研究室ではCbCという言語を提案しています。
-  CbCはCから関数の概念を取り払って、代わりに継続という概念を追加したもので、..
+  CbCはCから関数の概念を取り払って、
+  代わりにコードセグメントという処理単位を追加したものです。詳しくは

   CbCはこれまでMicro-Cというコンパイラを本研究室で独自に改良したもの
   つかってコンパイルしていました。
-  このMicro-CによるコンパイラもGCCとくらべて遜色ないほど、良いコードをはくのですが\ldots
-  細かな最適化などを比べると及ばない。
-  対応アーキテクチャ
+  このMicro-CもGCCとくらべて遜色ないほど、良いコードをはくのですが
+  はやり、UNIXの標準的なコンパイラであるGCCでコンパイルしたい

-  そこでGCCに移植する
-  以前の論文によりGCCへの実装方法がしめされた。
-  そこで、本研究ではGCCへの実装を行いました。
+  また、以前の論文によりTail callを使ったGCCへの実装方法がしめされた。
+  そこで、本研究ではCbCのGCCへの実装を行いましたので、
+  その評価と合わせて報告したいと思います
 \end{comment}


 \section{CbC}
 \begin{frame}
   \frametitle{Continuation based Cについて}
-  \begin{itemize}
-    \item
-  \end{itemize}
+  \begin{exampleblock}{What is it?}
+    \begin{itemize}
+      \item 琉球大学 並列信頼研究室で開発
+      \item 構文はC言語とほぼ同じ
+      \item 関数の除去、コードセグメントの追加
+      \item コードセグメントを繋ぐ``継続''を導入
+    \end{itemize}
+  \end{exampleblock}
 \end{frame}
+\begin{comment}
+  まずは、本研究室が提案しているCbCについて少し説明します
+  構文はC言語とほぼ同じです
+  ただし Cから関数や、while,forなどのloopを除去し
+  code segmentという処理の単位を追加しています
+  また、code segmentどうしの移動(これを継続と呼びます)
+  をgotoを使って表します
+  ...聴いても分かりにくいと思うので、コード例をみましょう
+\end{comment}

 \begin{frame}[fragile]
   \frametitle{CbCコード例}
@@ -77,15 +100,31 @@
     \includegraphics[width=\textwidth]{figures/CbC-loop.eps}
   \end{columns}
 \end{frame}
+\begin{comment}
+  見にくい？
+  これはCのwhile文をcode segmentにしたものです
+  みての通り、_ _codeという関数の様なものが三つあります
+  この一つずつがコードセグメントです
+  最初に while_condが実行されます これは条件判定ですね
+  .. .
+  簡単でしたが、少し分かっていただけたでしょうか？
+\end{comment}

 \begin{frame}[fragile]
   \frametitle{実装に必要な構文}
   \begin{itemize}
       \large
-    \item コードセグメント宣言 \hfill\verb|__ code cs(int a, char *b)|
-    \item 継続 \hfill\verb|goto cs(10, "abc");|
+    \item \verb|__code cs(int a, char *b)|
+    \item \verb|goto cs(10, "abc");|
   \end{itemize}
 \end{frame}
+\begin{comment}
+  実装に必要な構文を説明します
+  まずはcode segmentの定義です コード例にもあったように、
+  コードセグメントの定義や宣言、コードセグメントポインタの宣言などをこの構文で行えます
+  つぎにgoto.
+  この二つを実装することでCbCを動作させることができます
+\end{comment}

 \section{GCC}
 \begin{frame}
@@ -98,6 +137,11 @@
     \item コンパイルだけでなくas, ldなどの統合環境
   \end{itemize}
 \end{frame}
+\begin{comment}
+  GNU Compiler Collection
+  .. . ですが、皆さん良くご存知だと思いますので、
+  ここではGCCの内部構造について簡単に説明します
+\end{comment}

 \begin{frame}
   \frametitle{GCCコンパイルパス}
@@ -113,16 +157,24 @@
   \end{columns}
 \end{frame}
 \begin{comment}
+  図は GCCがどのようにコンパイルを進めるかを表したものです
   パーサによってGenericに変換
   一般的にいう構文木、言語の構造をそのままツリーにしている

-  Static Single Assignment であるGIMPLEに変換
-  ここで、ほとんど言語の違いがなくなる
+  次にGEnericはGimplifyというpassによってGIMPLEに変換されます
+  Static Single Assignment
+  データ構造自体はGenericとかわりまりませんが、いろいろ制約が加わります

   RTLに変換
   アーキテクチャに依存しないアセンブラ

-  実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる
+ * 実装の際にはParserにのみ変更を加えることで、アーキテクチャへの依存がなくなる
+  今回の実装でどの部分を変更したのか
+  コードセグメントや継続のパースのためにParserを修正
+  それらの構文を表すGeneric Treeを作る
+  そのTreeをRTLに変換するRTLGenerator を修正
+
+  そこで、Tailcalleliminationについて説明します
 \end{comment}


@@ -131,6 +183,24 @@
   \frametitle{Tail call elimination}
   \includegraphics[width=.9\textwidth]{figures/GCC-TailCall.eps}
 \end{frame}
+\begin{comment}
+  このTail call EliminationはGCCの最適化の一つで、
+  「関数の最後に別の関数を呼び出してる場合は、
+    callじゃなくてjmpでいいじゃないか」
+  というアイデアをもとに設計されてます
+
+  図を見ていただくと分かるとおり、ここでは関数main, A, B
+  を定義しています
+  そして関数Aでは最後に関数Bを呼び出しています
+  この場合、mainからAをよび、AからBをよび、
+  Bが終わるとAに戻り、すぐにret命令でmainにもどるという処理になります
+
+  ですが、明らかにAに戻るのは無駄でしょう
+  この無駄はAからBを呼ぶ際にcallでなくjmpを使うことで回避できます
+  これが単純なTail callの例です
+
+  ですが、たった1命令で最適化と言えるのか?
+\end{comment}

 \begin{frame}[fragile]
   \begin{columns}[t]
@@ -172,10 +242,8 @@
     \item caller側の引数サイズがcallee側の引数サイズより大きいもしくは等しい
     \item 書き込んだ引数が、その後書き込む引数を上書きしてはならない
   \end{enumerate}
-\end{frame}
-
-\begin{frame}
-  \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
+  \center
+  \visible<2>{引数をすべて固定数とすることで対応}
 \end{frame}

 \section{実装}
@@ -183,31 +251,44 @@
   \frametitle{実装}
   \begin{itemize}
     \item \_\_code トークンの追加
-    \item code segmentのパース
-    \item gotoのパース
-    \item \alert<2>{tree/RTL変換 (expand\_call)}
+    \item code segmentのパース \hfill Parser \hspace{5em}
+    \item gotoのパース \hfill Parser \hspace{5em}
+    \item code segment/goto を表すGeneric Tree
+    \item \alert<2>{tree/RTL変換 (expand\_call)} \hfill RTL Generator \hspace{5em}
     \item その他(エラー検出など)
   \end{itemize}
 \end{frame}
+\begin{comment}
+  トークン
+  パーサ recursive Decent
+  expand_call
+  expand_cbc_goto
+\end{comment}

 \begin{frame}
   \frametitle{expand\_call}
-  \begin{itemize}
-    \item 関数呼び出しのtreeからRTLへ変換する
-    \item Tail callが可能ならその最適化を行う
-    \item この関数のみで1200行もある
-    \item そのほとんどがTail call可否の判定
-    \item そして読みづらい
-  \end{itemize}
+  \begin{exampleblock}{What is the function?}
+    \begin{itemize}
+      \item 関数呼び出しのtreeからRTLへ変換する
+      \item Tail callが可能ならその最適化を行う
+      \item この関数のみで1200行もある
+      \item そのほとんどがTail call可否の判定
+      \item そして読みづらい
+    \end{itemize}
+  \end{exampleblock}
 \end{frame}

 \begin{frame}
   \frametitle{expand\_cbc\_goto}
-  \begin{itemize}
-    \item code segmentへのgotoを表したtreeを受け取る
-    \item 確実にTail callでcode segmentにgoto
-    \item 無駄なTail call可否判定を削除
-  \end{itemize}
+  \begin{exampleblock}{What is it doing?}
+    \begin{itemize}
+      \item code segmentへのgotoを表したtreeをRTLに変換
+      \item 無駄なTail call可否判定を削除
+      \item Tail callの条件を強制
+      \item 確実にTail callを適用
+      \item 500行程度
+    \end{itemize}
+  \end{exampleblock}
 \end{frame}


@@ -234,19 +315,32 @@
 \end{frame}

 \begin{frame}
+  \frametitle{考察}
+\end{frame}
+
+\begin{frame}
   \frametitle{まとめ}
-  \begin{itemize}
-    \item GCCにCbCコンパイラを実装
-    \item そのベンチマーク
-  \end{itemize}
-
+  \begin{block}{まとめ}
+    \begin{itemize}
+      \item GCCにCbCコンパイラを実装
+      \item そのベンチマーク
+      \item 性能向上を確認
+    \end{itemize}
+  \end{block}

-  \begin{itemize}
-    \item environment
-    \item PPCのRTL変換不能
-    \item オプションの強制
-    \item SPU対応とGCCのversion
-  \end{itemize}
+  \begin{block}{TO DO}
+    \begin{itemize}
+      \item environment
+      \item PPCのRTL変換不能
+      \item オプションの強制
+      \item SPU対応とGCCのversion
+    \end{itemize}
+  \end{block}
+\end{frame}
+
+\appendix
+\begin{frame}
+  \includegraphics[width=.9\textwidth]{figures/stack-tailcall.eps}
 \end{frame}

 \end{document}