Mercurial > hg > Papers > 2012 > nobu-thesis
changeset 16:9ec54b29df7c draft
add figure
line wrap: on
line diff
--- a/paper/figure/CbC_revision_graph.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/CbC_revision_graph.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./CbC_revision_graph.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 595 842 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/cbc-repo.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/cbc-repo.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./cbc-repo.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 567 313 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/cbc_replace.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/cbc_replace.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./cbc_replace.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 665 851 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/code-id.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/code-id.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./code-id.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 593 213 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/code-parse.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/code-parse.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./code-parse.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 593 246 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/codesegment.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/codesegment.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./codesegment.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 611 302 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/continuation.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/continuation.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./continuation.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 422 435 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/figure/conv1_for_resume.bb Fri Feb 24 14:46:26 2012 +0900 @@ -0,0 +1,5 @@ +%%Title: ./conv1_for_resume.pdf +%%Creator: extractbb 20110311 +%%BoundingBox: 0 0 468 285 +%%CreationDate: Fri Feb 24 14:42:52 2012 +
--- a/paper/figure/conv1_linux.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/conv1_linux.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./conv1_linux.pdf %%Creator: extractbb 20110311 -%%BoundingBox: 0 0 468 285 -%%CreationDate: Fri Feb 24 01:44:31 2012 +%%BoundingBox: 0 0 468 444 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/figure/conv1_mac.bb Fri Feb 24 14:46:26 2012 +0900 @@ -0,0 +1,5 @@ +%%Title: ./conv1_mac.pdf +%%Creator: extractbb 20110311 +%%BoundingBox: 0 0 473 495 +%%CreationDate: Fri Feb 24 14:40:08 2012 +
--- a/paper/figure/cs_prog.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/cs_prog.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./cs_prog.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 417 282 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/cs_prog_code.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/cs_prog_code.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./cs_prog_code.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 557 137 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/cs_stack.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/cs_stack.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./cs_stack.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 515 338 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/env_code.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/env_code.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./env_code.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 557 230 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/factorial.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/factorial.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./factorial.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 557 584 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/fastcall.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/fastcall.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./fastcall.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 656 459 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/gcc-repo.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/gcc-repo.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./gcc-repo.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 488 271 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/graph.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/graph.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./graph.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 726 1152 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/graph1.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/graph1.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./graph1.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 578 2039 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/graph2.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/graph2.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./graph2.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 993 1527 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/graph_2.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/graph_2.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./graph_2.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 782 1194 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/graph_gray.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/graph_gray.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./graph_gray.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 668 1106 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/ir.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/ir.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./ir.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 629 329 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/linux_conv.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/linux_conv.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./linux_conv.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 468 369 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/mac_conv.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/mac_conv.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./mac_conv.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 468 411 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/mercurial_update.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/mercurial_update.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./mercurial_update.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 482 567 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/regi-id.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/regi-id.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./regi-id.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 593 206 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/regi-node.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/regi-node.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./regi-node.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 593 180 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/ret_val_code.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/ret_val_code.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./ret_val_code.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 557 375 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/return_factorial.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/return_factorial.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./return_factorial.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 557 290 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/rid-goto.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/rid-goto.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./rid-goto.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 656 731 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/rid_goto.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/rid_goto.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./rid_goto.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 656 479 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/tail_call_flag.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/tail_call_flag.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./tail_call_flag.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 635 212 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/figure/typedefrec.bb Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/figure/typedefrec.bb Fri Feb 24 14:46:26 2012 +0900 @@ -1,5 +1,5 @@ %%Title: ./typedefrec.pdf %%Creator: extractbb 20110311 %%BoundingBox: 0 0 593 209 -%%CreationDate: Thu Feb 16 18:58:51 2012 +%%CreationDate: Fri Feb 24 14:40:08 2012
--- a/paper/resume.tex Fri Feb 24 14:31:58 2012 +0900 +++ b/paper/resume.tex Fri Feb 24 14:46:26 2012 +0900 @@ -33,14 +33,14 @@ %コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより, % Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている. コードセグメントは C の関数よりも細かな単位で, 状態を表すことができる. -その為 CbC では状態遷移記述を行うことができ, 状態探索といったモデル検査が行えると考えられている. +その為 CbC では状態遷移記述を行うことができ, 状態探索といったモデル検査等に使えると考えられている. %GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある. %当研究室には 2008 年に開発されて以来アップデートがGCC-4.5 をベースとした CbC コンパイラがある. CbC のコンパイラとしては Micro-C 版と GCC ベースのコンパイラ(以下 CbC-GCC) が開発されている. しかし, CbC-GCC はいくつかバグがあり機能の修正の余地があった. また, GCC の最新の機能を使用する為にも CbC-GCC は GCC のアップデートに合わせていく必要がある. -本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートとすると共に機能の修正 +本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に機能の修正 を行う. %本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. @@ -60,7 +60,7 @@ \section{GCC-4.6 への実装} -CbC 環境を保持しない継続は軽量継続と呼ばれる. +CbC の環境を保持しない継続は軽量継続と呼ばれる. GCC における軽量継続は Tail Call Ellimination (末尾除去)を強制することで実装する. これにより, コードセグメント間の移動を, call ではなく jmp 命令で行う. この為コードセグメントからのは戻値は無くなる. @@ -73,8 +73,8 @@ \label{fig:continue} \end{figure} -\subsection{Tail Call Elimination の矯正付与} -関数が Tail Call Elimination にかかる為には, ``呼び出し先関数と呼び出し元関数の方が一致している'' +\subsection{Tail Call Elimination の強制付与} +関数が Tail Call Elimination にかかる為には, ``呼び出し先関数と呼び出し元関数の型が一致している'' 等といった幾つかの条件をクリアしなければならない. これまでの実装ではコードセグメントに条件をクリアさせる為, 専用の関数を用意していた. しかし今回の実装ではその関数を廃止し, 末尾除去にかかるフラグを落とさせない @@ -87,16 +87,9 @@ これを環境付き継続という. 環境付き継続は, \verb+_CbC_environment+ と \verb+_CbC_return+ キーワードを 引数に渡しコードセグメントとして扱うことで使用できる. -%\verb+environment+ は 環境を表す情報を持つ. -%\verb+__return+ は環境付き継続の行き先であり, 関数の戻り値と\verb+__environment+ の二つの引数を -%持つコードセグメントになる. -%GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. -%戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:retval}) . -%実際には \verb+__return+ キーワードにより GCC 内部でlisting\ref{code:retval}のコードが生成されている. 実際には \verb+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている. \begin{figure}[h] \begin{minipage}[b]{.45\textwidth} -% \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:retval] \begin{verbatim} ({ __label__ _cbc_exit0; @@ -121,14 +114,14 @@ 環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである. 元々の実装では static で値の確保を行なっていた. しかしこれではスレッドセーフではない. -そこで retval 変数の値を static thread local で確保することでこの問題の解決を行った. +そこで retval 変数の値を static thread local でスレッド毎に確保することでこの問題の解決を行った. \subsection{構文の追加} \subsubsection{``\_\_rectype'', ``selftype'' 構文} %\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる. 通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない. -そこで, \verb+__rectype+を使うことでlisting\ref{code:rectype}の用な宣言が行うことができる. +そこで, \verb+__rectype+を使うことで以下の用な宣言が行うことができる. また, 構造体の宣言時に宣言中の構造体を指す``selftype'' 構文の追加も行った. 以下の様な宣言が行えるようになった. この時\verb+__rectype+は funcPtr を指し, selftype は struct node を指す. @@ -143,24 +136,22 @@ \end{verbatim} \end{minipage} \end{figure} -% \begin{lstlisting}[caption=\_\_rectype\, selftype 構文の使用例,label=code:rectype] -% \end{lstlisting} \section{評価} -今回実装を行った GCC-4.6 ベース と安定版である GCC-4.5 ベース, +今回実装を行った GCC-4.6 と GCC-4.5 ベース, それと Micro-C の CbC コンパイラでベンチマークを行った. プログラムは Micro-C のベンチマークにも使用されるものである. このプログラムは演算と継続を交互に行う. 引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる. 引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである. -また評価は \verb+x86_64+ 上の CentOS 5.7 で行った. +また評価は \verb+x86_64+ 上の Linux で行った. %また評価は \verb+x86_64+ 上の OS X(10.7) で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った. %結果を図\ref{fig:conv1}の様になった(斜線は segmentation fault を示す). \begin{figure}[htpb] \begin{center} -\scalebox{0.33}{\includegraphics{figure/conv1_linux.pdf}} +\scalebox{0.33}{\includegraphics{figure/conv1_for_resume.pdf}} \end{center} - \caption{各種コンパイラにより生成されたコードの速度比較} + \caption{各コンパイラにより生成されたコードの速度比較} \label{fig:conv1} \end{figure} @@ -170,7 +161,7 @@ 手動で最適化を行なっている引数 2 と 3 の時は余り差は無い. だが, 引数 1 の時は GCC-4.6 版が GCC-4.5 に比べて 1.67 倍程早い. アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて -必要最小限の継続だけを行なっていた. +必要最小限の継続だけを行なうプログラムとなっていた. アセンブラとこの結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた. \section{今後の課題}