Mercurial > hg > Papers > 2017 > atton-master
annotate paper/cbc.tex @ 130:80a196c82a4c
Update todo
| author | atton <atton@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 18 Feb 2017 15:43:09 +0900 |
| parents | ebe838b83ada |
| children |
| rev | line source |
|---|---|
| 12 | 1 \chapter{Continuation based C} |
| 22 | 2 \label{chapter:cbc} |
| 12 | 3 |
| 100 | 4 Continuation based C (CbC)は当研究室で開発しているプログラミング言語であり、OSや組み込みソフトウェアを主な対象としている。 |
| 13 | 5 CbC は C言語の下位の言語であり、構文はほぼC言語と同じものを持つが、よりアセンブラに近い形でプログラムを記述する。 |
| 12 | 6 CbC は CodeSegment と呼ばれる単位で処理を定義し、それらを組み合わせることにでプログラム全体を構成する。 |
| 7 データの単位は DataSegment と呼ばれる単位で定義し、それら CodeSegment によって変更していくことでプログラムの実行となる。 | |
| 8 CbC の処理系には llvm/clang による実装\cite{110009766999} と gcc\cite{weko_82695_1}による実装などが存在する。 | |
| 9 | |
| 13 | 10 % {{{ section: CodeSegment と DataSegment |
| 12 | 11 |
| 12 \section{CodeSegment と DataSegment} | |
| 13 本研究室では検証を行ないやすいプログラムの単位として CodeSegment と DataSegment を用いるプラグラミングスタイルを提案している。 | |
| 14 | |
| 15 CodeSegment は処理の単位である。 | |
| 16 入力を受け取り、それに対して処理を行なった後を出力を行なう。 | |
| 17 また、CodeSegment は他の CodeSegment と組み合わせることが可能である。 | |
| 87 | 18 あるCodeSegment A を CodeSegment B に接続した場合、 A の出力は B の入力となる(図~\ref{fig:csds})。 |
| 12 | 19 |
| 20 DataSegment は CodeSegment が扱うデータの単位であり、処理に必要なデータが全て入っている。 | |
| 21 CodeSegment の入力となる DataSegment は Input DataSegment と呼ばれ、出力は Output DataSegment と呼ばれる。 | |
| 22 CodeSegment A と CodeSegment B を接続した時、A の Output DataSegment は B の入力 Input DataSegment となる。 | |
| 23 | |
| 87 | 24 \begin{figure}[htbp] |
| 25 \begin{center} | |
| 26 \includegraphics[scale=0.5]{fig/csds.pdf} | |
| 27 \caption{CodeSegment と DataSegement} | |
| 28 \label{fig:csds} | |
| 29 \end{center} | |
| 30 \end{figure} | |
| 12 | 31 |
| 13 | 32 % }}} |
| 12 | 33 |
| 15 | 34 % {{{ Continuation based C における CodeSegment と DataSegment |
| 35 | |
| 12 | 36 \section{Continuation based C における CodeSegment と DataSegment} |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
37 最も基本的な CbC のソースコードをリスト\ref{src:goto}に、ソースコードが実行される流れを図\ref{fig:goto}に示す。 |
| 13 | 38 Continuation based C における CodeSegment は返り値を持たない関数として表現される。 |
| 39 CodeSegment を定義するためには、C言語の関数を定義する構文の返り値の型部分に \verb/__code/ キーワードを指定する。 | |
| 40 Input DataSegment は関数の引数として定義される。 | |
| 41 次の CodeSegment へ処理を移す際には \verb/goto/ キーワードの後に CodeSegment 名と Input DataSegment を指定する。 | |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
42 処理の移動を軽量継続と呼び、リスト\ref{src:goto}内の \verb/goto cs1(a+b);/ がこれにあたる。 |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
43 この時の \verb/(a+b)/ が次の CodeSegment である cs1 の Input DataSegment となる cs0 の Output DataSegment である。 |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
44 |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
45 \lstinputlisting[label=src:goto, caption=CodeSegment の軽量継続] {src/goto.cbc} |
| 12 | 46 |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
47 \begin{figure}[htbp] |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
48 \begin{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
49 \includegraphics[scale=1.0]{fig/goto.pdf} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
50 \caption{CodeSegment の軽量継続} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
51 \label{fig:goto} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
52 \end{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
53 \end{figure} |
| 13 | 54 |
| 55 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。 | |
| 56 通常環境とは関数の呼び出しスタックの状態である。 | |
| 57 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。 | |
| 100 | 58 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後には cs0 へ戻らずに処理を続ける。 |
| 13 | 59 |
| 15 | 60 もう少し複雑な CbC のソースコードをリスト\ref{src:factrial}に、実行される流れを図\ref{fig:factrial}に示す。 |
| 61 このソースコードは整数の階乗を求めるプログラムである。 | |
| 62 CodeSegment factorial0 では自分自身への再帰的な継続を用いて階乗を計算している。 | |
| 63 軽量継続時には関数呼び出しのスタックは存在しないが、計算中の値を DataSegment で持つことで再帰を含むループ処理も行なうことができる。 | |
| 64 | |
| 65 \lstinputlisting[label=src:factrial, caption=階乗を求める CbC プログラム] {src/factrial.cbc} | |
| 13 | 66 |
| 15 | 67 \begin{figure}[htbp] |
| 68 \begin{center} | |
| 69 \includegraphics[scale=0.8]{fig/factorial.pdf} | |
| 70 \caption{階乗を求める CbC プログラム} | |
| 71 \label{fig:factrial} | |
| 72 \end{center} | |
| 73 \end{figure} | |
| 12 | 74 |
| 15 | 75 % }}} |
| 12 | 76 |
| 16 | 77 % {{{ MetaCodeSegment と MetaDataSegment |
| 78 | |
| 12 | 79 \section{MetaCodeSegment と MetaDataSegment} |
| 16 | 80 プログラムを記述する際、本来行ないたい計算の他にも記述しなければならない部分が存在する。 |
| 81 メモリの管理やネットワーク処理、エラーハンドリングや並列処理などがこれにあたり、本来行ないたい計算と区別してメタ計算と呼ぶ。 | |
| 82 プログラムを動作させるためにメタ計算部分は必須であり、しばしば本来の処理よりも複雑度が高い。 | |
| 83 | |
| 84 CodeSegment を用いたプログラミングスタイルでは計算とメタ計算を分離して記述する。 | |
| 100 | 85 なお、分離した計算は階層構造を持つ。 |
| 86 本来行ないたい処理はノーマルレベルであり、メタ計算はメタレベルとして上位に位置する。 | |
| 16 | 87 複雑なメタ計算部分をライブラリやOS側が提供することで、ユーザはノーマルレベルの計算の記述に集中することができる。 |
| 88 また、ノーマルレベルのプログラムに必要なメタ計算を追加することで、並列処理やネットワーク処理などを含むプログラムに拡張できる。 | |
| 89 さらに、ノーマルレベルからはメタレベルは隠蔽されているため、メタ計算の実装を切り替えることも可能である。 | |
| 90 例えば、並列処理のメタ計算用いたプログラムを作成する際、CPUで並列処理を行なうメタ計算とGPUで並列処理メタ計算を環境に応じて作成することができる。 | |
| 91 | |
| 92 なお、メタ計算を行なう CodeSegment は Meta CodeSegment と呼び、メタ計算に必要な DataSegment は Meta DataSegment と呼ぶ。 | |
| 93 Meta CodeSegment は CodeSegment の前後にメタ計算を挟むことで実現され、Meta DataSegment は DataSegment を含む上位の DataSegment として実現できる。 | |
| 94 よって、メタ計算は通常の計算を覆うように計算を拡張するものだと考えられる(図\ref{fig:meta})。 | |
| 95 | |
| 96 \begin{figure}[htbp] | |
| 97 \begin{center} | |
| 87 | 98 \includegraphics[scale=0.5]{fig/meta.pdf} |
| 16 | 99 \caption{Meta CodeSegment と Meta DataSegment} |
| 100 \label{fig:meta} | |
| 101 \end{center} | |
| 102 \end{figure} | |
| 103 | |
| 104 % }}} | |
| 105 | |
| 18 | 106 % {{{ Continuation based C におけるメタ計算の例: GearsOS |
| 17 | 107 \section{Continuation based C におけるメタ計算の例: GearsOS} |
| 47 | 108 CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142109_1}が存在する。 |
| 76 | 109 GearsOS は並列に、信頼性高く動作することを目標としたOS であり、 マルチコアCPUやGPU環境での動作を対象としている。 |
| 100 | 110 現在はOSの設計と並列処理部分の実装が行なわれている。 |
| 93 | 111 GearsOS におけるメタ計算はMonad\cite{Moggi:1991:NCM:116981.116984}を用いている~\cite{kkb-master}。 |
| 100 | 112 実装済みのメタ計算はメモリの管理、並列に書き込むことが可能な Synchronized Queue、データの保存用の非破壊赤黒木がある。 |
| 12 | 113 |
| 17 | 114 GearsOS では CodeSegment と DataSegment はそれぞれ CodeGear と DataGear と呼ばれている。 |
| 74 | 115 マルチコアCPU環境では CodeGear と CodeSegment は同一だが、GPU 環境では CodeGear には OpenCL~\cite{opencl}/CUDA~\cite{cuda} における kernel も含まれる。 |
| 76 | 116 kernel とは GPU で実行される関数のことであり、GPU上のメモリに配置されたデータ群に対して並列に実行される。 |
| 117 通常 GPU でデータの処理を行なう場合は | |
| 17 | 118 |
| 76 | 119 \begin{itemize} |
| 120 \item データをメインメモリから GPUのメモリへ転送 | |
| 121 \item 転送終了を同期で確認 | |
| 122 \item kernel 起動(GPUメモリ上のデータに対して並列に処理) | |
| 123 \item 処理終了を同期で確認 | |
| 124 \item 計算結果であるデータを GPU のメモリからメインメモリへ転送 | |
| 125 \item 転送終了を同期で確認 | |
| 126 \end{itemize} | |
| 18 | 127 |
| 76 | 128 といった手順が必要であり、ユーザは処理したいデータの位置などを意識しながらプログラミングする必要がある。 |
| 129 GearsOS では CPU/GPU での処理をメタ計算としてユーザから隠すことにより、 CodeGear が実行されるデバイスや DataGear の位置を意識する必要がなくなる。 | |
| 130 | |
| 131 GearsOS で利用する Meta DataGear には以下のものが含まれる。 | |
| 18 | 132 |
| 133 \begin{itemize} | |
| 134 \item DataGear の型情報 | |
| 135 \item DataGear を格納するメモリの情報 | |
| 136 \item CodeGear の名前と CodeGear の関数ポインタ との対応表 | |
| 137 \item CodeGear が参照する DataGear へのポインタ | |
| 138 \end{itemize} | |
| 139 | |
| 140 実際の GearsOS におけるメモリ管理を含むメタ計算用の Meta DataGear の定義例をリスト\ref{src:context}に示す。 | |
| 141 Meta DataGear は Context という名前の構造体で定義されている。 | |
| 76 | 142 通常レベルの DataGear も構造体で定義されているが、メタ計算側から見た DataGear はそれぞれの構造体の共用体となっており、一様に扱える。 |
| 18 | 143 |
| 144 \lstinputlisting[label=src:context, caption=GearsOS における Meta DataGearの定義例] {src/context.h} | |
| 145 | |
| 76 | 146 リスト~\ref{src:context}のソースコードは以下のように対応している。 |
| 147 | |
| 18 | 148 \begin{itemize} |
| 149 \item DataGear の型情報 | |
| 150 | |
| 151 DataGear は構造体を用いて定義する(リスト\ref{src:context} 27-46行)。 | |
| 152 Tree や Node、 Allocate 構造体が DataGear に相当する。 | |
| 153 メタ計算は任意の DataGear 扱うために全ての DataGear を扱える必要がある。 | |
| 154 全ての DataGear の共用体を定義することで、 DataGear を一律に扱うことができる(リスト\ref{src:context} 26-47行)。 | |
| 155 メモリを確保する場合はこの型情報からサイズを決定する。 | |
| 156 | |
| 157 \item DataGear を格納するメモリの情報 | |
| 158 | |
| 159 メモリ領域の管理は、事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 | |
| 160 そのために Context は割り当て済みの領域 heap と、割り当てた DataGear の数 dataNum を持つ。 | |
| 161 | |
| 162 \item CodeGear の名前と CodeGear の関数ポインタ との対応表 | |
| 163 | |
| 164 CodeGear の名前と CodeGear の関数ポインタの対応は enum と関数ポインタによって実現されている。 | |
| 165 CodeGear の名前は enum (リスト\ref{src:context} 5-9行) で定義され、コンパイル後には整数へと変換される。 | |
| 166 プログラム全体で利用する CodeGear は code フィールドに格納されており、enum を用いてアクセスする。 | |
| 100 | 167 この対応表を動的に変更することで、実行時に比較ルーチンなどを変更することが可能になる。 |
| 18 | 168 |
| 169 \item CodeGear が参照する DataGear へのポインタ | |
| 170 | |
| 171 Meta CodeGear は Context を引数に取る CodeGear として定義されている。 | |
| 172 そのため、Meta CodeGear が DataGear の値を使う為には Context から DataGear を取り出す必要がある。 | |
| 173 取り出す必要がある DataGear は enum を用いて定義し(リスト\ref{src:context} 11-14行)、 CodeGear を実行する際に data フィールドから取り出す。 | |
| 174 \end{itemize} | |
| 175 | |
| 76 | 176 Meta CodeGear は定義された Meta DataGear を処理する CodeGear である。 |
| 177 メモリ管理や並列処理の待ち合わせといった処理はこのメタレベルにしか表れない。 | |
| 26 | 178 |
| 76 | 179 GearsOS においては軽量継続もメタ計算として実現されている。 |
| 180 とある CodeGear から次の CodeGear へと軽量継続する際には、次に実行される CodeGear の名前を指定する。 | |
| 181 その名前を Meta CodeGear が解釈し、対応する CodeGear へと処理を引き渡す(リスト~\ref{src:meta}の \verb/meta/)。 | |
| 27 | 182 |
| 28 | 183 \lstinputlisting[label=src:meta, caption=通常の CodeSegment の軽量継続] {src/meta.c} |
| 27 | 184 |
| 76 | 185 CodeGear と名前の対応は Meta DataGear に格納されており、従来の OS の Process や Thread に相当する。 |
| 186 名前の対応を動的に切り替えたり、Thread ごとに切り替えることにより、通常レベルのプログラムを変更せず実行を上書きできる。 | |
| 187 これは従来の OS の Dynamic Loading Libary や Command の呼び出しに相当する。 | |
| 188 | |
| 189 また、通常レベルの CodeGear から Meta DataGear を操作できてしまうと、ユーザがメタレベル操作を自由に記述できてしまい、メタ計算を分離した意味が無くなってしまう。 | |
| 190 これを防ぐために、CodeGear を実行する際は Meta DataGear から必要な DataGear だけを渡す。 | |
| 191 このように、 Meta DataGear から DataGear を取り出す Meta CodeGear を stub と呼ぶ。 | |
| 192 stub の例をリスト\ref{src:stub}に示す。 | |
| 193 \lstinputlisting[label=src:stub, caption=GearsOS における stub Meta CodeSegment] {src/stub.cbc} | |
| 28 | 194 |
| 76 | 195 stub は Context が持つ DataGear のポインタ data に対して enum を用いてアクセスしている。 |
| 196 なお、現在はメタレベルの計算とノーマルレベルの分離はコンパイラ側がサポートしていないため、引数に Meta DataGear である Context が渡されているが、本来はノーマルレベルではアクセスできない。 | |
| 197 | |
| 198 また、GearsOS におけるメタ計算として CodeGear のモデル検査がある。 | |
| 199 通常レベルの CodeGear を変更することなく、その仕様を検証するものである。 | |
| 200 個々の CodeGear の仕様を検証することにより、より信頼性の高いOSを目指す。 | |
| 28 | 201 |
| 202 % }}} |