Mercurial > hg > Papers > 2019 > mitsuki-master
changeset 1:9100f20b8797
copy mitsuki-sigos
line wrap: on
line diff
--- a/paper/abstract.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/abstract.tex Wed Jul 11 21:48:28 2018 +0900 @@ -22,3 +22,4 @@ モジュール化の詳細と、有効性について考察する。 \chapter*{Abstract} +%英語論文
--- a/paper/conclusion.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/conclusion.tex Wed Jul 11 21:48:28 2018 +0900 @@ -1,42 +1,36 @@ \chapter{結論} -本研究では Gears OS の並列実行機構の実装を行った。 -Gears OS は処理を Code Gear、データを Data Gear を用いて処理を実行する。 -Code Gear と Input/Output Data Gear の組を Task とし、並列実行を行う。 - -Gears OS のプログラミングは Interface という 一部の Code Gear と Data Gear の集合を表現する Meta Data Gear を用いて行われる。 -この Interface は stub Code Gear という全ての Code Gear に対応する Meta Code Gear で Data Gear を参照する。 +本論文では Gears OS のプロトタイプの設計と実装、メタ計算である Context と stub の生成を行う Perl スクリプトの記述、並列実行機構の実装を行った。 +Code Gear 、Data Gear を処理とデータの単位として用いて Gears OS を設計した。 +Code Gear、Data Gear にはメタ計算を記述するための Meta Code Gear、Meta Data Gear が存在する。 +メタ計算を Meta Code Gear、によって行うことでメタ計算を階層化して行うことができる。 +Code Gear は関数より細かく分割されてるためメタ計算を柔軟に記述できる。 +Gears OS は Code Gear と Input/Output Data Gear の組を Task とし、並列実行を行う。 -Gears OS の Task は Context という全ての Code/Data Gear を参照できる Meta Data Gear が対応する。 -並列処理を行う際は Context を生成し、 Code Gear と Input/Output Data Gear を Context に設定して TaskManager 経由で各 Worker の SynchronizedQueue に送信される。 -Context の設定はメタレベルの記述になるため、ノーマルレベルでは par goto 文というCbC の goto 文に近い記述で並列処理を行える。 -この par goto は通常のプログラミングの関数呼び出しのように扱える。 - -Gears OS の GPU 対応はアーキテクチャ用の Worker と Executor、 Buffer を用意することでアーキテクチャ毎に合わせた実行を行える。 -本研究では CUDA 実装として CUDAWorker、 CUDAExecutor、 CUDABufferの実装を行い、実行確認を行った。 -また、 CPU、 GPUの実行の切り替えは並列実行される Code Gear の stub Code Gear で継続先を切り替えることでメタレベルで記述することが可能となった。 +Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。 +Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。 +Interface は複数の実装をもち、Meta Data Gear として定義される。 +従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call するが、 +Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、操作に対応する Code Gear に goto する。 -Twice と BitonicSort の例題の測定結果では 1CPU と 32CPU で Twice では約 27.1 倍、BitonicSort では 約22.12 倍の速度向上が見られた。 -また、GPU 実行の測定も行い、 kernel のみの実行時間では 32 CPU より Twice では約7.2倍、BitonicSort では約11.48倍の速度向上がみられ、GPU の性能を活かすことができた。 +Context は使用する Code Gear、Data Gear をすべて格納している Meta Data Gear である。 +通常の計算から Context を直接扱うことはセキュリティ上好ましくない。 +このため Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear である stub Code Gear を定義した。 +stub Code Gear は Code Gear 毎に記述され、Code Gear 間の遷移に挿入される。 -\section{今後の課題} -今後の課題として、Gears OS の並列処理の信頼性の保証、 チューニングを行う。 - -Gears OS では証明とモデル検査をメタレベルで実行することで信頼性を保証する。 +並列処理を行う際は Context を生成し、 Code Gear と Input/Output Data Gear を Context に設定して TaskManager 経由で各 Worker の SynchronizedQueue に送信される。 +Context の設定はメタレベルの記述になるため、ノーマルレベルでは par goto 文という CbC の goto 文に近い記述で並列処理を行える。 +この par goto は通常のプログラミングの関数呼び出しのように扱える。 -証明は CbC のプログラムを証明支援系の Agda に対応させて証明を行う。 -現在は Gears OS の Interface 部分の動作の証明を行っており、Stack や Tree の動作の証明を行っている。 -Gears OS の並列処理の信頼性を証明するには Synchronized Queue の証明を行う必要がある。 +これらのメタ計算の記述は煩雑であるため Perl スクリプトによる自動生成を行なった。 +これにより Gears OS のコードの煩雑さは改善され、ユーザーレベルではメタを意識する必要がなくなった。 -モデル検査では CbC で記述されたモデル検査器である akasha \cite{atton-ipsj}を使用して行う。 -モデル検査の方針としては、Code Gear の実行を擬似並列で実行し、全ての組合せを列挙する方法で行う。 +Twice の例題の測定結果では 1CPU と 32CPU で約 27.1 倍、の速度向上が見られた。 +また、GPU 実行の測定も行い、kernel のみの実行時間では 32 CPU より約 7.2 倍の速度向上がみられ、 +GPU の性能を活かすことができた。 -Go、OpenMP との比較から、 Gears OS が1CPU での動作が遅いということがわかった。 +今後の課題は、 +Go、との比較から、 Gears OS が1CPU での動作が遅いということがわかった。 Gears OS は par goto 文を使用することで Context を生成し、並列処理を行う。 しかし、Context はメモリ空間の確保や使用する全ての Code/Data Gear を設定する必要があり、生成にある程度の時間がかかってしまう。 -そこで、 par goto のコンパイルタイミングで実行する Code Gear のフローをモデル検査で解析し、処理が軽い場合はContext を生成せずに、関数呼び出しを行う等の最適化を行うといったチューニングが必要である。 +そこで、 par goto のコンパイルタイミングで実行する Code Gear のフローをモデル検査で解析し、処理が軽い場合はContext を生成せずに、関数呼び出しを行う等の最適化を行なうといったチュ>ーニングが必要である。 -今回の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU にデータの送信する必要があった。 -しかし、CPU、 GPU 間のデータの通信はコストが高いことが例題の結果からわかった。 -GPU にあるデータは CPU 側ではポインタで持つことが出来る。 -そこで Meta Data Gear に Data Gear が CPU、GPU のどこで所持されているかを持たせる。 -GPU にある Data Gear が CPU で必要になったときに初めてデータの通信を行うことで、最低限のデータ通信で処理を実行できる。
--- a/paper/evaluation.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/evaluation.tex Wed Jul 11 21:48:28 2018 +0900 @@ -80,98 +80,12 @@ \label{fig:twice} \end{figure} -1 CPU と 32 CPU では 約 27.1 倍の速度向上が見られた。 ある程度の台数効果があると考えられる。 GPU での実行は kernel のみの実行時間は 32 CPU に比べて 約 7.2 倍の速度向上が見られた。 しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。 -\section{BitonicSort} -BitonicSort は並列処理向けのソートアルゴリズムである。 -代表的なソートアルゴリズムである Quick Sort も並列処理 を行うことが可能であるが、 QuickSort では ソートの過程で並列度が変動するため、台数効果が出づらい。 -一方でBitonic Sort は最初から最後まで並列度が変わらずに並列処理を行う。 -\figref{bitonicNetwork} は要素数8のデータに対する BitonicSort のソートネットワークである。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/bitonicNetwork.pdf} - \end{center} - \caption{要素数8の BitonicNetwork} - \label{fig:bitonicNetwork} -\end{figure} - -BitonicSort はステージ毎に決まった2点間の要素の入れ替えを並列に実行することによってソートを行う。 -Gears OS ではこのステージ毎に Output Data Gear を書き出し、 次のステージの Code Gear の Input Data Gear として記述することで BitonicSort を実現する。 - -要素数$2^{24}$ のデータに対する BitonicSort の実行結果を \tabref{bitonicSort}、\figref{bitonicSort}に示す。 -こちらも Twice と同じくCPU 実行の際は $2^{24}$ のデータを 64個のTask に分割して並列実行を行っている。 -つまり生成される Task は 64 * ステージ数 となる。 -GPU では1次元の block 数を $2^{14}$、 block 内の thread 数を $2^{10}$ で kernel の実行を行った。 - -\begin{table}[htbp] - \begin{center} - \begin{tabular}{|l||l|} \hline - Processor & Time(s) \\ \hline - 1 CPU & 41.416 \\ \hline - 2 CPUs & 23.340\\ \hline - 4 CPUs & 11.952\\ \hline - 8 CPUs & 6.320\\ \hline - 16 CPUs & 3.336\\ \hline - 32 CPUs & 1.872\\ \hline - GPU & 5.420\\ \hline - GPU(kernel only)& 0.163\\ \hline - \end{tabular} - \caption{$2^{24}$ のデータに対する BitonicSort} - \label{tab:bitonicSort} - \end{center} -\end{table} - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/bitonicSort.pdf} - \end{center} - \caption{$2^{24}$ のデータに対する BitonicSort} - \label{fig:bitonicSort} -\end{figure} - -\newpage - -1 CPU と 32 CPU で 約22.12 倍 の速度向上が見られた。 -GPU では通信時間を含めると 8 CPU の約1.16倍となり、 kernel のみの実行では 32 CPU の約11.48倍となった。 -現在の Gears OS の CUDA 実装では、 Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の実行結果の書き出しを行っており、その処理の時間で差が出たと考えられる。 -GPU で実行される Task 同士の依存関係の解決の際はCuDevicePtr などのGPU のメモリへのポインタを渡し、CPU でデータが必要になったときに初めて GPU から CPU へデータの通信を行うメタ計算の実装が必要となる。 - -\section{OpenMP との比較} -OpenMP\cite{openmp} は C、 C++ のプログラムにアノテーションを付けることで並列化を行う。 -アノテーションを \coderef{openMP} のように for 文の前につけることで、ループの並列化を行う。 - -\lstinputlisting[caption=OpenMP での Twice, label=code:openMP]{./src/openMP.c} - -OpenMP は既存のコードにアノテーションを付けるだけで並列化を行えるため、変更が少なくて済む。 -しかし、 ループのみの並列化ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになってしまう。 -OpenMP はループの並列化 ではなくブロック単位での並列実行もサポートしているが、アノテーションの記述が増えてしまう。 -また、 OpenMPはコードとデータを厳密に分離していないため、データの待ち合わせ処理をバリア等のアノテーションで記述する。 - -Gears OS では Input Data Gear が揃った Code Gear は並列に実行されるため、プログラム全体の並列度を高めることが出来る。 -また 並列処理のコードとデータの依存関係を par goto 文で簡潔に記述することが出来る。 - -Gears OS と OpenMP で実装した Twice の実行結果の比較を\figref{vsopenmp} に示す。 -実行環境は \tabref{powerEdge}、 $2^{27}$ のデータに対して行い、Gears OS 側は配列を 64個のTaskに分割し、OpenMP は for 文を static スケジュールで並列実行した。 -static スケジュールはループの回数をプロセッサーの数で分割し、並列実行を行う openMP のスケジュール方法である。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/vsopenmp.pdf} - \end{center} - \caption{vs OpenMP} - \label{fig:vsopenmp} -\end{figure} - -実行結果として OpenMP は 1CPUと 32CPU で約10.8 倍の速度向上がみられた。 -一方 Gears OS では約 27.1 倍の速度向上のため、台数効果が高くなっている。 -しかし、Gears OS は 1CPU での実行時間がOpenMP に比べて大幅に遅くなっている。 - \section{Go 言語との比較} Go 言語 は Google社が開発しているプログラミング言語である。 Go 言語によるTwice の実装例を\coderef{go}に示す。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/MetaGear.xbb Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,8 @@ +%%Title: fig/MetaGear.pdf +%%Creator: extractbb 20160307 +%%BoundingBox: 0 0 792 532 +%%HiResBoundingBox: 0.000000 0.000000 792.000000 532.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Wed Jul 11 21:17:57 2018 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/gears_structure.xbb Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,8 @@ +%%Title: ./pic/gears_structure.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 713 418 +%%HiResBoundingBox: 0.000000 0.000000 713.000000 418.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Fri Nov 24 17:30:26 2017 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/generate_context3.xbb Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,8 @@ +%%Title: fig/generate_context3.pdf +%%Creator: extractbb 20160307 +%%BoundingBox: 0 0 706 274 +%%HiResBoundingBox: 0.000000 0.000000 706.000000 274.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Wed Jul 11 21:38:58 2018 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/metaCS.xbb Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,8 @@ +%%Title: fig/metaCS.pdf +%%Creator: extractbb 20160307 +%%BoundingBox: 31 511 515 732 +%%HiResBoundingBox: 30.601520 511.100000 515.413800 732.012800 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Wed Jul 11 21:22:33 2018 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/fig/verification.xbb Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,8 @@ +%%Title: fig/verification.pdf +%%Creator: extractbb 20160307 +%%BoundingBox: 0 0 478 204 +%%HiResBoundingBox: 0.000000 0.000000 478.000000 204.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Wed Jul 11 21:17:57 2018 +
--- a/paper/gearsOS.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/gearsOS.tex Wed Jul 11 21:48:28 2018 +0900 @@ -1,141 +1,30 @@ -%TODO stub のこうで書きすぎ -% context と stub はジェネラルな紹介だけ - -\chapter{Gears OS の概念} -Gears OS は信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に開発している OSである。 - -Gears OS は処理の単位を Code Gear、データの単位を Data Gear と呼ばれる単位でプログラムを構成する。 -信頼性や拡張性はメタ計算として、通常の計算とは区別して記述する。 - -本章では Gears OS を構成する様々な要素について説明する。 - -\section{Code GearとData Gear} -Gears OS はプログラムとデータの単位として Gear を用いる。 -Gear は並列実行の単位、データの分割、Gear 間の接続等になる。 - -Code Gear はプログラムの処理そのもので、\figref{cdg1} で示しているように任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。 -また、Code Gear は接続された Data Gear 以外には参照を行わない。 -この Input / Output Data Gear の対応から依存関係を解決し、Code Gear の並列実行を可能とする。 - -Code Gear 間の移動は継続を用いて行われる。 -継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。 -そのため Code Gear、Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。 - -Gear の特徴として処理やデータの構造が Code Gear、Data Gear に閉じていることにある。 -これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。 +\chapter{Gears OS の構成} +Gears OS は以下の要素で構成される。 -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/codegear-datagear.pdf} - \end{center} - \caption{Code Gear と Data Gear の関係} - \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 を基本的な処理単位として記述できるプログラミング言語である。 -CbC の処理系として LLVM\cite{llvm}/Clang と GCC による実装が存在する\cite{kaito-lola}\cite{nobu-prosym}。 +\begin{itemize} + \item Context + \item TaskQueue + \item TaskManager + \item Worker +\end{itemize} -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 への入力になる。 - -\lstinputlisting[caption=Code Gearの軽量継続, label=code:cg1]{./src/cg1.cbc} +図\ref{fig:gearsos} に Gears OS の構成図を示す。 -CbC の goto 文による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。 -この継続を軽量継続と呼ぶ。 -\coderef{cg1} は cs0 から cs1 へ継続したあとには cs0 へ戻らずに処理を続ける。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=1.0]{./fig/goto.pdf} - \end{center} - \caption{goto 文による Code Gearの軽量継続} - \label{fig:cg1} +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{./fig/gears_structure} + \end{center} + \caption{Gears OS の構成図} + \label{fig:gearsos} \end{figure} -\section{メタ計算} -プログラムの記述する際は、ノーマルレベルの計算の他に、メモリ管理、スレッド管理、CPUがGPUの資源管理等を記述しなければならない処理が存在する。 -これらの計算はノーマルレベルの計算と区別してメタ計算と呼ぶ。 - -メタ計算は関数型言語では Monad\cite{moggi-monad} を用いて表現される\cite{kkb-sigos}。 -Monad は Haskell では実行時の環境を記述する構文として使われる。 - -従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。 -実行時にメタ計算の変更を行う場合には OS 内部のパラメータの変更を使用し、実行されるユーザープログラム自体への変更は限定的である。 -しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で実際のシステムコール単位では不十分である。 -例えば、モデル検査ではアセンブラあるいは バイトコード、インタプリタレベルでのメタ計算が必要になる。 -しかし、バイトコードレベルでは 粒度が細かすぎて扱いが困難になっている。具体的にはメタ計算の実行時間が大きくなってしまう。 - -\section{Meta Gear} -Gears OS の Code Gear は関数に比べて細かく分割されているため、メタ計算をより柔軟に記述できる。 -Code Gear と Data Gear にはそれぞれメタ計算の区分として Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実装する。 -Meta Gear は 制限された Monad に相当し、型付きアセンブラよりは大きな表現単位を提供する。 -Haskell などの関数型プログラミング言語では実行環境が複雑であり、実行時の資源使用を明確にすることができないが、Gears OS を記述している CbC はスタック上に隠された環境を持たないので、メタ計算で使用する資源を明確にできる利点がある。 -Meta Code Gear は\figref{mcg1}に示すように通常の Code Gear の直後に遷移され、メタ計算を実行する。 -また、Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.8]{./fig/meta_cg_dg.pdf} - \end{center} - \caption{Meta Code Gear の実行} - \label{fig:mcg1} -\end{figure} - -\section{Context} -Context とは一連の実行で使用される Code Gear と Data Gear の集合である。 -従来のスレッドやプロセスに対応する。 -Context は接続可能な Code/Data Gear のリスト、Data Gearを確保するメモリ空間、実行される Task への Code Gear等を持っている Meta Data Gearである。 -Gears OS では Code Gear と Data Gear への接続を Context を通して行う。 - -\coderef{context} に Context の定義を示す。 - -\lstinputlisting[caption=Contextの定義, label=code:context]{./src/context.h} +Data Gear は union と struct によって表現される。 +Context には Data Gear の Data Type の情報が格納されている。 +この情報から確保する Data Gear のサイズなどを決定する。 -\coderef{context} は以下の内容を定義している。 - -\begin{itemize} - \item Code Gear の名前と関数ポインタとの対応表 - - Code Gear の名前とポインタの対応は Context 内の code(\coderef{context} 5行目) に格納される。 - code は全ての Code Gear を列挙した enum と関数ポインタの組で表現される。 - Code Gear の名前は enum で定義され、コンパイル後には整数へと変換される。 - 実際に Code Gear に接続する際は番号(enum)を指定することで接続を行う。 - これにより、メタ計算の実行時に接続する Code Gear を動的に切り替えることが可能となる。 - \item Data Gear の Allocation 用の情報 - - Data Gear のメモリ空間は事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。 - 実際に 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 へアクセスする。 - \item 並列実行用の Task 情報 - - Context は 並列実行の Task も兼任するため、待っている Input Data Gear のカウンタ、Input/Output Data Gear が格納されている場所を示すインデックス、GPU での実行フラグ等を持っている(\coderef{context} 13-30行目)。 - \item Data Gear の型情報 - - Data Gear は構造体を用いて定義する(\coderef{context} 34-49行目)。Timer や TimerImplなどの構造体が Data Gear に相当する。 - メタ計算では任意のData Gear を一律に扱うため、全ての Data Gear の共用体を定義する(\coderef{context} 33-51行目)。 - Data Gear を確保する際のサイズはこの型情報から決定する。 -\end{itemize} - -\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 は使用される全ての Code Gear 毎に記述する必要がある。 -しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、後述する Interface を実装した Code Gear のstub Code Gear はスクリプトで自動生成する。 - -stub Code Gear はユーザーが自前で記述することも可能である。 -つまり、ユーザーがメタ計算を記述することができる。 -stub Code Gear を用いたメタ計算の例として、本来 stub Code Gear は対応した Code Gear に継続するが、自前で stub Code Gear を記述することで、継続先を柔軟に変更できる。 +Context は Task でもあり、Taskは通常のOSのスレッドに対応する。 +Task は実行する Code Gear と Data Gear をすべて持っている。 +TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。 +Gears OS における Task Queue は Synchronized Queue で実現される。 +Worker は TaskQueue から Task である Context を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。 +Input/Output Data Gear の依存関係が解決されたものから並列実行される。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/generate_code.tex Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,39 @@ +\chapter{コードの自動生成} + +\section{stub Code Gear の生成} + +stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。 +Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。 +stub Code Gear を 自動生成する generate stub を Perl スクリプトで作成することによって Code Gear の記述量を約半分にすることができる。 + +stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。 +generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。 +また、この時既に stub Code Gear が記述されている Code Gear は無視される。 + +cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(Code\ref{stack_c}) + +\lstinputlisting[label=stack_c, caption=stub Code Gear を加えたコード]{./src/ex_stub} + +\section{Context の生成} +generate\_context は Context.h、Interface.cbc、generate\_stub で生成されたImpl.cbc を見て Context を生成する Perl スクリプトである。 + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{./fig/generate_context3.pdf} + \end{center} + \caption{generate\_context による Context の生成} + \label{fig:gc} +\end{figure} + +Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。 + +generate\_context は context.h を読み宣言されている Data Gear を取得する。 +Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。 +取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。 + +Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。 +また、generate context は取得した Code/Data Gear から initContext の生成も行う。 + +Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 +Code Gear は Context を通して Data Gear へアクセスする。 +Data Gear の Allocation を行うコードは dataGearInit.cに生成される。
--- a/paper/interface.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/interface.tex Wed Jul 11 21:48:28 2018 +0900 @@ -19,122 +19,17 @@ % Context and stub の詳細な説明はここに書く % stub の説明は スクリプトによる goto の変換後 -\chapter{Gears OS のモジュール化} -Gears OS は stub Code Gear という Meta Code Gear で Context という全ての Code Gear と Data Gear を持った Meta Data Gear から値を取りだし、ノーマルレベルの Code Gear に値を渡す。 -しかし、Gears OS を実際に実装するにつれて、メタレベルからノーマルレベルへの継続の記述が煩雑になることがわかり、Code Gear と Data Gear のモジュール化が必要になった。 - -本章では Gears OS のモジュール化の仕組みである Interface について説明する。 - -\section{Context を経由しての継続の問題点} -Gears OS は Code Gear で必要な Input Data Gear を Context から番号を指定して取り出すことで処理を実行する。 -この処理は stub Code Gear で行われる。 -\coderef{contextContinuation} に stub Code Gear の記述例を示す。 - -\lstinputlisting[caption=Context を経由した継続, label=code:contextContinuation]{./src/contextContinuation.cbc} - -Context はプログラム全体でみると使用する全ての Code Gear と Data Gear の集合を表現する Meta Data Gear になっている。 -しかし、Gears OS を実装する上で Context から Code Gear と Data Gear の番号の組合せを全て展開すると Code Gear がどの Data Gear の番号に対応するかを stub Code Gear に書く必要があり、\coderef{contextContinuation} 9行目のような煩雑な記述が増えてしまった。 - -また、stub Code Gear の記述の煩雑さを避けるために、\coderef{contextContinuation} 11行目のような決まったenumに決まった型の Data Gear を生成し、その Data Gear を複数の Code Gear で使いまわすという、Data Gear をグローバル変数のように扱う問題が多発した。 - -これらの問題点は Context が全ての Code Gear と Data Gear の集合を表現するために起こった問題である。 -そこで、Gears OS をモジュール化する仕組みとして Interface を導入した。 - -\section{Interface の定義} -Interface はある Data Gear の定義と、それに対する操作(API)を行う Code Gear の集合を表現する Data Gear である。 -Context では全ての Code Gear と Data Gear の集合を表現していることに対し、Interface は一部の Code Gear と一部の Data Gear の集合を表現する。 -この Interface は Java のインターフェース、Haskell の型クラスに対応し、導入することでデータ構造を仕様と実装に分けて記述することが出来る。 - -\coderef{queueInterface} に Queue の Interface を示す。 -Interface には以下の内容を定義する。 -\begin{itemize} - \item 操作(API)の引数の Data Gear 群 - - \coderef{queueInterface} 3-4行目は引数の Data Gear 群を定義している。 - ここで定義された Data Gear 名は、定義された Code Gear の引数に対応する。 - - この Interface では10行目で Queue に要素を挿入する Code Gear を定義しており、引数として挿入する Queue の実装と挿入する要素を受け取る。 - この引数それぞれが3-4行目で定義した queue と data に対応する。 - - \item 操作(API) の実行後に継続される Code Gear - - 操作(API)は基本的に実行後の継続先は不定となっている。 - この継続は継続元から渡される。 - 継続元から渡される継続 は \coderef{queueInterface} 5-6行目に定義している変数に格納される。 - この継続は一種のクロージャとして扱うが、実際は Code Gear の番号を渡している。 - ``\_\_code next(...)'' の引数である ``...'' は継続先の Code Gear が複数の Input Data Gear を持つという意味である。 - この ``...'' は他のプログラミング言語では可変長引数のような扱いである。 - - 実行する操作(API) によってこの継続は複数設定される場合がある。 - 例えば、\coderef{queueInterface} は12行目で Queue が空かどうかを調べる Code Gear を定義しており、中身がある場合と空の場合で別の継続を渡す必要がある。 - - \item 操作(API) である Code Gear と Code Gear に渡す引数情報 - - 操作(API) に対応する Code Gear は \coderef{queueInterface} 9-12行目 のように \_\_code として定義する。 - この \_\_code の実体は Code Gear への番号が格納される変数であり、実装した Code Gear に対応する番号を代入する。 - Code Gear の引数には Data Gear と Code Gear 実行後に継続される Code Gear 等を記述する。 - 引数の Data Gear はその Code Gear のInput Data Gear になり、引数の Code Gear の中の引数が Output Data Gear になる。 - Code Gear の第一引数には Interface を実装した Data Gear を渡す。 - これは、Code Gear の操作の対象となる Data Gear を設定しており、後述する継続構文では引数として記述を行わない。 +\chapter{Interface} +Interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。 +呼び出される Code Gear の引数となる Data Gear はここで全て定義される。 - この Interface では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 になる。 -\end{itemize} - - -\lstinputlisting[caption=QueueのInterface, label=code:queueInterface]{./src/queueInterface.h} - -\section{Interface の実装} -Interface は Data Gear に対しての操作(API)を行う Code Gear とその Code Gear で扱われている Data Gear の集合を抽象的に表現した Data Gear であり、実装は別に定義する。 -Interface の実装は、実装する Data Gear の初期化と実装した Code Gear を Interface で定義した Code Gear に代入することで行う。 -この代入する Code Gear を入れ替えることで操作(API)は同じで処理は別の実装を複数表現することが出来る。 -また、実装された Code Gear は引数の Data 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 のインスタンスの生成は関数呼び出しで行われる。 -createSingleLinkedQueue 関数(\coderef{singleLinkedQueue} 3-14行目)は実装した Data Gear の生成を行っている。 -この関数は生成する Data Gear の初期化(\coderef{singleLinkedQueue} 7-8行目)と、実装した Code Gear を Interface で定義した Code Gear の代入(\coderef{singleLinkedQueue} 9-12行目)を行う。 -実際に実装する Data Gear は Interface の型に包まれて生成される(\coderef{singleLinkedQueue} 6行目)。 -このように生成することで実装した Data Gear は実装以外の場所からは Interface の型として扱う事ができる。 - -\lstinputlisting[caption=SingleLinkedQueue の実装, label=code:singleLinkedQueue]{./src/singleLinkedQueue.cbc} - -\section{Interface を利用した Code Gear の継続} -Gears OS では Interface を利用した Code Gear の継続用に ``goto interface-\textgreater method'' という構文を提供している。 -Interface を実装した Data Gear は外からは Interface の型として扱われる。 -そのため構文の``interface`` は実装した Data Gear を Interface の型で包んだポインタ、method は実装した Code Gear に対応する。 +Code\ref{interface}は stack の Interface である。 +Code Gear、Data Gear に参照するために Context を通す必要があるが、 +Interface を記述することでデータ構造の API と Data Gear を結びつけることが出来る。 -\coderef{singleLinkedQueueTest} に Queue Interface を使用した Code Gearの呼び出し例を示す。 -この呼び出しでは SingleLinkedQueue の put 実装に継続される。 - -\lstinputlisting[caption=Queue Interface での Code Gear の呼び出し, label=code:singleLinkedQueueTest]{./src/singleLinkedQueueTest.cbc} - -``goto interface-\textgreater method'' という構文は実際にはスクリプトで変換され、コンパイルされる。 -変換後のコードはメタレベルのコードとなるため、Context をマクロを経由し、直接参照を行う。 -\coderef{singleLinkedQueueTest_script} は \coderef{singleLinkedQueueTest} がスクリプトによってに変換されたソースコードを示しており、 \figref{goto_interface} は \coderef{singleLinkedQueueTest_script} が実行された際の Queue Interface と Code Gear、 Data Gear の関係を示している。 - -\coderef{singleLinkedQueueTest_script} 内の Gearef マクロ(\coderef{singleLinkedQueueTest_script} 5-7行目)は Context から Interface の引数格納用の Data Gear を取り出す。 -この引数格納用の Data Gear は Context の初期化の際に特別に生成され、型は使用される Interface の型と同じである。 -また、引数格納用の Data Gear はノーマルレベルでは参照されず、メタレベルの場合のみ参照される。 -引数格納用の Data Gear を取り出した後は変換前の呼び出しの引数を Interface で定義した Code Gear の引数情報に合わせて格納し、指定した Code Gear に継続する。 +\lstinputlisting[label=interface, caption=StackのInterface]{./src/Stack.cbc} -\coderef{singleLinkedQueueTest_script} では Queue Interface(\coderef{queueInterface}) の put を継続しているため、6行目で Input Data Gear として node Data Gear を 引数格納用の Data Gear の data に代入し、7行目で実行後に継続する Code Gear として queueTest2 を 引数格納用の Data Gear の next に代入している。 - -代入した引数は自動生成された stub Code Gear(\coderef{stubCodeGear})で展開され、実装された Code Gear に Data Gear を渡す。 -stub Code Gear で使用されている GearImpl マクロ(\coderef{stubCodeGear} 12行目)は引数として指定された Interface の型に包まれた Data Gear から実装の Data Gear を取り出す。 - -\lstinputlisting[caption=スクリプトによる変換後, label=code:singleLinkedQueueTest_script]{./src/singleLinkedQueueTest_script.cbc} +Code\ref{implement}は stack の実装の例である。 +createImpl は関数呼び出しで呼び出され、初期化と Code Gear のスロットに対応する Code Gear の番号を入れる。 -\lstinputlisting[caption=スクリプトによって生成された put stub Code Gear, label=code:stubCodeGear]{./src/stubCodeGear.cbc} - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/gotoInterface.pdf} - \end{center} - \caption{Queue Interface で実装した put Code Gear の呼び出し} - \label{fig:goto_interface} -\end{figure} +\lstinputlisting[label=implement, caption=SingleLinkedStackの実装]{./src/stackimpl.cbc}
--- a/paper/introduction.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/introduction.tex Wed Jul 11 21:48:28 2018 +0900 @@ -1,48 +1,47 @@ -\chapter{メタ計算を使った並列処理} -並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている。 -しかし、並列処理のプログラミングはスレッド間の共通資源の競合など非決定的な実行を持っており、その信頼性を保証するには従来のテストやデバッグでは不十分であり、テストしきれない部分が残ってしまう。 - -また、マルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサも並列処理をする上で無視できない。 -これらのプロセッサで性能を出すためにはアーキテクチャに合わせた並列プログラミングが必要になる。 -並列プログラミングフレームワークでは様々なプロセッサを抽象化し、CPU と同等に扱えるようにする柔軟性が求められる。 +\chapter{OS の拡張性と信頼性の両立} -本研究室では通常の計算をノーマルレベルとし、並列処理の信頼性をノーマルレベルの計算に対して保証し、拡張性をノーマルレベルとは別の階層のメタレベルの計算で実現することを目標に Gears OS\cite{kkb-master}を設計、開発中である。 -Gears OS では処理を Code Gear、データを Data Gear という単位を用いてプログラムを記述する。 -Code Gear は入力の Input Data Gear が揃ったら実行され、Output Data Gear を出力する。 -この Input/Output Data Gear の関係から依存関係を決定し、Input Data Gear が揃った Code Gear が並列に実行される。 +さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。OS の信頼性を保証する事自体が難しいが、時代とともに進歩する +ハードウェア、サービスに対応して OS 自体が拡張される必要がある。 +OS は非決定的な実行を持ち、その信頼性を保証するには、従来のテストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。 +これに対処するためには、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。 +モデル検査は無限の状態ではなくても巨大な状態を調べることになり、状態を有限に制限したり状態を抽象化したりする方法が用いられている。 +(図\ref{fig:verification}) +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{./fig/verification.pdf} + \end{center} + \caption{証明とモデル検査によるOSの検証} + \label{fig:verification} +\end{figure} -Gears OS のプログラムの信頼性の確保はモデル検査、検証を使用して行う。 -この信頼性のための計算はメタ計算として記述される。 -このメタ計算は信頼性の他に CPU、GPU などのアーキテクチャに沿った実行環境の切り替え、データの拡張等の拡張性を提供する。 -メタ計算の処理は Meta Code Gear、Meta Data Gear で表現する。 -Meta Code Gear は 通常の Code Gear 間に実行される。 +証明やモデル検査を用いて OS を検証する方法はさまざまなものが検討されている。 +検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。 +つまり信頼性と拡張性を両立させることが重要である。 -従来の研究では OS の実装言語として Python\cite{Sigurbjarnarson:2016:PVF:3026877.3026879} や Haskell\cite{Chen:2015:UCH:2815400.2815402}\cite{Klein:2009:SFV:1629575.1629596} をノーマルレベルとして採用し、メタレベルで検証を行う研究や、メタ計算の実装を型付きアセンブラ(Typed Assembler)\cite{Yang:2010:SLI:1806596.1806610} を用いる例もある。 -Gears OS は ノーマルレベルとメタレベルを共通して表現出来る Continuation Based C(CbC)\cite{utah-master} で実装を行い、証明支援系 Agda\cite{agda} を用いて証明を行う。 -CbC は Code Gear の単位でプログラムを記述し、軽量継続を用いてコード間を移動する。 -軽量継続は関数呼び出しとは異なり、呼び出し元に戻らないため、呼び出し元の環境を覚えずに行き先のみを指定する。 -この CbC は C と互換性のある言語で、型付きアセンブラに比べると大きな表現力を提供する。また Haskell などに比べて関数呼び出しではなく軽量継続を採用しているため、スタック上に隠された環境を持たない。 -そのためメタレベルで使用する資源を明確にできる利点がある。 - -Code Gear 間の継続は次の Code Gear の番号と Context という全ての Code Gear と Data Gear を参照できる Meta Data Gear で行われる。 -Context からノーマルレベルのCode Gear へ接続する際は stub Code Gear という Meta Code Gear を用いる。 -この stub Code Gear はメタレベルの計算であるため、継続先の Code Gear から自動的に生成されるのが望ましい。生成に必要な情報は Code Gear と Data Gear の集まりから得る。 この集まりを Interface\cite{mitsuki-prosym} として定義している。 +コンピュータの計算はプログラミング言語で記述されるが、その言語の実行は操作的意味論の定義などで規定される。 +プログラミング言語で記述される部分をノーマルレベルの計算と呼ぶ。 +コードが実行される時には、処理系の詳細や使用する資源、あるいは、コードの仕様や型などの言語以外の部分が服属する。 +これをメタレベルの計算という。 +この二つのレベルを同じ言語で記述できるようにして、ノーマルレベルの計算の信頼性をメタレベルから保証できるようにしたい。 +ノーマルレベルでの正当性を保証しつつ、新しく付け加えられたデバイスやプログラムを含む正当性を検証したい。 -Gears OS でのプロセス、スレッドは Context が担う。 -並列実行する際は新しく Context を生成し、それを CPU、GPU に割り振る事によって実現される。 -生成された Context には実行する Code Gear と対応する Input/Output Data Gear が登録され、割り振られた先で Context に設定された Code Gear を実行する。 -このContext を用いた並列処理は新規に実行環境を作り、引数を設定するなどの煩雑なメタレベルの処理であり、ノーマルレベルでは Go 言語\cite{go}の goroutine のような簡潔な並列構文があることが望ましい。 - -本研究では Gears OS の基本設計、マルチコアCPU と CUDA による GPUでの実行機構、並列構文を実装し、例題を用いて Gears OS の並列処理の評価を行う。 - -% これはryokka 向きかなぁ +ノーマルレベルとメタレベルを共通して表現できる言語として Continuation based C(以下CbC)\cite{cbc}を用いる。 +CbC は関数呼出時の暗黙の環境(Environment)を使わずに、コードの単位を行き来できる引数付き goto 文(parametarized goto)を持つ C と互換性のある言語である。 +これを用いて、Code Gear と Data Gear、さらにそのメタ構造を導入する。 +これらを用いて、検証された Gears OS を構築したい。 +図\ref{fig:MetaGear}。 +検証には定理証明支援系である Agda を用いる。 +Gears の記述をモジュール化するために Interface を導入した。 +さらに並列処理の記述用にpar goto 構文を導入する。 +これらの機能は Agda 上で継続を用いた関数型プログラムに対応するようになっている。 +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{./fig/MetaGear.pdf} + \end{center} + \caption{Gearsのメタ計算} + \label{fig:MetaGear} +\end{figure} -%現代の OS では拡張性と信頼性を両立させることが要求されている。 -%時代と主に進歩するハードウェア、サービスに対して OS 自体が拡張される必要がある。 -%しかし、OSには非決定的な実行を持っており、その信頼性を保証するには従来のテストとデバッグでは不十分であり、テスト仕切れない部分が残ってしまう。 -%これに対処するために証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。 -% 証明やモデル検査を用いて OS の検証する方法は様々なものが検討されている。 -% 型付きアセンブラ\cite{Yang:2010:SLI:1806596.1806610} -% 従来の研究ではPython\cite{Sigurbjarnarson:2016:PVF:3026877.3026879} や Haskell\cite{Chen:2015:UCH:2815400.2815402}\cite{Klein:2009:SFV:1629575.1629596}による記述した OS を検証する研究も存在する。 -% また SPIN などのモデル検査を OS の検証に用いた例もである。 -% 本研究室では信頼性をノーマルレベルの掲載に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を開発している。 +本論文では Interface と par goto の実装の詳細を記述し評価を行った。 +マルチ CPU と GPU 上での par goto 文の実行を確認した。 +
--- a/paper/master_paper.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/master_paper.tex Wed Jul 11 21:48:28 2018 +0900 @@ -94,10 +94,12 @@ %chapters \input{introduction.tex} -\input{gearsOS.tex} +\input{meta_computation.tex} +\input{GearsOS} \input{interface.tex} +\input{generate_code.tex} \input{parallelism_gears.tex} -\input{gpu.tex} +%\input{gpu.tex} \input{evaluation.tex} \input{conclusion.tex}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/meta_computation.tex Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,52 @@ +\chapter{Gears におけるメタ計算} +Gears OS ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を用いる。 +Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。(図\ref{fig:metaCS}) + +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{./fig/metaCS.pdf} + \end{center} + \caption{Gears でのメタ計算} + \label{fig:metaCS} +\end{figure} + +CbC は軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。 +CbC は LLVM\cite{llvm} と GCC\cite{gcc} 上で実装されている。 +メタレベルの記述は Perl スクリプトによって生成される stub と goto meta によって Code Gear で記述される。 + +Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。 +Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。 +Interface 作成時に Code Gear の集合を指定することにより複数の実装を持つことができる。 +Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して指定される。 +一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Meta Data Gear に格納される。 +この Meta Data Gear を Context という。 +ノーマルレベルでは Context を直接見ることはできない。 + +Code Gear の継続は関数型プログラミングからみると継続先の Context を含む Closure となっている。 +これを記述するために継続に不定長引数を追加する構文をスクプリトの変換機能として用意した。Code \ref{varargnext} +メタ計算側ではこれらの Context を常に持ち歩いているので goto 文で引数を用いることはなく、 +行き先は Code Gear の番号のみで指定される。 + +\lstinputlisting[label=varargnext, caption=不定長引数を持つ継続]{./src/varargnext.cbc} + +これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。 +Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。 +呼び出された Code Gear は必要な引数を Context から取り出す必要がある。 +これは スクリプトで生成された stub Meta Code Gear で行われる。 +Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。 + +Context を複製して複数の CPU に割り当てることにより並列実行を可能になる。 +これによりメタ計算として並列処理を記述したことになる。 +Gears のスレッド生成は Agda の関数型プログラミングに対応して行われるのが望ましい。 +そこで、par goto 構文を導入し、Agda の継続呼び出しに対応させることにした。 +par goto では Context の複製、入力の同期、タスクスケジューラーへの Context の登録などが行われる。 +par goto 文の継続として、スレッドの join に相当する \_\_exit を用意した。 +\_\_exit により par goto で分岐した Code Gear の出力を元のスレッドで受け取ることができる。 + +関数型プログラムではメモリ管理は GC などを通して暗黙に行われる。 +Gears OS ではメモリ管理は stub などのメタ計算部分で処理される。 +例えば、寿命の短いスレッドでは使い捨ての線形アロケーションを用いる。 + +%Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。 + +%これを図示したものが図\ref{fig:metaCS}である。
--- a/paper/parallelism_gears.tex Mon Jul 09 10:41:54 2018 +0900 +++ b/paper/parallelism_gears.tex Wed Jul 11 21:48:28 2018 +0900 @@ -5,301 +5,64 @@ % taskManager の初期化のコードはいらない \chapter{Gears OSの並列処理} -Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。 -Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。 - -本章では、Gears OS の並列処理の構成、機能について説明する。 - -\section{Task} -Gears OS では 並列実行する Task を Context で表現する\cite{ikkun-sigos}。 -Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている。 -Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を 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行目)。 -この Code Gear 実行後は通常 Output Data Gear を書き出す Code Gear に継続する。 -実際に Output Data Gear を書き出す場合、goto 文に Output Data Gear を引数に渡す(\coderef{codeGearExample} 3行目)。 - -\lstinputlisting[caption=並列実行される Code Gear の例, label=code:codeGearExample]{./src/codeGearExample.cbc} - -% Context の話を書く -% 生成されるstub は Context から input/output に index を指定して生成する。 -Task のInput/Output Data Gear の格納場所は Context の Task 情報が持っている。 -その為、Task に対応する Code Gear の stub Code Gear は context が持っている Input/Output Data Gear用のインデックスから Data Gear を取り出す。 -\coderef{metaCodeGearExample} に \coderef{codeGearExample} の stub Code Gear を示す。 -この stub Code Gear も Interface の stub Code Gear と同等にスクリプトによって自動生成される。 - -\lstinputlisting[caption=並列実行される Code Gear のstub Code Gear, label=code:metaCodeGearExample]{./src/metaCodeGearExample.cbc} - -\section{TaskManager} -Gears OS の TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。 -\coderef{taskManagerInterface} に TaskManager の Interface を示す。 - -\lstinputlisting[caption=TaskManager の Interface, label=code:taskManagerInterface]{./src/taskManagerInterface.cbc} - -TaskManager は 以下の API を持っている。 - -\begin{itemize} - \item Task の実行(spawn、spawnTasks) - \item Task の依存関係の設定(setWaitTask) - \item TaskManager が管理している Task 数のインクリメントとデクリメント(increment/decrementTaskCount) - \item TaskManager(shutdown)の終了処理 -\end{itemize} - -TaskManager は初期化の際に、指定した数の Worekr を生成する。 -その際CPU、GPU の数を指定することができ、指定した分の CPUWorker と GPUWorker が生成される。 - -TaskManager は \figref{sendTask}に示すように spawn を呼び出した際、実行する Task の Input Data Gear が用意されているかを判断する。 -Input Data Gear が全て用意されている場合、その Task を Worker の Queue に送信する。 - 送信する Worker は Task を実行する環境(CPU、GPU) によって決定する。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/sendTask.pdf} - \end{center} - \caption{Workerへの Task 送信} - \label{fig:sendTask} -\end{figure} - -\section{Worker} -Worker は自身の Queue から Task を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。 - -\coderef{createCPUWorker} に Task を CPU で実行する CPUWorker の初期化部分を示す。 -CPUWorker は初期化の際に スレッドを生成する(\coderef{createCPUWorker} 10行目)。 -生成されたスレッドはまず startWorker 関数(\coderef{createCPUWorker} 14-21行目)を呼び出し、このスレッド用の Context を生成する。 -Context をスレッド毎に生成することで、メモリ空間をスレッドごとに持てるため Gearef マクロ で Interface の引数を取得する際の競合、メモリ確保の処理での他のスレッドの停止を防ぐ事ができる。 - -\lstinputlisting[caption=CPUWorker の初期化, label=code:createCPUWorker]{./src/createCPUWorker.cbc} - -Context の生成後は Queue から Task を取得する Code Gear へ継続する。 -Task は Context なので、Worker は Context を入れ替えて Task の実行を行う。 - -CPUWorker での Task の実行を\coderef{workerRun}、 \figref{workerRun} に示す。 -\coderef{workerRun} は Context の入れ替えを行うため、getTaskCPUWorker(\coderef{workerRun} 1-9行目)の引数に入れ替え後のTask(Context)を記述している。 -Worker は中身が NULL の task を取得すると Worker の終了処理を行う(\coderef{workerRun} 2-4 行目)。 -Task が取得できた場合 Task の実行後に継続する Code Gear を格納し(\coderef{workerRun} 7行目)、Task を Context としてCode Gear に継続する(\coderef{workerRun} 8行目)。 -Task の実行後に継続する Code Gear は Data Gear の書き出しと依存関係の解決を行う。 -Data Gear 書き出し後は Task の Context を Worker の Context に入れ替え、再び Task を取得する Code Gear に継続する。 - -\lstinputlisting[caption=CPUWorker でのTaskの実行, label=code:workerRun]{./src/workerRun.cbc} - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/workerRun.pdf} - \end{center} - \caption{Workerでの Task 実行} - \label{fig:workerRun} -\end{figure} +Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。 +Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。 +Gears OS では 並列実行する Task を Context で表現する。 +Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている +Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を Worker に送信する。 +Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。 \section{SynchronizedQueue} SynchronizedQueue は Worker の Queue として使用される。 -Worker の Queue は TaskManager を経由して Task を送信するスレッドと Task を取得する Worker 自身のスレッドで扱われる。 -そのため SynchronizedQueue はマルチスレッドでもデータの一貫性を保証する Queue を実装する必要がある。 +Worker の Queue は TaskManager を経由して Task を送信するスレッドと Task を取得する Worker 自身のスレッドで扱われる。 +そのため SynchronizedQueue はマルチスレッドでもデータの一貫性を保証する Queue を実装する必要がある。 -データの一貫性を保証する解決例としての1つとしてロックを使った解決方法がある。 -しかし、ロックを行ってデータを更新した場合、同じ Queue に対して操作を行う際に待ち合わせが発生し、全体の並列度が下がってしまう。 -そこで、Gears OS ではデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue\cite{queue} を実装している。 -CAS は値の比較、更新をアトミックに行う命令である。 -CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。 -異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。 +データの一貫性を保証する解決例としての 1 つとしてロックを使った解決方法がある。 +しかし、ロックを行ってデータを更新した場合、同じ Queue に対して操作を行う際に待ち合わせが発生し、全体の並列度が下がってしまう。 +そこで、Gears OS ではデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue を実装している。 +CAS は値の比較、更新をアトミックに行う命令である。 +CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。 +異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。 -Gears OS ではこの CAS を行うための Interface を定義している(\coderef{atomicInterface})。 -この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義している(\coderef{atomicInterface} 6行目)。 +Gears OS ではこの CAS を行うための Interface を定義している(Code\ref{atomicInterface})。 +この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義して +いる(Code\ref{atomicInterface} 6行目)。 -\lstinputlisting[caption=AtomicInterface, label=code:atomicInterface]{./src/atomicInterface.h} +\lstinputlisting[label=atomicInterface, caption=AtomicInterface]{./src/atomicInterface.h} -AtomicInterface での CAS の実際の実装を \coderef{atomicImpl} に示す。 -実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(\coderef{atomicImpl} 2行目)。 +AtomicInterface での CAS の実際の実装を Code\ref{atomicImpl} に示す。 +実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(Code\ref{atomicImpl} 2行目)。 この関数は第一引数に渡されたアドレスに対して第二引数の値から第三引数の値ヘ CAS を行う。 CAS に成功した場合、true を返し、失敗した場合は false を返す。 -\coderef{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。 +Code\ref{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。 -\lstinputlisting[caption=CAS の実装, label=code:atomicImpl]{./src/atomicImpl.cbc} +\lstinputlisting[caption=CAS の実装, label=atomicImpl]{./src/atomicImpl.cbc} -SynchronizedQueue の Data Gear の定義を \coderef{synchronizedQueue} に示す。 +SynchronizedQueue の Data Gear の定義を Code\ref{synchronizedQueue} に示す。 SynchronizedQueue はデータのリストの先頭と、終端のポインタを持っている。 Queue を操作する際はこのポインタに対して CAS をすることでデータの挿入と取り出しを行う。 -\lstinputlisting[caption=SynchronizedQueue の定義, label=code:synchronizedQueue]{./src/synchronizedQueue.h} - -\figref{takeSynchronizedQueue1} は要素の取り出し(dequeue) を行った流れを示している。 -データを取り出す際はリストの先頭を次の要素へ CAS することででデータを取得する。 -この Queue では先頭に挿している要素はダミー扱いとする。 -その為、実際に取り出される値は CAS に成功した後の先頭の値となる。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/takeSynchronizedQueue1.pdf} - \end{center} - \caption{SynchronizedQueueによる要素の取り出し} - \label{fig:takeSynchronizedQueue1} -\end{figure} - -\figref{putSynchronizedQueue1} は要素の挿入(inqueue) を行った流れを示している。 -データを挿入する際は2度の CAS を行う。 -まず、末尾の要素の次の要素を新しい要素に CAS を行う。 -その後、末尾の要素が差している要素を挿入に成功した新しい要素に CAS を行う。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/putSynchronizedQueue1.pdf} - \end{center} - \caption{SynchronizedQueueによる要素の挿入} - \label{fig:putSynchronizedQueue1} -\end{figure} - -しかし、データの挿入する際は2度の CAS の間に他のスレッドの操作が入り、Queueの構造が破綻する場合がある。 -例えば\figref{putSynchronizedQueue2} に示すように、あるスレッドが末尾を更新した際に、他のスレッドが更新処理を行うとQueue が破綻する。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/putSynchronizedQueue2.pdf} - \end{center} - \caption{SynchronizedQueue によるデータの挿入時の破綻例} - \label{fig:putSynchronizedQueue2} -\end{figure} - -\newpage - -\figref{putSynchronizedQueue2}は2つのスレッドが以下の順番で処理を行っている。 - -\begin{enumerate} - \item threadA: 末尾の要素(data3)の次の要素を新しい要素(data4)に CAS を実行する - \item threadB: threadA での末尾更新をする前に末尾の要素(data3)の次の要素を新しい要素(data5)にCASを実行する。 - この時の末尾が指す要素は、threadA が要素挿入を行う前の状態と同じなため、この操作を行うとリストが破綻する。 - \item threadA: 末尾の要素(data3)を挿入に成功した要素(data4)に CAS を行う。 - \item threadB: 末尾の要素(data3)を挿入に成功した要素(data5)に CAS を行う。 - threadB が挿入の操作を行ったときの末尾はthreadA が末尾更新する前の末尾要素なので、このCAS は失敗する。 -\end{enumerate} - -この破綻は末尾の要素が必ず末尾を示していると仮定しているためである。 -しかし、データ挿入の際は2度の CAS の間に他のスレッドが割り込む場合がある。 -そこで、末尾の要素は必ずしも末尾を示さないと仮定して要素の取出しと挿入の処理を記述する。 -\coderef{putSynchronizedQueue} は要素の挿入の処理の一部である。 -末尾の要素が末尾を示さない場合の処理は\coderef{putSynchronizedQueue} の 13-16 行目に記述している。 -変数 nextElement は 末尾要素の次の要素を示しており、NULL ではない場合は末尾を差していない状態ということになる。 -その場合は、末尾の要素をnextElement に CAS を行う。 -この処理は要素の取り出しを行う際にも行われる。 - -\lstinputlisting[caption=SynchronizedQueue による要素の挿入, label=code:putSynchronizedQueue]{./src/putSynchronizedQueue.cbc} - -\section{依存関係の解決} -Gears OS は並列処理の依存関係を Input と Output の Data Gear と Code Gear の関係で解決する。 -Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。 - -Data Gear はメタレベルで依存関係解決のための Queue を持っている。 -この Queue にはその Data Gear を Input Data Gear として使用する Task(Context)が入っている。 - -依存関係の解決の流れを\figref{dependency} に示す。 -Worker は Task の Code Gear を実行後、Output Data Gear の 書き出し処理(Commit)を行う。 -書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。 -参照した Task には実行に必要な Input Data Gear のカウンタをもっているので、そのカウンタのデクリメントを行う。 -カウンタが $0$ になったら Task が待っている Input Data Gear が揃ったことになるので、その Task を TaskManager 経由で 実行される Worker に送信する。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.7]{./fig/dependency.pdf} - \end{center} - \caption{依存関係の解決処理} - \label{fig:dependency} -\end{figure} +\lstinputlisting[caption=SynchronizedQueue の定義, label=synchronizedQueue]{./src/synchronizedQueue.h} \section{並列構文} -Gears OS では並列実行する Task の設定をメタレベルで \coderef{metaCreateTask} のように行っている。 -\coderef{metaCreateTask} では実行する Code Gear、待ち合わせ中の Input Data Gear の数、Input/Output Data Gear への参照等の設定を記述している。 -これらの記述は Context などを含む煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である。 -そこで、Context を直接用いないノーマルレベルの並列構文である par goto 文を用意した。 - -\lstinputlisting[caption=メタレベルによる Task の生成, label=code:metaCreateTask]{./src/metaCreateTask.cbc} - -\coderef{parGotoCreateTask}に par goto文による記述例を示す。 -この記述はスクリプトにより、Task で実行される Code Gear の Input/Output の数を解析し、\coderef{metaCreateTask} に変換される。 - -\lstinputlisting[caption=par goto による並列実行, label=code:parGotoCreateTask]{./src/parGotoCreateTask.cbc} - -par goto の引数には Input/Output Data Gear と 実行後に継続する Code Gear を渡す。 -par goto で生成された Task は \_\_exit に継続することで終了する。 -Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、Output Data Gear への書き出し処理に継続される。 -これにより Code Gear と Data Gear の依存関係をノーマルレベルで記述できるようになる。 -この par goto 文は 通常のプログラミングの関数呼び出しのように扱える。 - -\section{Task(Context) 間の同期処理} -Gears OS では複数の Task(Context) から同じ Output Data Gear を修正する場合がある。 -その際に適切な同期処理を行わずそのまま実行すると Output Data Gear の整合性が取れない場合がある。 +Gears OS の並列構文は par goto文で用意されている(Code\ref{pargoto})。 +\lstinputlisting[caption=par goto による並列実行, label=pargoto]{./src/parGotoCreateTask.cbc} +par goto の引数には Input/Output Data Gear と 実行後に継続する \_\_exit を渡す。 +par goto で生成された Task は \_\_exit に継続することで終了する。 -そこで 複数のTask 間の同期処理を行うために Semaphore の実装を行った。 -Semaphore の Interface を \coderef{semaphoreInterface} に示す。 - -\lstinputlisting[caption=Semaphore Interface, label=code:semaphoreInterface]{./src/semaphoreInterface.h} - -Semaphore はある資源に対してアクセスできるスレッドの数を制限するものであり、P命令 と V命令がある。 -P命令は資源の消費に相当し、V命令が資源の開放に相当する命令である。 -P命令を行う際、資源がなければ V命令で開放されるまでそのスレッドは処理を停止する。 - -Gears OS の Context はスレッドに相当するため、 Gears OS 上で Semaphore を実装することは Context の停止を実装する必要がある。 -Gears OS の Semaphore は Context の停止を停止用の待ち Queue を使って行う。 +この par goto 文は通常のプログラミングの関数呼び出しのように扱うことができる。 -\figref{semaphoreSequence} に資源が1つのSemaphore に2つのContext が P命令を実行しているシーケンス図を示す。 - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.4]{./fig/semaphoreSequence.pdf} - \end{center} - \caption{Gears OS 上 Semaphore} - \label{fig:semaphoreSequence} -\end{figure} - -\figref{semaphoreSequence} の処理の流れを以下に示す。 +Code\ref{perlpargoto} は par goto である Code\ref{pargoto} を perl スクリプトによって変換が行われたコードである。 +\lstinputlisting[caption=perl スクリプトによる par goto の変換, label=perlpargoto]{./src/parGotoCreateTask.c} -\begin{enumerate} - \item Context1 が Semaphore に対して P命令を実行する。 - Semaphore には資源が残っているので資源を消費する - \item Context2 が Semaphore に対して P命令を実行する。 - この時、Semaphore に資源が残っていないので Context を Seamphore が持っている待ち Queue に追加する。 - その後はContext2 を取得していた Worker に処理を移譲する。 - \item Context1 が Semaphore に対して V命令を実行する。 - Semaphore の資源を開放しつつ、 待ち Queue に Context があるかの確認を行う。 - Context があった場合 1つ Context を 待ち Queue から取得し、TaskManager へ Context の実行を行う命令を実効する。 -\end{enumerate} - -TaskManager に送られた Context は Worker で取得される。 -取得された Context は停止した時の状態を記録しているため、停止した Code Gear である P命令を再び実行する。 - -\section{データ並列} -並列プログラミングを行う際、並列化の方式としてタスク並列とデータ並列の2つがある。 -Gears OS の並列処理は Task(Context) を使用したタスク並列により実現されている。 - -タスク並列は処理をタスクに分割し、各タスク間に依存関係のないものを集め、それを並列化する。 -Gears OS では依存関係を Input/Output Data Gear から解析を行い、依存関係が解決された Code Gear から実行される。 -一方でデータ並列は処理対象のデータが十分な数のサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法である。 -このデータ並列は GPGPU と相性が良く、GPU 環境でも実行できる Gears OS でもサポートを行った。 +par goto文でも 通常の goto 文と同様にメタへの goto 文へ置き換えられるが、par goto 文では通常の goto 文とは異なるメタへと継続する。 +Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、 +Output Data Gear への書き出し処理(Commit)に継続される。 -Gears OS でデータ並列実行を行う場合、\coderef{iteratePargoto} のようにpar goto 文の引数にデータ並列用の構文として iterate を入れて実行する。 -iterate は複数の数値を引数とし、数値の値がデータの分割数、数値の個数が次元数になる。 - -\lstinputlisting[caption=par goto によるデータ並列, label=code:iteratePargoto]{./src/iteratePargoto.cbc} - -Gears OS は データ並列用の par goto を実行した場合、 データ並列用に Task が生成される。 -この Task には \coderef{iteratorInterface} の Iterator Interface を実装した Data Gear を持たせる。 -このデータ並列用の Task は Input Data Gear が揃うまでは通常の Task 同等として扱う。 -依存関係が解決され、実行可能な Task になった際に、 Iterator Interface の exec を呼ぶ。 -exec では par goto で渡された次元、数値分 Task を コピーし、インデックスを割り当てる処理を行う。 -この index は コピーされた Task の Input Data Gear として扱われ、Code Gear 内では通常の Data Gear として利用される。 -\figref{iterateTaskExec} は1次元で 数値$4$ を渡した場合の Task 実行を示している。 -コピーされた Task は通常の Task と同じように TaskManager を通して Worker に送信される。 +Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。 +Code Gear の引数である\_\_next が持つ引数の Data Gear が Output Data Gear となる。 -\lstinputlisting[caption=Iterator Interface の定義, label=code:iteratorInterface]{./src/iteratorInterface.h} - -\begin{figure}[htbp] - \begin{center} - \includegraphics[scale=0.6]{./fig/iterateTaskExec.pdf} - \end{center} - \caption{1次元、数値$4$のデータ並列用 Task の実行} - \label{fig:iterateTaskExec} -\end{figure} - -通常の Task であれば、実行後に Output Data Gear を書き出す処理に入るが、 データ並列用の Task はコピーされた全てのTask 実行後に Output Data Gear の書き出しを行う。 -その判断と処理を行うのが Iterator Interface の barrier である。 -barrier は コピーされた Task 実行後に呼ばれ、Output Data Gear が書き出せる状態なら書き出し処理を行う Code Gear に継続し、書き出せる状態でないなら Worker に操作を移譲するCode Gear に継続する。 +書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。 +参照した Task が持つ実行に必要な Input Data Gear カウンタのデクリメントを行う。 +カウンタが0になると Task が待っている Input Data Gear が揃ったことになり、 +その Task を TaskManager 経由で 実行される Worker に送信する。
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/Stack.cbc Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,14 @@ +typedef struct Stack<Impl>{ + union Data* stack; + union Data* data; + union Data* data1; + __code whenEmpty(...); + __code clear(Impl* stack,__code next(...)); + __code push(Impl* stack,union Data* data, __code next(...)); + __code pop(Impl* stack, __code next(union Data*, ...)); + __code pop2(Impl* stack, union Data** data, union Data** data1, __code next(union Data**, union Data**, ...)); + __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); + __code get(Impl* stack, union Data** data, __code next(...)); + __code get2(Impl* stack,..., __code next(...)); + __code next(...); +} Stack;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/ex_stub Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,11 @@ +__code clearSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,enum Code next) { + stack->top = NULL; + goto meta(context, next); +} + +__code clearSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); + enum Code next = Gearef(context, Stack)->next; + goto clearSingleLinkedStack(context, stack, next); +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/parGotoCreateTask.c Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,31 @@ +__code code1(struct Context *context,struct Integer* integer1, struct Integer* integer2, struct Integer* output) { + struct Element* element; + context->task = NEW(struct Context); + initContext(context->task); + context->task->next = C_add; + context->task->idgCount = 2; + context->task->idg = context->task->dataNum; + context->task->maxIdg = context->task->idg + 2; + context->task->odg = context->task->maxIdg; + context->task->maxOdg = context->task->odg + 1; + GET_META(integer1)->wait = createSynchronizedQueue(context); + GET_META(integer2)->wait = createSynchronizedQueue(context); + GET_META(output)->wait = createSynchronizedQueue(context); + context->task->data[context->task->idg+0] = (union Data*)integer1; + context->task->data[context->task->idg+1] = (union Data*)integer2; + context->task->data[context->task->odg+0] = (union Data*)output; + element = &ALLOCATE(context, Element)->Element; + element->data = (union Data*)context->task; + element->next = context->taskList; + context->taskList = element; + Gearef(context, TaskManager)->taskList = context->taskList; + Gearef(context, TaskManager)->next1 = C_code2; + goto meta(context, C_code2); +} + +__code code1_stub(struct Context* context) { + Integer* integer1 = Gearef(context, Integer); + Integer* integer2 = Gearef(context, Integer); + Integer* output = Gearef(context, Integer); + goto code1(context, integer1, integer2, output); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/stackimpl.cbc Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,27 @@ +Stack* createSingleLinkedStack(struct Context* context) { + struct Stack* stack = new Stack(); + struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack(); + stack->stack = (union Data*)singleLinkedStack; + singleLinkedStack->top = NULL; + stack->push = C_pushSingleLinkedStack; + stack->pop = C_popSingleLinkedStack; + stack->pop2 = C_pop2SingleLinkedStack; + stack->get = C_getSingleLinkedStack; + stack->get2 = C_get2SingleLinkedStack; + stack->isEmpty = C_isEmptySingleLinkedStack; + stack->clear = C_clearSingleLinkedStack; + return stack; +} + +__code clearSingleLinkedStack(struct SingleLinkedStack* stack,__code next(...)) { + stack->top = NULL; + goto next(...); +} + +__code pushSingleLinkedStack(struct SingleLinkedStack* stack,union Data* data, __code next(...)) { + Element* element = new Element(); + element->next = stack->top; + element->data = data; + stack->top = element; + goto next(...); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/src/varargnext.cbc Wed Jul 11 21:48:28 2018 +0900 @@ -0,0 +1,9 @@ +__code popSingleLinkedStack(struct SingleLinkedStack* stack, __code next(union Data* data, ...)) { + if (stack->top) { + data = stack->top->data; + stack->top = stack->top->next; + } else { + data = NULL; + } + goto next(data, ...); +}