Papers/2010/kent-master: cbc.tex comparison

comparison cbc.tex @ 7:8ef81ff8cb52

emended.

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 12 Feb 2010 13:10:57 +0900
parents	b59d31966d7d
children	4b2af58b0302

comparison

equal deleted inserted replaced

-:b59d31966d7d
+:8ef81ff8cb52
 \chapter{Continuation based C (CbC)}
 \label{chp:cbc}
 Continuation based C（以下CbC）は当研究室の提案する、アセンブラよりも
-上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを使った
+上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを用いた
-研究を行っている。本章ではそのCbCの
+研究を行っている。本章ではそのCbCの仕様と現在の状況について説明し、ま
-仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。
+たCbCを用いた研究例についても紹介する。
 \section{CbCの要求仕様}
 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ
 あり、70 年代、80 年代に設計された言語は矛盾を抱えて来ている。
 オブジェクト指向技術とそれに基づいたJava などの言語が注目されているが
 、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ
 ベルな言語による記述に比べて、余分な条件判断（Method search, Meta level
 での実行） を増やしてしまい、コンパクトで高速な応答を期待される
-Real-time 処理や組み込み用途には適さない。
+Real-time 処理や組み込み用途には適さない。この用途にはハードウェアに近
+い記述が要求される。
+%ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記
+%述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー
+%ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル
+%チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため
+%に既存の言語に対するコンパイラをその都度設計し直すことが必要になってき
+%ている。
 ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記
-述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー
+述はあまりにも低レベルであり、依存性が強く汎用的ではない。さらに使用可
-ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル
+能なゲート数が増えるにつれ、RISC 的な対称性の高い少数の命令よりも、複
-チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため
+雑なSIMD命令やソフトウェアパイプライン命令を持つCPU が増えてきている。
-に既存の言語に対するコンパイラを一々設計し直すことが必要になってきてい
+そのために既存の言語に対するコンパイラをその都度設計し直すことが必要に
-る。
+なってきている。
 VHDL, Verilog などのハードウェア記述言語は有限状態遷移の中に閉じており
 、オブジェクト指向などの抽象化とはまったく別なものとなってしまっている。
-このように3 つは全く異なる方向を向いている。コンパイラの自動生成などが
+このようにハードウェア記述言語、アセンブラ、プログラミング言語の3つは
-重要な研究テーマとなると考えられるが、ハードウェア記述言語、アセンブラ
+全く異なる方向を向いている。コンパイラの自動生成などが重要な研究テーマ
-、プログラミング言語の3 つが全く独立したものであれば困難なものになると
+となると考えられるが、この3つが全く独立したものであれば困難なものにな
-考えられる。
+ると考えられる。
 そこでCbC はこの3 つを埋めるべく以下のような要求仕様に従って設計された。
 \begin{itemize}
 \item ハードウェアとスタックマシンの中間言語
-インタプリタ記述やコンパイラターゲットとして優れること。アーキテク
+インタプリタ記述やコンパイラターゲットとして優れる。アーキテクチャ
-チャ依存性が少ないこと、また、アーキテクチャ依存性をモデル化できる。
+依存性が少ない。また、アーキテクチャ依存性をモデル化できる。
 \item C 言語よりも下位の言語
-アセンブラよりも汎用性と記述性に優れC と互換であること。C をCbC に
+アセンブラよりも汎用性と記述性に優れC と互換である。C をCbC にコン
-コンパイルでき、ハンドコンパイルの結果を同値なコードに変換できる。
+パイルでき、ハンドコンパイルの結果を同値なコードに変換できる。
 \item 明確な実行モデル
 C++やProlog のような複雑な実行モデルは好ましくなく、ハードウェアに
 実行順序の変更を許す範囲を広くする。
 Yacc のような表駆動やC のような巨大なswitch 文ではなく直接に状態遷
 移ができ実行できる。
 \item Thread を実行モデルに内蔵できる
-並列処理記述法ではなく状態遷移として表現できる。
+%並列処理記述法ではなく状態遷移として表現できる。
+状態遷移記述とCbC上のスケジューラ実装によりスレッドを実現可能にす
+る。
 \item クリティカルパスの最適化
-全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出
+全体を散漫に最適化するのではなく、実行ルーチンから重要な箇所を抜き
-して最適化できる。
+出し、アセンブラに近い最適化をソースコードレベルで実現する。
+%全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出
+%して最適化できる。
 \end{itemize}
 これらの仕様はハードウェア記述とソフトウェア記述の両方を同時に行いつつ
 、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ
-グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移
+グラム変換やコンパイラターゲットとしての使用を意識している。状態遷移記
-記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に
+述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に適
-適した言語を作ることを考え、スタックマシンを避けてContinuation（継続）
+した言語を作ることを考え、スタックマシンを避けてContinuation（継続）が
-が導入されている。
+導入されている。
 \section{コードセグメントと継続}
 \subsection{call-returnから継続制御へ}
 \end{center}
 \caption{継続制御}
 \label{fig:continuation}
 \end{figure}
+\subsection{Schemeにおける継続制御}
+継続とは一般的には「現在の処理を続行するための情報」と解釈されている。
+継続制御はその情報をプログラム記述で操作するための構文である。
+例としてSchemeでの継続の使用をコード\ref{code:scheme-cont}に挙げる。
+%\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/
+\lstinputlisting
+[caption=Schemeでの継続制御の例,
+label=code:scheme-cont,
+language=Lisp,
+morekeywords={cont,cont-test},
+emph={gosh},
+emphstyle=\bfseries\underbar]
+{sources/scheme-cont-out.scmout}
+この例では関数\verb|cont-test|内にて\verb|call/cc|を呼ぶことで、現在の
+計算処理の``継続''を関数として変数\verb|cont|に保持している。
+その後、\verb|(cont)|という命令でその関数を実行すると、contが代入され
+た位置に処理が復帰する。そのため、直前の``before''は出力されずに
+``after''が出力されていることが分かる。\verb|cont|では関数の継続処理だ
+けでなく、引数などの環境も一緒に保持しているので、この\verb|cont|は呼
+ばれる度に \verb|i|カウントアップし、その値を返すことになる。
 CbCはこの継続制御を基本として設計されており、その実現のためにコードセ
 グメントと軽量継続という概念を用いている。
 以下ではその二つについて説明する。
 \subsection{コードセグメント}
 \end{center}
 \caption{\_\_returnの例}
 \label{fig:cbcreturn}
 \end{figure}%
+環境付きは実際にはCにおける\verb|setjmp()/longjmp()|とほぼ同じ処理であ
+る。この二つの関数はCで継続を実現するために用いられる。例としてコード
+\ref{code:setjmp}を挙げる。このコードでは\verb|setfunc|内で
+\verb|setjmp|を使用している。\verb|setjmp|は通常は0を返すため、if文の
+内部は実行されないが、その後\verb|longjmp|が実行されると、関連する
+\verb|setjmp|が呼び出された環境に``継続''し、非零を返すためif文の中が
+実行されることになる。この時、\verb|longjmp|の呼出側（この例では
+\verb|jmpfunc|）の環境は失われる。
+環境付き継続もこの動作によく似ており、if文内でreturnのみを記述すること
+に相当する。
+\lstset{morecomment=[is]{/*}{*/}} % /*コメント内を非表示にする*/
+\lstinputlisting
+[caption=setjmp/longjmpの例,
+basicstyle=\footnotesize\ttfamily,%
+commentstyle=\footnotesize\itshape\rmfamily,%
+label=code:setjmp,
+emph={setjmp,longjmp}]
+{sources/setjmp.c}
+\lstset{morecomment=[s]{/*}{*/}} % /*元に戻す*/
 \section{CbCの用途・先行研究}
 CbCによるプログラム記述の例として本研究室における研究例を紹介する。
 %\subsection{CbCによる分散プログラミング}
 %現在の分散プログラミングには様々な手法がある。ネットワークAPIを直接使
 %う方法、SOAPやMPIなどのライブラリ、Telescripに見られる言語仕様への埋め
 %込みなどがあった。これらは通信に関する複雑なセマンティクスを実現する手
 %段といえる。
-% TODO
+% TODO 分散プログラミング
-\section{CbCコンパイラの現状と問題点}
+\section{CbCコンパイラの現状と本研究における目標}
 \label{sec:cbc-problem}
 \subsection{micro-cとGCC}
 CbCのコンパイラには二つの実装が用意されている。一つは2000年に当研究室
 GCCは元より多数のアーキテクチャに対応しており、高機能な最適化も備えて
 いる。これらをCbCでも活用したいという要望からコンパイラ環境の移植が行
 われた。
-\subsection{GCCベースコンパイラの問題点}\label{sec:gcc-problems}
+\subsection{本研究における目標}\label{sec:gcc-problems}
 この時の実装でコードセグメント、継続制御構造などは実装され、一通りの
 CbCプログラムのコンパイルが可能となった。
-しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制
+本研究ではこのGCCベースのコンパイラをより実用的なCbCコンパイラとすべく
-御構造の実装方法の影響により、いくつかの問題が発生している。
+以下の項目を目標とする。
-以下にその問題点を列記する。
-%この問題に対せる解決を \ref{chp:impl}章にて説明する。
 \begin{itemize}
 \item 環境付き継続
-これは未実装の機能である。
+Cとの互換性のための制御構造である環境付き継続を実装する。
-仕様に若干変更があったので新しい仕様に対応したい。
 \item 並列代入
-CbCでは現在のコードセグメントのインタフェイスと次に継続するコード
+これまでGCCベースのコンパイラでは、実装方法の影響から継続制御に一
-セグメントの引数は同じメモリスペース（もしくはレジスタ）に格納して
+部制限が存在した。これは実行中のコードセグメントの引数と継続制御に
-いる。そのためコード\ref{code:parallel-example}のように変数の値を
+渡す引数の順序が入れ替わる場合等に継続が行えないという制限である。
-入れ替えるような処理では並列代入が行われることになる。
-前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる
+並列代入を行うことで引数順序の影響はなくなり、この制限を排除できる。
-複雑な並列代入ではバグが見つかっている。
-\lstinputlisting
-[caption=並列代入の例,
-label=code:parallel-example]
-{sources/parallel-example.cbc}
 \item PowerPCにおける間接継続(indirect goto)
-CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し
+Cでの関数ポインタを用いた間接呼び出し(indirect call)の様に、CbCで
-(indirect call)の様にコードセグメントポインタを用いた間接継続が可
+用いる継続制御においても、コードセグメントポインタを用いたメモリ参
-能である。
+照による間接的な継続が可能である。これを間接継続と呼んでいる。
+コード\ref{code:indirect-example}のcodepointerへの継続が間接継続に
+当たる。
 \lstinputlisting[
 caption=間接継続の例（2つめのgoto文）,
 label=code:indirect-example]
 {sources/indirect-example.cbc}
-しかしPowerPCアーキテクチャでは最適化の問題でこの機能が働かないこ
+しかしPowerPCアーキテクチャでは最適化の問題からこの間接継続がこれ
-とが分かっている。
+まで制限されていた。
 間接継続はCbCでのプログラミングには必須であり、また本研究室の主要
-プロジェクトであるCeriumはPS3をメインターゲットとしているため、こ
+プロジェクトであるCeriumはPS3（PowerPCをもつ）をメインターゲットと
-の対応は必須のものである。
+しているため、この対応は必須のものである。
-\item プロトタイプ宣言
+\item プロトタイプ宣言の自動化
-Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っている。
+Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っているが、
-しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記
+CbCでは返り値が存在しないなど、あまり重要な意味をなさない。
-述という性質上、プログラムを記述する際は上から下に実行順にコードセ
+また、micro-cではこれを極力排除するよう設計されているため、ソース
-グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大
+コードの互換性が薄れてしまう。
-な数になる。
-これはプログラミングにおける障害とも言える。
+プロトタイプを自動生成することにより、この互換性を向上させる。
-\item x86での継続制御のオーバヘッド
+\item x86での継続制御の最適化
-micro-c実装ではx86アーキテクチャでのコードセグメント継続の際には引
+x86では、Cの関数呼び出し全ての引数をメモリに格納する。コードセグメ
-数をレジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォ
+ントは関数をベースに作られているため、このABIに引きずられ実効速度
-ルトでは全ての引数をメモリに格納する。コードセグメントは関数をベー
+に影響をもたらしている。引数の一部をレジスタに格納することで、x86
-スに作られているため、このABIに引きずられ実効速度に影響をもたらす。
+における継続処理の高速化を行う。
+\item メンテナンス性の向上
+GCCのソースコードは200万行にものぼる。CbCコンパイラで修正するソー
+スコードはそのごく一部であるが、GCCのアップデートによる修正はCbC用
+のソースコードにも大きな影響をもたらす。
+GCCの最新リリースに追従するためには、アップデートも考慮し、洗練さ
+れたメンテナンス方法が必要になる。
 \end{itemize}
-これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ
-ていた。
 %特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。
-\ref{chp:impl}章ではこれらの問題の解決手法を説明する。
+\ref{chp:impl}章ではこれらの項目の実装を行う。

Mercurial > hg > Papers > 2010 > kent-master

comparison cbc.tex @ 7:8ef81ff8cb52