Papers/2010/kent-master: evaluations.tex comparison

comparison evaluations.tex @ 2:50e23a4b2f40

add many files.

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 05 Feb 2010 10:00:05 +0900
parents	aa09c34b90d3
children	30c102343b37

comparison

equal deleted inserted replaced

-:aa09c34b90d3
+:50e23a4b2f40
-\chapter{評価}
+\chapter{評価・考察}
 \label{chp:eval}
 本章では本研究の評価を行う。
 まず、gccでのCbCコンパイルにおける利点と欠点を考察する。
 次にgccベースのCbCコンパイラの性能評価を行う。
 最後に、\ref{chp:task}章のTaskManagerの開発を元に、CbC言語そのものの記述性、プログラミング手法などについて考察する。
+\section{gccを使うことの利点・欠点}
-\section{gccでを使うことの利点・欠点}
 \label{sec:merit}
-これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくgccが使
+これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくgccが
-用可能となった。ここでgccを用いることの利点と欠点について考察する。
+CwCのフルセットとして使用可能となった。ここでgccを用いることの利点と欠
+点について考察する。
 \subsection*{アーキテクチャ}
 mcにおいてはPPC,x86,MIPS,ARM,SPUなど、多数のCPUアーキテクチャをサポー
 トしてきた。しかしあるCPUに新しく対応するには多大な時間、労力が必要と
 特にレジスタの少ないアーキテクチャ、x86などではそれが顕著に現れる。
 mcではコードセグメントと関数は完全に別物として取り扱っており、この様な
 スタック操作はコードセグメントには現れないため、このオーバヘッドがgcc
 では不利な点である。
+% TODO: 取り除くには…
 % スタック処理が残ってしまう
 % 同じくcpuに特化したコンパイルに比べると
 \section{性能評価}
+\subsection{評価項目、比較対象}
+コンパイラの出力した実行ファイルを複数回実行し、その実効速度を測定する
+。CbCは実用的なプログラムの記述を目的としているので、プログラムの動作
+速度は性能の評価として妥当だと考えられる。
+またもう一つの項目として、出力した実行ファイルのファイルサイズも評価す
+る。一般的なプログラムではファイルサイズを気にすることは少ないが、CbC
+の用途には組み込みなども考えられているため、ファイルサイズの影響は大き
+い。比較する際はstripコマンドを用いてデバグ情報等を取り除いている。
+%SPUはm..
+実効速度、ファイルサイズの比較対象として2つ用意した。
+一つは過去の研究でのGCCベースコンパイラ、つまり今回の改善を含めてない
+ものである。こちらはGCCのバージョン4.2.3をベースとしている。
+もう一つの比較対象にはmicro-cベースのコンパイラ（以下mc）を用いる。
+さらにGCCでは最適化による効果も評価するため、
+\begin{inparaenum}[\itshape 1)\ttfamily]
+\item 最適化なし ``-O0''
+\item 速度最適化 ``-O2 -fomit-framepointer''
+\item サイズ最適化 ``-Os''
+\end{inparaenum}
+についてもそれぞれ比較する。
 \subsection{評価手法と環境}
-性能評価として、実際にコンパイラの出力した実行ファイルを複数回実行し、
-その実効速度の平均を測定する。 CbCは実用的なプログラムの記述を目的とし
-ているので、プログラムの動作速度は性能評価として妥当だと考えられる。ま
-た速度比較の対象として、もう一つのCbCコンパイラ実装であるmicro-cベース
-のコンパイラ（以下mc）を用いる。
 実行するプログラムとして、クイックソートのテストプログラムを作成した。
 クイックソートは再帰呼び出しを伴うため、スタック操作が必須となる。その
-ためより多く様々なコードセグメントへの継続制御が使用されることになり、
+ためより様々な状態でコードセグメントへの継続制御が使用されることになり、
 CbCの性能評価に適していると考えられる。クイックソートはCbCに先立ってC
-で実装し、参考文献\cite{bib:kinjo}で紹介する手法を用いてCbCに変換した。
+で実装し、参考文献\cite{bib:kinjo-2005}で紹介する手法を用いてCbCに変換
+した。このプログラムは付録\ref{apx:quicksort}に添付する。
-測定環境は両コンパイラが対応しているアーキテクチャ、OSから以下の5つ
-の組み合わせ[CPUアーキテクチャ/OS種別]を選択した。
+測定環境は両コンパイラが対応しているアーキテクチャ、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-4.2.3ベースコンパイラはppcでは実行不能であ
+ったためx86のみとなる。
+各評価マシンの詳細は付録\ref{sec:}に掲載する。
 %gccのコンパイルでは``-O2 -fomit-pointer''の最適化を付加して測定している。
 % noreturnもON.
 % x86ではfastcallもON,
 \subsection{評価結果}
