Mercurial > hg > Papers > 2019 > anatofuz-thesis
comparison paper/chapter3.tex @ 22:faeaa82a4479
add chapter3
author | anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 11 Feb 2019 16:38:51 +0900 (2019-02-11) |
parents | |
children | e929996bee43 |
comparison
equal
deleted
inserted
replaced
21:e6e66afc3a73 | 22:faeaa82a4479 |
---|---|
1 \chapter{Gears OS} | |
2 \section{Gears OS} | |
3 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。 | |
4 Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。 | |
5 Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。 | |
6 また、接続された Data Gear 以外には参照を行わない。 | |
7 処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。 | |
8 | |
9 Gears OS ではメタ計算を、Meta Code Gear、Meta Data Gear で表現する。 | |
10 Meta Code Gear は通常のCode Gear の直後に遷移され、メタ計算を実行する。 | |
11 | |
12 CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。 | |
13 | |
14 図\ref{fig:gearsos} に Gears OS の構成図を示す。 | |
15 | |
16 \begin{figure}[htpb] | |
17 \begin{center} | |
18 \scalebox{0.2}{\includegraphics{fig/gearsos.pdf}} | |
19 \end{center} | |
20 \caption{Gears OS の構成図} | |
21 \label{fig:gearsos} | |
22 \end{figure} | |
23 | |
24 \section{Context} | |
25 Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。 | |
26 Gears OS は必要な Code/Data Gear に参照したい場合、この Context を通す必要がある。 | |
27 メインとなる Context と Worker 用の Context がある。 | |
28 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。 | |
29 | |
30 Context は Task でもあり、TaskManager によってが Context 生成され CPUWorker へ送られる。 | |
31 Worker に渡された Task である Context の Input/Output Data Gear の依存関係が解決されたものから並列実行される。 | |
32 | |
33 %現在 CbC で Gears OS を記述すると通常の Computation に加えて Meta Computation である stub を記述する必要がある。 | |
34 %Meta Computation | |
35 | |
36 | |
37 %Context や stub は Meta Computation であるため。 | |
38 | |
39 | |
40 \section{interface の記述} | |
41 | |
42 interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。 | |
43 create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。 | |
44 return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。 | |
45 | |
46 \begin{lstlisting}[frame=lrbt,label=interface,caption={interface}] | |
47 typedef struct Stack<Impl>{ | |
48 union Data* stack; | |
49 union Data* data; | |
50 union Data* data1; | |
51 __code whenEmpty(...); | |
52 __code clear(Impl* stack,__code next(...)); | |
53 __code push(Impl* stack,union Data* data, __code next(...)); | |
54 __code pop(Impl* stack, __code next(union Data*, ...)); | |
55 __code pop2(Impl* stack, union Data** data, union Data** data1, __code next(union Data**, union Data**, ...)); | |
56 __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...)); | |
57 __code get(Impl* stack, union Data** data, __code next(...)); | |
58 __code get2(Impl* stack,..., __code next(...)); | |
59 __code next(...); | |
60 } Stack; | |
61 \end{lstlisting} | |
62 | |
63 \begin{lstlisting}[frame=lrbt,label=create,caption={createSingleLinkedStack}] | |
64 Stack* createSingleLinkedStack(struct Context* context) { | |
65 struct Stack* stack = new Stack(); | |
66 struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack(); | |
67 stack->stack = (union Data*)singleLinkedStack; | |
68 singleLinkedStack->top = NULL; | |
69 stack->push = C_pushSingleLinkedStack; | |
70 stack->pop = C_popSingleLinkedStack; | |
71 stack->pop2 = C_pop2SingleLinkedStack; | |
72 stack->get = C_getSingleLinkedStack; | |
73 stack->get2 = C_get2SingleLinkedStack; | |
74 stack->isEmpty = C_isEmptySingleLinkedStack; | |
75 stack->clear = C_clearSingleLinkedStack; | |
76 return stack; | |
77 } | |
78 \end{lstlisting} | |
79 | |
80 \section{Gearef、GearImpl} | |
81 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 | |
82 Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すためコードが煩雑になってしまう(リスト\ref{ref})。 | |
83 そこで Code Gear がデータを参照するための Gearef というマクロを定義した。 | |
84 Gearef に Context と型を渡すことでデータの参照が行える。 | |
85 また impliment のデータを参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。 | |
86 GearImpl は Context と interface 名、interface の変数名を指定して参照する。 | |
87 Gearef と GearImpl を用いたコードがリスト\ref{Gearef}である。 | |
88 | |
89 \begin{lstlisting}[frame=lrbt,label=ref,caption={Gearef、GearImplのないコード}] | |
90 __code pushSingleLinkedStack_stub(struct Context* context) { | |
91 SingleLinkedStack* stack = (SingleLinkedStack*)context->data[D_Stack]->Stack.stack->Stack.stack; | |
92 Data* data = context->data[D_Stack]->Stack.data; | |
93 enum Code next = context->data[D_Stack]->Stack.next; | |
94 goto pushSingleLinkedStack(context, stack, data, next); | |
95 } | |
96 \end{lstlisting} | |
97 | |
98 \begin{lstlisting}[frame=lrbt,label=Gearef,caption={Gearef、GearImplを使ったコード}] | |
99 __code pushSingleLinkedStack_stub(struct Context* context) { | |
100 SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack); | |
101 Data* data = Gearef(context, Stack)->data; | |
102 enum Code next = Gearef(context, Stack)->next; | |
103 goto pushSingleLinkedStack(context, stack, data, next); | |
104 } | |
105 \end{lstlisting} | |
106 | |
107 \section{stub Code Gear} | |
108 Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。 | |
109 しかし、Context を直接扱うのはセキュリティ上好ましくない。 | |
110 そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。 | |
111 stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。 | |
112 | |
113 %この機能により、CbC は Code Gear のみでなく Data Gear を単位として用いることが可能になった。 | |
114 %Meta Code Gear、Meta Data Gear により meta computation を通常の Code Gear 内に記述せずにすむ、Code Gear 間に実行される Meta Code Gear で継続先を変更する、エラーハンドリングを行うといった使い方ができるようになるだろう。 | |
115 | |
116 %\section{TaskQueue} | |
117 %ActiveTaskQueue と WaitTaskQueue の 2 つの TaskQueue を持つ。 | |
118 %先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。 | |
119 %Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。 | |
120 %Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。 | |
121 % | |
122 %\section{TaskManager} | |
123 %Task には Input Data Gear, Output Data Gear が存在する。 | |
124 %Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。 | |
125 %依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。 | |
126 %TaskManager はメインとなる Context を参照する。 | |
127 % | |
128 %\section{Persistent Data Tree} | |
129 %非破壊木構造で構成された Lock-free なデータストアである。 | |
130 %Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。 | |
131 % | |
132 %\section{Worker} | |
133 %TaskQueue から Task の取得・実行を行う。 | |
134 %Task の処理に必要なデータは Persistent Data Tree から取得する。 | |
135 %処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。 | |
136 % |