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}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 \usepackage{listings}
|
|
5
|
5 \usepackage{enumitem}
|
|
|
6
|
|
|
7 \lstset{
|
|
|
8 language=C,
|
|
|
9 tabsize=2,
|
|
|
10 frame=single,
|
|
|
11 basicstyle={\footnotesize},%
|
|
|
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 \renewcommand{\lstlistingname}{Code}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 \input{dummy.tex} %% Font
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 % ユーザが定義したマクロなど．
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 \makeatletter
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 \begin{document}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 % 和文表題
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 \title{Monad に基づくメタ計算を基本とする Gears OS の設計}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 % 英文表題
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 \etitle{}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 % 所属ラベルの定義
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 \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
|
44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 % 和文著者名
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 \author{
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 小久保 翔平\affiref{1}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 \and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 伊波 立樹\affiref{2}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 \and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 河野 真治\affiref{2}
|
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 % 英文著者名
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 \eauthor{
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 Shohei KOKUBO\affiref{1}\and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 Tatsuki Iha\affiref{2}\and
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 Shinji KONO\affiref{2}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 }
|
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 \contact{小久保 翔平\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 〒903-0213 沖縄県西原町千原1番地\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 琉球大学工学部情報工学科\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 email: kokubo@cr.ie.u-ryukyu.ac.jp}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 % 和文概要
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 \begin{abstract}
|
|
5
|
71 本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。
|
|
5
|
73 今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と Meta Data Gear を付属させる。
|
|
|
74 Code Gear が実行されるとそれに属する Meta Code Gear が実行され、Meta Computation が行われる。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 \end{abstract}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 % 英文概要
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 \begin{eabstract}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 \end{eabstract}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 % 表題などの出力
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 \maketitle
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86 % 本文はここから始まる
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87
|
|
5
|
88 % Introduce
|
|
|
89 \section{Gears OS}
|
|
|
90 並列実行は Code の並列実行だけでなく、Data の単位が重要である。
|
|
|
91 本研究では Code Gear, Data Gear という単位で細かく分割し、依存関係を記述することで並列実行するフレームワーク Gears OS の開発を行なっている。
|
|
|
92 Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能である。
|
|
|
93
|
|
|
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 ローを防止する。
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156
|
|
5
|
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{}
|
2
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
236 \nocite{*}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
237 \bibliographystyle{ipsjunsrt}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
238 \bibliography{sigos}
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
239
|
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
240 \end{document}
|
