\documentclass[twocolumn, a4j, twoside]{jarticle}
\usepackage{master_proc}
%\usepackage[dvips]{graphicx}
\usepackage[dvipdfm]{graphicx}
\usepackage{listings}
\usepackage{multirow}  %% tabularの上下の結合
\usepackage{slashbox}  %% tabularでの斜め線

% dvipdfm を使って PDF ファイルに日本語の栞をつける
% \usepackage[dvipdfm]{color}
% \usepackage[dvipdfm,bookmarks=true,bookmarksnumbered=true,%
% bookmarkstype=toc]{hyperref}

\lstdefinelanguage{cbc}[]{C}
  {morekeywords={code,\_\_return}}
\lstset{
  language=cbc,%
  %stringstyle=\ttfamily,%
  stringstyle=,%
  basicstyle=\small\ttfamily,%
  commentstyle=\itshape\rmfamily,%
  %identifierstyle=\color{blue}\bfseries,%
  keywordstyle=\bfseries,%
  framesep=5pt,%
  showstringspaces=false,%
  frameround=ftft,%
  frame=trBL,
  framextopmargin=2pt,
  framexbottommargin=3pt,
  emphstyle=\underbar,
  %frame=tRBl,
  %numbers=left,stepnumber=1,numberstyle=\footnotesize%
}%

\jtitle{組込み向け言語Continuation based CのGCC上の実装}
\etitle{Implementation of the Continuation based C on GCC}%英文タイトル
\author{与儀健人}	%著者名
\studentid{088511J}	%学籍番号
\teacher{河野真治}	%指導教官

\begin{document}
\maketitle

\section{はじめに}

企業システムの多様化、IT導入の加速により、ソフトウェアは大規模化・複雑
化する傾向にある。また家電製品のデジタル化も進み、組み込みシステムの需
要も増大している。

それにともないハードウェアは驚異的な進歩を遂げてきた。
しかしハードウェアの進歩に対し、ソフトウェアはその進歩に追いついていな
い。オブジェクト指向が発明され、Javaなどが注目されているが、ガベージコ
レクタや実行時コンパイルは余分な処理が必要となる。軽量かつ高速な応答が
要求される Real-time処理や組込み用途には適さない。

PlayStation3にはCellという特殊なCPUが採用され注目されている。しかしプ
ログラミングは格段に難しく複雑になった。

ハードウェアの進化や数学的検証にソフトウェアが対応するためには、これま
でとは違う新たな視点を持ったプログラミング言語が望ましい。

我々はこれらの問題に取り組むため、Continuation based C（以下CbC）とい
う言語を提案している。Continuationとはプログラムの次の実行処理を表現す
る制御構造で、継続とも呼ばれている。CbCではCからサブルーチンやループ制
御を除き、代わりに継続をベースとした実行制御を行う。

これまでCbCのコンパイルには、micro-cをベースとしたコンパイラが用いられ
てきた。加えて2008年の研究においてGCCをベースとしたCbCコンパイラが開発
され、継続処理の実装が行われた。

本研究ではGCCベースのコンパイラにおいて残るCbCの機能の実装を行い、実用
的な CbCプログラムの動作を目指す。


\section{Continuation based C (CbC)}

CbCは、スタックを保持しない継続、``軽量継続''をプログラミング記述のベ
ースとした言語である。関数の代わりとなるそれぞれの処理単位は
``コードセグメント''と呼ばれる。CbCではこのコードセグメントにより、状
態遷移を直接プログラムとして記述することができる。

以下では簡単なCbC記述の例として階乗計算を行うコードセグメントを例示す
る。
\begin{lstlisting}
code factor0(int prod, int x,
             code (*next)(int)) {
  if (x >= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    goto (*next)(prod);
  }
} \end{lstlisting}

この例の様にコードセグメントへの継続では、自分自身に対して継続すること
でループ制御を実現する事ができる。また、例にあるようにポインタの参照先
に継続する``間接継続''も可能になっている。


\section{軽量継続の実装方法}

初代のCbCコンパイラであるmicro-cは元より軽量継続を意識して開発されてお
り、コードセグメントに適した設計がなされている。
しかしGCCではメンテナンス性の理由からそのような深いレベルでの実装は好
ましくない。既に入念に設計され実際に使われている関数と関数呼び出しを利
用して軽量継続を実装する。

\subsection{末尾呼出による軽量継続}
末尾呼出とはリターン文直前の関数呼び出しのことで、GCCの最適化の一つで
ある。通常の関数呼び出しは復帰後に元の環境に戻るが、この末尾呼び出しの
場合はその必要がなく、call命令の代わりにjmp命令を使うことができる。そ
してスタックを余計に積むこともない（図\ref{fig:tailcallstack}）。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[width=.40\textwidth]{figures/tailcallstack.eps}
  \end{center}
  \caption{末尾呼出と通常呼出のスタックの変化}
  \label{fig:tailcallstack}
\end{figure}

この特徴は軽量継続のそれとほぼ同じである。構文解析にてこの最適化を強制
した関数呼出を生成することで、軽量継続の実装ができる。


\subsection{fastcallによる高速化}

以上で軽量継続は可能になったが、
これだけではCbC用に入念に設計されたmicro-cよりも良い性能を出すことはで
きない。特にx86アーキテクチャにおいての高速化を行う必要がある。
x86の関数呼出規約では全ての引数はスタックに確保するため、メモリアクセ
スが多い。 fastcallを用いてこの関数規約を変更しスタックでなくレジスタ
を使用するように変更する。

これによりメモリアクセスが減り、十分な高速化が得られた。
\ref{sec:eval}には測定結果が見られる。

