Mercurial > hg > Papers > 2018 > parusu-master
annotate paper/gearsOS.tex @ 16:77c129874cfa
UPdate
| author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 27 Jan 2018 17:13:05 +0900 |
| parents | 10cb71d30fc0 |
| children | 82c09c49bb4a |
| rev | line source |
|---|---|
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
1 \chapter{Gears OS の概念} |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
2 Gears OS は信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に開発している OSである。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
3 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
4 Gears OS は処理の単位を Code Gear、データの単位を Data Gear と呼ばれる単位でプログラムを構成する。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
5 信頼性や拡張性はメタ計算として、通常の計算とは区別して記述する。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
6 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
7 本章では Gears OS を構成する様々な要素について説明する。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
8 |
| 2 | 9 \section{Code GearとData Gear} |
| 10 Gears OS はプログラムとデータの単位として Gear を用いる。 | |
| 11 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 | |
| 12 | |
| 3 | 13 Code Gear はプログラムの処理そのもので、\figref{cdg1} で示しているように任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。 |
| 2 | 14 また、Code Gear は接続された Data Gear 以外には参照を行わない。 |
| 3 | 15 この Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。 |
| 2 | 16 |
| 17 Code Gear 間の移動は継続を用いて行われる。 | |
| 18 継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。 | |
| 3 | 19 そのため Code Gear、Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。 |
| 2 | 20 |
| 21 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。 | |
| 22 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。 | |
| 23 | |
| 24 \begin{figure}[htbp] | |
| 25 \begin{center} | |
| 3 | 26 \includegraphics[scale=0.6]{./fig/codegear-datagear.pdf} |
| 2 | 27 \end{center} |
| 3 | 28 \caption{Code Gear と Data Gear の関係} |
| 29 \label{fig:cdg1} | |
| 2 | 30 \end{figure} |
| 31 | |
| 32 \section{Continuation based C} | |
| 16 | 33 Gears OS の実装は本研究室で開発されている CbC(Continuation based C) を用いて行う。 |
| 2 | 34 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。 |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
35 CbC の処理系として llvm/clang\cite{kaito-lola} と gcc\cite{nobu-prosym} による実装などが存在する。 |
| 2 | 36 |
| 37 CbC の記述例を\coderef{cg1}に, 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。 | |
| 38 CbC の Code Gear は \_\_code という型を持つ関数として記述する。 | |
| 39 Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。 | |
| 40 そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。 | |
| 16 | 41 Code Gear から次の Code Gear への遷移は goto 文による継続で処理を行い、次の Code Gear への引数として入出力を与える。 |
| 3 | 42 \coderef{cg1}内の goto cg1 (a+b); が継続にあたり、 (a+b) がcg1 への入力になる。 |
| 2 | 43 |
| 44 \lstinputlisting[caption=CodeSegmentの軽量継続, label=code:cg1]{./src/cg1.cbc} | |
| 45 | |
| 16 | 46 CbC の goto 文による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。 |
| 3 | 47 この継続を軽量継続と呼ぶ。 |
| 48 \coderef{cg1} は cs0 から cs1 へ継続したあとには cs0 へ戻らずに処理を続ける。 | |
| 49 | |
| 2 | 50 \begin{figure}[htbp] |
| 51 \begin{center} | |
| 52 \includegraphics[scale=1.0]{./fig/goto.pdf} | |
| 53 \end{center} | |
| 16 | 54 \caption{goto 文による Code Gearの軽量継続} |
| 2 | 55 \label{fig:cg1} |
| 56 \end{figure} | |
| 57 | |
| 3 | 58 \section{メタ計算} |
| 59 プログラムの記述する際は、ノーマルレベルの計算の他に、メモリ管理、スレッド管理、CPUがGPUの資源管理等を記述しなければならない処理が存在する。 | |
| 60 これらの計算はノーマルレベルの計算と区別してメタ計算と呼ぶ。 | |
| 61 | |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
62 メタ計算は関数型言語では Monad\cite{moggi-monad} を用いて表現される。 |
| 3 | 63 Monad は Haskell では実行時の環境を記述する構文として使われる。 |
| 64 | |
| 65 従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。 | |
| 66 実行時にメタ計算の変更を行う場合には OS 内部のパラメータの変更を使用し、実行されるユーザープログラム自体への変更は限定的である。 | |
| 67 しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で実際のシステムコール単位では不十分である。 | |
| 68 例えば、モデル検査ではアセンブラあるいは バイトコード、インタプリタレベルでのメタ計算が必要になる。 | |
| 69 しかし、バイトコードレベルでは 粒度が細かすぎて扱いが困難になっている。具体的にはメタ計算の実行時間が大きくなってしまう。 | |
| 70 | |
| 71 \section{Meta Gear} | |
| 72 Gears OS の Code Gear は関数に比べて細かく分割されているため、メタ計算をより柔軟に記述できる。 | |
| 73 Code Gear と Data Gear にはそれぞれメタ計算の区分として Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実装する。 | |
| 74 Meta Gear は 制限された Monad に相当し、型付きアセンブラよりは大きな表現単位を提供する。 | |
| 75 Haskell などの関数型プログラミング言語では実行環境が複雑であり、実行時の資源使用を明確にすることができないが、Gears OS を記述している CbC はスタック上に隠された環境を持たないので、メタ計算で使用する資源を明確にできる利点がある。 | |
| 76 Meta Code Gear は\figref{mcg1}に示すように通常の Code Gear の直後に遷移され、メタ計算を実行する。 | |
| 77 また、 Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。 | |
| 78 | |
| 79 \begin{figure}[htbp] | |
| 80 \begin{center} | |
| 81 \includegraphics[scale=0.6]{./fig/meta_cg_dg.pdf} | |
| 82 \end{center} | |
| 83 \caption{Meta Code Gear の実行} | |
| 84 \label{fig:mcg1} | |
| 85 \end{figure} | |
| 2 | 86 |
| 87 \section{Context} | |
| 3 | 88 Context は接続可能な Code/Data Gear のリスト、Data Gearを確保するメモリ空間、実行される Task への Code Gear等を持っている Meta Data Gearである。 |
| 89 Gears OS では Code Gear と Data Gear への接続を Context を通して行う。 | |
| 90 | |
| 91 また、Context は並列実行の Task でもあり、従来のスレッドやプロセスに対応する。 | |
| 92 そのため Gears OS で並列実行を行うには Context を生成し、Task の実行を行う。 | |
| 93 | |
| 94 \coderef{context} に Context の定義を示す。 | |
| 95 | |
| 96 \lstinputlisting[caption=Contextの定義, label=code:context]{./src/context.h} | |
| 97 | |
| 98 \coderef{context} は以下の内容を定義している。 | |
| 99 | |
| 100 \begin{itemize} | |
| 101 \item Code Gear の名前と関数ポインタとの対応表 | |
| 10 | 102 |
| 3 | 103 Code Gear の名前とポインタの対応は Context 内の code(\coderef{context} 4行目) に格納される。 |
| 104 code は全ての Code Gear を列挙した enum と関数ポインタの組で表現される。 | |
| 105 Code Gear の名前は enum で定義され、コンパイル後には整数へと変換される。 | |
| 106 実際に Code Gear に接続する際は番号(enum)を指定することで接続を行う。 | |
| 107 これにより、メタ計算の実行時に接続する Code Gear を動的に切り替えることが可能となる。 | |
| 108 \item Data Gear の Allocation 用の情報 | |
| 10 | 109 |
| 3 | 110 Data Gear のメモリ空間は事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 |
| 111 実際に Allocation する際は Context内の heap(\coderef{context} 8行目)を Data Gear のサイズ分インクリメントすることで実現する。 | |
| 112 \item Code Gear が参照する DataGear へのポインタ | |
| 10 | 113 |
| 3 | 114 Allocation で生成した Data Gear へのポインタは Context 内のdata(\coderef{context} 6行目) に格納される。 |
| 115 Code Gear は data を参照して Data Gear へアクセスする。 | |
| 116 \item 並列実行用の Task 情報 | |
| 10 | 117 |
| 3 | 118 Context は 並列実行の Task も兼任するため、待っている Input Data Gear のカウンタ、Input/Output Data Gear が格納されている場所を示すインデックス、GPU での実行フラグ等を持っている(\coderef{context} 13-30行目)。 |
| 119 \item Data Gear の型情報 | |
| 10 | 120 |
| 3 | 121 Data Gear は構造体を用いて定義する(\coderef{context} 34-49行目)。Timer や TimerImplなどの構造体が Data Gear に相当する。 |
| 122 メタ計算では任意のData Gear を一律に扱うため、全ての Data Gear の共用体を定義する(\coderef{context} 33-51行目)。 | |
| 123 Data Gear を確保する際のサイズはこの型情報から決定する。 | |
| 124 \end{itemize} | |
| 125 | |
| 2 | 126 \section{Interface} |
| 3 | 127 Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合を表現する Data Gear である。 |
| 128 Interface には複数の実装を持つことができ、実装によって実行する Code Gear を切り替えることが可能になる。 | |
| 129 | |
| 130 Queue の Interface を \coderef{queueInterface} に示す。 | |
| 131 Interface は API となる Code Gear を \_\_code として 定義(\coderef{queueInterface} 6-9行目)する。 | |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
132 この \_\_code の実体は Code Gear への番号が格納される変数であり、Interface の実装毎に値は変化する。 |
| 3 | 133 |
| 134 \lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} | |
| 135 | |
| 136 \coderef{singleLinkedQueue} は Queue Interface を用いた SingleLinkedQueue の実装である。 | |
| 137 createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) は Queue Interface を実装した Data Gear の生成を行っている関数であり、 データ構造の初期化と実装した Code Gear の番号(enum)を Queue Interface で定義している Code Gear を示す変数に入れる(\coderef{singleLinkedQueue} 9-12行目)。 | |
| 138 | |
| 139 \lstinputlisting[caption=SingleLinkedQueue の実装, label=code:singleLinkedQueue]{./src/singleLinkedQueue.cbc} | |
| 140 | |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
141 Interface での Code Gear 呼び出しは ``goto interface-\textgreater method'' という構文で行う。 |
| 3 | 142 ここの interface は createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) 等で初期化を行った Interface へのポインタ、method は実装した Code Gear の番号になる。 |
| 143 | |
| 144 \coderef{singleLinkedQueueTest} に Queue Interface を使用した Code Gearの呼び出し例を示す。 | |
| 11 | 145 この呼び出しでは SingleLinkedQueue の put 実装に継続される。 |
| 3 | 146 |
| 147 \lstinputlisting[caption=Queue Interface での Code Gear の呼び出し, label=code:singleLinkedQueueTest]{./src/singleLinkedQueueTest.cbc} | |
| 148 | |
| 149 \coderef{singleLinkedQueueTest} は実際にはスクリプトによって \coderef{singleLinkedQueueTest_script} に変換されコンパイルされる。 | |
| 150 \coderef{singleLinkedQueueTest_script} 内の Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す。 | |
| 151 この引数格納用の Data Gear は Context の初期化の際に生成される。 | |
| 11 | 152 引数格納用の Data Gear を取り出した後は変換前の呼び出しの引数を Interface で定義した Code Gear の引数情報に合わせて格納し、指定した Code Gear に継続する。 |
| 3 | 153 |
| 154 \lstinputlisting[caption=スクリプトによる変換後, label=code:singleLinkedQueueTest_script]{./src/singleLinkedQueueTest_script.cbc} | |
| 155 | |
| 156 \section {stub Code Gear} | |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
157 stub Code Gear は Code Gear の接続の間に挟まれる Meta Code Gear である。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
158 ノーマルレベルの Code Gear から Meta Data Gear である Context を直接参照してしまうと、ユーザがメタ計算をノーマルレベルで自由に記述できてしまい、メタ計算を分離した意味がなくなってしまう。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
159 stub Code Gear はこの問題を防ぐため、 Context から必要な Data Gear のみを ノーマルレベルの Code Gear に渡す処理を行っている。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
160 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
161 \coderef{stubCodeGear} に stub Code Gear の例を示す。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
162 stub Code Gear は使用される全ての Code Gear 毎に記述する必要がある。 |
| 10 | 163 しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、Interface を実装した Code Gear などの型が決まっており、引数が格納されている場所がわかる stub Code Gear はスクリプトで自動生成する。 |
|
5
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
164 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
165 \lstinputlisting[caption=stub Code Gear, label=code:stubCodeGear]{./src/stubCodeGear.cbc} |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
166 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
167 stub Code Gear はユーザーが自前で記述することも可能である。 |
|
9efc9009838d
Add stub Code Gear session
Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
168 つまり、ユーザーがメタ計算を記述することができる。 |
| 11 | 169 stub Code Gear を用いたメタ計算の例として、本来 stub Code Gear は対応した Code Gear に継続するが、自前で stub Code Gear を記述することで、継続先を柔軟に変更できる。 |