# HG changeset patch # User Tatsuki IHA # Date 1517216571 -32400 # Node ID 82c09c49bb4a57b7d1c0f1bd75a917c6b7a02904 # Parent f3322ccfc818bc425298e474afe15b0a00f463c7 Update interface diff -r f3322ccfc818 -r 82c09c49bb4a paper/gearsOS.tex --- a/paper/gearsOS.tex Sun Jan 28 19:23:28 2018 +0900 +++ b/paper/gearsOS.tex Mon Jan 29 18:02:51 2018 +0900 @@ -29,6 +29,9 @@ \label{fig:cdg1} \end{figure} +また Gears OS 自体もこの Code Gear、Data Gear を用いた CbC(Continuation based C) で実装される。 +そのため、 Gears OS の実装は Code Gear、 Data Gear を用いたプログラミングスタイルの指標となる。 + \section{Continuation based C} Gears OS の実装は本研究室で開発されている CbC(Continuation based C) を用いて行う。 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。 @@ -78,7 +81,7 @@ \begin{figure}[htbp] \begin{center} - \includegraphics[scale=0.6]{./fig/meta_cg_dg.pdf} + \includegraphics[scale=0.7]{./fig/meta_cg_dg.pdf} \end{center} \caption{Meta Code Gear の実行} \label{fig:mcg1} @@ -111,8 +114,8 @@ 実際に Allocation する際は Context内の heap(\coderef{context} 8行目)を Data Gear のサイズ分インクリメントすることで実現する。 \item Code Gear が参照する DataGear へのポインタ - Allocation で生成した Data Gear へのポインタは Context 内のdata(\coderef{context} 6行目) に格納される。 - Code Gear は data を参照して Data Gear へアクセスする。 + Allocation で生成した Data Gear へのポインタは番号を割り振り、Context 内のdata(\coderef{context} 6行目) に格納される。 + Code Gear は data から番号を指定して Data Gear へアクセスする。 \item 並列実行用の Task 情報 Context は 並列実行の Task も兼任するため、待っている Input Data Gear のカウンタ、Input/Output Data Gear が格納されている場所を示すインデックス、GPU での実行フラグ等を持っている(\coderef{context} 13-30行目)。 @@ -123,36 +126,6 @@ Data Gear を確保する際のサイズはこの型情報から決定する。 \end{itemize} -\section{Interface} -Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合を表現する Data Gear である。 -Interface には複数の実装を持つことができ、実装によって実行する Code Gear を切り替えることが可能になる。 - -Queue の Interface を \coderef{queueInterface} に示す。 -Interface は API となる Code Gear を \_\_code として 定義(\coderef{queueInterface} 6-9行目)する。 -この \_\_code の実体は Code Gear への番号が格納される変数であり、Interface の実装毎に値は変化する。 - -\lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} - -\coderef{singleLinkedQueue} は Queue Interface を用いた SingleLinkedQueue の実装である。 -createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) は Queue Interface を実装した Data Gear の生成を行っている関数であり、 データ構造の初期化と実装した Code Gear の番号(enum)を Queue Interface で定義している Code Gear を示す変数に入れる(\coderef{singleLinkedQueue} 9-12行目)。 - -\lstinputlisting[caption=SingleLinkedQueue の実装, label=code:singleLinkedQueue]{./src/singleLinkedQueue.cbc} - -Interface での Code Gear 呼び出しは ``goto interface-\textgreater method'' という構文で行う。 -ここの interface は createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) 等で初期化を行った Interface へのポインタ、method は実装した Code Gear の番号になる。 - -\coderef{singleLinkedQueueTest} に Queue Interface を使用した Code Gearの呼び出し例を示す。 -この呼び出しでは SingleLinkedQueue の put 実装に継続される。 - -\lstinputlisting[caption=Queue Interface での Code Gear の呼び出し, label=code:singleLinkedQueueTest]{./src/singleLinkedQueueTest.cbc} - -\coderef{singleLinkedQueueTest} は実際にはスクリプトによって \coderef{singleLinkedQueueTest_script} に変換されコンパイルされる。 -\coderef{singleLinkedQueueTest_script} 内の Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す。 -この引数格納用の Data Gear は Context の初期化の際に生成される。 -引数格納用の Data Gear を取り出した後は変換前の呼び出しの引数を Interface で定義した Code Gear の引数情報に合わせて格納し、指定した Code Gear に継続する。 - -\lstinputlisting[caption=スクリプトによる変換後, label=code:singleLinkedQueueTest_script]{./src/singleLinkedQueueTest_script.cbc} - \section {stub Code Gear} stub Code Gear は Code Gear の接続の間に挟まれる Meta Code Gear である。 ノーマルレベルの Code Gear から Meta Data Gear である Context を直接参照してしまうと、ユーザがメタ計算をノーマルレベルで自由に記述できてしまい、メタ計算を分離した意味がなくなってしまう。 @@ -160,7 +133,7 @@ \coderef{stubCodeGear} に stub Code Gear の例を示す。 stub Code Gear は使用される全ての Code Gear 毎に記述する必要がある。 -しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、Interface を実装した Code Gear などの型が決まっており、引数が格納されている場所がわかる stub Code Gear はスクリプトで自動生成する。 +しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、後述する Interface を実装した Code Gear などの型が決まっており、引数が格納されている場所がわかる stub Code Gear はスクリプトで自動生成する。 \lstinputlisting[caption=stub Code Gear, label=code:stubCodeGear]{./src/stubCodeGear.cbc} diff -r f3322ccfc818 -r 82c09c49bb4a paper/interface.tex --- a/paper/interface.tex Sun Jan 28 19:23:28 2018 +0900 +++ b/paper/interface.tex Mon Jan 29 18:02:51 2018 +0900 @@ -14,7 +14,67 @@ % C++ で言うとCode Gearは virtual \chapter{Interface} + \section{Context を経由しての継続の問題点} +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 をグローバル変数のように扱う問題が多発した。 + +この問題点は Context が全ての Code Gear と Data Gear の集合を表現するために起こった問題である。 +そこで、 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 の型クラスに対応する。 + \section{Interface の定義} +Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合を表現する Meta Data Gear である。 +Interface は 定義されている Code Gear の引数になる Data Gear 群、 各 Code Gear の引数パターンの集合を記述する。 +Interface には複数の実装を持つことができ、実装によって実行する Code Gear を切り替えることが可能になる。 +この Code Gear は C++ の virtual 関数、 Java の abstract メソッドに対応する。 + +Queue の Interface を \coderef{queueInterface} に示す。 + +\coderef{queueInterface} の3-4行目は 引数の Data Gear 群を定義している。 +ここで定義された Data Gear 名は、 定義された Code Gear の引数に対応する。 +例えば \coderef{queueInterface} 10行目 には Queue に要素を挿入する Code Gear を定義しており、引数として 挿入する Queue と 挿入する要素を受け取る。 +この引数それぞれが \coderef{queueInterface} 3-4行目で定義した queue と data に対応する。 + +\coderef{queueInterface} の5-6行目は Interface の Code Gear の実行後に継続される Code Gear を定義している。 +この値は Interface の Code Gear を呼び出す際に外から代入される。 +Code Gear によってこの継続は複数設定される場合がある。 +例えば \coderef{queueInterface} の12行目には Queue が空かどうかを調べる Code Gear が定義されており、中身がある場合と空の場合で別の継続を渡す必要がある。 +``\_\_code next(...)'' の引数である ``...'' は複数の Output Data Gearを書き出すことを示している。 +つまり、実行後に継続される Code Gear の Input Data Gear に対応する。 +この ``...'' は通常のプログラミング言語では可変長引数のような扱いである。 + +\coderef{queueInterface} の9-12行目は 振る舞い(API)となる Code Gear を \_\_code として定義する。 +この Code Gear の引数には Data Gear と Code Gear 実行後に継続される Code Gear 等を渡す。 +引数の型と変数名は Interface で定義されている Data Gear 群に対応するように記述する。 +引数の Data Gear はその Code Gear のInput Data Gear になり、 + +この \_\_code の実体は Code Gear への番号が格納される変数であり、実装した Code Gear に対応する番号を代入する。 + +\lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} + \section{Interface の実装} +\coderef{singleLinkedQueue} は Queue Interface を用いた SingleLinkedQueue の実装である。 +createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) は Queue Interface を実装した Data Gear の生成を行っている関数であり、 データ構造の初期化と実装した Code Gear の番号(enum)を Queue Interface で定義している Code Gear を示す変数に入れる(\coderef{singleLinkedQueue} 9-12行目)。 + +\lstinputlisting[caption=SingleLinkedQueue の実装, label=code:singleLinkedQueue]{./src/singleLinkedQueue.cbc} + \section{Interface を利用した Code Gear の継続} +Interface での Code Gear 呼び出しは ``goto interface-\textgreater method'' という構文で行う。 +ここの interface は createSingleLinkedQueue(\coderef{singleLinkedQueue} 3-14 行目) 等で初期化を行った Interface へのポインタ、method は実装した Code Gear の番号になる。 + +\coderef{singleLinkedQueueTest} に Queue Interface を使用した Code Gearの呼び出し例を示す。 +この呼び出しでは SingleLinkedQueue の put 実装に継続される。 + +\lstinputlisting[caption=Queue Interface での Code Gear の呼び出し, label=code:singleLinkedQueueTest]{./src/singleLinkedQueueTest.cbc} + +\coderef{singleLinkedQueueTest} は実際にはスクリプトによって \coderef{singleLinkedQueueTest_script} に変換されコンパイルされる。 +\coderef{singleLinkedQueueTest_script} 内の Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す。 +この引数格納用の Data Gear は Context の初期化の際に生成される。 +引数格納用の Data Gear を取り出した後は変換前の呼び出しの引数を Interface で定義した Code Gear の引数情報に合わせて格納し、指定した Code Gear に継続する。 + +\lstinputlisting[caption=スクリプトによる変換後, label=code:singleLinkedQueueTest_script]{./src/singleLinkedQueueTest_script.cbc} diff -r f3322ccfc818 -r 82c09c49bb4a paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r f3322ccfc818 -r 82c09c49bb4a paper/parallelism_gears.tex --- a/paper/parallelism_gears.tex Sun Jan 28 19:23:28 2018 +0900 +++ b/paper/parallelism_gears.tex Mon Jan 29 18:02:51 2018 +0900 @@ -3,11 +3,15 @@ % 構成のセクションいるかしら? \chapter{Gears OSの並列処理} -Gears OS では Input Data Gear が揃っている Code Gear から 並列に実行される。 +Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。 +Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。 + +本章では、 Gears OS の並列処理の構成、機能について説明する。 + \section{並列処理の構成} \section{Task} -Gears OS では 並列実行する Task は Context で表現される。 +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 を書き出す。 @@ -69,7 +73,7 @@ \coderef{createCPUWorker} に Task を CPU で実行する CPUWorker の初期化部分を示す。 CPUWorker は初期化の際に スレッドを生成する(\coderef{createCPUWorker} 10行目)。 生成されたスレッドはまず startWorker 関数(\coderef{createCPUWorker} 14-21行目)を呼び出し、このスレッド用の Context を生成する。 -Context をスレッド毎に生成することで、メモリ空間をスレッドごとに持てるため Gearefマクロ で interface の引数を取得する際の競合、メモリ確保の処理での他のスレッドの停止を防ぐ事ができる。 +Context をスレッド毎に生成することで、メモリ空間をスレッドごとに持てるため Gearef マクロ で interface の引数を取得する際の競合、メモリ確保の処理での他のスレッドの停止を防ぐ事ができる。 \lstinputlisting[caption=CPUWorker の初期化, label=code:createCPUWorker]{./src/createCPUWorker.cbc} diff -r f3322ccfc818 -r 82c09c49bb4a paper/src/queueInterface.h --- a/paper/src/queueInterface.h Sun Jan 28 19:23:28 2018 +0900 +++ b/paper/src/queueInterface.h Mon Jan 29 18:02:51 2018 +0900 @@ -1,8 +1,11 @@ typedef struct Queue{ + // Data Gear parameter union Data* queue; union Data* data; __code next(...); __code whenEmpty(...); + + // Code Gear __code clear(Impl* queue, __code next(...)); __code put(Impl* queue, union Data* data, __code next(...)); __code take(Impl* queue, __code next(union Data*, ...));