-実効速度の測定結果を表\ref{tab:eval}に示す。
+実効速度の測定結果を表\ref{tab:eval-speed}に示す。
-ただし環境毎にCPUの速度は異なるので、上下の比較には意味はない。
+ただし環境毎にCPU速度は異なるので、上下の比較には意味はない。
+% -O2で約10秒になる要素数を選んだ方がいいかもしれない
+\begin{table}[htpb]
+\centering
+\begin{tabular}{|c|c|c|c|c|} \hline
+\multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
+& \multicolumn{3}{c|}{gcc} & \multirow{2}{*}{mc} \\ \cline{2-4}
+&最適化なし&速度最適化&サイズ最適化&  \\ \hline
+x86/OS X  & 5.901 & 2.434 & 2.785 & 2.857 \\ \hline
+x86/Linux & 5.732 & 2.401 & 2.876 & 2.254 \\ \hline
+ppc/OS X  &14.875 & 2.146 & 2.170 & 4.811 \\ \hline
+ppc/Linux &19.793 & 3.955 & 4.013 & 6.454 \\ \hline
+ppc/PS3   &39.176 & 5.874 & 6.111 &11.121 \\ \hline
+\end{tabular}
+\caption{アーキテクチャ毎のgccとmcの速度比較（単位: 秒）}
+\label{tab:eval-speed}
+\end{table}
+次に実行ファイルのstrip前のファイルサイズを表\ref{tab:eval-nostrip}
+に、strip後のファイルサイズを表\ref{tab:eval-strip}に示す。
+\begin{table}[htpb]
+\centering
+\begin{tabular}{|c|c|c|c|c|c|} \hline
+\multirow{3}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
+& \multicolumn{4}{c|}{GCC} & \multirow{3}{*}{mc} \\ \cline{2-5}
+& \multicolumn{2}{c|}{デバグ情報(-g)付き} & \multicolumn{2}{c|}{デバグ情報なし} &  \\ \cline{2-5}
+& -O2 & -Os & -O2 & -Os & \\ \hline
+x86/OS X  & 11100 & 11100 &  9804 &  9804 & 11136 \\ \hline
+x86/Linux & 18444 & 17310 &  8216 &  8214 &  9844 \\ \hline
+ppc/OS X  & 10392 & 10392 &  9172 &  9172 & 14396 \\ \hline
+ppc/Linux & 25138 & 23876 & 13030 & 13028 & 15453 \\ \hline
+ppc/PS3   & 22142 & 20452 &  9906 &  9672 & 15463 \\ \hline
+\end{tabular}
+\caption{実行ファイルのファイルサイズ比較 not stripped（単位: bytes）}
+\label{tab:eval-nostrip}
+\end{table}
 \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}
+& \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{mc} \\ \cline{2-3}
-& 最適化なし & 最適化あり &    \\ \hline
+& -O2 & -Os & \\ \hline
-x86/OS X  & 5.901 & 2.213 & 2.857 \\ \hline
+x86/OS X  &  9176 &  9176 &  9172 \\ \hline
-x86/Linux & 5.869 & 2.401 & 2.254 \\ \hline
+x86/Linux &  5752 &  5752 &  5796 \\ \hline
-ppc/OS X  &14.875 & 2.146 & 4.811 \\ \hline
+ppc/OS X  &  8576 &  8576 & 12664 \\ \hline
-ppc/Linux &19.722 & 3.927 & 6.596 \\ \hline
+ppc/Linux & 10068 & 10068 &  9876 \\ \hline
-ppc/PS3   &26.169 & 6.104 &11.536 \\ \hline
+ppc/PS3   &  6960 &  6728 &  8636 \\ \hline
 \end{tabular}
-\caption{アーキテクチャ毎のgccとmcの速度比較（単位: 秒）}
+\caption{実行ファイルのファイルサイズ比較 stripped（単位: bytes）}
-\label{tab:eval}
+\label{tab:eval-strip}
 \end{table}
