Mercurial > hg > Papers > 2010 > kent-master
diff 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 |
line wrap: on
line diff
--- a/cbc.tex Mon Feb 08 03:50:27 2010 +0900 +++ b/cbc.tex Fri Feb 12 13:10:57 2010 +0900 @@ -2,9 +2,9 @@ \label{chp:cbc} Continuation based C(以下CbC)は当研究室の提案する、アセンブラよりも -上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを使った -研究を行っている。本章ではそのCbCの -仕様と現在の状況について説明し、またCbCを用いた研究例も紹介する。 +上位でCよりも下位な記述言語である。我々は様々な視点からこのCbCを用いた +研究を行っている。本章ではそのCbCの仕様と現在の状況について説明し、ま +たCbCを用いた研究例についても紹介する。 \section{CbCの要求仕様} 90 年代以降、ハードウェアの進歩がプログラミング言語よりも早く進みつつ @@ -14,34 +14,41 @@ 、これらの言語は動的な適合性を中心に設計されたものである。C などの低レ ベルな言語による記述に比べて、余分な条件判断(Method search, Meta level での実行) を増やしてしまい、コンパクトで高速な応答を期待される -Real-time 処理や組み込み用途には適さない。 +Real-time 処理や組み込み用途には適さない。この用途にはハードウェアに近 +い記述が要求される。 +%ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記 +%述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー +%ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル +%チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため +%に既存の言語に対するコンパイラをその都度設計し直すことが必要になってき +%ている。 ハードウェアに一番近い言語はアセンブラであるがマクロアセンブラなどの記 -述はあまりにも低レベルであり、長年進歩していない。しかし使用可能なゲー -ト数が増えるにつれ、RISC 的な対称性の高い小数の命令よりも、複雑なマル -チメディア関係の命令などを持つCISC 的なCPU が増えてきている。そのため -に既存の言語に対するコンパイラを一々設計し直すことが必要になってきてい -る。 +述はあまりにも低レベルであり、依存性が強く汎用的ではない。さらに使用可 +能なゲート数が増えるにつれ、RISC 的な対称性の高い少数の命令よりも、複 +雑なSIMD命令やソフトウェアパイプライン命令を持つCPU が増えてきている。 +そのために既存の言語に対するコンパイラをその都度設計し直すことが必要に +なってきている。 VHDL, Verilog などのハードウェア記述言語は有限状態遷移の中に閉じており 、オブジェクト指向などの抽象化とはまったく別なものとなってしまっている。 -このように3 つは全く異なる方向を向いている。コンパイラの自動生成などが -重要な研究テーマとなると考えられるが、ハードウェア記述言語、アセンブラ -、プログラミング言語の3 つが全く独立したものであれば困難なものになると -考えられる。 +このようにハードウェア記述言語、アセンブラ、プログラミング言語の3つは +全く異なる方向を向いている。コンパイラの自動生成などが重要な研究テーマ +となると考えられるが、この3つが全く独立したものであれば困難なものにな +ると考えられる。 そこでCbC はこの3 つを埋めるべく以下のような要求仕様に従って設計された。 \begin{itemize} \item ハードウェアとスタックマシンの中間言語 - インタプリタ記述やコンパイラターゲットとして優れること。アーキテク - チャ依存性が少ないこと、また、アーキテクチャ依存性をモデル化できる。 + インタプリタ記述やコンパイラターゲットとして優れる。アーキテクチャ + 依存性が少ない。また、アーキテクチャ依存性をモデル化できる。 \item C 言語よりも下位の言語 - アセンブラよりも汎用性と記述性に優れC と互換であること。C をCbC に - コンパイルでき、ハンドコンパイルの結果を同値なコードに変換できる。 + アセンブラよりも汎用性と記述性に優れC と互換である。C をCbC にコン + パイルでき、ハンドコンパイルの結果を同値なコードに変換できる。 \item 明確な実行モデル @@ -55,20 +62,25 @@ \item Thread を実行モデルに内蔵できる - 並列処理記述法ではなく状態遷移として表現できる。 + %並列処理記述法ではなく状態遷移として表現できる。 + 状態遷移記述とCbC上のスケジューラ実装によりスレッドを実現可能にす + る。 \item クリティカルパスの最適化 - 全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出 - して最適化できる。 + 全体を散漫に最適化するのではなく、実行ルーチンから重要な箇所を抜き + 出し、アセンブラに近い最適化をソースコードレベルで実現する。 + + %全体を散漫に最適化するコンパイルではなくクリティカルパスを見つけ出 + %して最適化できる。 \end{itemize} これらの仕様はハードウェア記述とソフトウェア記述の両方を同時に行いつつ 、C よりも精密な実行記述を可能にするためのものである。また、CbC はプロ -グラム変換やコンパイラターゲットとして使うことを意識している。状態遷移 -記述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に -適した言語を作ることを考え、スタックマシンを避けてContinuation(継続) -が導入されている。 +グラム変換やコンパイラターゲットとしての使用を意識している。状態遷移記 +述のみでは制御機構は静的なものになってしまう。CbC では状態遷移記述に適 +した言語を作ることを考え、スタックマシンを避けてContinuation(継続)が +導入されている。 \section{コードセグメントと継続} @@ -102,6 +114,31 @@ \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はこの継続制御を基本として設計されており、その実現のためにコードセ グメントと軽量継続という概念を用いている。 以下ではその二つについて説明する。 @@ -220,7 +257,27 @@ \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]{/*}{*/}} % /*元に戻す*/ @@ -264,10 +321,10 @@ %う方法、SOAPやMPIなどのライブラリ、Telescripに見られる言語仕様への埋め %込みなどがあった。これらは通信に関する複雑なセマンティクスを実現する手 %段といえる。 -% TODO +% TODO 分散プログラミング -\section{CbCコンパイラの現状と問題点} +\section{CbCコンパイラの現状と本研究における目標} \label{sec:cbc-problem} \subsection{micro-cとGCC} @@ -282,74 +339,73 @@ いる。これらをCbCでも活用したいという要望からコンパイラ環境の移植が行 われた。 -\subsection{GCCベースコンパイラの問題点}\label{sec:gcc-problems} +\subsection{本研究における目標}\label{sec:gcc-problems} この時の実装でコードセグメント、継続制御構造などは実装され、一通りの CbCプログラムのコンパイルが可能となった。 -しかし、前節に説明した環境付き継続はまだ実装に至っておらず、また継続制 -御構造の実装方法の影響により、いくつかの問題が発生している。 -以下にその問題点を列記する。 -%この問題に対せる解決を \ref{chp:impl}章にて説明する。 +本研究ではこのGCCベースのコンパイラをより実用的なCbCコンパイラとすべく +以下の項目を目標とする。 \begin{itemize} \item 環境付き継続 - これは未実装の機能である。 - 仕様に若干変更があったので新しい仕様に対応したい。 + Cとの互換性のための制御構造である環境付き継続を実装する。 \item 並列代入 - CbCでは現在のコードセグメントのインタフェイスと次に継続するコード - セグメントの引数は同じメモリスペース(もしくはレジスタ)に格納して - いる。そのためコード\ref{code:parallel-example}のように変数の値を - 入れ替えるような処理では並列代入が行われることになる。 - 前実装では単純な並列代入に対しては問題がなかったが、構造体の混じる - 複雑な並列代入ではバグが見つかっている。 - \lstinputlisting - [caption=並列代入の例, - label=code:parallel-example] - {sources/parallel-example.cbc} + これまでGCCベースのコンパイラでは、実装方法の影響から継続制御に一 + 部制限が存在した。これは実行中のコードセグメントの引数と継続制御に + 渡す引数の順序が入れ替わる場合等に継続が行えないという制限である。 + + 並列代入を行うことで引数順序の影響はなくなり、この制限を排除できる。 \item PowerPCにおける間接継続(indirect goto) - CbCで用いる継続制御は、Cでの関数ポインタを用いた間接呼び出し - (indirect call)の様にコードセグメントポインタを用いた間接継続が可 - 能である。 + Cでの関数ポインタを用いた間接呼び出し(indirect call)の様に、CbCで + 用いる継続制御においても、コードセグメントポインタを用いたメモリ参 + 照による間接的な継続が可能である。これを間接継続と呼んでいる。 + コード\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のプロトタイプ宣言はコンパイル時のエラー検出に役立っている。 - しかしCbCのコードセグメントには返り値は存在しない。また状態遷移記 - 述という性質上、プログラムを記述する際は上から下に実行順にコードセ - グメントを並べることが多いため、プロトタイプ宣言をするとそれが膨大 - な数になる。 - これはプログラミングにおける障害とも言える。 + Cのプロトタイプ宣言はコンパイル時のエラー検出に役立っているが、 + CbCでは返り値が存在しないなど、あまり重要な意味をなさない。 + また、micro-cではこれを極力排除するよう設計されているため、ソース + コードの互換性が薄れてしまう。 + + プロトタイプを自動生成することにより、この互換性を向上させる。 + + \item x86での継続制御の最適化 - \item x86での継続制御のオーバヘッド + x86では、Cの関数呼び出し全ての引数をメモリに格納する。コードセグメ + ントは関数をベースに作られているため、このABIに引きずられ実効速度 + に影響をもたらしている。引数の一部をレジスタに格納することで、x86 + における継続処理の高速化を行う。 - micro-c実装ではx86アーキテクチャでのコードセグメント継続の際には引 - 数をレジスタに格納していた。しかしx86では、Cの関数呼び出しはデフォ - ルトでは全ての引数をメモリに格納する。コードセグメントは関数をベー - スに作られているため、このABIに引きずられ実効速度に影響をもたらす。 + \item メンテナンス性の向上 + GCCのソースコードは200万行にものぼる。CbCコンパイラで修正するソー + スコードはそのごく一部であるが、GCCのアップデートによる修正はCbC用 + のソースコードにも大きな影響をもたらす。 + GCCの最新リリースに追従するためには、アップデートも考慮し、洗練さ + れたメンテナンス方法が必要になる。 \end{itemize} -これらの問題は、CbCを実用的なプログラムを開発する際の大きな障害となっ -ていた。 %特にPowerPCで間接継続ができないことで、当研究室が開発するPS3を主な対象としたシステムであるCeriumが実装不能であった。 -\ref{chp:impl}章ではこれらの問題の解決手法を説明する。 +\ref{chp:impl}章ではこれらの項目の実装を行う。