|
0
|
1 \documentclass[techrep]{ipsjpapers}
|
|
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
|
3 \usepackage{url}
|
|
|
4 \usepackage{listings,jlisting}
|
|
|
5 \usepackage{enumitem}
|
|
|
6
|
|
|
7 \lstset{
|
|
6
|
8 language=C,
|
|
|
9 tabsize=2,
|
|
|
10 frame=single,
|
|
|
11 basicstyle={\ttfamily\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,
|
|
|
19 columns=[l]{fullflexible},%
|
|
|
20 xrightmargin=0zw,%
|
|
|
21 xleftmargin=1zw,%
|
|
|
22 aboveskip=1zw,
|
|
|
23 numberstyle={\scriptsize},%
|
|
|
24 stepnumber=1,
|
|
|
25 numbersep=0.5zw,%
|
|
|
26 lineskip=-0.5ex,
|
|
0
|
27 }
|
|
6
|
28 \renewcommand{\lstlistingname}{Code}
|
|
0
|
29
|
|
|
30 \input{dummy.tex} %% Font
|
|
|
31
|
|
|
32 % ユーザが定義したマクロなど．
|
|
|
33 \makeatletter
|
|
|
34
|
|
|
35 \begin{document}
|
|
|
36
|
|
|
37 % 和文表題
|
|
|
38 \title{Code Gear、 Data Gear に基づく OS のプロトタイプ}
|
|
|
39 % 英文表題
|
|
|
40 \etitle{}
|
|
|
41
|
|
|
42 % 所属ラベルの定義
|
|
|
43 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
|
|
|
44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
|
|
|
45
|
|
|
46 % 和文著者名
|
|
|
47 \author{
|
|
|
48 伊波 立樹\affiref{1}
|
|
|
49 \and
|
|
|
50 東恩納 琢偉 \affiref{2}
|
|
|
51 \and
|
|
|
52 河野 真治\affiref{2}
|
|
|
53 }
|
|
|
54
|
|
|
55 % 英文著者名
|
|
|
56 \eauthor{
|
|
|
57 Tatsuki IHA\affiref{1}
|
|
|
58 \and
|
|
|
59 Takui HIGASHIONNA\affiref{2}
|
|
|
60 \and
|
|
|
61 Shinji KONO\affiref{2}
|
|
|
62 }
|
|
|
63
|
|
|
64 % 連絡先（投稿時に必要．製版用では無視される．）
|
|
|
65 \contact{伊波 立樹\\
|
|
|
66 〒903-0213 沖縄県西原町千原1番地\\
|
|
|
67 琉球大学工学部情報工学科\\
|
|
|
68 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
|
|
|
69 email: innparusu@cr.ie.u-ryukyu.ac.jp}
|
|
|
70
|
|
|
71 % 和文概要
|
|
|
72 \begin{abstract}
|
|
|
73 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて並列実行を行う Gears OS を開発している
|
|
|
74 Gears OS では 並列実行をするための Task を Code Gear と Data Gear の組で表現する。
|
|
|
75 Task の依存関係は Code Gear を実行するために必要なInput Data Gear と Code Gearで作られる Output Data Gear によって決定し、それにそって並列実行を行う。
|
|
|
76 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。
|
|
|
77 Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。
|
|
|
78 本論文ではGears OS のプロトタイプとして並列処理機構を設計し、 CbC(Continuation based C) で実装する。
|
|
|
79 \end{abstract}
|
|
|
80
|
|
|
81 % 英文概要
|
|
|
82 \begin{eabstract}
|
|
|
83 \end{eabstract}
|
|
|
84
|
|
|
85 % 表題などの出力
|
|
|
86 \maketitle
|
|
|
87
|
|
|
88 % 本文はここから始まる
|
|
|
89
|
|
|
90 % Introduce
|
|
7
|
91 \section{Gears OS}
|
|
|
92 CPU の処理速度の向上のためクロック周波数の増加は発熱や消費電力の増大により難しくなっている。
|
|
|
93 そのため、クロック周波数を上げる代わりに CPU のコア数を増やす傾向にある。
|
|
|
94 マルチコア CPU の性能を発揮するには、処理をできるだけ並列化しなければならない。
|
|
|
95 また、PC の処理性能を上げるためにマルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサが登場している。
|
|
|
96 並列処理をする上でこれらのリソースを無視することができない。
|
|
|
97 しかし、これらのプロセッサで性能を出すためにはこれらのアーキテクチャに合わせた並列プログラミングが必要になる。
|
|
|
98 並列プログラミングフレームワークではこれらのプロセッサを抽象化し、CPU と同等に扱えるようにすることも求められる。
|
|
|
99 本研究では Cerium を開発して得られた知見を元にこれらの性質を持つ並列プログラミングフレームワークとして Gears OS の設計・実装を行う。
|
|
2
|
100
|
|
7
|
101 Cerium\cite{cerium} は本研究室で開発していた並列プログラミングフレームワークである。
|
|
|
102 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。
|
|
|
103 Cerium では依存関係を Task 間で設定するが、本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することができない。
|
|
|
104 また、Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がない。
|
|
|
105 そのため、本要ポインタをキャストして利用するしか無く、型の検査を行う事ができない。
|
|
|
106
|
|
|
107 Gears OS\cite{gears} は Code Gear と Data Gear によって構成される。
|
|
|
108 Code Gear は処理の単位、Data Gear はデータの単位となる。
|
|
|
109 Gears OS では Code/Data Gear を用いて記述することでプログラム全体の並列度を高めて、効率的に並列処理することが可能になることを目的とする。
|
|
|
110 また、Gears OS の実装自体が Code/Data Gear を用いたプログラミングの指針となるように実装する。
|
|
|
111 Gears OS における Task は実行する Code Gear と実行に必要な Input Data Gear, 出力される Output Data Gear の組で表現される。
|
|
|
112 Input/Output Data Gear によって依存関係が決定し、それに沿って並列実行する。
|
|
|
113 依存関係の解決などの Meta Computation の実行は Meta Code Gear で行われる。
|
|
|
114 Meta Code Gear は Code Gear に対応しており、 Code Gear が実行した後にそれに対応した Meta Code Gear が実行される。
|
|
|
115 本論文ではGears OS のプロトタイプとして Data Gear を管理する Persistent Data Tree, Task を管理する TaskQueue, 並列処理を行う Worker を実装し、簡単な例題を用いて Gears OS の評価を行う。
|
|
6
|
116
|
|
1
|
117 \section{Code Gear と Data Gear}
|
|
2
|
118 Gears OS はプログラムの単位として Gear を用いる。
|
|
|
119 Gear は並列実行の単位、データの分割、Gear 間の接続等になる。
|
|
|
120
|
|
|
121 Code Gear はプログラムの処理そのものである。
|
|
|
122 Code Gear は任意の数の Input Data Gear を参照し、 処理が完了すると任意の数の Output Data Gear に書き込む。
|
|
|
123 Code Gear は接続された Data Gear 以外には参照行わない。
|
|
|
124
|
|
|
125 Data Gear は Data そのものを表しており、int や文字列などの Primitive Data Type が入っている。
|
|
|
126
|
|
7
|
127 Code Gear、 Data Gear は 本研究室で開発されている Alice\cite{alice} で使われている単位である Code Segment、 Data Segment\cite{segment} それぞれに対応する。
|
|
|
128
|
|
2
|
129 Gears OS では Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Code Gear の並列実行を可能とする。
|
|
|
130
|
|
|
131 Gear の特徴として処理やデータの構造が Code Gear、 Data Gear に閉じていることにある。
|
|
|
132 これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。
|
|
|
133
|
|
7
|
134 \section{Meta Computation}
|
|
|
135 Gears OS では通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。
|
|
|
136 Meta Computation の例として並列処理の依存関係の解決や、 OS が行うネットワーク管理、メモリ管理等の資源制御などが挙げられる。
|
|
|
137
|
|
|
138 Gears OS では Meta Computation を Meta Code Gear、 Meta Data Gear で表現する。
|
|
|
139 Meta Code Gear は通常の Code Gear 直後に遷移され、 Meta Computation を実行する。
|
|
|
140 Meta Computation の実行後は通常の Code Gear で指定した Code Gear を実行する。
|
|
|
141 つまり Code Gear の実行後は何かしらの Meta Code Gear を実行する。
|
|
|
142
|
|
2
|
143 \section{Continuation based C}
|
|
7
|
144 Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行う。
|
|
2
|
145 CbC は処理を Code Segment を用いて記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。
|
|
0
|
146
|
|
2
|
147 CbC のプログラムでは C の関数の代わりに Code Segment を用いてい処理を記述している。 Code Segment は C の関数と異なり戻り値を持たない。
|
|
|
148 Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使うことで宣言できる。
|
|
|
149
|
|
|
150 Code Segment から Code Segment への移動は goto の後に Code Segment 名と引数を並べた記述するという構文を用いて行う。
|
|
|
151 この goto による処理の遷移を継続と呼ぶ。 図\ref{fig:cbc_goto} は Code Segment 間の継続関係を表している。
|
|
|
152
|
|
|
153 C では関数呼び出しを行うたび、関数の引数の値がスタックに積まれていくが、Code Segment では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要が無い。
|
|
|
154 このようなスタックに値を積まない継続、つまり呼び出し元の環境を持たない継続を軽量継続と呼ぶ。
|
|
|
155 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
|
|
|
156
|
|
|
157 \begin{figure}[ht]
|
|
|
158 \begin{center}
|
|
|
159 \includegraphics[width=70mm]{./pic/cbc_goto.pdf}
|
|
|
160 \end{center}
|
|
|
161 \caption{gotoによる Code Segment 間の接続}
|
|
|
162 \label{fig:cbc_goto}
|
|
|
163 \end{figure}
|
|
7
|
164
|
|
2
|
165 \section{CbC での Gears OS の構文サポート}
|
|
|
166 CbC は Gears OS の構文のサポートを行う。
|
|
|
167
|
|
|
168 Gesrs OS では Contextという接続可能な Data Gear のリストからデータを取り出して処理行う。
|
|
|
169 しかし、 Context を直接扱うのはセキュリティ上好ましくない。
|
|
|
170 そこで Gears OS では Context から必要なデータを取り出して Code Gear に接続する stub を定義する。
|
|
|
171 stub は Code Gear から推論することが可能のため、 CbC は自動的に stub の生成を行う。
|
|
|
172
|
|
7
|
173 また、Code Gear の遷移には Meta computation を行うために Meta Code Gear を挟む。
|
|
2
|
174 CbC では Meta Code Gear への接続も自動的に行うようにする。
|
|
|
175
|
|
3
|
176 \section{Gears OS の構成}
|
|
|
177 Gears OS は以下の要素で構成される。
|
|
|
178
|
|
|
179 \begin{itemize}
|
|
|
180 \item Context
|
|
|
181 \item TaskQueue
|
|
|
182 \item TaskManager
|
|
|
183 \item Persistent Data Tree
|
|
|
184 \item Worker
|
|
|
185 \end{itemize}
|
|
|
186
|
|
|
187 図\ref{fig:gearsos} に Gears OS の構成図を示す。
|
|
|
188
|
|
|
189 \begin{figure}[ht]
|
|
|
190 \begin{center}
|
|
6
|
191 \includegraphics[width=70mm]{./pic/gearsos.pdf}
|
|
3
|
192 \end{center}
|
|
|
193 \caption{gotoによる Code Segment 間の接続}
|
|
|
194 \label{fig:gearsos}
|
|
|
195 \end{figure}
|
|
|
196
|
|
|
197 \section{Context}
|
|
6
|
198 Context は接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、 Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。
|
|
|
199 Gears OS では必要な Code/Data Gear に参照したい場合、このContext を通す必要がある。
|
|
|
200
|
|
|
201 メインとなる Context と Worker 用 Context があり、 TaskQueue と Persistent Data Tree は共有される。
|
|
|
202 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することは出来ない。
|
|
|
203 Worker 間の相互作用は Persistent Data Tree への読み書きのみで行う。
|
|
|
204
|
|
3
|
205 \section{TaskQueue}
|
|
6
|
206 Gears OS における Task Queue は Synchronized Queue で実現される。
|
|
|
207 メインとなる Context と Worker 用 の Context で共有され、 Worker が TaskQueue から Task を取得し、実行することで並列処理を行う。
|
|
|
208
|
|
|
209 Gears OS の Queue は Queue を表す Data Gear と List を表現する Element という名前の Data Gear を組み合わせて表現する。
|
|
|
210 Queue を表す Data Gear には List 構造の先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。
|
|
|
211 Element を表す Data Gear は、Task を示す task、 次の Element を示す next が格納される。
|
|
|
212
|
|
|
213 Queue に対して操作を行う場合、 Queue 自体の Data Gear を書き換える。
|
|
|
214 Task を 挿入する場合、 新しく Element を生成し、 Queue の last から List 構造の末尾に新しい Element を追加し、 Queue の last を書き換える。
|
|
|
215 Task を 取得する場合、 Queue の first から List 構造を最初の要素を取り出し、 取り出した要素の次の要素の参照を Queue の first に書き込む。
|
|
|
216
|
|
|
217 Gears OS の TaskQueue はマルチスレッドでの操作を想定しているため、データの一貫性を保証する必要がある。
|
|
|
218 そのため、データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行っている。
|
|
|
219 CAS はデータの比較・置換をアトミックに行う命令である。
|
|
|
220 メモリからデータの読みだし、変更、メモリへのデータの書き出しという一連の処理を CAS を利用することで処理の間に他のスレッドがメモリに変更を加えないことを保証することができる。
|
|
|
221 CAS に失敗した場合は置換を行わず、再びデータの呼び出しから始める。
|
|
|
222
|
|
|
223 Code \ref{src:sync_enqueue} に CAS を使用した Task 挿入を示している。
|
|
|
224 Code \ref{src:sync_enqueue} は 2つのCode Gear を定義しており、 putQueue3 は要素がある場合、 putQueue4 は要素がない場合の Task 挿入を示している。
|
|
|
225
|
|
|
226 \lstinputlisting[label=src:sync_enqueue, caption=Enqueue]{./src/sync_enqueue.c}
|
|
|
227
|
|
|
228 \section{Persistent Data Tree}
|
|
|
229 Gears OS は Persistent Data Gear の管理に木構造を用いる。
|
|
|
230 この木構造は非破壊的で構成される。
|
|
|
231 非破壊木構造とは図\ref{fig:persistent_data_tree}のように一度構築した木構造を破壊すること無く新しい木構造を構築することで、木構造を編集する方法である。
|
|
|
232 非破壊木構造は木構造を書き換えることなく編集を行うため、読み書きを平行して行うことが可能である。
|
|
|
233
|
|
|
234 \begin{figure}[ht]
|
|
|
235 \begin{center}
|
|
|
236 \includegraphics[width=80mm]{./pic/persistent_date_tree.pdf}
|
|
|
237 \end{center}
|
|
|
238 \caption{木構造の非破壊的編集}
|
|
|
239 \label{fig:persistent_data_tree}
|
|
|
240 \end{figure}
|
|
|
241
|
|
|
242 Gears OS では Data Tree として木構造を利用する。
|
|
|
243 その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。
|
|
|
244 最悪なケースでは線形リストになり、計算量が O(n) となる。
|
|
|
245
|
|
|
246 そのため、挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。
|
|
|
247 Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。
|
|
|
248
|
|
|
249 \begin{itemize}
|
|
7
|
250 \item 各ノードは赤または黒の色を持つ。
|
|
|
251 \item ルートの色は黒である。
|
|
|
252 \item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。
|
|
|
253 \item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。
|
|
6
|
254 \end{itemize}
|
|
|
255
|
|
|
256 これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。
|
|
|
257
|
|
|
258 \section{Worker}
|
|
|
259 Worker は TaskQueue から Task を取得し、実行する。
|
|
|
260 Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。
|
|
|
261 実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。
|
|
|
262
|
|
|
263 各 Worker は個別の Context を参照しており、 メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。
|
|
|
264 ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。
|
|
|
265
|
|
|
266 Worker が Task の取得を行う Code Gear を Code \ref{src:sync_dequeue} に示す。
|
|
|
267 Task Queue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。
|
|
|
268
|
|
|
269 \lstinputlisting[label=src:sync_dequeue, caption=GetTask]{./src/sync_dequeue.c}
|
|
|
270
|
|
|
271 Worker から取得された Task の Code Gear は並列実行される。
|
|
|
272 並列実行される Code Gear と言っても他の Code Gear と同じである。
|
|
|
273 これは Gears OS 自体が Code Gear によって構成されていることに起因する。
|
|
|
274 つまり、 Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないとき、全て並列に実行することができる。
|
|
|
275
|
|
3
|
276 \section{TaskManager}
|
|
6
|
277 Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。
|
|
7
|
278 Task には Input/Output Data Gear の情報が格納されている。
|
|
|
279 Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。
|
|
|
280 Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。
|
|
|
281 この Input と Output の関係が依存関係となる。
|
|
|
282 TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。
|
|
6
|
283
|
|
|
284 \section{評価}
|
|
|
285 Gears OS の評価として依存関係のない例題の並列実行を行った。
|
|
|
286
|
|
|
287 今回使用した例題は Twice という整数配列を2倍にする例題である。
|
|
|
288 Code \ref{src:twice} に Twice の処理を行う Code Gear を示す。
|
|
|
289
|
|
|
290 \lstinputlisting[label=src:twice, caption=Twice]{./src/twice.c}
|
|
|
291
|
|
|
292 以下に今回の処理の流れを示す。
|
|
|
293
|
|
|
294 \begin{itemize}
|
|
7
|
295 \item 配列サイズを元に index, alignment, 配列へのポインタを持つ Data Gear に分割。
|
|
|
296 \item Data Gear を Persistent Data Tree に挿入。
|
|
|
297 \item 実行する Code Gear(Twice) と実行に必要な Data Gear への key を持つ Task を生成。
|
|
|
298 \item 生成した Task を TaskQueue に挿入。
|
|
|
299 \item Worker の起動。
|
|
|
300 \item Worker が TaskQueue から Task を取得。
|
|
|
301 \item 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得。
|
|
|
302 \item 並列の処理される Code Gear(Twice) を実行。
|
|
6
|
303 \end{itemize}
|
|
|
304
|
|
|
305 要素数$2^17$*1000 のデータを640個の Task に分割し、コア数を変更して測定を行った結果を表\ref{table:result}、図\ref{fig:result}に示す。
|
|
|
306
|
|
|
307 \begin{table}[ht]
|
|
7
|
308 \begin{center}
|
|
|
309 \small
|
|
|
310 \begin{tabular}[htpb]{|c||c|c|c|}
|
|
|
311 \hline
|
|
|
312 Processor & Time(ms) \\
|
|
|
313 \hline
|
|
|
314 \hline
|
|
|
315 1 CPU & 1315 \\
|
|
|
316 \hline
|
|
|
317 2 CPUs & 689 \\
|
|
|
318 \hline
|
|
|
319 4 CPUs & 366 \\
|
|
|
320 \hline
|
|
|
321 8 CPUs & 189 \\
|
|
|
322 \hline
|
|
|
323 12 CPUs & 111 \\
|
|
|
324 \hline
|
|
|
325 \end{tabular}
|
|
|
326 \caption{要素数$2^{17}$*1000 のデータに対する Twice}
|
|
|
327 \label{table:result}
|
|
|
328 \end{center}
|
|
6
|
329 \end{table}
|
|
|
330
|
|
|
331 \begin{figure}[ht]
|
|
7
|
332 \begin{center}
|
|
|
333 \includegraphics[width=70mm]{pic/twice_640.pdf}
|
|
|
334 \end{center}
|
|
|
335 \caption{要素数$2^{17}$*1000 のデータに対する Twice}
|
|
|
336 \label{fig:result}
|
|
6
|
337 \end{figure}
|
|
|
338
|
|
|
339 結果から、 1 CPU と 12 CPU で約 11.8 倍の速度向上が見られた。
|
|
|
340 しかし、 タスクの粒度が小さすぎると CAS の失敗が多くなり、性能がでないことがある。
|
|
|
341 Code Gear には実行時間を予想可能なものにするという特徴があるため、タスクが最適な粒度なのかを検査する機能が必要になると考えられる。
|
|
|
342
|
|
0
|
343 \section{まとめ}
|
|
7
|
344 本論文では Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った。
|
|
0
|
345
|
|
|
346 \nocite{*}
|
|
|
347 \bibliographystyle{ipsjunsrt}
|
|
|
348 \bibliography{sigos}
|
|
|
349
|
|
|
350 \end{document}
|
