Mercurial > hg > Papers > 2018 > nozomi-master
annotate paper/cbc.tex @ 26:5510bb043a74
Add rbtree description
| author | atton <atton@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 23 Jan 2017 15:42:08 +0900 |
| parents | 9325a5d0a6e0 |
| children | 243d8dc4a292 |
| rev | line source |
|---|---|
| 12 | 1 \chapter{Continuation based C} |
| 22 | 2 \label{chapter:cbc} |
| 12 | 3 |
| 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 と組み合わせることが可能である。 | |
| 18 あるCodeSegment A を CodeSegment B に接続した場合、 A の出力は B の入力となる。 | |
| 19 | |
| 20 % TODO: figure (cs A . cs B) | |
| 21 | |
| 22 DataSegment は CodeSegment が扱うデータの単位であり、処理に必要なデータが全て入っている。 | |
| 23 CodeSegment の入力となる DataSegment は Input DataSegment と呼ばれ、出力は Output DataSegment と呼ばれる。 | |
| 24 CodeSegment A と CodeSegment B を接続した時、A の Output DataSegment は B の入力 Input DataSegment となる。 | |
| 25 | |
| 26 % TODO: figure (cs A --(ds)--> cs B) | |
| 27 | |
| 13 | 28 % }}} |
| 12 | 29 |
| 15 | 30 % {{{ Continuation based C における CodeSegment と DataSegment |
| 31 | |
| 12 | 32 \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
|
33 最も基本的な CbC のソースコードをリスト\ref{src:goto}に、ソースコードが実行される流れを図\ref{fig:goto}に示す。 |
| 13 | 34 Continuation based C における CodeSegment は返り値を持たない関数として表現される。 |
| 35 CodeSegment を定義するためには、C言語の関数を定義する構文の返り値の型部分に \verb/__code/ キーワードを指定する。 | |
| 36 Input DataSegment は関数の引数として定義される。 | |
| 37 次の 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
|
38 処理の移動を軽量継続と呼び、リスト\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
|
39 この時の \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
|
40 |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
41 \lstinputlisting[label=src:goto, caption=CodeSegment の軽量継続] {src/goto.cbc} |
| 12 | 42 |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
43 \begin{figure}[htbp] |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
44 \begin{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
45 \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
|
46 \caption{CodeSegment の軽量継続} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
47 \label{fig:goto} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
48 \end{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
49 \end{figure} |
| 13 | 50 |
| 51 % TODO: scheme ref? | |
| 52 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。 | |
| 53 通常環境とは関数の呼び出しスタックの状態である。 | |
| 54 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。 | |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
55 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後にcs0 へ戻ることはできない。 |
| 13 | 56 |
| 15 | 57 もう少し複雑な CbC のソースコードをリスト\ref{src:factrial}に、実行される流れを図\ref{fig:factrial}に示す。 |
| 58 このソースコードは整数の階乗を求めるプログラムである。 | |
| 59 CodeSegment factorial0 では自分自身への再帰的な継続を用いて階乗を計算している。 | |
| 60 軽量継続時には関数呼び出しのスタックは存在しないが、計算中の値を DataSegment で持つことで再帰を含むループ処理も行なうことができる。 | |
| 61 | |
| 62 \lstinputlisting[label=src:factrial, caption=階乗を求める CbC プログラム] {src/factrial.cbc} | |
| 13 | 63 |
| 15 | 64 \begin{figure}[htbp] |
| 65 \begin{center} | |
| 66 \includegraphics[scale=0.8]{fig/factorial.pdf} | |
| 67 \caption{階乗を求める CbC プログラム} | |
| 68 \label{fig:factrial} | |
| 69 \end{center} | |
| 70 \end{figure} | |
| 12 | 71 |
| 15 | 72 % }}} |
| 12 | 73 |
| 16 | 74 % {{{ MetaCodeSegment と MetaDataSegment |
| 75 | |
| 12 | 76 \section{MetaCodeSegment と MetaDataSegment} |
| 16 | 77 プログラムを記述する際、本来行ないたい計算の他にも記述しなければならない部分が存在する。 |
| 78 メモリの管理やネットワーク処理、エラーハンドリングや並列処理などがこれにあたり、本来行ないたい計算と区別してメタ計算と呼ぶ。 | |
| 79 プログラムを動作させるためにメタ計算部分は必須であり、しばしば本来の処理よりも複雑度が高い。 | |
| 80 | |
| 81 CodeSegment を用いたプログラミングスタイルでは計算とメタ計算を分離して記述する。 | |
| 82 分離した計算は階層構造を持ち、本来行ないたい処理をノーマルレベルとし、メタ計算はメタレベルとしてノーマルレベルよりも上の存在に位置する。 | |
| 83 複雑なメタ計算部分をライブラリやOS側が提供することで、ユーザはノーマルレベルの計算の記述に集中することができる。 | |
| 84 また、ノーマルレベルのプログラムに必要なメタ計算を追加することで、並列処理やネットワーク処理などを含むプログラムに拡張できる。 | |
| 85 さらに、ノーマルレベルからはメタレベルは隠蔽されているため、メタ計算の実装を切り替えることも可能である。 | |
| 86 例えば、並列処理のメタ計算用いたプログラムを作成する際、CPUで並列処理を行なうメタ計算とGPUで並列処理メタ計算を環境に応じて作成することができる。 | |
| 87 | |
| 88 なお、メタ計算を行なう CodeSegment は Meta CodeSegment と呼び、メタ計算に必要な DataSegment は Meta DataSegment と呼ぶ。 | |
| 89 Meta CodeSegment は CodeSegment の前後にメタ計算を挟むことで実現され、Meta DataSegment は DataSegment を含む上位の DataSegment として実現できる。 | |
| 90 よって、メタ計算は通常の計算を覆うように計算を拡張するものだと考えられる(図\ref{fig:meta})。 | |
| 91 | |
| 92 \begin{figure}[htbp] | |
| 93 \begin{center} | |
| 94 \includegraphics[scale=1.0]{fig/meta.pdf} | |
| 95 \caption{Meta CodeSegment と Meta DataSegment} | |
| 96 \label{fig:meta} | |
| 97 \end{center} | |
| 98 \end{figure} | |
| 99 | |
| 100 % }}} | |
| 101 | |
| 18 | 102 % {{{ Continuation based C におけるメタ計算の例: GearsOS |
| 17 | 103 \section{Continuation based C におけるメタ計算の例: GearsOS} |
| 104 CbC におけるメタ計算は軽量継続を行なう際に Meta CodeSegment を挟むことで実現できる。 | |
| 105 CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142108_1}が存在する。 | |
| 106 GearsOS とはマルチコアCPUやGPU環境での動作を対象としたOSであり、現在OSの設計と並列処理部分の実装が行なわれている。 | |
| 107 現在存在するメタ計算としてメモリの確保と割り当て、並列に書き込むことが可能な Synchronized Queue、データの保存に用いる非破壊赤黒木がある。 | |
| 12 | 108 |
| 17 | 109 GearsOS では CodeSegment と DataSegment はそれぞれ CodeGear と DataGear と呼ばれている。 |
| 23 | 110 マルチコアCPU環境では CodeGear と CodeSegment は同一だが、GPU 環境では CodeGear には OpenCL/CUDA における kernel も含まれる。 % TODO: ref OpenCL/CUDA |
| 17 | 111 kernel とは GPU で実行される関数のことであり、GPU上のメモリに配置されたデータ群に対して並列に実行されるものである。 |
| 112 通常 GPU でデータの処理を行なう場合はデータの転送、転送終了を同期で確認、 kernel 実行、kernel の終了を同期で確認する、という手順が必要である。 | |
| 113 CPU/GPU での処理をメタ計算で行なうことにより、ノーマルレベルでは CodeGear が実行されるデバイスや DataGear の位置を意識する必要が無いというメリットがある。 | |
| 114 | |
| 18 | 115 GearsOS においては軽量継続の呼び出し部分もメタ計算として実現されている。 |
| 116 ある CodeGear から次の CodeGear へと継続する際には、次に実行される CodeGear の名前を指定する。 | |
| 117 その名前を Meta CodeGear が解釈し、対応する CodeGear へと処理を引き渡す。 | |
| 118 これは従来の OS の Dynamic Loading Libary や Command の呼び出しに相当する。 | |
| 119 CodeGear と名前の対応は Meta DataGear に格納されており、従来の OS の Process や Thread に相当する。 | |
| 120 | |
| 121 具体的には Meta DataGear には以下のようなものが格納される。 | |
| 122 | |
| 123 \begin{itemize} | |
| 124 \item DataGear の型情報 | |
| 125 \item DataGear を格納するメモリの情報 | |
| 126 \item CodeGear の名前と CodeGear の関数ポインタ との対応表 | |
| 127 \item CodeGear が参照する DataGear へのポインタ | |
| 128 \end{itemize} | |
| 129 | |
| 130 実際の GearsOS におけるメモリ管理を含むメタ計算用の Meta DataGear の定義例をリスト\ref{src:context}に示す。 | |
| 131 Meta DataGear は Context という名前の構造体で定義されている。 | |
| 132 | |
| 133 \lstinputlisting[label=src:context, caption=GearsOS における Meta DataGearの定義例] {src/context.h} | |
| 134 | |
| 135 \begin{itemize} | |
| 136 \item DataGear の型情報 | |
| 137 | |
| 138 DataGear は構造体を用いて定義する(リスト\ref{src:context} 27-46行)。 | |
| 139 Tree や Node、 Allocate 構造体が DataGear に相当する。 | |
| 140 メタ計算は任意の DataGear 扱うために全ての DataGear を扱える必要がある。 | |
| 141 全ての DataGear の共用体を定義することで、 DataGear を一律に扱うことができる(リスト\ref{src:context} 26-47行)。 | |
| 142 メモリを確保する場合はこの型情報からサイズを決定する。 | |
| 143 | |
| 144 \item DataGear を格納するメモリの情報 | |
| 145 | |
| 146 メモリ領域の管理は、事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 | |
| 147 そのために Context は割り当て済みの領域 heap と、割り当てた DataGear の数 dataNum を持つ。 | |
| 148 | |
| 149 \item CodeGear の名前と CodeGear の関数ポインタ との対応表 | |
| 150 | |
| 151 CodeGear の名前と CodeGear の関数ポインタの対応は enum と関数ポインタによって実現されている。 | |
| 152 CodeGear の名前は enum (リスト\ref{src:context} 5-9行) で定義され、コンパイル後には整数へと変換される。 | |
| 153 プログラム全体で利用する CodeGear は code フィールドに格納されており、enum を用いてアクセスする。 | |
| 154 この対応表を動的に変更することにより、実行時に比較ルーチンなどを変更することが可能になる。 | |
| 155 | |
| 156 | |
| 157 \item CodeGear が参照する DataGear へのポインタ | |
| 158 | |
| 159 Meta CodeGear は Context を引数に取る CodeGear として定義されている。 | |
| 160 そのため、Meta CodeGear が DataGear の値を使う為には Context から DataGear を取り出す必要がある。 | |
| 161 取り出す必要がある DataGear は enum を用いて定義し(リスト\ref{src:context} 11-14行)、 CodeGear を実行する際に data フィールドから取り出す。 | |
| 162 \end{itemize} | |
| 163 | |
| 19 | 164 なお、この Context から DataGear を取り出す Meta CodeSegment を stub と呼ぶ。 |
| 165 stub の例をリスト\ref{src:stub}に示す。 | |
| 166 stub は Context が持つ DataGear のポインタ data に対して enum を用いてアクセスしている。 | |
| 167 現在、この stub は全ての CodeGear に対してユーザが1つずつ定義する必要がある。 | |
| 168 この作業は非常に煩雑であり、CodeGear の定義から生成するスクリプトを用いて定義の簡易化を行なっているが、コンパイラ側でのサポートは入っていない。 | |
| 169 この stub を型情報から自動生成するために Continuation based C における型システムを定義する必要がある。 | |
| 170 | |
| 171 \lstinputlisting[label=src:stub, caption=GearsOS における stub Meta CodeSegment] {src/stub.cbc} | |
| 172 | |
| 18 | 173 % }}} |
| 174 | |
| 17 | 175 \section{メタ計算ライブラリ akasha を用いた赤黒木の実装の検証} |
| 24 | 176 現状の GearsOS に実装されているメタ計算として、非破壊赤黒木が存在する。 |
| 177 メタ計算として定義することにより、ノーマルレベルからは木のバランスを必要なく要素の挿入と探索、削除が行なえる。 | |
| 178 赤黒木とは二分探索木の一種であり、木の各ノードが赤と黒の色を持っている。 | |
| 179 木に対して要素の挿入や削除を行なった際、その色を用いて木のバランスを保つ。 | |
| 17 | 180 |
| 24 | 181 二分探索木の条件は以下である。 |
| 182 | |
| 183 \begin{itemize} | |
| 184 \item 左の子孫の値は親の値より小さい | |
| 185 \item 右の子孫の値は親の値より大きい | |
| 186 \end{itemize} | |
| 187 | |
| 188 加えて、赤黒木が持つ具体的な条件は以下のものである。 | |
| 189 | |
| 190 \begin{itemize} | |
| 191 \item 各ノードは赤か黒の色を持つ。 | |
| 192 \item ルートノードの色は黒である。 | |
| 193 \item 葉ノードの色は黒である。 | |
| 194 \item 赤ノードは2つの黒ノードを子として持つ(よって赤ノードが続くことは無い)。 | |
| 195 \item ルートから最下位ノードへの経路に含まれる黒ノードの数はどの最下位ノードでも一定である。 | |
| 196 \end{itemize} | |
| 197 | |
| 198 | |
| 199 数値を要素に持つ赤黒木の例を図\ref{fig:rbtree}に示す。 | |
| 200 ルートノードは黒であり、赤ノードは連続していない。 | |
| 201 加えて各最下位ノードへの経路に含まれる黒ノードの個数は全て2である。 | |
| 202 | |
| 203 \begin{figure}[htbp] | |
| 204 \begin{center} | |
| 205 \includegraphics[scale=0.5]{fig/rbtree.pdf} | |
| 206 \caption{赤黒木の例} | |
| 207 \label{fig:rbtree} | |
| 208 \end{center} | |
| 209 \end{figure} | |
| 210 | |
| 211 これらの条件より、木をルートから辿った際に最も長い経路は最も短い経路の高々二倍に収まる。 | |
| 212 | |
| 25 | 213 \newpage % for layout |
| 214 | |
| 24 | 215 GearsOS で実装されている赤黒木は特に非破壊赤黒木であり、一度構築した木構造は破壊される操作ごとに新しい木構造が生成される。 |
| 216 非破壊赤黒木の実装の基本的な戦略は、変更したいノードへのルートノードからの経路を全て複製し、変更後に新たなルートノードとする。 | |
| 217 この際に変更が行なわれていない部分は変更前の木と共有する(図\ref{fig:non-destructive-rbtree})。 | |
| 218 これは一度構築された木構造は破壊されないという非破壊の性質を用いたメモリ使用量の最適化である。 | |
| 219 | |
| 25 | 220 \begin{figure}[htbp] |
| 221 \begin{center} | |
| 222 \includegraphics[scale=0.5]{fig/non-destructive-rbtree} | |
| 223 \caption{非破壊赤黒木の編集} | |
| 224 \label{fig:non-destructive-rbtree} | |
| 225 \end{center} | |
| 226 \end{figure} | |
| 26 | 227 |
| 228 CbC を用いて赤黒木を実装する際の問題として、関数の呼び出しスタックが存在しないため、関数の再帰呼び出しによって木が辿れないことがある。 | |
| 229 経路を辿るためにはノードに親への参照を持たせるか、挿入・削除時に辿った経路を記憶する必要がある。 | |
| 230 ノードが親への参照を持つ非破壊木構造は共通部分の共有が行なえないため、辿った経路を記憶する方法を使う。 | |
| 231 経路の記憶にはスタックを用い、スタックは Meta DataSegment に保持させる。 | |
| 232 | |
| 233 赤黒木を格納する DataSegment と Meta DataSegment の定義をリスト\ref{src:rbtree-context}に示す。 | |
| 234 経路の記憶に用いるスタックは Meta DataSegment である Context 内部の \verb/node_stack/ である。 | |
| 235 DataSegment は各ノード情報を持つ \verb/Node/構造体と、赤黒木を格納する \verb/Tree/構造体、挿入などで操作中の一時的な木を格納する \verb/Traverse/共用体などがある。 | |
| 236 | |
| 237 \lstinputlisting[label=src:rbtree-context, caption=赤黒木の DataSegment と Meta DataSegment] {src/rbtreeContext.h} | |
| 238 | |
| 239 Meta DataSegment を初期化する Meta CodeSegment initLLRBContext をリスト\ref{src:init-rbtree-context}に示す。 | |
| 240 この Meta CodeSegment ではメモリ領域の確保、CodeSegment 名と CodeSegment の実体の対応表の作成などを行なう。 | |
| 241 メモリ領域はプログラムの起動時に一定数のメモリを確保し、ヒープとして \verb/heap/ フィールドに保持させる。 | |
| 242 CodeSegment 名と CodeSegment の実体との対応は、enum で定義された CodeSegment 名の添字へと CodeSegment の関数ポインタを代入することにより持つ。 | |
| 243 例えば \verb/Put/ の実体は \verb/put_stub/ である。 | |
| 244 他にも DataSegment の初期化(リスト\ref{src:init-rbtree-context} 34-48)とスタックの初期化(リスト\ref{src:init-rbtree-context} 50-51)を行なう。 | |
| 245 | |
| 246 \lstinputlisting[label=src:init-rbtree-context, caption=赤黒木の Meta DataSegment の初期化を行なう Meta CodeSegment ] {src/initLLRBContext.c} | |
| 247 | |
| 248 実際の赤黒木の実装に用いられている Meta CodeSegment の一例をリスト\ref{src:rbtree-insert-case-2}に示す。 | |
| 249 Meta CodeSegment \verb/insertCase2/ は要素を挿入した場合に呼ばれる Meta CodeSegment の一つであり、親ノードの色によって処理を変える。 | |
| 250 まず、色を確認するために経路を記憶しているスタックから親の情報を取り出す。 | |
| 251 親の色が黒ならば処理を終了し、次の CodeSegment へと軽量継続する(リスト\ref{src:rbtree-insert-case-2} 5-8)。 | |
| 252 親の色が赤であるならばさらに処理を続行して \verb/InsertCase3/ へと軽量継続する。 | |
| 253 ここで、経路情報を再現するためにスタックへと親を再代入してから軽量継続を行なっている。 | |
| 254 なお、Meta CodeSegment でも Context から DataSegment を展開する処理は stub によって行なわれる(リスト\ref{src:rbtree-insert-case-2} 14-16)。 | |
| 255 | |
| 256 \lstinputlisting[label=src:rbtree-insert-case-2, caption=赤黒木の実装に用いられている Meta CodeSegment例] {src/insertCase2.c} | |
| 257 | |
| 258 | |
| 259 % TODO: akasha context case x の解説くらい | |
| 260 % TODO: akasha context の初期化 | |
| 261 % TODO: verification の assert | |
| 262 % TODO: akasha の結果 |