+最後に、本研究での実装GCC-4.4.2と以前のバージョンGCC-4.2.3との比較であ
+る。こちらはx86のみ、最適化も-Osは対応していない。
+\begin{table}[htpb]
+\centering
+\begin{tabular}{|c|c|c|c|c|} \hline
+\multirow{2}{*}{ \backslashbox{CPU/OS}{コンパイラ}  }
+& \multicolumn{2}{c|}{CbC on GCC-4.4.2} &
+\multicolumn{2}{c|}{CbC on GCC-4.2.3} \\ \hline
+&  -O0  &  -O2  &  -O0  &  -O2  \\ \hline
+x86/OS X  & 5.907 & 2.434 & 4.668 & 3.048 \\ \hline
+x86/Linux & 5.715 & 2.401 & 4.525 & 2.851 \\ \hline
+\end{tabular}
+\caption{GCC-4.2.3ベースとGCC-4.4.2ベースの速度比較（単位: 秒）}
+\label{tab:eval-speed}
+\end{table}
 % ppcのが圧倒的に早い
 % x86ではあまりさはでない
 % 最適化が効いている
+% TODO: ファイルサイズの比較
-まずどのアーキテクチャにおいてもgccの最適化の効果が大きいことが分かる
+%       SPUに送るのに有利
-。 x86では約2.5倍、ppcでは4~7倍もの差が生じている。ppcの方で異様に効果
+% コンパイルにかかる時間？
-が高いように見えるのは、関数やコードセグメントの引数渡しがレジスタベー
-スのため、最適化なしの場合には無駄なメモリアクセスが生じているためであ
+\subsection{評価結果考察}
-る。
+% stripするとx86はサイズに変化がない
+\subsubsection{速度面}
-x86はOS XとLinuxの環境で測定を行った。OS Xではmcに比べて20\%ほど早くな
+まずは速度面からこの測定結果を考察する。
-ったことが分かる。しかし逆にLinux環境では6\%の速度低下が示された。
-どちらにおいてもppcほどの良い結果ではない。これは自由に使えるレジスタ
+まずどのアーキテクチャにおいても、GCCの最適化が大きな速度差を生み出し
-が極めて少ないというx86の特殊なアーキテクチャが要因だと考えられる。そ
+ている事が分かる。最適化なしと速度最適化を比較すると、x86では2.4倍、
-のためにgccの最適化が十分に働かなかった可能性がある。逆に言うとmcが高
+ppcでは5〜7倍もの差が生じている。
-いレベルでx86のアセンブラ命令を実行しているともとれる。この6\%の差は実
+ただしppcのこの以上な速度差は\ref{ssec:}並列代入で示した様に、継続の引
-用レベルでは問題なく、プログラムの構成によっては結果は逆転する事も十分
+数を全て一時変数に入れていることが大きい。その場合最適化なしではすべて
-にある。
+の引数を一度メモリに確保するので、その分逆に遅くなっているのだと考えら
+れる。しかしながら最適化を有効にすることでそのメモリへの一時変数の確保
-ppcではどのオペレーティングシステムでもmcに比べてgccが早いことが分かる
+も解消されるということが分かった。
-。いずれも約2倍近くあるいはそれ以上に速度が向上している。これはgccの最
-適化機構が十分に働いている要因が大きい。
+x86はOS XとLinuxの環境で測定を行った。速度最適化のGCCとmcを比べると、
+OS Xではmcに比べて20\%ほど早くなった事が分かる。しかし逆にLinux環境で
+は6\%の速度低下が示された。どちらにしてもppcほどの良い結果ではない。こ
+れは自由に使えるレジスタが極めて少ないというx86の特殊なアーキテクチャ
+が要因だと考えられる。そのためGCCの最適化が十分に機能できなかった可能
+性がある。この6\%の差は実用レベルでは問題なく、プログラムの構成によっ
+ては結果は逆転する事も十分にある。
+ppcにおいてはどのオペレーティングシステムでも、速度最適化を使ったGCCは
+mcに比べて早い事が分かる。いずれも約2倍、もしくはそれ以上に速度が向上
+している。これはGCCの最適化機構が十分に働いている要因が大きい。
+\subsubsection{アセンブラ比較}
+実際に出力されたアセンブラから速度向上の要因を確かめるため、quicksort
+プログラムで使用されているコードセグメントを一つ例に挙げる。CbCのプロ
+グラムソースがコード \ref{code:divider-e}である。このコードセグメント
+の速度最適化を使ったGCCによる出力がコード\ref{code:divider-e-gcc}、mc
+による出力がコード \ref{code:divider-e-mc}である。
+どちらもアーキテクチャはppcである。
+%まずどのアーキテクチャにおいても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プログラムで使われているコードセグメントを一つ例
+%比較のため、quicksortプログラムで使われているコードセグメントを一つ例
-にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン
+%にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン
-トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー
+%トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー
-ド \ref{code:divider_s_mc} である。
+%ド \ref{code:divider_s_mc} である。
+%
 \lstinputlisting[
 caption=quicksortプログラムで使われているコードセグメント,
-label=code:divider_s]
+label=code:divider-e]
-{sources/quicksort_divider_s.cbc}
+{sources/divider-e.cbc}
 \begin{minipage}[t]{.45\textwidth}
 \lstinputlisting[
-caption=divider\_sのgccによる出力（PowerPC）,
+caption=divider\_eのgccによる出力(ppc),
-label=code:divider_s_gcc]
+label=code:divider-e-gcc]
-{sources/gcc_divider_s.asm}
+{sources/divider-e-gcc.asm}
 \end{minipage}
 \hfill
 \begin{minipage}[t]{.45\textwidth}
 \lstinputlisting[
-caption=divider\_sのmcによる出力（PowerPC）,
+caption=divider\_eのmcによる出力(ppc),
-label=code:divider_s_mc]
+label=code:divider-e-mc]
-{sources/mc_divider_s.asm}
+{sources/divider-e-mc.asm}
 \end{minipage}
