Mercurial > hg > Papers > 2015 > kkb-sigos

comparison paper/sigos.tex @ 5:05be3fd35750

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
edit
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 05 May 2015 14:24:59 +0900
parents 8e3bf4806e33
children b02e6b40f470
comparison
equal deleted inserted replaced
4:537ebaa79b21 5:05be3fd35750
1 \documentclass[techrep]{ipsjpapers} 1 \documentclass[techrep]{ipsjpapers}
2 \usepackage[dvipdfm]{graphicx} 2 \usepackage[dvipdfm]{graphicx}
3 \usepackage{url} 3 \usepackage{url}
4 \usepackage{listings} 4 \usepackage{listings}
5 \lstset{% 5 \usepackage{enumitem}
6 language={C++},%使用言語 6
7 basicstyle={\small},%書体 7 \lstset{
8 commentstyle={\small\itshape},%コメントの書体 8 language=C,
9 keywordstyle={\small\bfseries},%キーワードの書体 9 tabsize=2,
10 %identifierstyle={\small},% 10 frame=single,
11 %ndkeywordstyle={\small},% 11 basicstyle={\footnotesize},%
12 stringstyle={\small},%文字列の書体 12 identifierstyle={\footnotesize},%
13 frame={trlb},%外枠 13 commentstyle={\footnotesize\itshape},%
14 breaklines=true,%改行 14 keywordstyle={\footnotesize\bfseries},%
15 ndkeywordstyle={\footnotesize},%
16 stringstyle={\footnotesize\ttfamily},
17 breaklines=true,
18 captionpos=b,
15 columns=[l]{fullflexible},% 19 columns=[l]{fullflexible},%
16 xrightmargin=0zw,% 20 xrightmargin=0zw,%
17 xleftmargin=3zw,% 21 xleftmargin=1zw,%
18 %numbers=none,%行番号の表示 22 aboveskip=1zw,
19 %numberstyle={\scriptsize},%行番号の書体 23 numberstyle={\scriptsize},%
20 %numbersep=1zw,% 24 stepnumber=1,
21 %stepnumber=1, 25 numbersep=1zw,%
22 lineskip=-0.5ex,% 26 lineskip=-0.5ex%
23 captionpos=b,%キャプションの位置
24 } 27 }
28
25 \renewcommand{\lstlistingname}{Code} 29 \renewcommand{\lstlistingname}{Code}
26 \input{dummy.tex} %% Font 30 \input{dummy.tex} %% Font
27 31
28 % ユーザが定義したマクロなど． 32 % ユーザが定義したマクロなど．
29 \makeatletter 33 \makeatletter
62 TEL: (098)895-2221\qquad FAX: (098)895-8727\\ 66 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
63 email: kokubo@cr.ie.u-ryukyu.ac.jp} 67 email: kokubo@cr.ie.u-ryukyu.ac.jp}
64 68
65 % 和文概要 69 % 和文概要
66 \begin{abstract} 70 \begin{abstract}
67 本研究室では Code Segment, Data Segment を用いた並列フレームワークの開発を行なっている。 71 本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
68 並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。 72 並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。
69 今回設計した Gears OS では Code Segment, Data Segment それぞれに Meta Code Segment と Meta Data Segment を付属させる。 73 今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と Meta Data Gear を付属させる。
70 Code Segment が実行されるとそれに属する Meta Code Segment が実行され、Meta Computation が行われる。 74 Code Gear が実行されるとそれに属する Meta Code Gear が実行され、Meta Computation が行われる。
71 Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。 75 Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
72 本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。 76 本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
73 \end{abstract} 77 \end{abstract}
74 78
75 % 英文概要 79 % 英文概要
79 % 表題などの出力 83 % 表題などの出力
80 \maketitle 84 \maketitle
81 85
82 % 本文はここから始まる 86 % 本文はここから始まる
83 87
84 \input{introduction} 88 % Introduce
85 \input{theory} 89 \section{Gears OS}
86 \input{design} 90 並列実行は Code の並列実行だけでなく、Data の単位が重要である。
87 \input{gearbox} 91 本研究では Code Gear, Data Gear という単位で細かく分割し、依存関係を記述することで並列実行するフレームワーク Gears OS の開発を行なっている。
88 \input{implement} 92 Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能である。
89 \input{conclusion} 93
90 94 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
95 Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。
96
97 Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。
98 これにより、生成されたプログラムの信頼性を保証する。
99
100 Gears OS は Gear を継続することによる柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
101
102 % Theory
103 \section{Monad とメタ計算}
104 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
105 がある。
106 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
107 作用、メモリ管理などがある。
108 メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案
109 されている。
110 Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。
111
112 Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの
113 に必要な情報を格納している。
114 失敗する可能性がある計算の場合は、計算が失敗したかどうかのフラグが
115 Monad に含まれる。
116 並行処理の場合は、Monad は可能な計算の interleaving(並び替え) になるが、
117 実際に並び替えを持っているわけではなく、マルチプロセッサで実行する環境
118 そのものが Monad に対応する。
119
120 通常の関数を Monad を返すように変更することにより、メタ関数が得られる。
121 逆に Monad の中にある通常の戻り値のみに着目すると通常の関数に戻る。
122 このように、Monad を用いたメタ計算の表現では通常の計算とメタ計算が一対
123 一に対応する。
124
125 一般的には複数の Monad の組み合わせが Monad になることを示すのは難しい。
126 Gears OS では Code と Data を分離して、Code から他の Code への呼び出し
127 を継続を用いて行う。
128 Gears OS での Monad は Meta Code と Meta Data になる。
129
130 % Code Gear
131 % Data Gear
132 % Meta Code Gear
133 % Meta Data Gear
134 \section{Code Gear と Data Gear}
135 Gears OS ではプログラムの実行単位として様々な Gear を使う。
136 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。
137
138 Code Gear はプログラムの実行コードそのものであり、Cuda
139 の kernel に相当する。
140 Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
141 き込む。
142 Code Gear は接続された Data Gear 以外には触らない。
143 Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。
144 その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
145
146 Data Gear には、int や文字列などの Primitive Data Type が入る。
147 自分が持っていない Code Gear, Data Gear は名前で指し示す。
148
149 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることに
150 ある。
151 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
152
153 Code Gear, Data Gear はポインタを直接には扱わない。
154 これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフ
155 ローを防止する。
156
157 Code Gear, Data Gear はそれぞれ関係を持っている。
158 例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ
159 Data Gear などである。
160 Gear の関連付けは Meta Gear を通して行う。
161 Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当
162 する。
163 なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
164
165 % s/Segment/Gear
166
167 % Context
168 \section{継続}
169 ある Code Gear から継続するときには、次に実行する Code Gear を名前で指
170 定する。
171 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
172 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対
173 応する。
174 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
175 この Meta Data Gear を Context と呼ぶことにする。
176 これは従来の OS の Process や Thread に対応する。
177
178 Context には以下のようなものが格納される。
179 \begin{itemize}
180 \item Code Gear の名前とポインタの対応表
181 \item Data Gear の Allocation 用の情報
182 \item Code Gear が参照する Data Gear へのポインタ
183 \item Data Gear に格納される Data Type の情報
184 \end{itemize}
185
186 \lstinputlisting[caption=Context]{source/context.h}
187
188 \textbf{Code Gear の名前とポインタの対応表}
189
190 Code Gear の名前とポインタの対応は enum と関数ポインタによって表現される。
191 これにより、実行時に比較ルーチンなどを動的に変更することが可能になる。
192
193 \textbf{Data Gear の Allocation 用の情報}
194
195 Context の生成時にある程度の領域を確保する。
196 Context にはその領域へのポインタとサイズが格納されている。
197 そのポインタを必要な Data Gear のサイズに応じて、インクリメントすることによって Data Gear の Allocation を実現する。
198
199 \textbf{Code Gear が参照する Data Gear へのポインタ}
200
201 Context には Data Gear へのポインタが格納されている。
202 Code Gear は Context を通して Data Gear へアクセスする。
203
204 \textbf{Data Gear に格納される Data Type の情報}
205
206 Data Gear は union と struct によって表現される。
207 Context には Data Gear の Data Type の情報が格納されている。
208 この情報から確保する Data Gear のサイズなどを決定する。
209
210 \lstinputlisting[caption=initContext]{source/context.c}
211
212 % Persistent
213 \section{Persistent Data Gear}
214 Data Gear の管理には木構造を用いる。
215 この木構造は非破壊で構築される。
216 非破壊的木構造では、編集元の木構造を破壊することなく新しい木構造を構成する。
217 破壊的木構造と異なりロックの必要がなく、平行して読み書き、参照を行うことが可能である。
218 また、変更前の木構造をすべて保持しているので過去のデータにアクセスすることができる。
219
220 \begin{figure}[!h]
221 \centering
222 \includegraphics[width=70mm]{images/nondestructive_tree_modification.pdf}
223 \caption{木構造の非破壊的編集}
224 \end{figure}
225
226 % allocator
227 \section{Allocator}
228 Gears OS では Context の生成時にある程度の領域を確保し、その領域を指すポインタをインクリメントすることで Allocation を実現する。
229
230 Context には Allocation 用の Data Gear が格納されている。
231 この Data Gear に確保するサイズと確保後に接続する Code Gear の名前を書き込み、Allocation を行う Code Gear に接続することで必要な領域を確保する。
232
233 \lstinputlisting[caption=Allocator]{source/allocate.h}
234
235 \section{}
91 \nocite{*} 236 \nocite{*}
92 %\nocite{opencl}
93 %\nocite{opencl:ref}
94 %\nocite{opencl:applied}
95 %\nocite{yutaka:os}
96 \bibliographystyle{ipsjunsrt} 237 \bibliographystyle{ipsjunsrt}
97 \bibliography{sigos} 238 \bibliography{sigos}
98 %\bibliography{cerium,book}
99
100 239
101 \end{document} 240 \end{document}