Mercurial > hg > Papers > 2015 > kkb-sigos

comparison paper/sigos.tex @ 11:37c481e6d758

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 22:29:16 +0900
parents 92f7c78d8d6c
children 6b32ea521f5b
comparison
equal deleted inserted replaced
10:92f7c78d8d6c 11:37c481e6d758
80 80
81 % 英文概要 81 % 英文概要
82 \begin{eabstract} 82 \begin{eabstract}
83 We are developing parallel framework using a Code/Data Gear. 83 We are developing parallel framework using a Code/Data Gear.
84 Code/Data Gear are unit of processing and data. 84 Code/Data Gear are unit of processing and data.
85 We obtains meta function for parallel execution, based on a Monad in Functional Language. 85 Meta function for parallel execution based on a Monad in Functional Language is used in Geas OS.
86 Meta Code/Data Gear attached to Code/Data Gear with designed a Gears OS. 86 A Meta Code/Data Gear attached to a Code/Data Gear as a Monad.
87 Meta Code Gear is executed after a Code Gear, which perform a Meta Computation.
88 Meta Computation performs Network Management, Memory Management and more. 87 Meta Computation performs Network Management, Memory Management and more.
89 We designs basic functions and evaluate it using CbC. 88 We show same implemetation of Gears OS using CbC(Continuation based C).
90 \end{eabstract} 89 \end{eabstract}
91 90
92 % 表題などの出力 91 % 表題などの出力
93 \maketitle 92 \maketitle
94 93
95 % 本文はここから始まる 94 % 本文はここから始まる
96 95
97 % Introduce 96 % Introduce
98 \section{Cerium と Alice} 97 \section{Cerium と Alice}
99 本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なっていた。 98 本研究室では並列プログラミングフレームワーク Cerium\cite{cerium} と分散ネットフレームワーク Alice\cite{alice} の開発を行なってきた。
100 99
101 Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。 100 Cerium と Alice を開発して得られた知見から Inherent Parallel, Distributed Open Computation をキーワードとして並列分散フレームワーク Gears OS の設計・開発を行う。
102 101
103 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。 102 Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を実現する。
104 依存関係はプログラマ自身が意識して記述する必要がある。 103 依存関係はプログラマ自身が意識して記述する必要がある。
115 Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。 114 Code Segment 使用する Input Data Segment, Output Data Segment を指定することで処理とデータの関係を記述する。
116 Alice は Java で実装されており、実行速度が遅いという問題がある。 115 Alice は Java で実装されており、実行速度が遅いという問題がある。
117 また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。 116 また、Data Segment にアクセスする API のシンタックスが特殊で Alice を用いてプログラムを作成するためには慣れが必要になる。
118 117
119 \section{Gears OS} 118 \section{Gears OS}
120 Cerium と Alice から得られた知見から並列実行には Code の単位だけでなく、Data の単位も必要であることがわかった。 119 Cerium と Alice の例題から Code の単位だけでなく、Data の単位も必要であることがわかった。
121 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。 120 Gears OS では Gear という単位を用いてプログラムを Code Gear, Data Gear に細かく分割する。
122 Code Gear は Input Data Gear から Output Data Gear を生成する。 121 Code Gear は Input Data Gear から Output Data Gear を生成する。
123 Input と Output の関係から Code Gear 同士の依存関係を解決し、並列実行するフレームワークの開発を行う。 122 Input と Output の関係から Code Gear 同士の依存関係を解決し、並列実行するフレームワークの開発を行う。
124 Code Gear はそれに接続された Data Gear のみを扱う。 123 Code Gear はそれに接続された Data Gear のみを扱う。
125 Code/Data Gear 同士の関係は Meta Code/Data Gear によって表現される。 124 Code/Data Gear 同士の関係は Meta Code/Data Gear によって表現される。
126 この Meta Code/Data Gear を用いることで機能やデータ自体を拡張することができる。 125 この Meta Code/Data Gear を用いることで機能やデータ自体を拡張することができる。
127 126
128 Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。 127 Cerium は初め Cell 向けのフレームワークとして設計されたという経緯からプロセッサ毎の実行機構が異なる。
129 Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。 128 Gears OS では Many Core CPU, GPU をはじめとする様々なプロセッサを同等な実行機構でサポートする。
130 129
131 Gears OS は本研究室で開発している CbC(Continuation based C)\cite{cbc} で実装する。 130 本研究室で開発している CbC(Continuation based C)\cite{cbc} を用いて、Gears OS を実装する。
132 CbC はプログラムを Code Segment, Data Segment という単位で記述する。 131 CbC はプログラムを Code Segment, Data Segment という単位で記述する。
133 CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。 132 CbC において Code Segment 間の処理の移動は function call ではなく、goto を用いた軽量継続を用いる。
134 CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる。 133 CbC のコンパイルには LLVM をバックエンドとしたコンパイラ\cite{cbc-llvm}を用いる。
135 134
136 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。 135 従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
143 これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。 142 これにより、並列実行時のデッドロックの検出などを行うことでプログラムの信頼性を確保する。
144 Model Checking も Meta Code/Data Gear を用いて実現する。 143 Model Checking も Meta Code/Data Gear を用いて実現する。
145 144
146 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。 145 Gears OS は Many Core CPU, GPU といった並列実行環境に合わせた設計・実装を行う。
147 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。 146 また、接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。
147 Gears OS の構成は図\ref{fig:arch}の通りである。
148
149 \begin{figure}[!h]
150 \centering
151 \includegraphics[width=70mm]{images/arch.pdf}
152 \caption{Gears OS の構成}
153 \label{fig:arch}
154 \end{figure}
148 155
149 % Theory 156 % Theory
150 \section{Monad とメタ計算} 157 \section{Monad とメタ計算}
151 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの 158 関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
152 がある。 159 がある。
292 \label{fig:list} 299 \label{fig:list}
293 \end{figure} 300 \end{figure}
294 301
295 \section{Synchronized Queue} 302 \section{Synchronized Queue}
296 Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。 303 Gears OS では List を表現する Code/Data Gear に CAS(Compare and Swap) を行う Meta Code/Data Gear を接続することで Synchronized Queue を実現する。
297 Synchronized Queue があれば並行制御を行うことが可能となり、Gears OS は Cerium と同等の機能を持つことになる。 304 Gears OS の機能は状態遷移図とクラスダイアグラムを組み合わせた図で表現する。
305 この図を GearBox と呼ぶことにする。
306 図\ref{fig:sync}は Synchronized Queue の GearBox である。
307 M:receiver/sender が CAS を行う Meta Code Gear となる。
308
309 \begin{figure}[!h]
310 \centering
311 \includegraphics[width=70mm]{images/synchronizedQueue.pdf}
312 \caption{Synchronized Queue}
313 \label{fig:sync}
314 \end{figure}
298 315
299 \section{比較} 316 \section{比較}
300 Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。 317 Cerium/Alice, OpenCL/CUDA, 従来の OS との比較を以下に示す。
301 318
302 \paragraph*{Cerium/Alice} 319 \paragraph*{Cerium/Alice}
304 Cerium とは異なり、Gears OS は処理とデータが分離している。 321 Cerium とは異なり、Gears OS は処理とデータが分離している。
305 Gears OS では分離したデータを Data Gear と呼称する。 322 Gears OS では分離したデータを Data Gear と呼称する。
306 これは Alice の Data Segment と同等のものである。 323 これは Alice の Data Segment と同等のものである。
307 Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。 324 Gears OS では Alice と同様に Code と Data の関係から依存関係を解決する。
308 325
309 Alice は Data Segment を MessagePack を利用して通信することで分散実行を実現する。 326 Alice は Data Segment を MessagePack\cite{msg} を利用して通信することで分散実行を実現する。
310 Gears OS 上での分散実行も Alice に沿って設計・実装する。 327 Gears OS 上での分散実行も Alice に沿って設計・実装する。
311 328
312 \paragraph*{OpenCL/CUDA} 329 \paragraph*{OpenCL/CUDA}
313 Code Gear は OpenCL/CUDA の kernel に相当する。 330 Code Gear は OpenCL/CUDA の kernel に相当する。
314 OpenCL/CUDA には Data Gear に相当する仕組みはない。 331 OpenCL/CUDA には Data Gear に相当する仕組みはない。