--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/evaluations.tex	Fri Jan 29 15:45:41 2010 +0900
@@ -0,0 +1,225 @@
+\chapter{評価}
+\label{chp:eval}
+
+本章では本研究の評価を行う。
+まず、gccでのCbCコンパイルにおける利点と欠点を考察する。
+次にgccベースのCbCコンパイラの性能評価を行う。
+最後に、\ref{chp:task}章のTaskManagerの開発を元に、CbC言語そのものの記述性、プログラミング手法などについて考察する。
+
+
+\section{gccでを使うことの利点・欠点}
+\label{sec:merit}
+
+これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくgccが使
+用可能となった。ここでgccを用いることの利点と欠点について考察する。
+
+\subsection*{アーキテクチャ}
+
+mcにおいてはPPC,x86,MIPS,ARM,SPUなど、多数のCPUアーキテクチャをサポー
+トしてきた。しかしあるCPUに新しく対応するには多大な時間、労力が必要と
+なる。
+gccは現在、既に20を越えるCPUに対応しており、またOS毎のABIの差異も吸収
+可能である。これはgccをコンパイラとすることに最大の利点である。
+
+またそれだけでなく、gccは新しいアーキテクチャへの対応も早い。この特徴
+は、gccがフロントエンドとバックエンドという形で言語実装とアーキテクチ
+ャを分離していることからくる。一般的に新しいCPUアーキテクチャが開発さ
+れた場合にはその開発者自身がgccにコミットすることが多いため、組み込み
+用途を目的の一つとするCbCではよりその強みがます。
+
+\subsection*{最適化の恩恵}
+gccは豊富な最適化機構を備えている。
+代表的な最適化だけでもループ最適化、分岐スレッディング(jump threading)
+、共通式除去(common subexpression elimination)、命令スケジューリング
+(instruction scheduling)などがある。
+
+とくに、プログラムにおいては類似した形の式(expression)を扱うことがよく
+あるため、共通式除去は非常に効果が高い。同様の効果は同じ式を保持する変
+数を用意することでも実現できるがソースコードの修正が必要になる。
+mcにはこの最適化は含まれていないため、複雑な計算式を含むプログラムにお
+いてはgccの方が良いコンパイル結果を示すものと考えられる。
+
+%\ref{sec:}の性能評価では最適化の効果についても測定する。
+
+\subsection*{デバッガ}
+これまでCbCにはデバッガが存在しなかった。デバッガの実装には出力するア
+センブラに行番号や変数名、関数名などの情報を付加する必要があるが、gcc
+は標準でこれを行っている。そのためCのデバッガとして広く一般的に使われ
+ている gdbをそのままCbCのデバッガとして使用することが可能であり、ソフ
+トウェア開発の大きな助力となる。
+
+%ただし継続制御では``next''コマンドが使いづらいなどの操作性の問題がいく
+%つか確認している。これらは
+
+  %
+\subsection*{関数呼出しの名残り}
+上記の利点に対し、gccであるゆえの欠点も存在する。
+
+本研究による軽量継続制御の実装には\ref{chp:impl}章で説明したように関数
+の末尾最適化を利用した。それゆえコードセグメントのアセンブラ出力の命令
+列には一部関数呼び出し時のスタック処理が残ってしまうことが分かっている。
+特にレジスタの少ないアーキテクチャ、x86などではそれが顕著に現れる。
+
+mcではコードセグメントと関数は完全に別物として取り扱っており、この様な
+スタック操作はコードセグメントには現れないため、このオーバヘッドがgcc
+では不利な点である。
+
+  % スタック処理が残ってしまう
+  % 同じくcpuに特化したコンパイルに比べると
+
+
+\subsection*{互換性、ABI}
+%これは最後の考察に入れよう
+ソースコードレベルでの互換性の問題がある。
+また、継続制御のパラメタを
+  % 関数宣言
+  % 型推定
+  % ABI、特にppc
+
+
+% 最適化
+% SPUでのベクトル演算
+% gdb
+% architecture
+
+% 関数呼び出しのオーバヘッド
+% 互換性,ソースコード、ABI
+
+
+\section{性能評価}
+
+\subsection{評価手法と環境}
+性能評価として、実際にコンパイラの出力した実行ファイルを複数回実行し、
+その実効速度の平均を測定する。 CbCは実用的なプログラムの記述を目的とし
+ているので、プログラムの動作速度は性能評価として妥当だと考えられる。ま
+た速度比較の対象として、もう一つのCbCコンパイラ実装であるmicro-cベース
+のコンパイラ（以下mc）を用いる。
+
+実行するプログラムとして、クイックソートのテストプログラムを作成した。
+クイックソートは再帰呼び出しを伴うため、スタック操作が必須となる。その
+ためより多く様々なコードセグメントへの継続制御が使用されることになり、
+CbCの性能評価に適していると考えられる。クイックソートはCbCに先立ってC
+で実装し、参考文献\cite{bib:kinjo}で紹介する手法を用いてCbCに変換した。
+
+測定環境は両コンパイラが対応しているアーキテクチャ、OSから以下の5つ
+の組み合わせ[CPUアーキテクチャ/OS種別]を選択した。
+\begin{itemize}
+  \item ppc/OS X
+  \item ppc/linux
+  \item ppc/linux on PS3
+  \item x86/OS X
+  \item x86/linux
+\end{itemize}
+なお、mcはmips,armにも対応しているが、現在その処理系が用意できなかった
+ので割愛した。
+
+%gccのコンパイルでは``-O2 -fomit-pointer''の最適化を付加して測定している。
+% noreturnもON.
+% x86ではfastcallもON,
+
+\subsection{評価結果}
+実効速度の測定結果を表\ref{tab:eval}に示す。
+ただし環境毎にCPUの速度は異なるので、上下の比較には意味はない。
+\begin{table}[htpb]
+  \centering
+  \begin{tabular}{|c|c|c|c|} \hline
+    \multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
+              & \multicolumn{2}{c|}{gcc} & \multirow{2}{*}{mc} \\ \cline{2-3}
+              & 最適化なし & 最適化あり &    \\ \hline
+    x86/OS X  & 5.901 & 2.213 & 2.857 \\ \hline
+    x86/Linux & 5.869 & 2.401 & 2.254 \\ \hline
+    ppc/OS X  &14.875 & 2.146 & 4.811 \\ \hline
+    ppc/Linux &19.722 & 3.927 & 6.596 \\ \hline
+    ppc/PS3   &26.169 & 6.104 &11.536 \\ \hline
+  \end{tabular}
+  \caption{アーキテクチャ毎のgccとmcの速度比較（単位: 秒）}
+  \label{tab:eval}
+\end{table}
+% ppcのが圧倒的に早い
+% x86ではあまりさはでない
+% 最適化が効いている
+
+まずどのアーキテクチャにおいてもgccの最適化の効果が大きいことが分かる
+。 x86では約2.5倍、ppcでは4~7倍もの差が生じている。ppcの方で異様に効果
+が高いように見えるのは、関数やコードセグメントの引数渡しがレジスタベー
+スのため、最適化なしの場合には無駄なメモリアクセスが生じているためであ
+る。
+
+x86はOS XとLinuxの環境で測定を行った。OS Xではmcに比べて20\%ほど早くな
+ったことが分かる。しかし逆にLinux環境では6\%の速度低下が示された。
+どちらにおいてもppcほどの良い結果ではない。これは自由に使えるレジスタ
+が極めて少ないというx86の特殊なアーキテクチャが要因だと考えられる。そ
+のためにgccの最適化が十分に働かなかった可能性がある。逆に言うとmcが高
+いレベルでx86のアセンブラ命令を実行しているともとれる。この6\%の差は実
+用レベルでは問題なく、プログラムの構成によっては結果は逆転する事も十分
+にある。
+
+ppcではどのオペレーティングシステムでもmcに比べてgccが早いことが分かる
+。いずれも約2倍近くあるいはそれ以上に速度が向上している。これはgccの最
+適化機構が十分に働いている要因が大きい。
+
+%\subsubsection{アセンブラ比較}
+比較のため、quicksortプログラムで使われているコードセグメントを一つ例
+にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン
+トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー
+ド \ref{code:divider_s_mc} である。
+
+\lstinputlisting[
+  caption=quicksortプログラムで使われているコードセグメント,
+  label=code:divider_s]
+  {sources/quicksort_divider_s.cbc}
+\begin{minipage}[t]{.45\textwidth}
+  \lstinputlisting[
+    caption=divider\_sのgccによる出力（PowerPC）,
+    label=code:divider_s_gcc]
+    {sources/gcc_divider_s.asm}
+\end{minipage}
+\hfill
+\begin{minipage}[t]{.45\textwidth}
+  \lstinputlisting[
+    caption=divider\_sのmcによる出力（PowerPC）,
+    label=code:divider_s_mc]
+    {sources/mc_divider_s.asm}
+\end{minipage}
+
+もっとも比較しやすい箇所は\verb|s+1|の処理である。
+コード\ref{code:divider_s_gcc}のgccではこれを1命令の\verb|addi 4,4,1| 
+で行っている。 mcではこれが\verb|mr, addi, mr|という3命令になっている
+。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で
+ある。この様な細かい命令の展開が速度に差が出る要因である。
+
+またこの出力からも、x86での速度差が少ないことが頷ける。引数のほとんど
+をメモリに格納するx86では計算には一度レジスタに格納しないといけない事
+から、結局3 命令になる。そのためgccの最適化が十分には働かないのである。
+実際x86でのdivider\_sのアセンブラ出力はgccでは 24命令、mcでは18命令と
+となっている。
+
+この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度
+の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が
+言えるが、前の(手続きやメソッドにおける)環境を保持する必要がないCbCでは
+その影響がより強い。
+
+%レジスタの数は
+
+
+
+%まずどのアーキテクチャにおいても、gccを使った場合は最適化の有無で大きな差が出ていることが分かる。
+%ppc/OS Xでは倍以上の速度を示すことができた。
+%これはgccの最適化機構が十分に働いている要因が大きい。
+%特に構造体のポインタからそのメンバにアクセスする処理（Cにおけるアロー演算子である）では違いがでた。ppcではその処理のために
+%特に共通部分式除去(Common Subexpression Elimination)の処理はmcにはなく、この例題では多数その処理が適用可能な部分が出てきているためその影響があるものと思われる。
+%x86/OS Xでは約23\%ほど高速化された。
+%x86/OS Xでは約23\%、 ppc/OS Xでは最適化ありのgccはmcと比べて倍以上の速度を示すことができた。
+%しかしx86/Linuxでは逆に6\%ほど速度が低下している事が分かる。
+%この主な原因は関数呼出し時のスタック操作である。今回\ref{chp:impl}章で説明したように、継続制御の実装には末尾最適化を応用する形をとった。そのためgccとしては関数として処理しているので、一部のスタック操作（x86なら\verb|pop, push|である）が残ってしまうことが分かっている。元から継続制御用に設計されたmcではそれが存在しないため、その分の処理が速度としてに現れたものと思われる。
+%レジスタの多いアーキテクチャであるほど、速度は改善されると考えられる。
+%その中でPowerPC(ppc)での最適化ありとなしの差が非常に大きい。これはppcアセンブラの特徴であるレジスタの多さが原因の一つである。ppcの関数呼出し規約ではほとんどの引数はレジスタにのせて呼出し先に渡すことができる。
+%しかし呼出し先でさらに別の関数を呼び出す場合はそのレジスタを置き換えるため、スタックに積むなど値を保存しなければならない。この処理を最適に行うには呼び出し後の使用する変数、保持すべき変数を考慮する必要があるため、単純に全てをスタックに積む事とは違う処理が必要になる。
+
+
+\section{CbCでのプログラム}
+
+
+
+
+