Mercurial > hg > Papers > 2018 > nozomi-master
annotate paper/cbc.tex @ 17:db2909ab202d
Add GearsOS
| author | atton <atton@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 20 Jan 2017 12:40:43 +0900 |
| parents | 3ffd17f96e06 |
| children | 415fa6d79d00 |
| rev | line source |
|---|---|
| 12 | 1 \chapter{Continuation based C} |
| 2 | |
| 3 Continuation based C (CbC)は当研究室で開発しているプログラミング言語であり、OSや組み込みソフトウェアの開発を主な対象としている。 | |
| 13 | 4 CbC は C言語の下位の言語であり、構文はほぼC言語と同じものを持つが、よりアセンブラに近い形でプログラムを記述する。 |
| 12 | 5 CbC は CodeSegment と呼ばれる単位で処理を定義し、それらを組み合わせることにでプログラム全体を構成する。 |
| 6 データの単位は DataSegment と呼ばれる単位で定義し、それら CodeSegment によって変更していくことでプログラムの実行となる。 | |
| 7 CbC の処理系には llvm/clang による実装\cite{110009766999} と gcc\cite{weko_82695_1}による実装などが存在する。 | |
| 8 | |
| 13 | 9 % {{{ section: CodeSegment と DataSegment |
| 12 | 10 |
| 11 \section{CodeSegment と DataSegment} | |
| 12 本研究室では検証を行ないやすいプログラムの単位として CodeSegment と DataSegment を用いるプラグラミングスタイルを提案している。 | |
| 13 | |
| 14 CodeSegment は処理の単位である。 | |
| 15 入力を受け取り、それに対して処理を行なった後を出力を行なう。 | |
| 16 また、CodeSegment は他の CodeSegment と組み合わせることが可能である。 | |
| 17 あるCodeSegment A を CodeSegment B に接続した場合、 A の出力は B の入力となる。 | |
| 18 | |
| 19 % TODO: figure (cs A . cs B) | |
| 20 | |
| 21 DataSegment は CodeSegment が扱うデータの単位であり、処理に必要なデータが全て入っている。 | |
| 22 CodeSegment の入力となる DataSegment は Input DataSegment と呼ばれ、出力は Output DataSegment と呼ばれる。 | |
| 23 CodeSegment A と CodeSegment B を接続した時、A の Output DataSegment は B の入力 Input DataSegment となる。 | |
| 24 | |
| 25 % TODO: figure (cs A --(ds)--> cs B) | |
| 26 | |
| 13 | 27 % }}} |
| 12 | 28 |
| 15 | 29 % {{{ Continuation based C における CodeSegment と DataSegment |
| 30 | |
| 12 | 31 \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
|
32 最も基本的な CbC のソースコードをリスト\ref{src:goto}に、ソースコードが実行される流れを図\ref{fig:goto}に示す。 |
| 13 | 33 Continuation based C における CodeSegment は返り値を持たない関数として表現される。 |
| 34 CodeSegment を定義するためには、C言語の関数を定義する構文の返り値の型部分に \verb/__code/ キーワードを指定する。 | |
| 35 Input DataSegment は関数の引数として定義される。 | |
| 36 次の 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
|
37 処理の移動を軽量継続と呼び、リスト\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
|
38 この時の \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
|
39 |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
40 \lstinputlisting[label=src:goto, caption=CodeSegment の軽量継続] {src/goto.cbc} |
| 12 | 41 |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
42 \begin{figure}[htbp] |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
43 \begin{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
44 \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
|
45 \caption{CodeSegment の軽量継続} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
46 \label{fig:goto} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
47 \end{center} |
|
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
48 \end{figure} |
| 13 | 49 |
| 50 % TODO: scheme ref? | |
| 51 Scheme などの call/cc といった継続はトップレベルから現在までの位置を環境として保持する。 | |
| 52 通常環境とは関数の呼び出しスタックの状態である。 | |
| 53 CbC の軽量継続は呼び出し元の情報を持たないため、スタックを破棄しながら処理を続けていく。 | |
|
14
6bf2e0196a1e
Add goto.cbc and goto.pdf
atton <atton@cr.ie.u-ryukyu.ac.jp>
parents:
13
diff
changeset
|
54 よって、リスト\ref{src:goto} のプログラムでは cs0 から cs1 へと継続した後にcs0 へ戻ることはできない。 |
| 13 | 55 |
| 15 | 56 もう少し複雑な CbC のソースコードをリスト\ref{src:factrial}に、実行される流れを図\ref{fig:factrial}に示す。 |
| 57 このソースコードは整数の階乗を求めるプログラムである。 | |
| 58 CodeSegment factorial0 では自分自身への再帰的な継続を用いて階乗を計算している。 | |
| 59 軽量継続時には関数呼び出しのスタックは存在しないが、計算中の値を DataSegment で持つことで再帰を含むループ処理も行なうことができる。 | |
| 60 | |
| 61 \lstinputlisting[label=src:factrial, caption=階乗を求める CbC プログラム] {src/factrial.cbc} | |
| 13 | 62 |
| 15 | 63 \begin{figure}[htbp] |
| 64 \begin{center} | |
| 65 \includegraphics[scale=0.8]{fig/factorial.pdf} | |
| 66 \caption{階乗を求める CbC プログラム} | |
| 67 \label{fig:factrial} | |
| 68 \end{center} | |
| 69 \end{figure} | |
| 12 | 70 |
| 15 | 71 % }}} |
| 12 | 72 |
| 16 | 73 % {{{ MetaCodeSegment と MetaDataSegment |
| 74 | |
| 12 | 75 \section{MetaCodeSegment と MetaDataSegment} |
| 16 | 76 プログラムを記述する際、本来行ないたい計算の他にも記述しなければならない部分が存在する。 |
| 77 メモリの管理やネットワーク処理、エラーハンドリングや並列処理などがこれにあたり、本来行ないたい計算と区別してメタ計算と呼ぶ。 | |
| 78 プログラムを動作させるためにメタ計算部分は必須であり、しばしば本来の処理よりも複雑度が高い。 | |
| 79 | |
| 80 CodeSegment を用いたプログラミングスタイルでは計算とメタ計算を分離して記述する。 | |
| 81 分離した計算は階層構造を持ち、本来行ないたい処理をノーマルレベルとし、メタ計算はメタレベルとしてノーマルレベルよりも上の存在に位置する。 | |
| 82 複雑なメタ計算部分をライブラリやOS側が提供することで、ユーザはノーマルレベルの計算の記述に集中することができる。 | |
| 83 また、ノーマルレベルのプログラムに必要なメタ計算を追加することで、並列処理やネットワーク処理などを含むプログラムに拡張できる。 | |
| 84 さらに、ノーマルレベルからはメタレベルは隠蔽されているため、メタ計算の実装を切り替えることも可能である。 | |
| 85 例えば、並列処理のメタ計算用いたプログラムを作成する際、CPUで並列処理を行なうメタ計算とGPUで並列処理メタ計算を環境に応じて作成することができる。 | |
| 86 | |
| 87 なお、メタ計算を行なう CodeSegment は Meta CodeSegment と呼び、メタ計算に必要な DataSegment は Meta DataSegment と呼ぶ。 | |
| 88 Meta CodeSegment は CodeSegment の前後にメタ計算を挟むことで実現され、Meta DataSegment は DataSegment を含む上位の DataSegment として実現できる。 | |
| 89 よって、メタ計算は通常の計算を覆うように計算を拡張するものだと考えられる(図\ref{fig:meta})。 | |
| 90 | |
| 91 \begin{figure}[htbp] | |
| 92 \begin{center} | |
| 93 \includegraphics[scale=1.0]{fig/meta.pdf} | |
| 94 \caption{Meta CodeSegment と Meta DataSegment} | |
| 95 \label{fig:meta} | |
| 96 \end{center} | |
| 97 \end{figure} | |
| 98 | |
| 99 % }}} | |
| 100 | |
| 17 | 101 \section{Continuation based C におけるメタ計算の例: GearsOS} |
| 102 CbC におけるメタ計算は軽量継続を行なう際に Meta CodeSegment を挟むことで実現できる。 | |
| 103 | |
| 104 CbC を用いてメタ計算を実現した例として、GearsOS\cite{weko_142108_1}が存在する。 | |
| 105 GearsOS とはマルチコアCPUやGPU環境での動作を対象としたOSであり、現在OSの設計と並列処理部分の実装が行なわれている。 | |
| 106 現在存在するメタ計算としてメモリの確保と割り当て、並列に書き込むことが可能な Synchronized Queue、データの保存に用いる非破壊赤黒木がある。 | |
| 12 | 107 |
| 17 | 108 GearsOS では CodeSegment と DataSegment はそれぞれ CodeGear と DataGear と呼ばれている。 |
| 109 マルチコアCPU環境では CodeGear と CodeSegment は同一だが、GPU 環境では CodeGear には OpenCL/CUDA における kernel も含まれる。 % TODO: ref | |
| 110 kernel とは GPU で実行される関数のことであり、GPU上のメモリに配置されたデータ群に対して並列に実行されるものである。 | |
| 111 通常 GPU でデータの処理を行なう場合はデータの転送、転送終了を同期で確認、 kernel 実行、kernel の終了を同期で確認する、という手順が必要である。 | |
| 112 CPU/GPU での処理をメタ計算で行なうことにより、ノーマルレベルでは CodeGear が実行されるデバイスや DataGear の位置を意識する必要が無いというメリットがある。 | |
| 113 | |
| 114 \section{メタ計算ライブラリ akasha を用いた赤黒木の実装の検証} | |
| 115 |