Mercurial > hg > Papers > 2017 > atton-master

comparison paper/cbc.tex @ 100:ebe838b83ada

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Self review
author atton <atton@cr.ie.u-ryukyu.ac.jp>
date Sun, 12 Feb 2017 11:52:20 +0900
parents 16dc3337a5a9
children
comparison
equal deleted inserted replaced
99:a891d7551bbf 100:ebe838b83ada
1 \chapter{Continuation based C} 1 \chapter{Continuation based C}
2 \label{chapter:cbc} 2 \label{chapter:cbc}
3 3
4 Continuation based C (CbC)は当研究室で開発しているプログラミング言語であり、OSや組み込みソフトウェアの開発を主な対象としている。 4 Continuation based C (CbC)は当研究室で開発しているプログラミング言語であり、OSや組み込みソフトウェアを主な対象としている。
5 CbC は C言語の下位の言語であり、構文はほぼC言語と同じものを持つが、よりアセンブラに近い形でプログラムを記述する。 5 CbC は C言語の下位の言語であり、構文はほぼC言語と同じものを持つが、よりアセンブラに近い形でプログラムを記述する。
6 CbC は CodeSegment と呼ばれる単位で処理を定義し、それらを組み合わせることにでプログラム全体を構成する。 6 CbC は CodeSegment と呼ばれる単位で処理を定義し、それらを組み合わせることにでプログラム全体を構成する。
7 データの単位は DataSegment と呼ばれる単位で定義し、それら CodeSegment によって変更していくことでプログラムの実行となる。 7 データの単位は DataSegment と呼ばれる単位で定義し、それら CodeSegment によって変更していくことでプログラムの実行となる。
8 CbC の処理系には llvm/clang による実装\cite{110009766999} と gcc\cite{weko_82695_1}による実装などが存在する。 8 CbC の処理系には llvm/clang による実装\cite{110009766999} と gcc\cite{weko_82695_1}による実装などが存在する。
9 9
53 \end{figure} 53 \end{figure}
54 54
55 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。 55 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。
56 通常環境とは関数の呼び出しスタックの状態である。 56 通常環境とは関数の呼び出しスタックの状態である。
57 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。 57 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。
58 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後にcs0 へ戻ることはできない。 58 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後には cs0 へ戻らずに処理を続ける。
59 59
60 もう少し複雑な CbC のソースコードをリスト\ref{src:factrial}に、実行される流れを図\ref{fig:factrial}に示す。 60 もう少し複雑な CbC のソースコードをリスト\ref{src:factrial}に、実行される流れを図\ref{fig:factrial}に示す。
61 このソースコードは整数の階乗を求めるプログラムである。 61 このソースコードは整数の階乗を求めるプログラムである。
62 CodeSegment factorial0 では自分自身への再帰的な継続を用いて階乗を計算している。 62 CodeSegment factorial0 では自分自身への再帰的な継続を用いて階乗を計算している。
63 軽量継続時には関数呼び出しのスタックは存在しないが、計算中の値を DataSegment で持つことで再帰を含むループ処理も行なうことができる。 63 軽量継続時には関数呼び出しのスタックは存在しないが、計算中の値を DataSegment で持つことで再帰を含むループ処理も行なうことができる。
80 プログラムを記述する際、本来行ないたい計算の他にも記述しなければならない部分が存在する。 80 プログラムを記述する際、本来行ないたい計算の他にも記述しなければならない部分が存在する。
81 メモリの管理やネットワーク処理、エラーハンドリングや並列処理などがこれにあたり、本来行ないたい計算と区別してメタ計算と呼ぶ。 81 メモリの管理やネットワーク処理、エラーハンドリングや並列処理などがこれにあたり、本来行ないたい計算と区別してメタ計算と呼ぶ。
82 プログラムを動作させるためにメタ計算部分は必須であり、しばしば本来の処理よりも複雑度が高い。 82 プログラムを動作させるためにメタ計算部分は必須であり、しばしば本来の処理よりも複雑度が高い。
83 83
84 CodeSegment を用いたプログラミングスタイルでは計算とメタ計算を分離して記述する。 84 CodeSegment を用いたプログラミングスタイルでは計算とメタ計算を分離して記述する。
85 分離した計算は階層構造を持ち、本来行ないたい処理をノーマルレベルとし、メタ計算はメタレベルとしてノーマルレベルよりも上の存在に位置する。 85 なお、分離した計算は階層構造を持つ。
86 本来行ないたい処理はノーマルレベルであり、メタ計算はメタレベルとして上位に位置する。
86 複雑なメタ計算部分をライブラリやOS側が提供することで、ユーザはノーマルレベルの計算の記述に集中することができる。 87 複雑なメタ計算部分をライブラリやOS側が提供することで、ユーザはノーマルレベルの計算の記述に集中することができる。
87 また、ノーマルレベルのプログラムに必要なメタ計算を追加することで、並列処理やネットワーク処理などを含むプログラムに拡張できる。 88 また、ノーマルレベルのプログラムに必要なメタ計算を追加することで、並列処理やネットワーク処理などを含むプログラムに拡張できる。
88 さらに、ノーマルレベルからはメタレベルは隠蔽されているため、メタ計算の実装を切り替えることも可能である。 89 さらに、ノーマルレベルからはメタレベルは隠蔽されているため、メタ計算の実装を切り替えることも可能である。
89 例えば、並列処理のメタ計算用いたプログラムを作成する際、CPUで並列処理を行なうメタ計算とGPUで並列処理メタ計算を環境に応じて作成することができる。 90 例えば、並列処理のメタ計算用いたプログラムを作成する際、CPUで並列処理を行なうメタ計算とGPUで並列処理メタ計算を環境に応じて作成することができる。
90 91
104 105
105 % {{{ Continuation based C におけるメタ計算の例: GearsOS 106 % {{{ Continuation based C におけるメタ計算の例: GearsOS
106 \section{Continuation based C におけるメタ計算の例: GearsOS} 107 \section{Continuation based C におけるメタ計算の例: GearsOS}
107 CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142109_1}が存在する。 108 CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142109_1}が存在する。
108 GearsOS は並列に、信頼性高く動作することを目標としたOS であり、 マルチコアCPUやGPU環境での動作を対象としている。 109 GearsOS は並列に、信頼性高く動作することを目標としたOS であり、 マルチコアCPUやGPU環境での動作を対象としている。
109 現在OSの設計と並列処理部分の実装が行なわれている。 110 現在はOSの設計と並列処理部分の実装が行なわれている。
110 GearsOS におけるメタ計算はMonad\cite{Moggi:1991:NCM:116981.116984}を用いている~\cite{kkb-master}。 111 GearsOS におけるメタ計算はMonad\cite{Moggi:1991:NCM:116981.116984}を用いている~\cite{kkb-master}。
111 現在実装済みのメタ計算はメモリの管理、並列に書き込むことが可能な Synchronized Queue、データの保存用の非破壊赤黒木がある。 112 実装済みのメタ計算はメモリの管理、並列に書き込むことが可能な Synchronized Queue、データの保存用の非破壊赤黒木がある。
112 113
113 GearsOS では CodeSegment と DataSegment はそれぞれ CodeGear と DataGear と呼ばれている。 114 GearsOS では CodeSegment と DataSegment はそれぞれ CodeGear と DataGear と呼ばれている。
114 マルチコアCPU環境では CodeGear と CodeSegment は同一だが、GPU 環境では CodeGear には OpenCL~\cite{opencl}/CUDA~\cite{cuda} における kernel も含まれる。 115 マルチコアCPU環境では CodeGear と CodeSegment は同一だが、GPU 環境では CodeGear には OpenCL~\cite{opencl}/CUDA~\cite{cuda} における kernel も含まれる。
115 kernel とは GPU で実行される関数のことであり、GPU上のメモリに配置されたデータ群に対して並列に実行される。 116 kernel とは GPU で実行される関数のことであり、GPU上のメモリに配置されたデータ群に対して並列に実行される。
116 通常 GPU でデータの処理を行なう場合は 117 通常 GPU でデータの処理を行なう場合は
161 \item CodeGear の名前と CodeGear の関数ポインタ との対応表 162 \item CodeGear の名前と CodeGear の関数ポインタ との対応表
162 163
163 CodeGear の名前と CodeGear の関数ポインタの対応は enum と関数ポインタによって実現されている。 164 CodeGear の名前と CodeGear の関数ポインタの対応は enum と関数ポインタによって実現されている。
164 CodeGear の名前は enum (リスト\ref{src:context} 5-9行) で定義され、コンパイル後には整数へと変換される。 165 CodeGear の名前は enum (リスト\ref{src:context} 5-9行) で定義され、コンパイル後には整数へと変換される。
165 プログラム全体で利用する CodeGear は code フィールドに格納されており、enum を用いてアクセスする。 166 プログラム全体で利用する CodeGear は code フィールドに格納されており、enum を用いてアクセスする。
166 この対応表を動的に変更することにより、実行時に比較ルーチンなどを変更することが可能になる。 167 この対応表を動的に変更することで、実行時に比較ルーチンなどを変更することが可能になる。
167
168 168
169 \item CodeGear が参照する DataGear へのポインタ 169 \item CodeGear が参照する DataGear へのポインタ
170 170
171 Meta CodeGear は Context を引数に取る CodeGear として定義されている。 171 Meta CodeGear は Context を引数に取る CodeGear として定義されている。
172 そのため、Meta CodeGear が DataGear の値を使う為には Context から DataGear を取り出す必要がある。 172 そのため、Meta CodeGear が DataGear の値を使う為には Context から DataGear を取り出す必要がある。
192 stub の例をリスト\ref{src:stub}に示す。 192 stub の例をリスト\ref{src:stub}に示す。
193 \lstinputlisting[label=src:stub, caption=GearsOS における stub Meta CodeSegment] {src/stub.cbc} 193 \lstinputlisting[label=src:stub, caption=GearsOS における stub Meta CodeSegment] {src/stub.cbc}
194 194
195 stub は Context が持つ DataGear のポインタ data に対して enum を用いてアクセスしている。 195 stub は Context が持つ DataGear のポインタ data に対して enum を用いてアクセスしている。
196 なお、現在はメタレベルの計算とノーマルレベルの分離はコンパイラ側がサポートしていないため、引数に Meta DataGear である Context が渡されているが、本来はノーマルレベルではアクセスできない。 196 なお、現在はメタレベルの計算とノーマルレベルの分離はコンパイラ側がサポートしていないため、引数に Meta DataGear である Context が渡されているが、本来はノーマルレベルではアクセスできない。
197 % また、stub は全ての CodeGear に対してユーザが1つずつ定義する必要があるため、 CodeGear の定義が煩雑になっている。
198 % レベルの分離と stub の自動生成を行なうスクリプトも存在しているが、コンパイラ側のサポートはまだ行なわれていない。
199 % 型情報を用いたコンパイル時 stub 生成や、軽量継続時の型チェックを行なうために本研究では CbC の型システムを定義する。
200 197
201 また、GearsOS におけるメタ計算として CodeGear のモデル検査がある。 198 また、GearsOS におけるメタ計算として CodeGear のモデル検査がある。
202 通常レベルの CodeGear を変更することなく、その仕様を検証するものである。 199 通常レベルの CodeGear を変更することなく、その仕様を検証するものである。
203 個々の CodeGear の仕様を検証することにより、より信頼性の高いOSを目指す。 200 個々の CodeGear の仕様を検証することにより、より信頼性の高いOSを目指す。
204 201