# HG changeset patch # User Nobuyasu Oshiro # Date 1330095636 -32400 # Node ID 669655c106eb0a83d23548e57f63f2f3d3a7bed0 # Parent d276144b815c50cf93acc3292a02a4ba6678dcac commit diff -r d276144b815c -r 669655c106eb paper/figure/conv1_for_resume.bb --- a/paper/figure/conv1_for_resume.bb Fri Feb 24 19:42:48 2012 +0900 +++ b/paper/figure/conv1_for_resume.bb Sat Feb 25 00:00:36 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./conv1_for_resume.pdf %%Creator: extractbb 20110311 -%%BoundingBox: 0 0 468 285 -%%CreationDate: Fri Feb 24 14:42:52 2012 +%%BoundingBox: 0 0 468 243 +%%CreationDate: Fri Feb 24 20:29:54 2012 diff -r d276144b815c -r 669655c106eb paper/figure/conv1_for_resume.pdf Binary file paper/figure/conv1_for_resume.pdf has changed diff -r d276144b815c -r 669655c106eb paper/resume.tex --- a/paper/resume.tex Fri Feb 24 19:42:48 2012 +0900 +++ b/paper/resume.tex Sat Feb 25 00:00:36 2012 +0900 @@ -45,9 +45,12 @@ %本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. \section{Continuation basede C (CbC)} -Continuation based C (以下 CbC) は C を基本としたプログラミング言語である. -構文は C と同じであるが, 継続(goto) やコードセグメントの導入によりループ制御や関数コールが取り除かれる. -CbC のプログラムはコードセグメントの末尾から次のコードセグメントへの継続を記述することで作られる. +CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る. +構文は C と同じであるが, ループ制御や関数コールが取り除かれる. + +\subsection{コードセグメント} +コードセグメントの記述は C の関数の構文と同じで, 型に``\_\_code'' を使うことで宣言できる. +コードセグメントへの移動は``goto'' の後にコードセグメント名と引数を並べて記述することで行える. 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. \begin{figure}[htpb] @@ -58,6 +61,13 @@ \label{fig:cs} \end{figure} +\subsection{軽量継続(light-weight continuation)} +コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る. +C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく. +だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない. + +%軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる. + \section{GCC-4.6 への実装} CbC の継続は, 環境を保持しない為軽量継続と呼ばれる. @@ -81,71 +91,16 @@ コードを追加することで Tail Call Elimination の条件をかわすようになった. これにより GCC のアップデート時に伴う専用関数の修正が不要となり, 楽な管理が行えるようになった. -\subsection{環境付き継続} -CbC には通常の C の関数からコードセグメントに継続する際, - その関数から値を戻す処理への継続を得ることができる. -これを環境付き継続という. -環境付き継続は, \verb+_CbC_environment+ と \verb+_CbC_return+ キーワードを -引数に渡しコードセグメントとして扱うことで使用できる. -実際には \verb+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている. -\begin{figure}[h] - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} -({ -__label__ _cbc_exit0; -static int retval; -void _cbc_internal_return(int retval_, - void *_envp){ - retval = retval_; - goto _cbc_exit0; -} -if (0) { - _cbc_exit0: - return retval; - } -_cbc_internal_return; -}) - \end{verbatim} - \end{minipage} - \hfill -\end{figure} -\subsubsection{環境付き継続の問題と改良} -環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである. -元々の実装では static で値の確保を行なっていた. -しかしこれではスレッドセーフではない. -そこで retval 変数の値を static thread local でスレッド毎に確保することでこの問題の解決を行った. - -\subsection{構文の追加} - -\subsubsection{``\_\_rectype'', ``selftype'' 構文} -%\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる. -通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない. -そこで, \verb+__rectype+を使うことで以下の様な宣言が行うことができる. -また, 構造体の宣言時に宣言中の構造体を指す``selftype'' 構文の追加も行った. -以下の様な宣言が行えるようになった. -この時\verb+__rectype+は funcPtr を指し, selftype は struct node を指す. -\begin{figure}[h] - \begin{minipage}[b]{.45\textwidth} - \begin{verbatim} -typedef __code (*funcPtr)(int,__rectype*); -struct node { - int num; - selftype child; -} - \end{verbatim} - \end{minipage} -\end{figure} \section{評価} -今回実装を行った GCC-4.6 と GCC-4.5 ベース, - それと Micro-C の CbC コンパイラでベンチマークを行った. +今回実装を行った CbC-GCC-4.6 と CbC-GCC-4.5 でベンチマークを行った. プログラムは Micro-C のベンチマークにも使用されるものである. -このプログラムは演算と継続を交互に行う. -引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる. -引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである. +このプログラムは演算と継続を交互に行う処理をループの回数分繰り返すというものである. +引数 1 は自作のスタックを作り, そこに継続先のコードセグメント(以下 cs)と値を確保して +渡していくプログラムである. +引数 2 は Micro-C 用に手動で最適化を行ったプログラムである. +引数 3 は C で書かれたプログラムをただ CbC へと変換したプログラムになる. また評価は \verb+x86_64+ 上の Linux で行った. -%また評価は \verb+x86_64+ 上の OS X(10.7) で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った. -%結果を図\ref{fig:conv1}の様になった(斜線は segmentation fault を示す). \begin{figure}[htpb] \begin{center} @@ -155,18 +110,61 @@ \label{fig:conv1} \end{figure} + \subsection{評価の考察} -まず, Micro-C 版より GCC 版コンパイラの方が結果が良いことが確認できる. -次に GCC-4.5 と GCC-4.6 を比較してみる. 手動で最適化を行なっている引数 2 と 3 の時は余り差は無い. -だが, 引数 1 の時は GCC-4.6 版が 32 bit, 64 bit 共に GCC-4.5 に比べて 1.5 倍以上早い. -アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて -必要最小限の継続だけを行なうプログラムとなっていた. -この結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた. +寧ろわずかだが GCC-4.6 版の方が遅くなっている. +しかし, 引数 1 の時は GCC-4.6 版 GCC-4.5 版より, 32 bit は 2.45 倍, 64 bit は 1.5 倍以上早いことが確認できる. +これは引数 2 と 3 の処理に比べて引数 1 の処理は最適化にかけにくいことが要因としてあげられる. +GCC-4.6 へとアップデートを行ったことで, より良い最適化にかかることができたと予想する. + +%この結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた. +%アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて +%必要最小限の継続だけを行なうプログラムとなっていた. + +\subsection{アセンブラコードの比較の結果} +では具体的にはどのようなより良い最適化になっているのかを調べてみる. +結果に差の出た引数 1 の時のアセンブラコードを比較した. +まず, プログラムの大まかな流れを図\ref{fig:conv1_arg0}に示す. +\begin{figure}[htpb] + \begin{center} +\scalebox{0.35}{\includegraphics{figure/conv1_arg0.pdf}} + \end{center} + \caption{conv1プログラムの挙動} + \label{fig:conv1_arg0} +\end{figure} +\newpage +四角は cs を, 矢印は継続を表している. +また, cs の中の処理は演算の部分は省いて継続に関する部分だけにしてある. +プログラムの処理は cs f から継続が始まり cs g\_h1 まで継続を行いループするという流れになる. +注意点としては, cs f\_g1, cs g\_h1 への継続は cs f\_g0, cs f\_g で自作のスタック(実態は構造体)に +関数ポインタを入れて置き継続している部分である. + +まず, CbC-GCC-4.5 のアセンブラをみてみると main 関数から``call f''により継続が行われていた. +cs f へと継続後は図\ref{fig:conv1_arg0}に示す通りの動作を行った. + +しかし, CbC-GCC-4.6 の方では main 関数からは``call g\_h1''から継続が行われ, loop check 後も +g\_h1 から継続されていた. +この処理を図\ref{fig:conv1_arg0_2}に示す. +\begin{figure}[htpb] + \begin{center} +\scalebox{0.35}{\includegraphics{figure/conv1_arg0_2.pdf}} + \end{center} + \caption{conv1プログラムの挙動( CbC-GCC-4.6 )} + \label{fig:conv1_arg0_2} +\end{figure} + +cs f から cs h まで継続の処理はインライン展開によりまとめて計算されて定数として出されていた. +cs g\_h1 と cs f\_g1 の処理がインライン展開されないのは, 関数ポインタとして扱っていた為だと思われる. + +%CbC-GCC-4.6 では cs g_h1 までの処理はインライン展開されてまとめて計算を行われていたのが確認できた. \section{今後の課題} 今回, CbC コンパイラを GCC-4.6 へとアップデートを行った. -アップデートに伴い実装の修正を行い, また CbC の記述に便利な新たな構文の追加も行うことができた. +アップデートに伴い実装の修正と, 本稿では説明していないが``\verb+__rectype+'' や``selftype''と言った +構文の追加も行えた. +また, GCC をアップデートしたことで、より協力な最適化がかかることも確認できた. +%アップデートに伴い実装の修正を行い, また CbC の記述に便利な新たな構文の追加も行うことができた. GCC 版 CbC コンパイラは細かい実装の除けば, 以後 GCC のアップデートに合わせていくだけとなる. CbC コンパイラの今後としては LLVM への実装, もしくは Google go 言語での実装の検討も行なっていく予定である.