\section{環境付き継続の実装}

既存のソフトウェアを無駄にしないためにも、新しい言語が受け入れられるた
めにも、既存の言語との互換性は必須である。 CbCでは環境付き継続という形
でC との互換性を担保している。

こちらはCの関数内から先ほどのコードセグメントfactor0に継続する例である。
\begin{lstlisting}
int caller() {
  goto factor0(1, i, __return);
}
\end{lstlisting}
本来は継続した場合、元の環境に復帰することはできないが、ここでは復帰の
ために \verb|__return|という特殊なコードセグメントをfactor0に渡してい
る。この特殊なコードセグメントは\verb|factor0|が処理を終える際に間接継
続として引数xと共に継続対象となり、その時、関数\verb|caller|は返り値x
を伴って復帰する。

この環境付き継続の実装にはsetjmp()/longjmp()を使った方法も考えられるが
、ポータビリティのため、ここではGCCの拡張機能でもある内部関数を用いて
実装を行った。


\section{メンテナンス性の向上に関する取り組み}

新しいコンパイラはGCCをベースとした。GCCの本家でのアップデートリリース
は年5回ほどあり、CbCコンパイラもこれに追従するのが望ましい。
\begin{figure}[h]
  \begin{center}
    \includegraphics[width=.45\textwidth]{figures/gcc-repository.eps}
  \end{center}
  %\caption{<+caption text+>}
  %\label{fig:<+label+>}
\end{figure}

このメンテナンスのため、CbCコンパイラの管理に分散バージョン管理を用い
、GCC本家のリリースを追従するリポジトリとCbC開発用のリポジトリの2つを
管理する手法を用いた。この手法により、アップデートの手順が明確になり、
重要な変更点のみに集中できるようになった。

\section{評価}

\subsection{micro-cとの速度比較}
GCCベースのコンパイラとmicro-cをベースとしたコンパイラで生成した実行フ
ァイルの速度差を比較する。次の表がその結果である。
\begin{table}[h]
  \centering
  \begin{tabular}{|c|c|c|c|} \hline
              & \multicolumn{2}{c|}{GCC} & \multirow{2}{*}{micro-c} \\ \cline{2-3}
              &最適化なし&速度最適化&  \\ \hline
    x86/OS X  & 5.901 & 2.434 & 2.857 \\ \hline
    x86/Linux & 5.732 & 2.401 & 2.254 \\ \hline
    ppc/OS X  &14.875 & 2.146 & 4.811 \\ \hline
    ppc/Linux &19.793 & 3.955 & 6.454 \\ \hline
    ppc/PS3   &39.176 & 5.874 &11.121 \\ \hline
  \end{tabular}
  %\caption{GCCとmicro-cの速度比較（単位: 秒）}
  %\label{tab:speed-mc-vs-gcc}
\end{table}
x86に特化したコンパイラであるmicro-cとほぼ伍角の速度を得られた。また
PowerPCにおいてはいずれの環境でもmicro-cの倍近い速度を計測することがで
きた。

\subsection{前バージョンとのとの速度比較}\label{sec:eval}
次に、前回の実装時におけるGCCベースコンパイラと、今回改善したコンパイ
ラとの速度比較を次の表に示す。
\begin{table}[h]
  \centering
  \begin{tabular}{|c|c|c|c|c|} \hline
              & \multicolumn{2}{c|}{新バージョン} &
              \multicolumn{2}{c|}{前バージョン} \\ \hline
     最適化   &  なし &  あり &  なし &  あり \\ \hline
    x86/OS X  & 5.907 & 2.434 & 4.668 & 3.048 \\ \hline
    x86/Linux & 5.715 & 2.401 & 4.525 & 2.851 \\ \hline
  \end{tabular}
  %\caption{GCC-4.2.3ベースとGCC-4.4.2ベースの速度比較（単位: 秒）}
  %\label{tab:speed-old-vs-new}
\end{table}

新バージョンでは最適化を行わない場合に速度の低下が見られた。これは末尾
呼出の強制のために行った処理が影響したものであり、予想通りの結果であっ
た。この速度低下は最適化によりカバーされ得る。実際に最適化を行った場合
は15--20\%ほど旧バージョンより高速化に成功している。こちらはfastcallに
よる影響だと考えられる。


\section{まとめと今後の課題}

本研究による成果を以下にあげる。
\begin{itemize}
  \item GCCをベースとしたCbCコンパイラがCbCのフルセットとして利用可能
    となった
  \item CbCが20以上の多数のアーキテクチャに対応
  \item CbCの高速化（特にx86について大幅に改善された）
  \item デバッガとしてgdbが使用可能になった
\end{itemize}

今後の課題を以下に述べる。
\begin{itemize}
  \item Real-time、組込み向けに実用的な例題の作成
  \item タブロー法を用いた検証手法の確立
  \item オブジェクティブなCbCの設計
  \item スケジューラを使ったCbCの並列化
\end{itemize}

\begin{thebibliography}{9}
  \bibitem{bib:kono-april-2008}
    河野真治. ``Implementing Continuation based language in GCC'',
    Continuation Festa 2008, April, 2008 

  \bibitem{kent} 与儀健人, 河野真治.
    ``組み込み向け低レベル言語CbCのGCCによる実装'',
    第6回ディペンダブルシステムワークショップ, July, 2008 

  \bibitem{bib:kono-march-2008}
    河野真治. ``検証を自身で表現できるハードウェア、ソフトウェア記述言
    語 Continuation based C と、そのCell への応用'',
    電子情報通信学会VLSI設計技術研究会, March, 2008
\end{thebibliography}

\end{document}