Mercurial > hg > Papers > 2010 > kent-master
view evaluations.tex @ 5:dfb89e32eea1
added gcc.tex, conclusion.tex
and some sources.
writed abstraction.
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 08 Feb 2010 00:35:58 +0900 |
parents | 30c102343b37 |
children | 8ef81ff8cb52 |
line wrap: on
line source
\chapter{評価・考察} \label{chp:eval} 本章では本研究の評価を行う。 \section{GCCを使うことの利点・欠点} \label{sec:merit} これまでCbCのコンパイルに使用してきたmc(micro-c)に対し、新しくGCCが CwCのフルセットとして使用可能となった。ここで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 では不利な点である。 \subsection*{互換性、ABI} %これは最後の考察に入れよう ソースコードレベルでの互換性の問題がある。 また、継続制御のパラメタを % 関数宣言 % 型推定 % ABI、特にppc % 最適化 % SPUでのベクトル演算 % gdb % architecture % 関数呼び出しのオーバヘッド % 互換性,ソースコード、ABI \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に先立ってC で実装し、参考文献\cite{bib:kinjo-2005}で紹介する手法を用いてCbCに変換 した。このプログラムは付録\ref{apx:quicksort}に添付する。 測定環境は両コンパイラが対応しているアーキテクチャ、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:machine-specs}に掲載する。 %GCCのコンパイルでは``-O2 -fomit-pointer''の最適化を付加して測定している。 % noreturnもON. % x86ではfastcallもON, \subsection{評価結果} 実効速度の測定結果を表\ref{tab:speed-mc-vs-gcc}に示す。 ただし環境毎に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:speed-mc-vs-gcc} \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} & -O2 & -Os & \\ \hline x86/OS X & 9176 & 9176 & 9172 \\ \hline x86/Linux & 5752 & 5752 & 5796 \\ \hline ppc/OS X & 8576 & 8576 & 12664 \\ \hline ppc/Linux & 10068 & 10068 & 9876 \\ \hline ppc/PS3 & 6960 & 6728 & 8636 \\ \hline \end{tabular} \caption{実行ファイルのファイルサイズ比較 stripped(単位: bytes)} \label{tab:eval-strip} \end{table} 最後に、本研究での実装GCC-4.4.2と以前のバージョンGCC-4.2.3との比較を表 \ref{tab:speed-old-vs-new}に示す。こちらは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:speed-old-vs-new} \end{table} \subsection{評価結果考察} % stripするとx86はサイズに変化がない \subsubsection{速度面} まずは速度面からこの測定結果を考察する。 まずどのアーキテクチャにおいても、GCCの最適化が大きな速度差を生み出し ている事が分かる。最適化なしと速度最適化を比較すると、x86では2.4倍、 ppcでは5〜7倍もの差が生じている。 ただしppcのこの以上な速度差は\ref{sec:impl-parallel}並列代入で示した様に、継続の引 数を全て一時変数に入れていることが大きい。その場合最適化なしではすべて の引数を一度メモリに確保するので、その分逆に遅くなっているのだと考えら れる。しかしながら最適化を有効にすることでそのメモリへの一時変数の確保 も解消されるということが分かった。 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プログラムで使われているコードセグメントを一つ例 %にあげる。 CbCのソースがコード\ref{code:divider_s}、そのコードセグメン %トのgccによる出力がコード\ref{code:divider_s_gcc}、mcによる出力がコー %ド \ref{code:divider_s_mc} である。 % \lstinputlisting[ caption=quicksortプログラムで使われているコードセグメント, label=code:divider-e] {sources/divider-e.cbc} \begin{minipage}[t]{.45\textwidth} \lstinputlisting[ caption=divider\_eのGCCによる出力(ppc), label=code:divider-e-gcc] {sources/divider-e-gcc.asm} \end{minipage} \hfill \begin{minipage}[t]{.45\textwidth} \lstinputlisting[ caption=divider\_eのmcによる出力(ppc), label=code:divider-e-mc] {sources/divider-e-mc.asm} \end{minipage} もっとも比較しやすい箇所は\verb|e-1|の処理である。 コード\ref{code:divider-e-gcc}のGCCではこれを1命令の\verb|addi 5,5,-1| で行っている。 mcではこれが\verb|mr, addi, mr|という3命令になっている 。これは変数\verb|s|の値を一度別のレジスタに移して計算するという処理で ある。この様な細かい命令の展開が速度に差が出る要因である。 またこのppcのアセンブラからも、x86での速度差が少ないことが頷ける。引数 のほとんどをメモリに格納するx86では、計算のために一度レジスタに格納し ないといけないことから、この命令は結局3命令になるはずであり、実際にx86 ではGCC,mc共にそのようなコードが出力されていた。 この結果より、CbCで記述されたプログラムではレジスタが多い方が実効速度 の面で有利であるということが分る。これは他のコンパイラ言語でも同じ事が 言えるが、(手続きやメソッドにおける)前の環境を保持する必要がないCbC ではその影響がより強い。 %レジスタの数は \subsubsection{ファイルサイズ} 次に、実行ファイルのファイルサイズの面から考察する。 実行ファイルのファイルサイズは組み込み用途のプログラムには重要な要素と なる。多くの場合、組み込み機器では大容量のメモリは用意されておらず、 OSも存在しないため仮想記憶の概念がない。そのためメモリに乗り切らないプ ログラムはそもそも実行不能である。 まず、評価の主な特徴として、strip後のファイルサイズ\ref{tab:eval-strip} をみると、x86ではmcとGCCでほとんど差がない事が分かる。この環境では速度 面でも大きな差はなく、mcの精度の良さがわかる。 デバグ情報のあり/なし/strip後との比較で大きな差が出ているのは全て Linux(PS3含む)である。Linuxでは実行ファイルのファイル形式にELFを用い ている。この形式はLinuxの標準的な実行形式で、様々な研究に用いられてい るため、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{メンテナンス性の向上に関する取り組み}\label{sec:mentainance} 本研究室ではこれまでCbCコンパイラとしてmicro-cを利用していた。このコン パイラはベースとなるmicro-cには依存せずに、ほぼ独立な開発を続けている。 これに対しGCCは現在も精力的に開発が続けられており、年数回のアップデー トではバグの除去や最適化の改善などが行われている。 そのためCbCコンパイラでもそのリリースに沿ってアップデートすることが望 ましく、実際に今回の改善の際にも2010年1月現在での最新リリースである 4.4.2をベースとしている。 しかしアップデートの度に新しいソースコードを書き換えるのは無理があり、 現実的ではない。最良の方法はGCCの正式な機能として開発リポジトリにマー ジしてもらうことだが、現段階ではそこには至っていない。 そのため現在はMercurialを使ったソースコード管理を行っている。ここでは その手法を説明する。 \subsection{二つのリポジトリ} Mercurialは分散型のバージョン管理システムである。 開発環境毎に複数のリポジトリを分散して持つすることができ、そのためそれ ぞれのリポジトリのマージの機能に優れる。 CbCコンパイラの管理ではこの特徴を利用する。 具体的にはCbC開発用に二つのリポジトリを持つ。一つは本家のGCCリリースと まったく同一のソースをもったGCC-copyと言うリポジトリである。もう一つは この GCC-copyからブランチする形で作成したCbConGCCというリポジトリであ る。 こちらがCbCに関するメインの開発環境となる。図\ref{fig:gcc-repository} では中央と右のラインがそのリポジトリを表している。 \begin{figure}[htpb] \begin{center} \includegraphics[width=.4\textwidth]{figures/gcc-repository.eps} \end{center} \caption{CbCコンパイラ開発でのリポジトリ管理(左が本家のリリースタイ ムライン、中央がGCC-copy、右がCbCの開発用リポジトリのタイムライン)} \label{fig:gcc-repository} \end{figure} 新しいバージョンがリリースされた際のCbConGCCでのアップデートは次の手順 で実現できる。 \begin{itemize} \item GCC-copyリポジトリにて \begin{enumerate} \item GCC-copyリポジトリ中のファイル全てを消す(バージョン管理情 報以外) \item gcc-core-4.4.3.tar.gzを展開し、全ファイルをGCC-copyに追加 \item \verb|hg status|で追加ファイル、削除ファイルを確認 \item コミット \item gcc-4.4.3タグの追加 \end{enumerate} \item CbConGCCリポジトリにて \begin{enumerate} \item GCC-copyから\verb|pull|. \item \verb|hg merge|でマージ実行 \item 衝突のあったファイルを修正 \item 実際にビルドしてテストファイルが動くことを確認 \item コミット \item cbc-4.4.3タグの追加 \end{enumerate} \end{itemize} 以上でアップデートが完了する。 \subsection{このリポジトリ管理方法の評価} 実際にこのリポジトリ管理方法を用いてアップデートを行った。この作業では バージョン 4.4.0から4.4.2へのアップデートと、4.4.2から4.4.3へのアップ デートである。 アップデートの際に何らかの問題が生じるのはCbConGCCリポジトリでの衝突フ ァイルの修正だけである。4.4.3へのアップデートでは特になにも衝突するこ とはなかったが、4.4.2ではある関数の引数が変わっており、その修正に手作 業を要した。しかし複雑な作業はこの衝突ファイルの修正だけに抑えられる。 この手法を用いず、これまでの様に一つのリポジトリのみで行っていた場合に は、本家GCCの新旧の差分をとるか、もしくは本家の旧GCCとCbCでの差分をと り、新しく適用する必要がある。この差分の取得はdiffを使って手動で行う必 要があるが手順は非常に複雑になり、どこに問題が生じたかも判別しにくくな る。 新しいリポジトリ管理方法ではdiffを用いた複雑な作業は必要なく、作業は衝 突したファイルのみに抑えられる。これによりソースコードアップデートに関 するメンテナンス性の向上が実現できた。