Mercurial > hg > Papers > 2010 > kent-master

comparison resume/handout.tex @ 10:3d9addf62d0b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
organized repository.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 14:35:36 +0900
parents
children
comparison
equal deleted inserted replaced
9:ae0a3666f7f9 10:3d9addf62d0b
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}