Mercurial > hg > Papers > 2016 > kkb-master
diff paper/comparison.tex @ 16:958634b9fa32
make paper directory
author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 17 Feb 2016 16:59:46 +0900 |
parents | comparison.tex@94c9c506bba9 |
children | 85d3468efecc |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/comparison.tex Wed Feb 17 16:59:46 2016 +0900 @@ -0,0 +1,65 @@ +\chapter{比較} +本章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。 +また、Gears OS は以下のような性質を有している。 + +\begin{itemize} +\item リソース管理 \\ + Context 毎に異なるメモリ空間を持ち、それを管理する。 + Meta Code Gear, Meta Data Gear を用いてネットワーク管理、並行制御等を行う。 +\item 処理の効率化 \\ + 依存関係のない Code Gear は並列実行することが可能である。 + また、Code Gear 自体が処理の最小単位となっており Code Gear を利用してプログラムを記述するとプログラム全体の並列度を高めることに繋がる。 +\item プロセッサ利用の抽象化 \\ + Multi Core CPU, GPU を同等の実行機構で実行可能である。 +\end{itemize} + +これらの性質を有する Gears OS はオペレーティングシステムであると言えるので既存の OS との比較も行う。 + +\section{Cerium} +Cerium ではサブルーチンまたは関数を Task の単位としてプログラムを分割する。 +Task には依存関係のある Task を設定することができ、TaskManager が依存関係を解決することで並列処理を実現している。 +実行に必要なデータのアドレスを Task の生成時に設定することで Task はデータにアクセスすることが可能になる。 +データは汎用ポインタとして渡されるので Task 側で型変換して扱うことになる。 +ここで問題となるのが Task 間だけにしか依存関係がないことと Task 実行時にデータの型情報がないことである。 + +本来 Task は必要なデータが揃ったときに実行されるべきものである。 +不正なデータが渡された場合、実行せずに不正なデータがであることを実行者に伝えることが望ましい。 +Cerium では Task の終了のみに着目して依存関係を解決するので途中で不正なデータになっても処理を続けてしまい不正な処理を特定することが難しい。 + +複雑なデータ構造を持つ場合、間違った型変換でデータの構造を破壊する可能性がある。 +型システムは正しい型に対して正しい処理が行われることを前提にしてプログラムの正しさを保証する。 +型情報がない Cerium では型システムによる安全性を保証できず、型に基づくバグが入り込む可能性がある。 + +Gears OS では Code Gear, Data Gear という単位でプログラムを分割する。 +Code Gear は処理の単位、Data Gear はデータそのものである。 +Code Gear には Input/Output Data Gear が設定されており、Input と Output の関係が Code Gear 間の依存関係となる。 +Gears OS の TaskManager は Data Gear が格納されている Persistent Data Tree を監視して依存関係を解決する。 +Data Gear は Context に構造体として定義されており、型情報を持つ。 + +\section{OpenCL/CUDA} +OpenCL/CUDA では並列処理に用いる関数を kernel として定義する。 +OpenCL では CommandQueue, CUDA では Stream という命令キューに命令を発行することで GPU を利用することができる。 +命令キューは発行された順番通りに命令が実行されることが保証されている。 +複数の命令キューを準備して、各命令キューに命令を発行することで命令を並列に実行することができる。 +命令キュー単位で依存関係を設定することができる。 +つまり、命令キューに入っている最後の命令次第でデータを待っているのか kernel の実行を待っているのか変わるので依存関係の記述が複雑になる。 +データは kernel の引数の定義に型変換され渡される。 +データ転送の際には型情報が落として渡す必要があり、型を意識したプログラミングが必要になる。 + +一方、Gears OS ではデータによって依存関係が決定する。 +また、データを Data Segment という単位で分割して管理しており型情報を保ったままデータの受け渡しを行うことができる。 + +\section{OpenMP} +OpenMP ではループ制御構文の前にアノテーションを付ける(ソースコード:\ref{openmp})ことでコンパイラが解釈し、スレッド処理を行うように変換して並列処理を行う。 + +\lstinputlisting[label=openmp, caption=OpenMP]{src/openmp.c} + +他の並列化手法に比べて既存のコードに対する変更が少なくて済む。 +しかし、この方法ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになる。 + +一方、Gears OS では初めから Code Gear, Data Gear という単位でプログラムを分割して記述するのでプログラム全体の並列度を高めることができる。 + +\section{従来の OS} +従来の OS が行ってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code/Data Gear として定義する。 +通常の Code Gear から必要な制御を推論し、Meta Code Gear を接続することで従来の OS が行ってきた制御を提供する。 +このメタ計算は関数型言語で用いられる Monad に基づいて実現する。