# HG changeset patch # User anatofuz # Date 1549870731 -32400 # Node ID faeaa82a4479ae7af2407cee3507fede2b9f7977 # Parent e6e66afc3a73b6df4f1e3d2bed8bf5124fb5bc2f add chapter3 diff -r e6e66afc3a73 -r faeaa82a4479 paper/chapter3.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/chapter3.tex Mon Feb 11 16:38:51 2019 +0900 @@ -0,0 +1,136 @@ +\chapter{Gears OS} +\section{Gears OS} +Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。 +Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。 +Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。 +また、接続された Data Gear 以外には参照を行わない。 +処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。 + +Gears OS ではメタ計算を、Meta Code Gear、Meta Data Gear で表現する。 +Meta Code Gear は通常のCode Gear の直後に遷移され、メタ計算を実行する。 + +CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。 + +図\ref{fig:gearsos} に Gears OS の構成図を示す。 + +\begin{figure}[htpb] + \begin{center} + \scalebox{0.2}{\includegraphics{fig/gearsos.pdf}} + \end{center} + \caption{Gears OS の構成図} + \label{fig:gearsos} +\end{figure} + +\section{Context} +Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。 +Gears OS は必要な Code/Data Gear に参照したい場合、この Context を通す必要がある。 +メインとなる Context と Worker 用の Context がある。 +Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。 + +Context は Task でもあり、TaskManager によってが Context 生成され CPUWorker へ送られる。 +Worker に渡された Task である Context の Input/Output Data Gear の依存関係が解決されたものから並列実行される。 + +%現在 CbC で Gears OS を記述すると通常の Computation に加えて Meta Computation である stub を記述する必要がある。 +%Meta Computation + + +%Context や stub は Meta Computation であるため。 + + +\section{interface の記述} + +interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。 +create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。 +return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。 + +\begin{lstlisting}[frame=lrbt,label=interface,caption={interface}] +typedef struct Stack{ + 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; +\end{lstlisting} + +\begin{lstlisting}[frame=lrbt,label=create,caption={createSingleLinkedStack}] +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; +} +\end{lstlisting} + +\section{Gearef、GearImpl} +Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 +Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すためコードが煩雑になってしまう(リスト\ref{ref})。 +そこで Code Gear がデータを参照するための Gearef というマクロを定義した。 +Gearef に Context と型を渡すことでデータの参照が行える。 +また impliment のデータを参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。 +GearImpl は Context と interface 名、interface の変数名を指定して参照する。 +Gearef と GearImpl を用いたコードがリスト\ref{Gearef}である。 + +\begin{lstlisting}[frame=lrbt,label=ref,caption={Gearef、GearImplのないコード}] +__code pushSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)context->data[D_Stack]->Stack.stack->Stack.stack; + Data* data = context->data[D_Stack]->Stack.data; + enum Code next = context->data[D_Stack]->Stack.next; + goto pushSingleLinkedStack(context, stack, data, next); +} +\end{lstlisting} + +\begin{lstlisting}[frame=lrbt,label=Gearef,caption={Gearef、GearImplを使ったコード}] +__code pushSingleLinkedStack_stub(struct Context* context) { + SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); + Data* data = Gearef(context, Stack)->data; + enum Code next = Gearef(context, Stack)->next; + goto pushSingleLinkedStack(context, stack, data, next); +} +\end{lstlisting} + +\section{stub Code Gear} +Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。 +しかし、Context を直接扱うのはセキュリティ上好ましくない。 +そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。 +stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。 + +%この機能により、CbC は Code Gear のみでなく Data Gear を単位として用いることが可能になった。 +%Meta Code Gear、Meta Data Gear により meta computation を通常の Code Gear 内に記述せずにすむ、Code Gear 間に実行される Meta Code Gear で継続先を変更する、エラーハンドリングを行うといった使い方ができるようになるだろう。 + +%\section{TaskQueue} +%ActiveTaskQueue と WaitTaskQueue の 2 つの TaskQueue を持つ。 +%先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。 +%Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。 +%Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。 +% +%\section{TaskManager} +%Task には Input Data Gear, Output Data Gear が存在する。 +%Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。 +%依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。 +%TaskManager はメインとなる Context を参照する。 +% +%\section{Persistent Data Tree} +%非破壊木構造で構成された Lock-free なデータストアである。 +%Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。 +% +%\section{Worker} +%TaskQueue から Task の取得・実行を行う。 +%Task の処理に必要なデータは Persistent Data Tree から取得する。 +%処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。 +% diff -r e6e66afc3a73 -r faeaa82a4479 paper/main.pdf Binary file paper/main.pdf has changed diff -r e6e66afc3a73 -r faeaa82a4479 paper/main.tex --- a/paper/main.tex Mon Feb 11 15:59:08 2019 +0900 +++ b/paper/main.tex Mon Feb 11 16:38:51 2019 +0900 @@ -82,7 +82,7 @@ %\input{chapter3.tex} % %% 実装 -%\input{chapter4.tex} +\input{chapter4.tex} % %% 評価 %\input{chapter5.tex}