-もっとも比較しやすい箇所は\verb|s+1|の処理である。
+もっとも比較しやすい箇所は\verb|e-1|の処理である。
-コード\ref{code:divider_s_gcc}のgccではこれを1命令の\verb|addi 4,4,1|
+コード\ref{code:divider-e-gcc}のgccではこれを1命令の\verb|addi 5,5,-1|
 で行っている。 mcではこれが\verb|mr, addi, mr|という3命令になっている
 。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で
 ある。この様な細かい命令の展開が速度に差が出る要因である。
-またこの出力からも、x86での速度差が少ないことが頷ける。引数のほとんど
+またこのppcのアセンブラからも、x86での速度差が少ないことが頷ける。引数
-をメモリに格納するx86では計算には一度レジスタに格納しないといけない事
+のほとんどをメモリに格納するx86では、計算のために一度レジスタに格納し
-から、結局3 命令になる。そのためgccの最適化が十分には働かないのである。
+ないといけないことから、この命令は結局3命令になるはずであり、実際にx86
-実際x86でのdivider\_sのアセンブラ出力はgccでは 24命令、mcでは18命令と
+ではGCC,mc共にそのようなコードが出力されていた。
-となっている。
 この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度
 の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が
-言えるが、前の(手続きやメソッドにおける)環境を保持する必要がないCbCでは
+言えるが、（手続きやメソッドにおける）前の環境を保持する必要がないCbC
-その影響がより強い。
+ではその影響がより強い。
 %レジスタの数は
