Mercurial > hg > Papers > 2015 > kkb-sigos

comparison paper/sigos.tex @ 9:12a7b1cb59fe

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 Wed, 06 May 2015 02:52:05 +0900
parents b02e6b40f470
children 92f7c78d8d6c
comparison
equal deleted inserted replaced
8:bb5fab31cf41 9:12a7b1cb59fe
35 \begin{document} 35 \begin{document}
36 36
37 % 和文表題 37 % 和文表題
38 \title{Monad に基づくメタ計算を基本とする Gears OS の設計} 38 \title{Monad に基づくメタ計算を基本とする Gears OS の設計}
39 % 英文表題 39 % 英文表題
40 \etitle{} 40 \etitle{Design of Gears OS with Meta Computation based on Monad}
41 41
42 % 所属ラベルの定義 42 % 所属ラベルの定義
43 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.} 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.} 44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
45 45
52 河野 真治\affiref{2} 52 河野 真治\affiref{2}
53 } 53 }
54 54
55 % 英文著者名 55 % 英文著者名
56 \eauthor{ 56 \eauthor{
57 Shohei KOKUBO\affiref{1}\and 57 Shohei KOKUBO\affiref{1}
58 Tatsuki Iha\affiref{2}\and 58 \and
59 Tatsuki Iha\affiref{2}
60 \and
59 Shinji KONO\affiref{2} 61 Shinji KONO\affiref{2}
60 } 62 }
61 63
62 % 連絡先（投稿時に必要．製版用では無視される．） 64 % 連絡先（投稿時に必要．製版用では無視される．）
63 \contact{小久保 翔平\\ 65 \contact{小久保 翔平\\
76 本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。 78 本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
77 \end{abstract} 79 \end{abstract}
78 80
79 % 英文概要 81 % 英文概要
80 \begin{eabstract} 82 \begin{eabstract}
83 We are developing parallel framework using Code Gear, Data Gear.
84 We obtain meta function for parallel execution, based on Monad in Functional Language.
85 Meta Code Gear and Meta Data Gear attached to Code Gear and Data Gear with designed Gears OS.
86 Meta Code Gear is executed after Code Gear, this is Meta Computation.
87 Meta Computation performs Network Management, Memory Management and more.
88 We implement basic functions using CbC and evaluate it.
81 \end{eabstract} 89 \end{eabstract}
82 90
83 % 表題などの出力 91 % 表題などの出力
84 \maketitle 92 \maketitle
85 93
86 % 本文はここから始まる 94 % 本文はここから始まる
87 95
88 % Introduce 96 % Introduce
97 \section{Cerium と Alice}
98 本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なっている。
99
100 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
101 依存関係はプログラマ自身が意識して記述する必要がある。
102 Task の種類が増えると記述が煩雑になり、プログラマの負担が大きくなる。
103 依存関係の記述がデータの依存関係と無関係という問題もある。
104 また、Task の取り扱うデータには型情報がなく、Task とデータも分離されていない。
105 Cerium は C++ で実装されている。
106 Cell\cite{cell}, Many Core CPU, GPU といった様々なプロセッサをサポートしている。
107 高速で動作するが、非常に複雑な実装となっており機能の追加やデバッグが難しい現状である。
108
109 Alice は本研究室で開発を行なっている分散管理フレームワークである。
110 Alice では処理の単位である Code Segment, データの単位である Data Segment を用いてプログラムを記述する。
111 Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。
112 Alice は Java で実装されている。
113 ガベージコレクション(GC)が実行されると性能が低下するといった問題がある。
114 また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。
115
116 Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
117
89 \section{Gears OS} 118 \section{Gears OS}
90 並列実行は Code の並列実行だけでなく、Data の単位が重要である。 119 Cerium と Alice から並列実行には Code の並列実行だけでなく、Data の単位が重要であることが明らかとなった。
91 本研究では Code Gear, Data Gear という単位で細かく分割し、依存関係を記述することで並列実行するフレームワーク Gears OS の開発を行なっている。 120 本研究では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割し、Code と Data の関係から Code Gear 同士の依存関係を解決して並列実行するフレームワーク Gears OS の開発を行なっている。
92 Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能である。 121 Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能となるように設計する。
122 Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。
123 Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。
124 Gears OS は本研究室で開発している CbC(Continuation based C)\cite{cbc} で実装する。
125 CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる
93 126
94 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。 127 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
95 Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。 128 Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。
96 129
97 Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。 130 Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。
98 Model Chaecking によって、並列実行時のデッドロックの検出などを行う。 131 Model Chaecking によって、並列実行時のデッドロックの検出などを行う。
99 これにより、プログラムの信頼性を保証する。 132 これにより、プログラムの信頼性を保証する。
100 133
101 Gears OS は接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。 134 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
135 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
102 136
103 % Theory 137 % Theory
104 \section{Monad とメタ計算} 138 \section{Monad とメタ計算}
105 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの 139 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
106 がある。 140 がある。
107 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副 141 メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
108 作用、メモリ管理などがある。 142 作用、メモリ管理などがある。
109 メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{Monad} 143 メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{monad}
110 されている。 144 されている。
111 Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。 145 Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。
112 146
113 Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの 147 Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの
114 に必要な情報を格納している。 148 に必要な情報を格納している。
134 % Meta Data Gear 168 % Meta Data Gear
135 \section{Code Gear と Data Gear} 169 \section{Code Gear と Data Gear}
136 Gears OS ではプログラムの実行単位として様々な Gear を使う。 170 Gears OS ではプログラムの実行単位として様々な Gear を使う。
137 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。 171 Gear が平行実行の単位、データ分割、Gear 間の接続などになる。
138 172
139 Code Gear はプログラムの実行コードそのものであり、CUDA 173 Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda}
140 の kernel に相当する。 174 の kernel に相当する。
141 Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書 175 Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
142 き込む。 176 き込む。
143 Code Gear は接続された Data Gear 以外には触らない。 177 Code Gear は接続された Data Gear 以外には触らない。
144 Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。 178 Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。
239 \includegraphics[width=70mm]{images/List.pdf} 273 \includegraphics[width=70mm]{images/List.pdf}
240 \caption{List の表現} 274 \caption{List の表現}
241 \label{fig:list} 275 \label{fig:list}
242 \end{figure} 276 \end{figure}
243 277
244 \section{} 278 \section{比較}
279 Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。
280
281 \paragraph*{Cerium/Alice}
282 Gears OS の Code Gear は Cerium の Task, Context は HTask に相当する。
283 Cerium とは異なり、Gears OS は処理とデータが分離している。
284 Gears OS では分離したデータを Data Gear と呼称する。
285 これは Alice の Data Segment と同等のものである。
286 Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。
287
288 \paragraph*{OpenCL/CUDA}
289 Code Gear は OpenCL/CUDA の kernel に相当する。
290 OpenCL/CUDA には Data Gear に相当する仕組みはない。
291 接続された複数の Code Gear は接続された順番通りに実行される。
292 これは、OpenCL の CommandQueue, CUDA の Stream と同等のものである。
293 OpenCL/CUDA では kernel の依存関係を複雑に記述する必要があるが、Gears OS では Code と Data の関係から自動的に依存関係を解決する。
294
295 \paragraph*{従来の OS}
296 従来の OS が行なってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code Gear, Meta Data Gear を用いて行う。
297 このメタ計算は Monad に基づいて実現される。
298
299 \section{まとめ}
300 Gears OS は Inherent Parallel をキーワードとして、Gears OS 上で実行されるプログラムが自動的に並列で処理されるように設計した。
301 Gear を他の Gear に接続することで機能およびデータの拡張を行える柔軟性を持つ。
302 Meta な機能や並行制御を関数型言語における Monad に基づいて実現する。
303 また、機能として Model Checking を持ち、Gears OS 上で実行されるプログラムの信頼性を保証する。
304 本論文では必要な機能の一部である Context, Allocator, List, Non-Destructive Red-Black Tree を CbC を用いて実装した。
305 今後は、Synchronized Queue, Woker を実装する予定である。
306 これにより、Cerium と同等の例題を動かすことが可能となる。
307 例題としては Bitonic Sort, Word Count を予定している。
308 例題が動くことを確認し次第、Gears OS の測定・評価を行う。
309
245 \nocite{*} 310 \nocite{*}
246 \bibliographystyle{ipsjunsrt} 311 \bibliographystyle{ipsjunsrt}
247 \bibliography{sigos} 312 \bibliography{sigos}
248 313
249 \end{document} 314 \end{document}