Mercurial > hg > Papers > 2011 > nobu-thesis

comparison nobu-midthesis.tex @ 7:24b02780ca8f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify midthesis
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 19 Nov 2011 16:22:19 +0900
parents a0bf68477575
children 60c8ce5eb0e0
comparison
equal deleted inserted replaced
6:a0bf68477575 7:24b02780ca8f
25 %\date{H23 11/18 fri} 25 %\date{H23 11/18 fri}
26 \maketitle 26 \maketitle
27 \thispagestyle{fancy} 27 \thispagestyle{fancy}
28 28
29 \section{研究背景と目的} 29 \section{研究背景と目的}
30 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している。 30 当研究室ではプログラムをコードセグメント (Code Segment) 単位で記述するプログラミング言語 Continuation based C (以下CbC) を開発している.
31 Code Segment は並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。これにより、 31 コードセグメントは並列実行の単位として使うことができ, プログラムの正しさを示す単位としても使用することができる.これにより,
32 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。 32 Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている.
33 33
34 GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は、GCC のアップデートに合わせて変更する必要がある。 34 GCC をベースとした CbC のコンパイラ (以下 CbC-GCC)は, GCC のアップデートに合わせて変更する必要がある.
35 本研究では、GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い、Intel64 に対応するとともに、CbC の拡張を行う。 35 本研究では, GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へのアップデートを行い, Intel64 に対応するとともに, CbC の拡張を行う.
36 36
37 %\subsection{研究内容} 37 %\subsection{研究内容}
38 %今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った。 38 %今回 GCC-4.5 をベースとしていた CbC-GCC を GCC-4.6 へとアップデートを行った.
39 39
40 %現在の GCC ベースの CbC (以下CbC-GCC) コンパイラには幾つかのバグが見られる。 40 %現在の GCC ベースの CbC (以下CbC-GCC) コンパイラには幾つかのバグが見られる.
41 %特に Code Segmtne への処理移動が jmp でなく call で行われる部分あげられる。 41 %特に Code Segmtne への処理移動が jmp でなく call で行われる部分あげられる.
42 %現在 CbC を実装した GCC コンパイラのバージョンは、初めに実装が行われた GCC-4.2 よりバージョンを上げた GCC-4.5 となる。 42 %現在 CbC を実装した GCC コンパイラのバージョンは,初めに実装が行われた GCC-4.2 よりバージョンを上げた GCC-4.5 となる.
43 %本研究では、CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする。 43 %本研究では,CbC-GCC を GCC-4.6 へのバージョンアップすると共に実装を突き詰めることを目的とする.
44 %また、GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う。 44 %また,GCC に変わるコンパイラとして注目されてきている LLVM への CbC の実装の考察も行う.
45 \section{Continuation basede C (CbC)} 45 \section{Continuation basede C (CbC)}
46 CbC のプログラムはコードセグメント毎に記述され、コード間をgoto(軽量継続)により処理を移る。 46 CbC のプログラムはコードセグメント毎に記述され, コード間をgoto(軽量継続)により処理を移る.
47 構文は C と同じであるが、ループ制御や関数コールが取り除かれる。 47 構文は C と同じであるが, ループ制御や関数コールが取り除かれる.
48 48
49 \subsection{コードセグメント} 49 \subsection{コードセグメント}
50 コードセグメントの記述は C の関数の構文と同じで、型に“\_\_code” を使うことで宣言できる。 50 コードセグメントの記述は C の関数の構文と同じで, 型に“\_\_code” を使うことで宣言できる.
51 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える。 51 コードセグメントへの移動は“goto” の後にコードセグメント名と引数を並べて記述することで行える.
52 図\ref{fig:cs}はコードセグメント間の処理の流れを表している。 52 図\ref{fig:cs}はコードセグメント間の処理の流れを表している.
53 53
54 \begin{figure}[htpb] 54 \begin{figure}[htpb]
55 \begin{center} 55 \begin{center}
56 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}} 56 \scalebox{0.35}{\includegraphics{figure/codesegment.eps}}
57 \end{center} 57 \end{center}
58 \caption{コードセグメント間の継続(goto)} 58 \caption{コードセグメント間の継続(goto)}
59 \label{fig:cs} 59 \label{fig:cs}
60 \end{figure} 60 \end{figure}
61 61
62 %また、コードセグメント間の移動は軽量継続によって行われる。 62 %また,コードセグメント間の移動は軽量継続によって行われる.
63 %プログラムの末尾に次のコードセグメントを記述し処理を続けていく。 63 %プログラムの末尾に次のコードセグメントを記述し処理を続けていく.
64 %コードセグメントの記述の仕方は C の関数の記述と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う. 64 %コードセグメントの記述の仕方は C の関数の記述と同じだが, 型に“\_\_code”を使って宣言を行うところだけが違う.
65 %コードセグメントへの処理の移りは call ではなく jmp で行われ、その為 C の関数の様に呼び出し元への復帰がない。 65 %コードセグメントへの処理の移りは call ではなく jmp で行われ,その為 C の関数の様に呼び出し元への復帰がない.
66 %構文では“\_\_code”で関数を宣言することでコードセグメントとして扱うようにしている。 66 %構文では“\_\_code”で関数を宣言することでコードセグメントとして扱うようにしている.
67 67
68 \subsection{軽量継続(light-weight continuation)} 68 \subsection{軽量継続(light-weight continuation)}
69 コードセグメントは C の関数と違って返り値を持たず、処理が終われば次のコードセグメントへと処理を移る。 69 コードセグメントは C の関数と違って返り値を持たず, 処理が終われば次のコードセグメントへと処理を移る.
70 C おいて関数呼び出しを繰り返し行う場合、呼び出された関数の引数の数だけスタックに値が積まれていく。 70 C において関数呼び出しを繰り返し行う場合, 呼び出された関数の引数の数だけスタックに値が積まれていく.
71 だが、返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く、スタックは変更されない。 71 だが, 返り値を持たないコードセグメントではスタックに値を積んでいく必要な無く, スタックは変更されない.
72 72
73 軽量継続により並列化, ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる。 73 軽量継続により並列化, ループ制御, 関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようになる.
74 74
75 75
76 %だが、返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ。 76 %だが,返り値を持たないコードセグメントではスタックに積まれる値は1つのコードセグメントの引数の分だけですむ.
77 77
78 \section{GCC-4.6 への実装} 78 \section{GCC-4.6 への実装}
79 % \subsection{軽量継続の実装} 79 % \subsection{軽量継続の実装}
80 GCCでの計量継続を Tail Call Ellimination (末尾除去)を強制することで実装する。 80 GCCでの計量継続を Tail Call Ellimination (末尾除去)を強制することで実装する.
81 これにより、コードセグメント間の移動を、call ではなく jmp 命令で実現する。 81 これにより, コードセグメント間の移動を, call ではなく jmp 命令で実現する.
82 コードセグメント自体には戻値はない。 82 コードセグメント自体には戻値はない.
83 83
84 %「caller側とcallee側の返り値の型が同じ」といった、幾つかのの条件下において行われる最適化になる。 84 %「caller側とcallee側の返り値の型が同じ」といった,幾つかのの条件下において行われる最適化になる.
85 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す。 85 図\ref{fig:continue}は Tail Call Elimination によるプログラムの処理の流れを表す.
86 \begin{figure}[htpb] 86 \begin{figure}[htpb]
87 \begin{center} 87 \begin{center}
88 \scalebox{0.30}{\includegraphics{figure/continuation.eps}} 88 \scalebox{0.30}{\includegraphics{figure/continuation.eps}}
89 \end{center} 89 \end{center}
90 \caption{Tail Call Elimination の例} 90 \caption{Tail Call Elimination の例}
91 \label{fig:continue} 91 \label{fig:continue}
92 \end{figure} 92 \end{figure}
93 93
94 \subsubsection{expand\_call} 94 \subsection{expand\_call 関数}
95 GCCでは、ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で以下の条件で判断される. 95 GCCでは, ある関数が Tail Call Elimination を行えるかどうかは expand\_call 関数で以下の条件で判断される.
96 96
97 \begin{itemize} 97 \begin{itemize}
98 \item caller 側と callee 側の返す値の型が一致している. 98 \item caller 側と callee 側の戻値の型が一致している.
99 \item 関数呼び出しがリターンの直前に行われている. 99 \item 関数呼び出しがリターンの直前に行われている.
100 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない. 100 \item 呼出先関数の引数に用いられるスタックサイズが呼出元関数のそれより少ない.
101 \item 引数の並びのコピーに上書きがない. 101 \item 引数の並びのコピーに上書きがない.
102 \end{itemize} 102 \end{itemize}
103 103
106 \begin{itemize} 106 \begin{itemize}
107 \item コードセグメントは void 型で統一する 107 \item コードセグメントは void 型で統一する
108 \item Cの関数からコードセグメントにgotoする場合は返す値の型チェックを行わない. 108 \item Cの関数からコードセグメントにgotoする場合は返す値の型チェックを行わない.
109 \item goto の直後に retrun を置く． 109 \item goto の直後に retrun を置く．
110 \item スタックサイズは関数宣言時に決まったサイズにする． 110 \item スタックサイズは関数宣言時に決まったサイズにする．
111 \item 引数は一旦、一時変数にコピーして重なりがないようにする． 111 \item 引数は一旦, 一時変数にコピーして重なりがないようにする．
112 \end{itemize} 112 \end{itemize}
113 113
114 GCCでは, この他にもTCEを禁止しするルールがあり, GCC-4.5, 4.6 でも 114 GCCでは, この他にもTCEを禁止しするルールがあり, GCC-4.5, 4.6 でも
115 Tail Call Elimination にかからないコードセグメントがある. 115 Tail Call Elimination にかからないコードセグメントがある.
116 この点を改善する必要がある. 116 この点を改善する必要がある.
117 117
118 118
119 %\subsubsection{try_tail_call フラグ} 119 %\subsubsection{try_tail_call フラグ}
120 %Tail Call Elimination が可能である場合、try_tail_call フラグが立てられる。 120 %Tail Call Elimination が可能である場合,try_tail_call フラグが立てられる.
121 %コードセグメントへの jmp は Tail Call Elimination を受けることで実装される。 121 %コードセグメントへの jmp は Tail Call Elimination を受けることで実装される.
122 %軽量継続において重要なのは上記でも述べた Tail Call Elimination に必要な幾つかの条件をクリアすることであった。 122 %軽量継続において重要なのは上記でも述べた Tail Call Elimination に必要な幾つかの条件をクリアすることであった.
123 %最初に開発された CbC-GCC ではコードセグメントの場合は上記の『ある特定の条件』をクリアするよう実装されていた。 123 %最初に開発された CbC-GCC ではコードセグメントの場合は上記の『ある特定の条件』をクリアするよう実装されていた.
124 %しかし、CbC のコードをアセンブラに出力してみると幾つか call で呼び出されていることが分かった。 124 %しかし,CbC のコードをアセンブラに出力してみると幾つか call で呼び出されていることが分かった.
125 %この問題を解決し、全てのコードセグメントは jmp によって呼びされるようにする必要がある。 125 %この問題を解決し,全てのコードセグメントは jmp によって呼びされるようにする必要がある.
126 126
127 127
128 %\begin{figure}[htpb] 128 %\begin{figure}[htpb]
129 % \begin{center} 129 % \begin{center}
130 %\scalebox{0.35}{\includegraphics{figure/cs_stack.eps}} 130 %\scalebox{0.35}{\includegraphics{figure/cs_stack.eps}}
135 135
136 136
137 %\subsubsection{typedefrec の実装方法} 137 %\subsubsection{typedefrec の実装方法}
138 %typedefrec 138 %typedefrec
139 139
140 %GCC における C の構文解析では、関数名はハッシュテーブルによって管理される。 140 %GCC における C の構文解析では,関数名はハッシュテーブルによって管理される.
141 %ここで問題となるのが、関数の宣言を全て読んだ後にハッシュテーブルに追加されるということである。 141 %ここで問題となるのが,関数の宣言を全て読んだ後にハッシュテーブルに追加されるということである.
142 %その為、関数の引数に自身の関数名がでるとそのような関数はないとエラーにされてしまう。 142 %その為,関数の引数に自身の関数名がでるとそのような関数はないとエラーにされてしまう.
143 %そこで typedefrec の付いた関数は先行して宣言を行うことにする。 143 %そこで typedefrec の付いた関数は先行して宣言を行うことにする.
144 %すると、宣言中でもハッシュテーブルから関数の情報をとることができるようになる。 144 %すると,宣言中でもハッシュテーブルから関数の情報をとることができるようになる.
145 145
146 %\subsection{\_\_return 変数} 146 %\subsection{\_\_return 変数}
147 \subsection{環境付き継続} 147 \subsection{環境付き継続}
148 CbC には通常の C の関数からコードセグメントに継続する際、 148 CbC には通常の C の関数からコードセグメントに継続する際,
149 その関数から値を戻す処理への継続を得ることができる. 149 その関数から値を戻す処理への継続を得ることができる.
150 これを環境付き継続という. 150 これを環境付き継続という.
151 これらは, 以下の二種類の CbC で定義した特殊変数である. 151 これらは, 以下の二種類の CbC で定義した特殊変数である.
152 \_\_environment は, 環境を表す情報である. 152 \_\_environment は, 環境を表す情報である.
153 \_\_return は, これを環境付き継続の行き先であり, 関数の戻値と \_\_environment の二つの引数を持つ 153 \_\_return は, これを環境付き継続の行き先であり, 関数の戻値と \_\_environment の二つの引数を持つ
154 コードセグメントである. 例えば、以下のように使うと, \verb+main()+ は 1 を返す. 154 コードセグメントである. 例えば, 以下のように使うと, \verb+main()+ は 1 を返す.
155 155
156 \begin{verbatim} 156 \begin{verbatim}
157 __code c1(__code ret(int,void *),void *env) { 157 __code c1(__code ret(int,void *),void *env) {
158 goto ret(1,env); 158 goto ret(1,env);
159 } 159 }
162 goto c1(__return, __environment); 162 goto c1(__return, __environment);
163 } 163 }
164 \end{verbatim} 164 \end{verbatim}
165 165
166 GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す. 166 GCC内部では, \verb+__return+ は, 関数内で定義された \verb+_cbc_internal_return+関数へのポインタを返す.
167 戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(図\ref{code:_ret_val}). 167 戻値は, \verb+cbc_internal_return+ 関数内で定義された変数\verb+retval+を通して返される(Listing\ref{code:_ret_val}).
168 168
169 \begin{figure}[h] 169 \begin{figure}[h]
170 \begin{minipage}[b]{.45\textwidth} 170 \begin{minipage}[b]{.45\textwidth}
171 \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val] 171 \begin{lstlisting}[caption=環境付き継続を行うコード,label=code:_ret_val]
172 __label__ _cbc_exit0; 172 __label__ _cbc_exit0;
186 \end{figure} 186 \end{figure}
187 187
188 \subsubsection{環境付き継続の問題} 188 \subsubsection{環境付き継続の問題}
189 現在環境付き継続は 189 現在環境付き継続は
190 このコードを GCC 内部で生成することで実現している. これは正しく動作しているが, 190 このコードを GCC 内部で生成することで実現している. これは正しく動作しているが,
191 \verb+retval+に static を指定してしまうと, 191 \verb+retval+に static を指定してしまうと,
192 スレッドセーフな実装でなくなる. 192 スレッドセーフな実装でなくなる.
193 これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の 193 これを通常の変数にすると, 関数内の関数は closure として実装される. しかし, GCC 4.6 と Lion の
194 組合せでは closure は正しく動作してないことがわかった. 194 組合せでは closure は正しく動作してないことがわかった.
195 Thread local 変数を用いると, やはり closure が出力されてしまう. 195 Thread local 変数を用いると, やはり closure が出力されてしまう.
196 本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず, 196 本来は, 戻値用のレジスタが使用されれば問題ないが, 戻値の型は整数やポインタとは限らず,
197 浮動小数点や構造体自体である可能性があり複雑である. 197 浮動小数点や構造体自体である可能性があり複雑である.
198 一つの解決策はレジスタ渡しと考えているが, 他の方もありえる. 少し重いが setjmp を用いた実装方法もある. 198 一つの解決策はレジスタ渡しと考えているが, 他の方法もありえる. 少し重いが setjmp を用いた実装方法もある.
199 199
200 200
201 \section{現状と今後の課題} 201 \section{現状と今後の課題}
202 %アセンブラ出力を見ることができ、gdb を使ってのデバッグが可能になったことである。 202 %アセンブラ出力を見ることができ,gdb を使ってのデバッグが可能になったことである.
203 %CbC-GCC により CbC のプログラム開発が行いやすくなった。 203 %CbC-GCC により CbC のプログラム開発が行いやすくなった.
204 %CbC-GCC は GCC に合わせてアップデートされてきた。 204 %CbC-GCC は GCC に合わせてアップデートされてきた.
205 %しかし、アップデートに伴い幾つか実装を見直す必要がでてきた。 205 %しかし,アップデートに伴い幾つか実装を見直す必要がでてきた.
206 %同時に、現時点で見つかっている問題以外にもバグが無いかを調べていく。 206 %同時に,現時点で見つかっている問題以外にもバグが無いかを調べていく.
207 今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく。 207 今後は本稿でも述べたとおり CbC コンパイラの実装を行なっていく.
208 また、実装後は、32ビット, 64ビットそれぞれでコンパイルしたプログラムの比較、 208 また, 実装後は, 32ビット, 64ビットそれぞれでコンパイルしたプログラムの比較,
209 それと Micro-C による実装との性能比較も行う予定である。 209 それと Micro-C による実装との性能比較も行う予定である.
210 210
211 時間があれば, LLVM での実装, コードセグメントの宣言に便利な \verb+typedefrec+ の実装, 211 時間があれば, LLVM での実装, コードセグメントの宣言に便利な \verb+typedefrec+ の実装,
212 あるいは, Google go 言語での実装などの研究も行う予定である. 212 あるいは, Google go 言語での実装などの研究も行う予定である.
213 213
214 214
215 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある。 215 %今後は本稿で述べた CbC-GCC の問題点を改善していく必要がある.
216 %また、CbC を GCC だけでなく LLVM での実装や、C 言語以外の言語への変更も検討していく。 216 %また,CbC を GCC だけでなく LLVM での実装や,C 言語以外の言語への変更も検討していく.
217 217
218 \thispagestyle{fancy} 218 \thispagestyle{fancy}
219 \begin{thebibliography}{9} 219 \begin{thebibliography}{3}
220 220
221 \bibitem{1}{河野真治}: 221 \bibitem{1}{河野真治}:
222 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002 222 “継続を基本とした言語 CbC の gcc 上の実装”. 日本ソフトウェア科学会第 19 回大会論文集, Sep, 2002
223 223
224 \bibitem{3}{与儀健人,河野真治}: 224 \bibitem{2}{与儀健人,河野真治}:
225 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008 225 “Continuation based CコンパイラのGCC-4.2による実装”. 琉球大学　情報工学科 学位論文, 2008
226 226
227 \bibitem{7}{GNU Compiler Collection (GCC) Internals}: 227 \bibitem{3}{GNU Compiler Collection (GCC) Internals}:
228 “http://gcc.gnu.org/onlinedocs/gccint/” 228 “http://gcc.gnu.org/onlinedocs/gccint/”
229 229
230 230
231 \end{thebibliography} 231 \end{thebibliography}
232 \end{document} 232 \end{document}