Mercurial > hg > Papers > 2012 > nobu-thesis
annotate paper/resume.tex @ 15:6a667be77762 draft
modify Makefile
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 24 Feb 2012 14:31:58 +0900 |
| parents | 003a659c528e |
| children | 9ec54b29df7c |
| rev | line source |
|---|---|
| 4 | 1 \documentclass[twocolumn,twoside,9.5pt]{jarticle} |
| 2 %\usepackage[dvips]{graphicx} | |
| 3 \usepackage[dvipdfm]{graphicx} | |
| 4 \usepackage{picins} | |
| 5 \usepackage{fancyhdr} | |
| 6 \usepackage{listings} | |
| 7 \usepackage{url} | |
| 8 | |
| 9 \lhead{\parpic{\includegraphics[height=1zw,clip,keepaspectratio]{figure/emblem-bitmap.eps}}琉球大学主催 工学部情報工学科 卒業研究発表会} | |
| 10 \rhead{} | |
| 11 \cfoot{} | |
| 12 | |
| 13 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}} | |
| 14 \setlength{\headheight}{0mm} | |
| 15 \setlength{\headsep}{5mm} | |
| 16 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}} | |
| 17 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}} | |
| 18 \setlength{\textwidth}{181mm} | |
| 19 \setlength{\textheight}{261mm} | |
| 20 \setlength{\footskip}{0mm} | |
| 21 \pagestyle{empty} | |
| 22 | |
| 23 \begin{document} | |
| 24 \title{Continuation based C コンパイラのGCC-4.6における実装} | |
| 25 \author{学籍番号:085711E 氏名:大城信康 {}{} 指導教員 : 河野真治} | |
| 26 %\date{H23 11/18 fri} | |
| 27 %\date{平成23 年11 月18 日} | |
| 28 \maketitle | |
| 29 \thispagestyle{fancy} | |
| 30 | |
| 13 | 31 \section{はじめに} |
|
6
b6584cc0f737
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
32 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下 CbC) を提案している. |
| 13 | 33 %コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより, |
| 34 % Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている. | |
| 35 コードセグメントは C の関数よりも細かな単位で, 状態を表すことができる. | |
| 36 その為 CbC では状態遷移記述を行うことができ, 状態探索といったモデル検査が行えると考えられている. | |
| 4 | 37 |
| 13 | 38 %GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある. |
| 39 %当研究室には 2008 年に開発されて以来アップデートがGCC-4.5 をベースとした CbC コンパイラがある. | |
|
15
6a667be77762
modify Makefile
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
40 CbC のコンパイラとしては Micro-C 版と GCC ベースのコンパイラ(以下 CbC-GCC) が開発されている. |
|
6a667be77762
modify Makefile
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
41 しかし, CbC-GCC はいくつかバグがあり機能の修正の余地があった. |
| 13 | 42 また, GCC の最新の機能を使用する為にも CbC-GCC は GCC のアップデートに合わせていく必要がある. |
| 43 本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートとすると共に機能の修正 | |
| 44 を行う. | |
| 45 %本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う. | |
| 4 | 46 |
| 47 \section{Continuation basede C (CbC)} | |
| 13 | 48 Continuation based C (以下 CbC) は C を基本としたプログラミング言語である. |
|
6
b6584cc0f737
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
49 構文は C と同じであるが, 継続(goto) やコードセグメントの導入によりループ制御や関数コールが取り除かれる. |
|
7
1f5bfcd8b685
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
50 CbC のプログラムはコードセグメントの末尾から次のコードセグメントへの継続を記述することで作られる. |
| 4 | 51 図\ref{fig:cs}はコードセグメント間の処理の流れを表している. |
| 52 | |
| 53 \begin{figure}[htpb] | |
| 54 \begin{center} | |
| 55 \scalebox{0.35}{\includegraphics{figure/codesegment.pdf}} | |
| 56 \end{center} | |
| 57 \caption{コードセグメント間の継続(goto)} | |
| 58 \label{fig:cs} | |
| 59 \end{figure} | |
| 60 | |
| 61 | |
| 62 \section{GCC-4.6 への実装} | |
| 12 | 63 CbC 環境を保持しない継続は軽量継続と呼ばれる. |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
64 GCC における軽量継続は Tail Call Ellimination (末尾除去)を強制することで実装する. |
| 10 | 65 これにより, コードセグメント間の移動を, call ではなく jmp 命令で行う. |
| 12 | 66 この為コードセグメントからのは戻値は無くなる. |
| 4 | 67 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す. |
| 68 \begin{figure}[htpb] | |
| 69 \begin{center} | |
| 70 \scalebox{0.30}{\includegraphics{figure/continuation.pdf}} | |
| 71 \end{center} | |
| 72 \caption{Tail Call Elimination の例} | |
| 73 \label{fig:continue} | |
| 74 \end{figure} | |
| 75 | |
| 10 | 76 \subsection{Tail Call Elimination の矯正付与} |
| 77 関数が Tail Call Elimination にかかる為には, ``呼び出し先関数と呼び出し元関数の方が一致している'' | |
| 78 等といった幾つかの条件をクリアしなければならない. | |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
79 これまでの実装ではコードセグメントに条件をクリアさせる為, 専用の関数を用意していた. |
| 12 | 80 しかし今回の実装ではその関数を廃止し, 末尾除去にかかるフラグを落とさせない |
| 10 | 81 コードを追加することで Tail Call Elimination の条件をクリアさせるようになった. |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
82 これにより GCC のアップデート時に伴う専用関数の修正が不要となり, 楽な管理が行えるようになった. |
| 4 | 83 |
| 84 \subsection{環境付き継続} | |
| 85 CbC には通常の C の関数からコードセグメントに継続する際, | |
| 86 その関数から値を戻す処理への継続を得ることができる. | |
| 87 これを環境付き継続という. | |
| 14 | 88 環境付き継続は, \verb+_CbC_environment+ と \verb+_CbC_return+ キーワードを |
| 10 | 89 引数に渡しコードセグメントとして扱うことで使用できる. |
| 90 %\verb+environment+ は 環境を表す情報を持つ. | |
| 91 %\verb+__return+ は環境付き継続の行き先であり, 関数の戻り値と\verb+__environment+ の二つの引数を | |
| 92 %持つコードセグメントになる. | |
| 93 %GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. | |
| 94 %戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:retval}) . | |
| 13 | 95 %実際には \verb+__return+ キーワードにより GCC 内部でlisting\ref{code:retval}のコードが生成されている. |
| 14 | 96 実際には \verb+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている. |
| 4 | 97 \begin{figure}[h] |
| 98 \begin{minipage}[b]{.45\textwidth} | |
| 13 | 99 % \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:retval] |
| 100 \begin{verbatim} | |
| 4 | 101 ({ |
| 102 __label__ _cbc_exit0; | |
| 11 | 103 static int retval; |
| 4 | 104 void _cbc_internal_return(int retval_, |
| 105 void *_envp){ | |
| 106 retval = retval_; | |
| 107 goto _cbc_exit0; | |
| 108 } | |
| 109 if (0) { | |
| 110 _cbc_exit0: | |
| 111 return retval; | |
| 112 } | |
| 113 _cbc_internal_return; | |
| 114 }) | |
| 13 | 115 \end{verbatim} |
| 4 | 116 \end{minipage} |
| 117 \hfill | |
| 118 \end{figure} | |
| 119 | |
| 120 \subsubsection{環境付き継続の問題と改良} | |
| 121 環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである. | |
| 14 | 122 元々の実装では static で値の確保を行なっていた. |
| 4 | 123 しかしこれではスレッドセーフではない. |
| 124 そこで retval 変数の値を static thread local で確保することでこの問題の解決を行った. | |
| 125 | |
| 11 | 126 \subsection{構文の追加} |
| 4 | 127 |
| 11 | 128 \subsubsection{``\_\_rectype'', ``selftype'' 構文} |
| 4 | 129 %\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる. |
| 130 通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない. | |
| 131 そこで, \verb+__rectype+を使うことでlisting\ref{code:rectype}の用な宣言が行うことができる. | |
|
8
42e6dd499688
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
132 また, 構造体の宣言時に宣言中の構造体を指す``selftype'' 構文の追加も行った. |
| 13 | 133 以下の様な宣言が行えるようになった. |
|
8
42e6dd499688
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
134 この時\verb+__rectype+は funcPtr を指し, selftype は struct node を指す. |
| 4 | 135 \begin{figure}[h] |
| 136 \begin{minipage}[b]{.45\textwidth} | |
| 13 | 137 \begin{verbatim} |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
138 typedef __code (*funcPtr)(int,__rectype*); |
| 4 | 139 struct node { |
| 140 int num; | |
| 141 selftype child; | |
| 142 } | |
| 13 | 143 \end{verbatim} |
| 4 | 144 \end{minipage} |
| 145 \end{figure} | |
| 13 | 146 % \begin{lstlisting}[caption=\_\_rectype\, selftype 構文の使用例,label=code:rectype] |
| 147 % \end{lstlisting} | |
| 4 | 148 \section{評価} |
|
15
6a667be77762
modify Makefile
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
14
diff
changeset
|
149 今回実装を行った GCC-4.6 ベース と安定版である GCC-4.5 ベース, |
| 4 | 150 それと Micro-C の CbC コンパイラでベンチマークを行った. |
| 10 | 151 プログラムは Micro-C のベンチマークにも使用されるものである. |
| 14 | 152 このプログラムは演算と継続を交互に行う. |
| 10 | 153 引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる. |
| 154 引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである. | |
| 12 | 155 また評価は \verb+x86_64+ 上の CentOS 5.7 で行った. |
| 156 %また評価は \verb+x86_64+ 上の OS X(10.7) で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った. | |
| 157 %結果を図\ref{fig:conv1}の様になった(斜線は segmentation fault を示す). | |
| 158 | |
| 4 | 159 \begin{figure}[htpb] |
| 160 \begin{center} | |
| 161 \scalebox{0.33}{\includegraphics{figure/conv1_linux.pdf}} | |
| 162 \end{center} | |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
163 \caption{各種コンパイラにより生成されたコードの速度比較} |
| 12 | 164 \label{fig:conv1} |
| 4 | 165 \end{figure} |
| 166 | |
| 167 \subsection{評価の考察} | |
| 168 まず, Micro-C 版より GCC 版コンパイラの方が結果が良いことが確認できる. | |
| 12 | 169 次に GCC-4.5 と GCC-4.6 を比較してみる. |
| 170 手動で最適化を行なっている引数 2 と 3 の時は余り差は無い. | |
| 171 だが, 引数 1 の時は GCC-4.6 版が GCC-4.5 に比べて 1.67 倍程早い. | |
| 14 | 172 アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて |
| 173 必要最小限の継続だけを行なっていた. | |
| 174 アセンブラとこの結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた. | |
| 4 | 175 |
| 176 \section{今後の課題} | |
| 177 今回, CbC コンパイラを GCC-4.6 へとアップデートを行った. | |
| 12 | 178 アップデートに伴い実装の修正と Intel64 bit への対応を行った. |
| 4 | 179 また, CbC の記述に便利な新たな構文の追加も行うことができた. |
| 180 | |
| 181 GCC 版 CbC コンパイラは細かい実装の除けば, 以後 GCC のアップデートに合わせていくだけとなる. | |
| 182 CbC コンパイラの今後としては LLVM への実装, もしくは Google go 言語での実装の検討を行なっていく予定である. | |
| 183 | |
| 184 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある. | |
| 185 %また,CbC を GCC だけでなく LLVM での実装や,C 言語以外の言語への変更も検討していく. | |
| 186 | |
| 187 \thispagestyle{fancy} | |
| 188 \begin{thebibliography}{3} | |
| 189 | |
| 190 \bibitem{1}{河野真治}: | |
| 191 ``継続を基本とした言語 CbC の gcc 上の実装''. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 | |
| 192 | |
| 193 \bibitem{2}{与儀健人,河野真治}: | |
| 194 ``Continuation based CコンパイラのGCC-4.2による実装''. 琉球大学 情報工学科 学位論文, 2008 | |
| 195 | |
| 196 \bibitem{3}{GNU Compiler Collection (GCC) Internals}: | |
| 197 ``http://gcc.gnu.org/onlinedocs/gccint/'' | |
| 198 | |
| 199 | |
| 200 \end{thebibliography} | |
| 201 \end{document} |