Mercurial > hg > Papers > 2012 > nobu-thesis
annotate paper/resume.tex @ 18:d276144b815c draft
modify
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 24 Feb 2012 19:42:48 +0900 |
| parents | 0f406370c241 |
| children | 669655c106eb |
| 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 の関数よりも細かな単位で, 状態を表すことができる. | |
| 18 | 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 のアップデートに合わせていく必要がある. |
| 17 | 43 本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートをすると共に実装の修正 |
| 18 | 44 を行った. |
| 13 | 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 への実装} | |
| 17 | 63 CbC の継続は, 環境を保持しない為軽量継続と呼ばれる. |
| 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 | |
| 16 | 76 \subsection{Tail Call Elimination の強制付与} |
| 77 関数が Tail Call Elimination にかかる為には, ``呼び出し先関数と呼び出し元関数の型が一致している'' | |
| 10 | 78 等といった幾つかの条件をクリアしなければならない. |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
79 これまでの実装ではコードセグメントに条件をクリアさせる為, 専用の関数を用意していた. |
| 12 | 80 しかし今回の実装ではその関数を廃止し, 末尾除去にかかるフラグを落とさせない |
| 17 | 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 引数に渡しコードセグメントとして扱うことで使用できる. |
| 14 | 90 実際には \verb+_CbC_return+ キーワードにより GCC 内部で次の様なコードが生成されている. |
| 4 | 91 \begin{figure}[h] |
| 92 \begin{minipage}[b]{.45\textwidth} | |
| 13 | 93 \begin{verbatim} |
| 4 | 94 ({ |
| 95 __label__ _cbc_exit0; | |
| 11 | 96 static int retval; |
| 4 | 97 void _cbc_internal_return(int retval_, |
| 98 void *_envp){ | |
| 99 retval = retval_; | |
| 100 goto _cbc_exit0; | |
| 101 } | |
| 102 if (0) { | |
| 103 _cbc_exit0: | |
| 104 return retval; | |
| 105 } | |
| 106 _cbc_internal_return; | |
| 107 }) | |
| 13 | 108 \end{verbatim} |
| 4 | 109 \end{minipage} |
| 110 \hfill | |
| 111 \end{figure} | |
| 112 | |
| 113 \subsubsection{環境付き継続の問題と改良} | |
| 114 環境付き継続で特に重要になってくるのが retval 変数の値をどこに確保するかである. | |
| 14 | 115 元々の実装では static で値の確保を行なっていた. |
| 4 | 116 しかしこれではスレッドセーフではない. |
| 16 | 117 そこで retval 変数の値を static thread local でスレッド毎に確保することでこの問題の解決を行った. |
| 4 | 118 |
| 11 | 119 \subsection{構文の追加} |
| 4 | 120 |
| 11 | 121 \subsubsection{``\_\_rectype'', ``selftype'' 構文} |
| 4 | 122 %\verb+__rectype+キーワードはリカーシブタイプを宣言する時に使われる. |
| 123 通常, 関数定義において引数の中に自分自身を指す関数ポインタを入れることはできない. | |
| 17 | 124 そこで, \verb+__rectype+を使うことで以下の様な宣言が行うことができる. |
|
8
42e6dd499688
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
125 また, 構造体の宣言時に宣言中の構造体を指す``selftype'' 構文の追加も行った. |
| 13 | 126 以下の様な宣言が行えるようになった. |
|
8
42e6dd499688
modify resume.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
127 この時\verb+__rectype+は funcPtr を指し, selftype は struct node を指す. |
| 4 | 128 \begin{figure}[h] |
| 129 \begin{minipage}[b]{.45\textwidth} | |
| 13 | 130 \begin{verbatim} |
|
9
942888c0f8aa
modify explanation of tailcall elimination
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
131 typedef __code (*funcPtr)(int,__rectype*); |
| 4 | 132 struct node { |
| 133 int num; | |
| 134 selftype child; | |
| 135 } | |
| 13 | 136 \end{verbatim} |
| 4 | 137 \end{minipage} |
| 138 \end{figure} | |
| 139 \section{評価} | |
| 16 | 140 今回実装を行った GCC-4.6 と GCC-4.5 ベース, |
| 4 | 141 それと Micro-C の CbC コンパイラでベンチマークを行った. |
| 10 | 142 プログラムは Micro-C のベンチマークにも使用されるものである. |
| 14 | 143 このプログラムは演算と継続を交互に行う. |
| 10 | 144 引数 1 は C で書かれたプログラムをただ CbC へと変換したプログラムになる. |
| 145 引数 2 と 3 は Micro-C 用に手動で最適化を行ったプログラムである. | |
| 16 | 146 また評価は \verb+x86_64+ 上の Linux で行った. |
| 12 | 147 %また評価は \verb+x86_64+ 上の OS X(10.7) で 32bit と 64bit それぞれに最適化オプション(-O2)をつけての評価を行った. |
| 148 %結果を図\ref{fig:conv1}の様になった(斜線は segmentation fault を示す). | |
| 149 | |
| 4 | 150 \begin{figure}[htpb] |
| 151 \begin{center} | |
| 16 | 152 \scalebox{0.33}{\includegraphics{figure/conv1_for_resume.pdf}} |
| 4 | 153 \end{center} |
| 16 | 154 \caption{各コンパイラにより生成されたコードの速度比較} |
| 12 | 155 \label{fig:conv1} |
| 4 | 156 \end{figure} |
| 157 | |
| 158 \subsection{評価の考察} | |
| 159 まず, Micro-C 版より GCC 版コンパイラの方が結果が良いことが確認できる. | |
| 12 | 160 次に GCC-4.5 と GCC-4.6 を比較してみる. |
| 161 手動で最適化を行なっている引数 2 と 3 の時は余り差は無い. | |
| 17 | 162 だが, 引数 1 の時は GCC-4.6 版が 32 bit, 64 bit 共に GCC-4.5 に比べて 1.5 倍以上早い. |
| 14 | 163 アセンブラの比較も行なってみると, GCC-4.6 版の方では演算の結果が求められていて |
| 16 | 164 必要最小限の継続だけを行なうプログラムとなっていた. |
| 17 | 165 この結果から GCC-4.5 に比べ GCC-4.6 の最適化が修正されよりよくなっているのが確認できた. |
| 4 | 166 |
| 167 \section{今後の課題} | |
| 168 今回, CbC コンパイラを GCC-4.6 へとアップデートを行った. | |
| 17 | 169 アップデートに伴い実装の修正を行い, また CbC の記述に便利な新たな構文の追加も行うことができた. |
| 4 | 170 |
| 171 GCC 版 CbC コンパイラは細かい実装の除けば, 以後 GCC のアップデートに合わせていくだけとなる. | |
| 17 | 172 CbC コンパイラの今後としては LLVM への実装, もしくは Google go 言語での実装の検討も行なっていく予定である. |
| 4 | 173 |
| 174 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある. | |
| 175 %また,CbC を GCC だけでなく LLVM での実装や,C 言語以外の言語への変更も検討していく. | |
| 176 | |
| 177 \thispagestyle{fancy} | |
| 178 \begin{thebibliography}{3} | |
| 179 | |
| 180 \bibitem{1}{河野真治}: | |
| 181 ``継続を基本とした言語 CbC の gcc 上の実装''. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 | |
| 182 | |
| 183 \bibitem{2}{与儀健人,河野真治}: | |
| 184 ``Continuation based CコンパイラのGCC-4.2による実装''. 琉球大学 情報工学科 学位論文, 2008 | |
| 185 | |
| 186 \bibitem{3}{GNU Compiler Collection (GCC) Internals}: | |
| 187 ``http://gcc.gnu.org/onlinedocs/gccint/'' | |
| 188 | |
| 189 | |
| 190 \end{thebibliography} | |
| 191 \end{document} |