2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \documentclass[techrep]{ipsjpapers}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 \usepackage[dvipdfm]{graphicx}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 \usepackage{url}
|
|
10
|
4 \usepackage{listings,jlisting}
|
|
5
|
5 \usepackage{enumitem}
|
|
|
6
|
|
|
7 \lstset{
|
|
|
8 language=C,
|
|
|
9 tabsize=2,
|
|
|
10 frame=single,
|
|
10
|
11 basicstyle={\ttfamily\footnotesize},%
|
|
5
|
12 identifierstyle={\footnotesize},%
|
|
|
13 commentstyle={\footnotesize\itshape},%
|
|
|
14 keywordstyle={\footnotesize\bfseries},%
|
|
|
15 ndkeywordstyle={\footnotesize},%
|
|
|
16 stringstyle={\footnotesize\ttfamily},
|
|
|
17 breaklines=true,
|
|
|
18 captionpos=b,
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 columns=[l]{fullflexible},%
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 xrightmargin=0zw,%
|
|
5
|
21 xleftmargin=1zw,%
|
|
|
22 aboveskip=1zw,
|
|
|
23 numberstyle={\scriptsize},%
|
|
|
24 stepnumber=1,
|
|
|
25 numbersep=1zw,%
|
|
|
26 lineskip=-0.5ex%
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 }
|
|
5
|
28
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 \input{dummy.tex} %% Font
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 % ユーザが定義したマクロなど．
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 \makeatletter
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 \begin{document}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 % 和文表題
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 \title{Monad に基づくメタ計算を基本とする Gears OS の設計}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 % 英文表題
|
|
9
|
39 \etitle{Design of Gears OS with Meta Computation based on Monad}
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 % 所属ラベルの定義
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 % 和文著者名
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 \author{
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 小久保 翔平\affiref{1}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 \and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 伊波 立樹\affiref{2}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 \and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 河野 真治\affiref{2}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 % 英文著者名
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 \eauthor{
|
|
9
|
56 Shohei KOKUBO\affiref{1}
|
|
|
57 \and
|
|
|
58 Tatsuki Iha\affiref{2}
|
|
|
59 \and
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 Shinji KONO\affiref{2}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 }
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 % 連絡先（投稿時に必要．製版用では無視される．）
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 \contact{小久保 翔平\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 〒903-0213 沖縄県西原町千原1番地\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 琉球大学工学部情報工学科\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 email: kokubo@cr.ie.u-ryukyu.ac.jp}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 % 和文概要
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 \begin{abstract}
|
|
5
|
72 本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
|
|
10
|
73 Code Gear, Data Gear は処理とデータの単位である。
|
|
|
74 並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現する。
|
|
|
75 今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と Meta Data Gear を対応させる。
|
|
|
76 Code Gear が実行されるとそれに対応する Meta Code Gear が実行され、Meta Computation が行われる。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
|
|
10
|
78 本論文では基本的な機能を設計し、CbC(Continuation based C) で実装する。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 \end{abstract}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 % 英文概要
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 \begin{eabstract}
|
|
10
|
83 We are developing parallel framework using a Code/Data Gear.
|
|
|
84 Code/Data Gear are unit of processing and data.
|
|
11
|
85 Meta function for parallel execution based on a Monad in Functional Language is used in Geas OS.
|
|
|
86 A Meta Code/Data Gear attached to a Code/Data Gear as a Monad.
|
|
9
|
87 Meta Computation performs Network Management, Memory Management and more.
|
|
11
|
88 We show same implemetation of Gears OS using CbC(Continuation based C).
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 \end{eabstract}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 % 表題などの出力
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 \maketitle
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 % 本文はここから始まる
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95
|
|
5
|
96 % Introduce
|
|
9
|
97 \section{Cerium と Alice}
|
|
11
|
98 本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なってきた。
|
|
10
|
99
|
|
|
100 Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
|
|
9
|
101
|
|
|
102 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
|
|
|
103 依存関係はプログラマ自身が意識して記述する必要がある。
|
|
|
104 Task の種類が増えると記述が煩雑になり、プログラマの負担が大きくなる。
|
|
10
|
105 Task の依存関係がデータの依存関係を正しく保証しない場合があるという問題がある。
|
|
|
106 また、Task の取り扱うデータには型情報がない。
|
|
|
107 汎用ポインタをキャストして利用するしかなく、型の検査が行われていない。
|
|
|
108 Cerium は C++ で実装されているが、オブジェクトと並列処理が直接対応していないのでオブジェクト指向で記述する利点が少ない。
|
|
9
|
109 Cell\cite{cell}, Many Core CPU, GPU といった様々なプロセッサをサポートしている。
|
|
10
|
110 しかし、それぞれの環境でプログラムを高速に動作させるためにはそれぞれに合わせた実行機構を必要としている。
|
|
9
|
111
|
|
|
112 Alice は本研究室で開発を行なっている分散管理フレームワークである。
|
|
10
|
113 Alice では処理の単位である Code Segment, データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
|
|
9
|
114 Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。
|
|
10
|
115 Alice は Java で実装されており、実行速度が遅いという問題がある。
|
|
9
|
116 また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。
|
|
|
117
|
|
10
|
118 \section{Gears OS}
|
|
11
|
119 Cerium と Alice の例題から Code の単位だけでなく、Data の単位も必要であることがわかった。
|
|
10
|
120 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
|
|
|
121 Code Gear は Input Data Gear から Output Data Gear を生成する。
|
|
|
122 Input と Output の関係から Code Gear 同士の依存関係を解決し、並列実行するフレームワークの開発を行う。
|
|
|
123 Code Gear はそれに接続された Data Gear のみを扱う。
|
|
|
124 Code/Data Gear 同士の関係は Meta Code/Data Gear によって表現される。
|
|
|
125 この Meta Code/Data Gear を用いることで機能やデータ自体を拡張することができる。
|
|
9
|
126
|
|
|
127 Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。
|
|
|
128 Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。
|
|
10
|
129
|
|
11
|
130 本研究室で開発している CbC(Continuation based C)\cite{cbc} を用いて、Gears OS を実装する。
|
|
10
|
131 CbC はプログラムを Code Segment, Data Segment という単位で記述する。
|
|
|
132 CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。
|
|
|
133 CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる。
|
|
5
|
134
|
|
|
135 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
|
|
10
|
136 関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
|
|
|
137 Gears OS では、Meta Code/Data Gear を Monad として定義し、Meta Computation を実現する。
|
|
5
|
138
|
|
10
|
139 Gears OS では並列実行をサポートするだけでなく、信頼性も確保する。
|
|
|
140 そのために Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能\cite{model-check}を提供する。
|
|
|
141 並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。
|
|
|
142 これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
|
|
|
143 Model Checking も Meta Code/Data Gear を用いて実現する。
|
|
5
|
144
|
|
9
|
145 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
|
|
|
146 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
|
|
11
|
147 Gears OS の構成は図\ref{fig:arch}の通りである。
|
|
|
148
|
|
|
149 \begin{figure}[!h]
|
|
|
150 \centering
|
|
|
151 \includegraphics[width=70mm]{images/arch.pdf}
|
|
|
152 \caption{Gears OS の構成}
|
|
|
153 \label{fig:arch}
|
|
|
154 \end{figure}
|
|
5
|
155
|
|
|
156 % Theory
|
|
|
157 \section{Monad とメタ計算}
|
|
|
158 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
|
|
|
159 がある。
|
|
|
160 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
|
|
|
161 作用、メモリ管理などがある。
|
|
9
|
162 メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{monad}
|
|
5
|
163 されている。
|
|
|
164 Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。
|
|
|
165
|
|
|
166 Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの
|
|
|
167 に必要な情報を格納している。
|
|
|
168 失敗する可能性がある計算の場合は、計算が失敗したかどうかのフラグが
|
|
|
169 Monad に含まれる。
|
|
|
170 並行処理の場合は、Monad は可能な計算の interleaving(並び替え) になるが、
|
|
|
171 実際に並び替えを持っているわけではなく、マルチプロセッサで実行する環境
|
|
|
172 そのものが Monad に対応する。
|
|
|
173
|
|
|
174 通常の関数を Monad を返すように変更することにより、メタ関数が得られる。
|
|
|
175 逆に Monad の中にある通常の戻り値のみに着目すると通常の関数に戻る。
|
|
|
176 このように、Monad を用いたメタ計算の表現では通常の計算とメタ計算が一対
|
|
|
177 一に対応する。
|
|
|
178
|
|
|
179 一般的には複数の Monad の組み合わせが Monad になることを示すのは難しい。
|
|
|
180 Gears OS では Code と Data を分離して、Code から他の Code への呼び出し
|
|
|
181 を継続を用いて行う。
|
|
|
182 Gears OS での Monad は Meta Code と Meta Data になる。
|
|
|
183
|
|
|
184 % Code Gear
|
|
|
185 % Data Gear
|
|
|
186 % Meta Code Gear
|
|
|
187 % Meta Data Gear
|
|
|
188 \section{Code Gear と Data Gear}
|
|
|
189 Gears OS ではプログラムの実行単位として様々な Gear を使う。
|
|
|
190 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。
|
|
|
191
|
|
9
|
192 Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
|
|
5
|
193 の kernel に相当する。
|
|
|
194 Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
|
|
|
195 き込む。
|
|
|
196 Code Gear は接続された Data Gear 以外には触らない。
|
|
|
197 Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。
|
|
|
198 その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
|
|
|
199
|
|
|
200 Data Gear には、int や文字列などの Primitive Data Type が入る。
|
|
|
201 自分が持っていない Code Gear, Data Gear は名前で指し示す。
|
|
|
202
|
|
|
203 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることに
|
|
|
204 ある。
|
|
|
205 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
|
|
|
206
|
|
|
207 Code Gear, Data Gear はポインタを直接には扱わない。
|
|
|
208 これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフ
|
|
|
209 ローを防止する。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210
|
|
5
|
211 Code Gear, Data Gear はそれぞれ関係を持っている。
|
|
|
212 例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ
|
|
|
213 Data Gear などである。
|
|
|
214 Gear の関連付けは Meta Gear を通して行う。
|
|
|
215 Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当
|
|
|
216 する。
|
|
|
217 なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
|
|
|
218 % s/Segment/Gear
|
|
|
219
|
|
|
220 % Context
|
|
|
221 \section{継続}
|
|
|
222 ある Code Gear から継続するときには、次に実行する Code Gear を名前で指
|
|
|
223 定する。
|
|
|
224 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
|
|
|
225 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対
|
|
|
226 応する。
|
|
|
227 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
|
|
|
228 この Meta Data Gear を Context と呼ぶことにする。
|
|
|
229 これは従来の OS の Process や Thread に対応する。
|
|
|
230
|
|
|
231 Context には以下のようなものが格納される。
|
|
|
232 \begin{itemize}
|
|
|
233 \item Code Gear の名前とポインタの対応表
|
|
|
234 \item Data Gear の Allocation 用の情報
|
|
|
235 \item Code Gear が参照する Data Gear へのポインタ
|
|
|
236 \item Data Gear に格納される Data Type の情報
|
|
|
237 \end{itemize}
|
|
|
238
|
|
|
239 \lstinputlisting[caption=Context]{source/context.h}
|
|
|
240
|
|
6
|
241 \paragraph*{Code Gear の名前とポインタの対応表}
|
|
5
|
242 Code Gear の名前とポインタの対応は enum と関数ポインタによって表現される。
|
|
|
243 これにより、実行時に比較ルーチンなどを動的に変更することが可能になる。
|
|
|
244
|
|
6
|
245 \paragraph*{Data Gear の Allocation 用の情報}
|
|
5
|
246 Context の生成時にある程度の領域を確保する。
|
|
|
247 Context にはその領域へのポインタとサイズが格納されている。
|
|
|
248 そのポインタを必要な Data Gear のサイズに応じて、インクリメントすることによって Data Gear の Allocation を実現する。
|
|
|
249
|
|
6
|
250 \paragraph*{Code Gear が参照する Data Gear へのポインタ}
|
|
5
|
251 Context には Data Gear へのポインタが格納されている。
|
|
|
252 Code Gear は Context を通して Data Gear へアクセスする。
|
|
|
253
|
|
6
|
254 \paragraph*{Data Gear に格納される Data Type の情報}
|
|
5
|
255 Data Gear は union と struct によって表現される。
|
|
|
256 Context には Data Gear の Data Type の情報が格納されている。
|
|
|
257 この情報から確保する Data Gear のサイズなどを決定する。
|
|
|
258
|
|
|
259 \lstinputlisting[caption=initContext]{source/context.c}
|
|
|
260
|
|
|
261 % Persistent
|
|
|
262 \section{Persistent Data Gear}
|
|
|
263 Data Gear の管理には木構造を用いる。
|
|
|
264 この木構造は非破壊で構築される。
|
|
6
|
265 非破壊的木構造では、図\ref{fig:non-destructive_tree}のように編集元の木構造を破壊することなく新しい木構造を構成する。
|
|
5
|
266 破壊的木構造と異なりロックの必要がなく、平行して読み書き、参照を行うことが可能である。
|
|
|
267 また、変更前の木構造をすべて保持しているので過去のデータにアクセスすることができる。
|
|
|
268
|
|
|
269 \begin{figure}[!h]
|
|
|
270 \centering
|
|
|
271 \includegraphics[width=70mm]{images/nondestructive_tree_modification.pdf}
|
|
|
272 \caption{木構造の非破壊的編集}
|
|
6
|
273 \label{fig:non-destructive_tree}
|
|
5
|
274 \end{figure}
|
|
|
275
|
|
|
276 % allocator
|
|
|
277 \section{Allocator}
|
|
|
278 Gears OS では Context の生成時にある程度の領域を確保し、その領域を指すポインタをインクリメントすることで Allocation を実現する。
|
|
|
279
|
|
|
280 Context には Allocation 用の Data Gear が格納されている。
|
|
|
281 この Data Gear に確保するサイズと確保後に接続する Code Gear の名前を書き込み、Allocation を行う Code Gear に接続することで必要な領域を確保する。
|
|
|
282
|
|
10
|
283 \lstinputlisting[label=allocate, caption=Allocator]{source/allocate.h}
|
|
|
284
|
|
|
285 ソースコード\ref{allocate}では Code Gear である code1 でポインタを扱っており、Code Gear でポインタを扱わないという設計思想に合っていない。
|
|
|
286 そこで、ソースコード\ref{allocate-ideal}をソースコード\ref{allocate}として解釈するようにコンパイラを改良する。
|
|
|
287
|
|
|
288 \lstinputlisting[label=allocate-ideal, caption=SyntaxSugar]{source/allocate-ideal.c}
|
|
5
|
289
|
|
6
|
290 % List
|
|
|
291 \section{List}
|
|
|
292 通常 List は要素と次へのポインタを持つ構造体で表現される。
|
|
|
293 Gears OS の場合、Meta レベル以外でポインタは扱わないので図\ref{fig:list}のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。
|
|
|
294
|
|
|
295 \begin{figure}[!h]
|
|
|
296 \centering
|
|
|
297 \includegraphics[width=70mm]{images/List.pdf}
|
|
|
298 \caption{List の表現}
|
|
|
299 \label{fig:list}
|
|
|
300 \end{figure}
|
|
|
301
|
|
10
|
302 \section{Synchronized Queue}
|
|
|
303 Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。
|
|
11
|
304 Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。
|
|
|
305 この図を GearBox と呼ぶことにする。
|
|
|
306 図\ref{fig:sync}は Synchronized Queue の GearBox である。
|
|
|
307 M:receiver/sender が CAS を行う Meta Code Gear となる。
|
|
|
308
|
|
|
309 \begin{figure}[!h]
|
|
|
310 \centering
|
|
|
311 \includegraphics[width=70mm]{images/synchronizedQueue.pdf}
|
|
|
312 \caption{Synchronized Queue}
|
|
|
313 \label{fig:sync}
|
|
|
314 \end{figure}
|
|
10
|
315
|
|
9
|
316 \section{比較}
|
|
|
317 Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。
|
|
|
318
|
|
|
319 \paragraph*{Cerium/Alice}
|
|
|
320 Gears OS の Code Gear は Cerium の Task, Context は HTask に相当する。
|
|
|
321 Cerium とは異なり、Gears OS は処理とデータが分離している。
|
|
|
322 Gears OS では分離したデータを Data Gear と呼称する。
|
|
|
323 これは Alice の Data Segment と同等のものである。
|
|
|
324 Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。
|
|
|
325
|
|
11
|
326 Alice は Data Segment を MessagePack\cite{msg} を利用して通信することで分散実行を実現する。
|
|
10
|
327 Gears OS 上での分散実行も Alice に沿って設計・実装する。
|
|
|
328
|
|
9
|
329 \paragraph*{OpenCL/CUDA}
|
|
|
330 Code Gear は OpenCL/CUDA の kernel に相当する。
|
|
|
331 OpenCL/CUDA には Data Gear に相当する仕組みはない。
|
|
|
332 接続された複数の Code Gear は接続された順番通りに実行される。
|
|
|
333 これは、OpenCL の CommandQueue, CUDA の Stream と同等のものである。
|
|
|
334 OpenCL/CUDA では kernel の依存関係を複雑に記述する必要があるが、Gears OS では Code と Data の関係から自動的に依存関係を解決する。
|
|
|
335
|
|
|
336 \paragraph*{従来の OS}
|
|
|
337 従来の OS が行なってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code Gear, Meta Data Gear を用いて行う。
|
|
|
338 このメタ計算は Monad に基づいて実現される。
|
|
|
339
|
|
|
340 \section{まとめ}
|
|
|
341 Gears OS は Inherent Parallel をキーワードとして、Gears OS 上で実行されるプログラムが自動的に並列で処理されるように設計した。
|
|
|
342 Gear を他の Gear に接続することで機能およびデータの拡張を行える柔軟性を持つ。
|
|
|
343 Meta な機能や並行制御を関数型言語における Monad に基づいて実現する。
|
|
|
344 また、機能として Model Checking を持ち、Gears OS 上で実行されるプログラムの信頼性を保証する。
|
|
|
345 本論文では必要な機能の一部である Context, Allocator, List, Non-Destructive Red-Black Tree を CbC を用いて実装した。
|
|
|
346 今後は、Synchronized Queue, Woker を実装する予定である。
|
|
|
347 これにより、Cerium と同等の例題を動かすことが可能となる。
|
|
|
348 例題としては Bitonic Sort, Word Count を予定している。
|
|
|
349 例題が動くことを確認し次第、Gears OS の測定・評価を行う。
|
|
|
350
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
351 \nocite{*}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
352 \bibliographystyle{ipsjunsrt}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
353 \bibliography{sigos}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
354
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
355 \end{document}
|