+\subsubsection{ファイルサイズ}
-%まずどのアーキテクチャにおいても、gccを使った場合は最適化の有無で大きな差が出ていることが分かる。
+次に、実行ファイルのファイルサイズの面から考察する。
-%ppc/OS Xでは倍以上の速度を示すことができた。
-%これはgccの最適化機構が十分に働いている要因が大きい。
+実行ファイルのファイルサイズは組み込み用途のプログラムには重要な要素と
-%特に構造体のポインタからそのメンバにアクセスする処理（Cにおけるアロー演算子である）では違いがでた。ppcではその処理のために
+なる。多くの場合、組み込み機器では大容量のメモリは用意されておらず、
-%特に共通部分式除去(Common Subexpression Elimination)の処理はmcにはなく、この例題では多数その処理が適用可能な部分が出てきているためその影響があるものと思われる。
+OSも存在しないため仮想記憶の概念がない。そのためメモリに乗り切らないプ
-%x86/OS Xでは約23\%ほど高速化された。
+ログラムはそもそも実行不能である。
-%x86/OS Xでは約23\%、 ppc/OS Xでは最適化ありのgccはmcと比べて倍以上の速度を示すことができた。
-%しかしx86/Linuxでは逆に6\%ほど速度が低下している事が分かる。
+まず、評価の主な特徴として、strip後のファイルサイズ\ref{tab:eval-strip}
-%この主な原因は関数呼出し時のスタック操作である。今回\ref{chp:impl}章で説明したように、継続制御の実装には末尾最適化を応用する形をとった。そのためgccとしては関数として処理しているので、一部のスタック操作（x86なら\verb|pop, push|である）が残ってしまうことが分かっている。元から継続制御用に設計されたmcではそれが存在しないため、その分の処理が速度としてに現れたものと思われる。
+をみると、x86ではmcとGCCでほとんど差がない事が分かる。この環境では速度
-%レジスタの多いアーキテクチャであるほど、速度は改善されると考えられる。
+面でも大きな差はなく、mcの精度の良さがわかる。
-%その中でPowerPC(ppc)での最適化ありとなしの差が非常に大きい。これはppcアセンブラの特徴であるレジスタの多さが原因の一つである。ppcの関数呼出し規約ではほとんどの引数はレジスタにのせて呼出し先に渡すことができる。
-%しかし呼出し先でさらに別の関数を呼び出す場合はそのレジスタを置き換えるため、スタックに積むなど値を保存しなければならない。この処理を最適に行うには呼び出し後の使用する変数、保持すべき変数を考慮する必要があるため、単純に全てをスタックに積む事とは違う処理が必要になる。
+デバグ情報のあり／なし／strip後との比較で大きな差が出ているのは全て
+Linux（PS3含む）である。Linuxでは実行ファイルのファイル形式にELFを用い
+ている。この形式はLinuxの標準的な実行形式で、様々な研究に用いられてい
-\section{CbCでのプログラム}
+るため、Mach-Oと比べて付加機能が豊富である。そのため多くの情報が含まれ
+ているのだと考えられる。
+Linuxは組み込み用途に多く用いられているため、極端にメモリの制限された
+環境ではデバグが困難になることが考えられる。
+また興味深い特徴として、-O2と-Osの差がppc/PS3以外は全くないことも分か
+った。 -Osは-O2の最適化機能から、ファイルサイズが大きくなるものを除外
+したものである。評価結果には-Osによるファイルサイズの減少はほとんどな
+く、しかし速度は少々遅くなっている。このことからCbCによるプログラムで
+は-Osを用いる必要はなく、-O2で十分であることが分かった。
+% ELF, Mach-O
+% o OS Xはデバグ情報が少ない。逆か、ELFが多いのか
+% o x86でほぼ同じサイズ
+%   - mcがんばってる
+% o -Osと-O2が変わらない、でも速度は-O2
+% o PS3とLinuxで大きく違う
+%
+\subsubsection{以前のバージョンとの速度比較}\label{sec:compare2old}
+古いバージョンとの速度差についても考察を重ねる。
+実行環境にppcが存在しないのは、\ref{sec:impl-indirect}節における問題の
+ためである。今回用意したプログラムは間接継続を用いているため、古いバー
+ジョンではバグにより実行できなかった。
+また、速度向上に関する改善は\ref{sec:impl-fastcall}節におけるfastcall
+の追加のみなであり、このfastcallはx86環境にしか影響しないはずである。
+表を見ると、\verb|-O0|の場合は新バージョンの方が旧バージョンより遅くな
+っているのが分かる。これは\ref{sec:impl-parallel}節の一時変数への退避
+処理のためだと考えられる。この処理では、最適化により無駄なスタックへの
+アクセスは排除されることを期待して実装していた。\verb|-O0|は最適化を行
+わないので、この場合は逆に遅くなっている。これは予想通りの結果である。
+しかし最適化を行った場合は新バージョンに劣化はない。したがって一時変数
+への退避処理においては、期待通り無駄な命令は十分に排除されていることが
+分かった。
+また、それだけなら速度はほぼ同じ結果がでるところだが、ここではいずれの
+環境でも新しいバージョンの方が速い。15~20\%ほど高速化していることがわ
+かる。これは本研究で行った改善の一つ、fastcallの影響である。
+\section{CbCでのプログラミング}
+% TODO:
+\section{バージョン管理}
+% TODO: version management
 \section{本研究における成果}
-本研究では、これまでバグが多くプログラムの動作に問題のあった
+本研究では、これまでバグが多くプログラムの動作に問題のあった GCCベース
-GCCベースのCbCコンパイラを、実用的なプログラムが動くレベルまで改善する
+のCbCコンパイラを、実用的なプログラムが動くレベルまで改善することがで
-ことができた。
+きた。
+2008年の研究にて、GCCベースのCbCコンパイラは一部実装されていた。
-\section{以前のバージョンとの速度比較}
+そして本研究により、そのコンパイラの改善が行われた。
+\begin{itemize}
+\item CwCの全機能に対応
+\item 一部バグのあったアーキテクチャに対応
+\item バージョン管理の
+\item 宣言の簡略化
+\item
+\end{itemize}

Mercurial > hg > Papers > 2010 > kent-master

comparison evaluations.tex @ 2:50e23a4b2f40