Mercurial > hg > Papers > 2018 > parusu-master
changeset 25:43a2be7500dd
Replace ','
| author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 30 Jan 2018 05:00:39 +0900 |
| parents | 2c896f2b2d04 |
| children | 9d2a0a735986 |
| files | paper/gearsOS.tex paper/interface.tex paper/master_paper.pdf paper/parallelism_gears.tex |
| diffstat | 4 files changed, 41 insertions(+), 42 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/gearsOS.tex Tue Jan 30 04:48:12 2018 +0900 +++ b/paper/gearsOS.tex Tue Jan 30 05:00:39 2018 +0900 @@ -12,13 +12,13 @@ Code Gear はプログラムの処理そのもので、\figref{cdg1} で示しているように任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。 また、Code Gear は接続された Data Gear 以外には参照を行わない。 -この Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。 +この Input / Output Data Gear の対応から依存関係を解決し、Code Gear の並列実行を可能とする。 Code Gear 間の移動は継続を用いて行われる。 継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。 そのため Code Gear、Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。 -Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。 +Gear の特徴として処理やデータの構造が Code Gear、Data Gear に閉じていることにある。 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。 \begin{figure}[htbp] @@ -30,19 +30,19 @@ \end{figure} また Gears OS 自体もこの Code Gear、Data Gear を用いた CbC(Continuation based C) で実装される。 -そのため、 Gears OS の実装は Code Gear、 Data Gear を用いたプログラミングスタイルの指標となる。 +そのため、Gears OS の実装は Code Gear、Data Gear を用いたプログラミングスタイルの指標となる。 \section{Continuation based C} Gears OS の実装は本研究室で開発されている CbC(Continuation based C) を用いて行う。 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。 CbC の処理系として llvm/clang\cite{kaito-lola} と gcc\cite{nobu-prosym} による実装などが存在する。 -CbC の記述例を\coderef{cg1}に, 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。 +CbC の記述例を\coderef{cg1}に、 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。 CbC の Code Gear は \_\_code という型を持つ関数として記述する。 Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。 そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。 Code Gear から次の Code Gear への遷移は goto 文による継続で処理を行い、次の Code Gear への引数として入出力を与える。 -\coderef{cg1}内の goto cg1 (a+b); が継続にあたり、 (a+b) がcg1 への入力になる。 +\coderef{cg1}内の goto cg1 (a+b); が継続にあたり、(a+b) がcg1 への入力になる。 \lstinputlisting[caption=CodeSegmentの軽量継続, label=code:cg1]{./src/cg1.cbc} @@ -77,7 +77,7 @@ Meta Gear は 制限された Monad に相当し、型付きアセンブラよりは大きな表現単位を提供する。 Haskell などの関数型プログラミング言語では実行環境が複雑であり、実行時の資源使用を明確にすることができないが、Gears OS を記述している CbC はスタック上に隠された環境を持たないので、メタ計算で使用する資源を明確にできる利点がある。 Meta Code Gear は\figref{mcg1}に示すように通常の Code Gear の直後に遷移され、メタ計算を実行する。 -また、 Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。 +また、Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。 \begin{figure}[htbp] \begin{center} @@ -129,7 +129,7 @@ \section {stub Code Gear} stub Code Gear は Code Gear の接続の間に挟まれる Meta Code Gear である。 ノーマルレベルの Code Gear から Meta Data Gear である Context を直接参照してしまうと、ユーザがメタ計算をノーマルレベルで自由に記述できてしまい、メタ計算を分離した意味がなくなってしまう。 -stub Code Gear はこの問題を防ぐため、 Context から必要な Data Gear のみを ノーマルレベルの Code Gear に渡す処理を行っている。 +stub Code Gear はこの問題を防ぐため、Context から必要な Data Gear のみを ノーマルレベルの Code Gear に渡す処理を行っている。 \coderef{stubCodeGear} に stub Code Gear の例を示す。 stub Code Gear は使用される全ての Code Gear 毎に記述する必要がある。
--- a/paper/interface.tex Tue Jan 30 04:48:12 2018 +0900 +++ b/paper/interface.tex Tue Jan 30 05:00:39 2018 +0900 @@ -8,7 +8,7 @@ % ここでいうグローバルな変数は Context % interface は Data Gear % interface を使うことで Gear OS のモジュール化ができるようになった - % interface は Meta Data Gear で、 引数の Data Gear 群, Code Gear の引数のパターンの集合, Code Gear の引数のパターンは全部 interface に記述されている必要がある。 + % interface は Meta Data Gear で、引数の Data Gear 群, Code Gear の引数のパターンの集合, Code Gear の引数のパターンは全部 interface に記述されている必要がある。 % interface 内部の Code Gearは 自由に 引数の Data Gear, 実装のData Gear にアクセス出来る。 % inteface の実装の際は Code Gear に代入して書く % C++ で言うとCode Gearは virtual @@ -19,23 +19,23 @@ Gears OS は Code Gear で必要な Input Data Gear を Context から番号を指定して取り出すことで処理を実行する。 Context はプログラム全体でみると使用する全ての Code Gear と Data Gear の集合を表現する Meta Data Gear になっている。 しかし、Gears OS を実装する上で Context から Code Gear と Data Gear の番号の組合せを全て展開すると Code Gear がどの Data Gear の番号に対応するかを stub Code Gear に書く必要があり、記述が煩雑になってしまった。 -また、stub Code Gear の記述の煩雑さを避けるために、決まった番号に決まった型の Data Gear を生成し、その Data Gear を複数の Code Gear で使いまわすという、 Data Gear をグローバル変数のように扱う問題が多発した。 +また、stub Code Gear の記述の煩雑さを避けるために、決まった番号に決まった型の Data Gear を生成し、その Data Gear を複数の Code Gear で使いまわすという、Data Gear をグローバル変数のように扱う問題が多発した。 この問題点は Context が全ての Code Gear と Data Gear の集合を表現するために起こった問題である。 -そこで、 Gears OS をモジュール化する仕組みとして Interface を導入した。 +そこで、Gears OS をモジュール化する仕組みとして Interface を導入した。 Interface は ある Data Gear の定義と、それに対する操作(API)を行う Code Gear の集合を表現する Meta Data Gear である。 -Context では全ての Code Gear と Data Gear の集合を表現してることに比べ、 Interface は 一部の Data Gear と 一部の Code Gear の集合を表現する。 -この Interface は Java の インターフェース、 Haskell の型クラスに対応する。 +Context では全ての Code Gear と Data Gear の集合を表現してることに比べ、Interface は 一部の Data Gear と 一部の Code Gear の集合を表現する。 +この Interface は Java の インターフェース、Haskell の型クラスに対応する。 \section{Interface の定義} Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合を表現する Meta Data Gear である。 -Interface は 定義されている Code Gear の引数になる Data Gear 群、 各 Code Gear の引数パターンの集合を記述する。 +Interface は 定義されている Code Gear の引数になる Data Gear 群、各 Code Gear の引数パターンの集合を記述する。 Interface には複数の実装を持つことができ、実装によって実行する Code Gear を切り替えることが可能になる。 -この Code Gear は C++ の virtual 関数、 Java の abstract メソッドに対応する。 +この Code Gear は C++ の virtual 関数、Java の abstract メソッドに対応する。 Queue の Interface を \coderef{queueInterface} に示す。 \coderef{queueInterface} の3-4行目は 引数の Data Gear 群を定義している。 -ここで定義された Data Gear 名は、 定義された Code Gear の引数に対応する。 +ここで定義された Data Gear 名は、定義された Code Gear の引数に対応する。 例えば \coderef{queueInterface} の10行目は Queue に要素を挿入する Code Gear を定義しており、引数として 挿入する Queue の実装と 挿入する要素を受け取る。 この引数それぞれが \coderef{queueInterface} 3-4行目で定義した queue と data に対応する。 @@ -47,30 +47,29 @@ つまり、実行後に継続される Code Gear の Input Data Gear に対応する。 この ``...'' は通常のプログラミング言語では可変長引数のような扱いである。 -\coderef{queueInterface} の9-12行目は 振る舞い(API)となる Code Gear を \_\_code として定義する。 \_\_code の実体は Code Gear への番号が格納される変数であり、実装した Code Gear に対応する番号を代入する。 +\coderef{queueInterface} の9-12行目は実装される Data Gear の操作(API)を行う Code Gear を \_\_code として定義する。 \_\_code の実体は Code Gear への番号が格納される変数であり、実装した Code Gear に対応する番号を代入する。 この Code Gear の引数には Data Gear と Code Gear 実行後に継続される Code Gear 等を渡す。 引数の型と変数名は Interface で定義されている Data Gear 群に対応するように記述する。 -引数の Data Gear はその Code Gear のInput Data Gear になり、 引数の Code Gear の中の引数が Output Data Gear になる。 +引数の Data Gear はその Code Gear のInput Data Gear になり、引数の Code Gear の中の引数が Output Data Gear になる。 例えば\coderef{queueInterface} の11行目は Queue から要素の取り出しを行う Code Gear を定義しており、引数として 取り出すQueue の実装と、Code Gear 実行後に継続される Code Gear を受け取る。 -引数の Code Gear である``\_\_code next(union Data*, ...)``の ``(union Data*, ...)'' は Queue の要素取り出しを行う Code Gear の Output Data Gear であり、 実行後に継続される Code Gear の Input Data Gear になる。 +引数の Code Gear である``\_\_code next(union Data*, ...)``の ``(union Data*, ...)'' は Queue の要素取り出しを行う Code Gear の Output Data Gear であり、実行後に継続される Code Gear の Input Data Gear になる。 \lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} \section{Interface の実装} -Interface はあくまでも、 ある Data Gear に対しての振る舞いとなる Code Gear とその Code Gear で扱われている Data Gear を抽象的に表現した Meta Data Gear であり、実装は別に定義する。 -Interface の実装は、 実装する Data Gear の初期化と実装した Code Gear を Interface で定義した Code Gear に代入することで行う。 -この代入する Code Gear を入れ替えることで振る舞いは同じで処理は別の実装を複数表現することが出来る。 +Interface は Data Gear に対しての操作(API)を行う Code Gear とその Code Gear で扱われている Data Gear の集合を抽象的に表現した Meta Data Gear であり、実装は別に定義する。 +Interface の実装は、実装する Data Gear の初期化と実装した Code Gear を Interface で定義した Code Gear に代入することで行う。 +この代入する Code Gear を入れ替えることで操作(API)は同じで処理は別の実装を複数表現することが出来る。 また、実装された Code Gear は引数の Data Gear と 実装した Data Gear 以外にアクセスすることはない。 -Interface で定義された API の Code Gear 以外の Code Gear も実装することが出来る。 -この Code Gear は Java の private メソッドのように扱われる。 -そのため、外から呼ぶのではなく、Interface で定義された Code Gear から呼ばれる。 -この Code Gear も外から渡された Data Gear に自由にアクセス出来る。 +Interface で指定された Code Gear 以外の Code Gear も実装することが出来る。 +このような Code Gear は基本的に Interface で指定された Code Gear 内からのみ継続されるため、Java の private メソッドのように扱われる。 +この Code Gear もInterface で指定された Code Gear と同じく外から渡された Data Gear にアクセス出来る。 \coderef{singleLinkedQueue} は Queue Interface(\coderef{queueInterface}) を用いた SingleLinkedQueue の実装である。 Interface で実装した Data Gear の生成は関数呼び出しで行われる。 \coderef{singleLinkedQueue} では 3-14行目のcreateSingleLinkedQueue 関数 で Data Gear の生成を行っている。 -この関数は生成する Data Gear の初期化(\coderef{singleLinkedQueue} 7-8行目)と、 実装した Code Gear を Interface で定義した Code Gear の代入(\coderef{singleLinkedQueue} 9-12行目)を行う。 +この関数は生成する Data Gear の初期化(\coderef{singleLinkedQueue} 7-8行目)と、実装した Code Gear を Interface で定義した Code Gear の代入(\coderef{singleLinkedQueue} 9-12行目)を行う。 実際に実装する Data Gear(\coderef{singleLinkedQueue} の場合 SingleLinkedQueue) は Interface の型に包まれて生成される(\coderef{singleLinkedQueue} 6行目)。 このように生成することで実装した Data Gear は実装以外の場所からは Interface の型として扱う事ができる。
--- a/paper/parallelism_gears.tex Tue Jan 30 04:48:12 2018 +0900 +++ b/paper/parallelism_gears.tex Tue Jan 30 05:00:39 2018 +0900 @@ -6,22 +6,22 @@ Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。 Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。 -本章では、 Gears OS の並列処理の構成、機能について説明する。 +本章では、Gears OS の並列処理の構成、機能について説明する。 \section{並列処理の構成} \section{Task} Gears OS では 並列実行する Task を Context で表現する。 Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている。 -Task は Input Data Gear が揃っているかを TaskManager で判断し、 Worker に送信される。 -Worker は送信された Task が指定した Code Gear を実行し、 Output Data Gear を書き出す。 +Task は Input Data Gear が揃っているかを TaskManager で判断し、Worker に送信される。 +Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。 実行される Code Gear の例を \coderef{codeGearExample} に示す。 -\coderef{codeGearExample} は Integer 型 の Input Data Gear を2つ受け取り、 加算処理を行い、 Integer 型 の Output Data Gear に書き出す。 -並列処理を行う Code Gear は Interface の Code Gear と同じく、引数に Input Data Gear、処理が終了した後に継続する Code Gear、 引数の Code Gear の中に Output Data Gear を記述する(\coderef{codeGearExample} 1行目)。 +\coderef{codeGearExample} は Integer 型 の Input Data Gear を2つ受け取り、加算処理を行い、Integer 型 の Output Data Gear に書き出す。 +並列処理を行う Code Gear は Interface の Code Gear と同じく、引数に Input Data Gear、処理が終了した後に継続する Code Gear、引数の Code Gear の中に Output Data Gear を記述する(\coderef{codeGearExample} 1行目)。 引数のCode Gear の中には書き出される Output Data Gear を記述する。 処理が終了した Code Gear は Output Data Gear を書き出す Code Gear に継続する。 -実際に Output Data Gear を書き出す場合、 goto 文に Output Data Gear を引数に渡す(\coderef{codeGearExample} 3行目)。 +実際に Output Data Gear を書き出す場合、goto 文に Output Data Gear を引数に渡す(\coderef{codeGearExample} 3行目)。 \lstinputlisting[caption=並列実行される Code Gear の例, label=code:codeGearExample]{./src/codeGearExample.cbc} @@ -43,7 +43,7 @@ TaskManager は 以下の API を持っている。 \begin{itemize} - \item Task の実行(spawn, spawnTasks) + \item Task の実行(spawn、spawnTasks) \item Task の依存関係の設定(setWaitTask) \item TaskManager が管理している Task 数のインクリメントとデクリメント(increment/decrementTaskCount) \item TaskManager(shutdown)の終了処理 @@ -68,7 +68,7 @@ \end{figure} \section{Worker} -Worker は自身の Queue から Task を取得し、Task の Code Gear を実行し、 Output Data Gear の書き出しを行っている。 +Worker は自身の Queue から Task を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。 \coderef{createCPUWorker} に Task を CPU で実行する CPUWorker の初期化部分を示す。 CPUWorker は初期化の際に スレッドを生成する(\coderef{createCPUWorker} 10行目)。 @@ -78,12 +78,12 @@ \lstinputlisting[caption=CPUWorker の初期化, label=code:createCPUWorker]{./src/createCPUWorker.cbc} Context の生成後は Queue から Task を取得する Code Gear へ継続する。 -Task は Context なので、 Worker は Context を入れ替えて Task の実行を行う。 +Task は Context なので、Worker は Context を入れ替えて Task の実行を行う。 CPUWorker での Task の実行を\coderef{workerRun} に示す。 -\coderef{workerRun} は Context の入れ替えを行うため、 Meta Code Gear として記述されており、getTaskCPUWorker(\coderef{workerRun} 1-9行目)の引数に Context を記述している。 +\coderef{workerRun} は Context の入れ替えを行うため、Meta Code Gear として記述されており、getTaskCPUWorker(\coderef{workerRun} 1-9行目)の引数に Context を記述している。 CPUWorker は中身が NULL の task を取得すると Worker の終了処理を行う(\coderef{workerRun} 2-4 行目)。 -Task が取得できた場合 Task の実行後に継続する Code Gear を格納し(\coderef{workerRun} 7行目)、 Task を Context としてCode Gear に継続する(\coderef{workerRun} 8行目)。 +Task が取得できた場合 Task の実行後に継続する Code Gear を格納し(\coderef{workerRun} 7行目)、Task を Context としてCode Gear に継続する(\coderef{workerRun} 8行目)。 Task の実行後に継続する Code Gear は Data Gear の書き出しと依存関係の解決を行う。 \lstinputlisting[caption=CPUWorker でのTaskの実行, label=code:workerRun]{./src/workerRun.cbc} @@ -101,14 +101,14 @@ 異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。 Gears OS ではこの CAS を行うための Interface を定義している(\coderef{atomicInterface})。 -この Interface では、 Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義している(\coderef{atomicInterface} 6行目)。 +この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義している(\coderef{atomicInterface} 6行目)。 \lstinputlisting[caption=AtomicInterface, label=code:atomicInterface]{./src/atomicInterface.h} AtomicInterface での CAS の実際の実装を \coderef{atomicImpl} に示す。 実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(\coderef{atomicImpl} 2行目)。 この関数は第一引数に渡されたアドレスに対して第二引数の値から第三引数の値ヘ CAS を行う。 -CAS に成功した場合、 true を返し、 失敗した場合は false を返す。 +CAS に成功した場合、true を返し、失敗した場合は false を返す。 \coderef{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。 \lstinputlisting[caption=CAS の実装, label=code:atomicImpl]{./src/atomicImpl.cbc} @@ -201,9 +201,9 @@ \section{並列構文} Gears OS では並列実行する Task の設定をメタレベルで \coderef{metaCreateTask} のように行っている。 -\coderef{metaCreateTask} では実行する Code Gear、待ち合わせ中の Input Data Gear の数、 Input/Output Data Gear への参照等の設定を記述している。 +\coderef{metaCreateTask} では実行する Code Gear、待ち合わせ中の Input Data Gear の数、Input/Output Data Gear への参照等の設定を記述している。 これらの記述は Context などを含む煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である。 -そこで、 Context を直接用いないノーマルレベルの並列構文である par goto 文を用意した。 +そこで、Context を直接用いないノーマルレベルの並列構文である par goto 文を用意した。 \lstinputlisting[caption=メタレベルによる Task の生成, label=code:metaCreateTask]{./src/metaCreateTask.cbc} @@ -214,7 +214,7 @@ par goto の引数には Input/Output Data Gear と 実行後に継続する Code Gear を渡す。 par goto で生成された Task は \_\_exit に継続することで終了する。 -Gears OS の Task は Output Data Gear を生成した時点で終了するので、 par goto では直接 \_\_exit に継続するのではなく、Output Data Gear への書き出し処理に継続される。 +Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、Output Data Gear への書き出し処理に継続される。 これにより Code Gear と Data Gear の依存関係をノーマルレベルで記述できるようになる。 \section{待ち機構}