|
0
|
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
|
|
2
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
0
|
3 \usepackage{picins}
|
|
|
4 \usepackage{fancyhdr}
|
|
|
5 %\pagestyle{fancy}
|
|
|
6 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
|
|
|
7 \rhead{}
|
|
|
8 \cfoot{}
|
|
|
9
|
|
|
10 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
|
|
|
11 \setlength{\headheight}{0mm}
|
|
|
12 \setlength{\headsep}{5mm}
|
|
|
13 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
|
|
|
14 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
|
|
|
15 \setlength{\textwidth}{181mm}
|
|
|
16 \setlength{\textheight}{261mm}
|
|
|
17 \setlength{\footskip}{0mm}
|
|
|
18 \pagestyle{empty}
|
|
|
19
|
|
4
|
20 \input{dummy.tex}
|
|
0
|
21 \begin{document}
|
|
4
|
22 \title{Code Gear, Data Gearに基づくGears OS の設計}
|
|
2
|
23 \author{125716B 氏名 {伊波}{立樹} 指導教員 : 河野 真治}
|
|
0
|
24 \date{}
|
|
|
25 \maketitle
|
|
|
26 \thispagestyle{fancy}
|
|
|
27
|
|
1
|
28 \section{先行研究}
|
|
|
29 本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なってきた。
|
|
|
30
|
|
|
31 CeriumではTaskと呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
|
|
|
32 依存関係はプログラマ自身が意識して記述する必要があり、
|
|
|
33 Taskの種類が増えると記述が複雑になり、 負担が大きくなる。
|
|
|
34 Taskの依存関係がデータの依存関係を正しく保証しない場合があるという問題がある。
|
|
|
35 また、Taskの取り扱うデータに型情報がないため、 汎用ポインタをキャストして利用するしかなく、型の検査が行われていない。
|
|
|
36 Cerium は C++で実装されているが、オブジェクトと並列処理が直接対応していないのでオブジェクト指向で記述する利点が少ない。
|
|
|
37
|
|
|
38 Alice では処理の単位である Code Segment、 データの単位である Data Segment を用いてプログラムを記述\cite{segment}する。
|
|
|
39 Code Segment は使用する Input Data Segment, Output Data Segment を指定することで処理とデータの依存関係を解決する。
|
|
|
40 Alice は Javaで実装されており、実効速度が遅いという問題がある。
|
|
|
41 また、 Data SegmentをアクセスするAPIのシンタックスが特殊なため、Aliceを用いてプログラムを作成するには慣れが必要になる。
|
|
|
42
|
|
|
43 \section{Gears OS}
|
|
|
44 Cerium と Alice を開発して得られた知見から、並列実行をサポートするだけでなく、信頼性も確保したGears OS の設計・開発を行う。
|
|
|
45
|
|
|
46 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
|
|
|
47 Code Gear は Input Data Gear から Output Data Gearを生成する。
|
|
|
48 Input と Outputの関係から Code Gear 同士の依存関係を解決し、並列実行を行う。
|
|
|
49
|
|
|
50 Ceriumは初め、Cell\cite{cell} 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行形式が異なる。
|
|
|
51 Gears OSでは Many Core CPU、GPUをはじめとする様々なプロセッサを同等な実行機構でサポートする。
|
|
|
52
|
|
|
53 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
|
|
|
54 Meta Computationは本論のComputationを支えるComputationのことである。
|
|
|
55 関数型言語では Meta Computation に Monad を用いる手法\cite{monad}がある。
|
|
|
56 Gears OS では、Meta Code/Data Gear を Monadとして定義し、Meta Computationを実現する。
|
|
|
57
|
|
|
58 Gears OS は並列実行をサポートするだけでなく、 信頼性も確保する。
|
|
|
59 そのために Gears OSを用いて作成されたプログラムに対する Model Checkingを行う機能\cite{model-check}を提供する。
|
|
|
60 並列プログラムに Model Checking を行うことでそのプログラムがとり得る状態を列挙する。
|
|
|
61 これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
|
|
|
62 Model Checking の実現には Meta Code/Data Gearを用いる。
|
|
0
|
63
|
|
3
|
64 本研究室で開発している CbC(Continuation based C)\cite{cbc-llvm} を用いて、Gears OS を実装する。
|
|
|
65 CbC はプログラムを Code Segment, Data Segment という単位で記述する。
|
|
|
66 CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。
|
|
|
67
|
|
1
|
68 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
|
|
|
69 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
|
|
|
70
|
|
|
71 \section{Code Gear と Data Gear}
|
|
|
72 Gears OS ではプログラムの実行単位として様々な Gear を使う。
|
|
|
73 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。
|
|
|
74
|
|
|
75 Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
|
|
|
76 の kernel に相当する。
|
|
2
|
77
|
|
|
78 Code Gear 処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書
|
|
|
79 き込む。また、接続された Data Gear 以外には参照を行わない。
|
|
|
80
|
|
1
|
81 Code Gear はfunction callではないので、呼び出し元に戻る概念はない。
|
|
|
82 その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。
|
|
|
83
|
|
|
84 Data Gear には、int や文字列などの Primitive Data Type が入る。
|
|
0
|
85
|
|
1
|
86 Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることに
|
|
|
87 ある。
|
|
|
88 これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。
|
|
|
89
|
|
|
90 Code Gear, Data Gear はポインタを直接には扱わない。
|
|
2
|
91 これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフローを防止する。
|
|
1
|
92
|
|
|
93 Code Gear, Data Gear はそれぞれ関係を持っている。
|
|
2
|
94 例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ Data Gear などである。
|
|
1
|
95 Gear の関連付けは Meta Gear を通して行う。
|
|
2
|
96 Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当する。
|
|
1
|
97 なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
|
|
|
98
|
|
|
99 \section{Context}
|
|
4
|
100 ある Code Gear から継続するときには、次に実行する Code Gear を名前で指定する。
|
|
2
|
101 Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
|
|
4
|
102 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。
|
|
2
|
103 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
|
|
|
104 この Meta Data Gear を Context と呼ぶことにする。
|
|
|
105 これは従来の OS の Process や Thread に対応する。
|
|
|
106
|
|
|
107 Context には以下のようなものが格納される。
|
|
|
108 \begin{itemize}
|
|
|
109 \item Code Gear の名前とポインタの対応表
|
|
|
110 \item Data Gear の Allocation 用の情報
|
|
|
111 \item Code Gear が参照する Data Gear へのポインタ
|
|
|
112 \item Data Gear に格納される Data Type の情報
|
|
|
113 \end{itemize}
|
|
|
114
|
|
1
|
115 \section{List}
|
|
2
|
116 通常 List は要素と次へのポインタを持つ構造体で表現される。
|
|
|
117 Gears OS の場合、Meta レベル以外でポインタは扱わないので図\ref{fig:list}のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。
|
|
|
118
|
|
|
119 \begin{figure}[ht]
|
|
|
120 \centering
|
|
|
121 \includegraphics[width=70mm]{pic/List.pdf}
|
|
|
122 \caption{List の表現}
|
|
|
123 \label{fig:list}
|
|
|
124 \end{figure}
|
|
1
|
125
|
|
|
126 \section{Synchronized Queue}
|
|
2
|
127 Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。
|
|
|
128 Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。
|
|
|
129 この図を GearBox と呼ぶことにする。
|
|
|
130 図\ref{fig:sync}は Synchronized Queue の GearBox である。
|
|
3
|
131 M:get/put が CAS を行う Meta Code Gear となる。
|
|
|
132 今回は CAS で実装しているが、接続する Meta Code Gear を変更することで通常のQueueやLockを使用したsynchronizedQueueなど仕様変更にも対応できる。
|
|
|
133
|
|
2
|
134 \begin{figure}[ht]
|
|
|
135 \centering
|
|
|
136 \includegraphics[width=70mm]{pic/synchronizedQueue.pdf}
|
|
|
137 \caption{Synchronized Queue}
|
|
|
138 \label{fig:sync}
|
|
|
139 \end{figure}
|
|
|
140
|
|
4
|
141
|
|
|
142 \section{今後の課題}
|
|
|
143 Gears OS の今後の目的はCeriumと同等の例題を動かすことである。
|
|
|
144 現在、必要な機能として Context、 Allocator、 List、 Non-Destructive Red-Black Tree、 Synchronized Queue を CbC を用いて実装しており、足りない機能としてはWorkerがある。
|
|
|
145 Workerの実装後、動かす例題としては Bitonic Sort、 Word Count を予定している。
|
|
|
146 例題の実装後、測定・評価を行う。
|
|
|
147
|
|
2
|
148 \begin{thebibliography}{10}
|
|
|
149 \bibitem{cerium}
|
|
|
150 宮國 渡，河野真治，神里 晃，杉山千秋：Cell 用の Fine-grain Task Manager
|
|
|
151 の実装，情報処理学会
|
|
|
152 システムソフトウェアとオペレーティング・システム研究会(OS) (2008).
|
|
|
153
|
|
|
154 \bibitem{alice}
|
|
|
155 赤嶺一樹，河野真治：DataSegment API
|
|
|
156 を用いた分散フレームワークの設計，日本ソフトウェア科学会第28回大会論文集
|
|
|
157 (2011).
|
|
|
158
|
|
|
159 \bibitem{segment}
|
|
|
160 河野真治，杉本 優：Code Segment と Data Segment
|
|
|
161 によるプログラミング手法，第54回プログラミング・シンポジウム (2013).
|
|
0
|
162
|
|
5
|
163 \bibitem{cell}
|
|
|
164 {Sony Corporation}: {Cell broadband engine architecture} (2005).
|
|
2
|
165
|
|
|
166 \bibitem{monad}
|
|
3
|
167 Moggi, E.: Computational lambda-calculus and monads, {\em Proceedings of the Fourth Annual Symposium on Logic in computer science} (1989).
|
|
2
|
168
|
|
|
169 \bibitem{model-check}
|
|
|
170 下地篤樹，河野真治：線形時相論理によるContinuation based
|
|
|
171 Cプログラムの検証，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
|
|
|
172 (2007).
|
|
|
173
|
|
5
|
174 \bibitem{cbc-llvm}
|
|
|
175 徳森海斗，河野真治：Continuation based C の LLVM/clang 3.5
|
|
|
176 上の実装について，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
|
|
|
177 (2014).
|
|
|
178
|
|
2
|
179 \bibitem{opencl}
|
|
3
|
180 {Aaftab Munshi, Khronos OpenCL Working Group}: {\em {The OpenCL Specification Version 1.0}} (2007).
|
|
2
|
181
|
|
|
182 \bibitem{cuda}
|
|
|
183 : {CUDA}, {https://developer.nvidia.com/category/zone/cuda-zone/}.
|
|
0
|
184
|
|
|
185 \end{thebibliography}
|
|
1
|
186 \end{document}
|
