|
10
|
1 \documentclass[twocolumn, a4j, twoside]{jarticle}
|
|
|
2 \usepackage{master_proc}
|
|
|
3 %\usepackage[dvips]{graphicx}
|
|
|
4 \usepackage[dvipdfm]{graphicx}
|
|
|
5 \usepackage{listings}
|
|
|
6 \usepackage{multirow} %% tabularの上下の結合
|
|
|
7 \usepackage{slashbox} %% tabularでの斜め線
|
|
|
8
|
|
|
9 % dvipdfm を使って PDF ファイルに日本語の栞をつける
|
|
|
10 % \usepackage[dvipdfm]{color}
|
|
|
11 % \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
|
|
|
12 % bookmarkstype=toc]{hyperref}
|
|
|
13
|
|
|
14 \lstdefinelanguage{cbc}[]{C}
|
|
|
15 {morekeywords={code,\_\_return}}
|
|
|
16 \lstset{
|
|
|
17 language=cbc,%
|
|
|
18 %stringstyle=\ttfamily,%
|
|
|
19 stringstyle=,%
|
|
|
20 basicstyle=\small\ttfamily,%
|
|
|
21 commentstyle=\itshape\rmfamily,%
|
|
|
22 %identifierstyle=\color{blue}\bfseries,%
|
|
|
23 keywordstyle=\bfseries,%
|
|
|
24 framesep=5pt,%
|
|
|
25 showstringspaces=false,%
|
|
|
26 frameround=ftft,%
|
|
|
27 frame=trBL,
|
|
|
28 framextopmargin=2pt,
|
|
|
29 framexbottommargin=3pt,
|
|
|
30 emphstyle=\underbar,
|
|
|
31 %frame=tRBl,
|
|
|
32 %numbers=left,stepnumber=1,numberstyle=\footnotesize%
|
|
|
33 }%
|
|
|
34
|
|
|
35 \jtitle{組込み向け言語Continuation based CのGCC上の実装}
|
|
|
36 \etitle{Implementation of the Continuation based C on GCC}%英文タイトル
|
|
|
37 \author{与儀健人} %著者名
|
|
|
38 \studentid{088511J} %学籍番号
|
|
|
39 \teacher{河野真治} %指導教官
|
|
|
40
|
|
|
41 \begin{document}
|
|
|
42 \maketitle
|
|
|
43
|
|
|
44 \section{はじめに}
|
|
|
45
|
|
|
46 企業システムの多様化、IT導入の加速により、ソフトウェアは大規模化・複雑
|
|
|
47 化する傾向にある。また家電製品のデジタル化も進み、組み込みシステムの需
|
|
|
48 要も増大している。
|
|
|
49
|
|
|
50 それにともないハードウェアは驚異的な進歩を遂げてきた。
|
|
|
51 しかしハードウェアの進歩に対し、ソフトウェアはその進歩に追いついていな
|
|
|
52 い。オブジェクト指向が発明され、Javaなどが注目されているが、ガベージコ
|
|
|
53 レクタや実行時コンパイルは余分な処理が必要となる。軽量かつ高速な応答が
|
|
|
54 要求される Real-time処理や組込み用途には適さない。
|
|
|
55
|
|
|
56 PlayStation3にはCellという特殊なCPUが採用され注目されている。しかしプ
|
|
|
57 ログラミングは格段に難しく複雑になった。
|
|
|
58
|
|
|
59 ハードウェアの進化や数学的検証にソフトウェアが対応するためには、これま
|
|
|
60 でとは違う新たな視点を持ったプログラミング言語が望ましい。
|
|
|
61
|
|
|
62 我々はこれらの問題に取り組むため、Continuation based C（以下CbC）とい
|
|
|
63 う言語を提案している。Continuationとはプログラムの次の実行処理を表現す
|
|
|
64 る制御構造で、継続とも呼ばれている。CbCではCからサブルーチンやループ制
|
|
|
65 御を除き、代わりに継続をベースとした実行制御を行う。
|
|
|
66
|
|
|
67 これまでCbCのコンパイルには、micro-cをベースとしたコンパイラが用いられ
|
|
|
68 てきた。加えて2008年の研究においてGCCをベースとしたCbCコンパイラが開発
|
|
|
69 され、継続処理の実装が行われた。
|
|
|
70
|
|
|
71 本研究ではGCCベースのコンパイラにおいて残るCbCの機能の実装を行い、実用
|
|
|
72 的な CbCプログラムの動作を目指す。
|
|
|
73
|
|
|
74
|
|
|
75 \section{Continuation based C (CbC)}
|
|
|
76
|
|
|
77 CbCは、スタックを保持しない継続、``軽量継続''をプログラミング記述のベ
|
|
|
78 ースとした言語である。関数の代わりとなるそれぞれの処理単位は
|
|
|
79 ``コードセグメント''と呼ばれる。CbCではこのコードセグメントにより、状
|
|
|
80 態遷移を直接プログラムとして記述することができる。
|
|
|
81
|
|
|
82 以下では簡単なCbC記述の例として階乗計算を行うコードセグメントを例示す
|
|
|
83 る。
|
|
|
84 \begin{lstlisting}
|
|
|
85 code factor0(int prod, int x,
|
|
|
86 code (*next)(int)) {
|
|
|
87 if (x >= 1) {
|
|
|
88 goto factor0(prod*x, x-1, next);
|
|
|
89 } else {
|
|
|
90 goto (*next)(prod);
|
|
|
91 }
|
|
|
92 } \end{lstlisting}
|
|
|
93
|
|
|
94 この例の様にコードセグメントへの継続では、自分自身に対して継続すること
|
|
|
95 でループ制御を実現する事ができる。また、例にあるようにポインタの参照先
|
|
|
96 に継続する``間接継続''も可能になっている。
|
|
|
97
|
|
|
98
|
|
|
99 \section{軽量継続の実装方法}
|
|
|
100
|
|
|
101 初代のCbCコンパイラであるmicro-cは元より軽量継続を意識して開発されてお
|
|
|
102 り、コードセグメントに適した設計がなされている。
|
|
|
103 しかしGCCではメンテナンス性の理由からそのような深いレベルでの実装は好
|
|
|
104 ましくない。既に入念に設計され実際に使われている関数と関数呼び出しを利
|
|
|
105 用して軽量継続を実装する。
|
|
|
106
|
|
|
107 \subsection{末尾呼出による軽量継続}
|
|
|
108 末尾呼出とはリターン文直前の関数呼び出しのことで、GCCの最適化の一つで
|
|
|
109 ある。通常の関数呼び出しは復帰後に元の環境に戻るが、この末尾呼び出しの
|
|
|
110 場合はその必要がなく、call命令の代わりにjmp命令を使うことができる。そ
|
|
|
111 してスタックを余計に積むこともない（図\ref{fig:tailcallstack}）。
|
|
|
112 \begin{figure}[htpb]
|
|
|
113 \begin{center}
|
|
|
114 \includegraphics[width=.40\textwidth]{figures/tailcallstack.eps}
|
|
|
115 \end{center}
|
|
|
116 \caption{末尾呼出と通常呼出のスタックの変化}
|
|
|
117 \label{fig:tailcallstack}
|
|
|
118 \end{figure}
|
|
|
119
|
|
|
120 この特徴は軽量継続のそれとほぼ同じである。構文解析にてこの最適化を強制
|
|
|
121 した関数呼出を生成することで、軽量継続の実装ができる。
|
|
|
122
|
|
|
123
|
|
|
124 \subsection{fastcallによる高速化}
|
|
|
125
|
|
|
126 以上で軽量継続は可能になったが、
|
|
|
127 これだけではCbC用に入念に設計されたmicro-cよりも良い性能を出すことはで
|
|
|
128 きない。特にx86アーキテクチャにおいての高速化を行う必要がある。
|
|
|
129 x86の関数呼出規約では全ての引数はスタックに確保するため、メモリアクセ
|
|
|
130 スが多い。 fastcallを用いてこの関数規約を変更しスタックでなくレジスタ
|
|
|
131 を使用するように変更する。
|
|
|
132
|
|
|
133 これによりメモリアクセスが減り、十分な高速化が得られた。
|
|
|
134 \ref{sec:eval}には測定結果が見られる。
|
|
|
135
|
|
|
136 \section{環境付き継続の実装}
|
|
|
137
|
|
|
138 既存のソフトウェアを無駄にしないためにも、新しい言語が受け入れられるた
|
|
|
139 めにも、既存の言語との互換性は必須である。 CbCでは環境付き継続という形
|
|
|
140 でC との互換性を担保している。
|
|
|
141
|
|
|
142 こちらはCの関数内から先ほどのコードセグメントfactor0に継続する例である。
|
|
|
143 \begin{lstlisting}
|
|
|
144 int caller() {
|
|
|
145 goto factor0(1, i, __return);
|
|
|
146 }
|
|
|
147 \end{lstlisting}
|
|
|
148 本来は継続した場合、元の環境に復帰することはできないが、ここでは復帰の
|
|
|
149 ために \verb|__return|という特殊なコードセグメントをfactor0に渡してい
|
|
|
150 る。この特殊なコードセグメントは\verb|factor0|が処理を終える際に間接継
|
|
|
151 続として引数xと共に継続対象となり、その時、関数\verb|caller|は返り値x
|
|
|
152 を伴って復帰する。
|
|
|
153
|
|
|
154 この環境付き継続の実装にはsetjmp()/longjmp()を使った方法も考えられるが
|
|
|
155 、ポータビリティのため、ここではGCCの拡張機能でもある内部関数を用いて
|
|
|
156 実装を行った。
|
|
|
157
|
|
|
158
|
|
|
159 \section{メンテナンス性の向上に関する取り組み}
|
|
|
160
|
|
|
161 新しいコンパイラはGCCをベースとした。GCCの本家でのアップデートリリース
|
|
|
162 は年5回ほどあり、CbCコンパイラもこれに追従するのが望ましい。
|
|
|
163 \begin{figure}[h]
|
|
|
164 \begin{center}
|
|
|
165 \includegraphics[width=.45\textwidth]{figures/gcc-repository.eps}
|
|
|
166 \end{center}
|
|
|
167 %\caption{<+caption text+>}
|
|
|
168 %\label{fig:<+label+>}
|
|
|
169 \end{figure}
|
|
|
170
|
|
|
171 このメンテナンスのため、CbCコンパイラの管理に分散バージョン管理を用い
|
|
|
172 、GCC本家のリリースを追従するリポジトリとCbC開発用のリポジトリの2つを
|
|
|
173 管理する手法を用いた。この手法により、アップデートの手順が明確になり、
|
|
|
174 重要な変更点のみに集中できるようになった。
|
|
|
175
|
|
|
176 \section{評価}
|
|
|
177
|
|
|
178 \subsection{micro-cとの速度比較}
|
|
|
179 GCCベースのコンパイラとmicro-cをベースとしたコンパイラで生成した実行フ
|
|
|
180 ァイルの速度差を比較する。次の表がその結果である。
|
|
|
181 \begin{table}[h]
|
|
|
182 \centering
|
|
|
183 \begin{tabular}{|c|c|c|c|} \hline
|
|
|
184 & \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{micro-c} \\ \cline{2-3}
|
|
|
185 &最適化なし&速度最適化& \\ \hline
|
|
|
186 x86/OS X & 5.901 & 2.434 & 2.857 \\ \hline
|
|
|
187 x86/Linux & 5.732 & 2.401 & 2.254 \\ \hline
|
|
|
188 ppc/OS X &14.875 & 2.146 & 4.811 \\ \hline
|
|
|
189 ppc/Linux &19.793 & 3.955 & 6.454 \\ \hline
|
|
|
190 ppc/PS3 &39.176 & 5.874 &11.121 \\ \hline
|
|
|
191 \end{tabular}
|
|
|
192 %\caption{GCCとmicro-cの速度比較（単位: 秒）}
|
|
|
193 %\label{tab:speed-mc-vs-gcc}
|
|
|
194 \end{table}
|
|
|
195 x86に特化したコンパイラであるmicro-cとほぼ伍角の速度を得られた。また
|
|
|
196 PowerPCにおいてはいずれの環境でもmicro-cの倍近い速度を計測することがで
|
|
|
197 きた。
|
|
|
198
|
|
|
199 \subsection{前バージョンとのとの速度比較}\label{sec:eval}
|
|
|
200 次に、前回の実装時におけるGCCベースコンパイラと、今回改善したコンパイ
|
|
|
201 ラとの速度比較を次の表に示す。
|
|
|
202 \begin{table}[h]
|
|
|
203 \centering
|
|
|
204 \begin{tabular}{|c|c|c|c|c|} \hline
|
|
|
205 & \multicolumn{2}{c|}{新バージョン} &
|
|
|
206 \multicolumn{2}{c|}{前バージョン} \\ \hline
|
|
|
207 最適化 & なし & あり & なし & あり \\ \hline
|
|
|
208 x86/OS X & 5.907 & 2.434 & 4.668 & 3.048 \\ \hline
|
|
|
209 x86/Linux & 5.715 & 2.401 & 4.525 & 2.851 \\ \hline
|
|
|
210 \end{tabular}
|
|
|
211 %\caption{GCC-4.2.3ベースとGCC-4.4.2ベースの速度比較（単位: 秒）}
|
|
|
212 %\label{tab:speed-old-vs-new}
|
|
|
213 \end{table}
|
|
|
214
|
|
|
215 新バージョンでは最適化を行わない場合に速度の低下が見られた。これは末尾
|
|
|
216 呼出の強制のために行った処理が影響したものであり、予想通りの結果であっ
|
|
|
217 た。この速度低下は最適化によりカバーされ得る。実際に最適化を行った場合
|
|
|
218 は15--20\%ほど旧バージョンより高速化に成功している。こちらはfastcallに
|
|
|
219 よる影響だと考えられる。
|
|
|
220
|
|
|
221
|
|
|
222 \section{まとめと今後の課題}
|
|
|
223
|
|
|
224 本研究による成果を以下にあげる。
|
|
|
225 \begin{itemize}
|
|
|
226 \item GCCをベースとしたCbCコンパイラがCbCのフルセットとして利用可能
|
|
|
227 となった
|
|
|
228 \item CbCが20以上の多数のアーキテクチャに対応
|
|
|
229 \item CbCの高速化（特にx86について大幅に改善された）
|
|
|
230 \item デバッガとしてgdbが使用可能になった
|
|
|
231 \end{itemize}
|
|
|
232
|
|
|
233 今後の課題を以下に述べる。
|
|
|
234 \begin{itemize}
|
|
|
235 \item Real-time、組込み向けに実用的な例題の作成
|
|
|
236 \item タブロー法を用いた検証手法の確立
|
|
|
237 \item オブジェクティブなCbCの設計
|
|
|
238 \item スケジューラを使ったCbCの並列化
|
|
|
239 \end{itemize}
|
|
|
240
|
|
|
241 \begin{thebibliography}{9}
|
|
|
242 \bibitem{bib:kono-april-2008}
|
|
|
243 河野真治. ``Implementing Continuation based language in GCC'',
|
|
|
244 Continuation Festa 2008, April, 2008
|
|
|
245
|
|
|
246 \bibitem{kent} 与儀健人, 河野真治.
|
|
|
247 ``組み込み向け低レベル言語CbCのGCCによる実装'',
|
|
|
248 第6回ディペンダブルシステムワークショップ, July, 2008
|
|
|
249
|
|
|
250 \bibitem{bib:kono-march-2008}
|
|
|
251 河野真治. ``検証を自身で表現できるハードウェア、ソフトウェア記述言
|
|
|
252 語 Continuation based C と、そのCell への応用'',
|
|
|
253 電子情報通信学会VLSI設計技術研究会, March, 2008
|
|
|
254 \end{thebibliography}
|
|
|
255
|
|
|
256 \end{document}
|
