Mercurial > hg > Papers > 2016 > kkb-master

annotate paper/comparison.tex @ 28:85d3468efecc default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 25 Feb 2016 16:40:05 +0900
parents 958634b9fa32
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{比較}
14
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
2 本章では今回設計・実装した Gears OS と既存の並列フレームワークとの比較を行う。
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 また、Gears OS は以下のような性質を有している。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 \begin{itemize}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 \item リソース管理 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 Context 毎に異なるメモリ空間を持ち、それを管理する。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Meta Code Gear, Meta Data Gear を用いてネットワーク管理、並行制御等を行う。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 \item 処理の効率化 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 依存関係のない Code Gear は並列実行することが可能である。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 また、Code Gear 自体が処理の最小単位となっており Code Gear を利用してプログラムを記述するとプログラム全体の並列度を高めることに繋がる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \item プロセッサ利用の抽象化 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 Multi Core CPU, GPU を同等の実行機構で実行可能である。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \end{itemize}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 これらの性質を有する Gears OS はオペレーティングシステムであると言えるので既存の OS との比較も行う。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \section{Cerium}
28
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
19 \begin{itemize}
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
20 \item 依存関係 \\
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
21 Cerium では Task 間で依存関係を設定する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
22 Task の途中でデータが破損しても完了を TaskManager に通知し、依存関係を解決して次の Task が実行される。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
23 これではデータの正しさを保証することができない。
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
28
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
25 Gears OS では Task に Input/Output Data Gear を設定することで Input と Output の関係から依存関係を決定する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
26 TaskManager は Persistent Data Tree を監視し、必要な Data Gear が揃っていることを確認すると依存関係を解決する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
27 \item データの型情報 \\
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
28 Cerium では Task にデータを引き渡すとき汎用ポインタを用いる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
29 このときデータの型情報が落ちるので Task の組み合わせが型的に安全なのか保証することができない。
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
28
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
31 Gears OS では型情報を持つ分割されたデータとして Data Gear を定義し、Data Gear 単位でデータを Task に引き渡す。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
32 Data Gear を型シグネチャとして Task の組み合わせが正しいことを保証する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
33 \item Allocator \\
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
34 Cerium では Thread 間で Allocator を共有している。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
35 ある Thread がメモリ確保を行うとその間、他の Thread はメモリを確保することができず並列度が低下する。
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
28
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
37 Gears OS では Thraed ごとに Context を割り当てる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
38 Context は独立したメモリ空間を持つので他の Thread と干渉することないメモリの確保を行うことができる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
39 \item 並列処理との相性 \\
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
40 Cerium はオブジェクト指向言語である C++ で実装されている。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
41 オブジェクト指向は保守性と再利用性を高めるためにカプセル化とポリモフィズムを重視する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
42 オブジェクトの状態によって振る舞いが変わるため参照透過な処理でなくなり並列処理との相性が悪い。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
43
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
44 Gears OS は本研究で開発している CbC を用いて実装する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
45 CbC は Code Segment という単位でプログラムを記述する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
46 Code Segment はスタックに値を積まない軽量継続を用いて他の Code Segment に遷移する。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
47 この軽量継続により並列化、ループ制御などを意識した最適化がソースコードレベルで行うことができる。
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
48 \end{itemize}
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 \section{OpenCL/CUDA}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 OpenCL/CUDA では並列処理に用いる関数を kernel として定義する。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 OpenCL では CommandQueue, CUDA では Stream という命令キューに命令を発行することで GPU を利用することができる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 命令キューは発行された順番通りに命令が実行されることが保証されている。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 複数の命令キューを準備して、各命令キューに命令を発行することで命令を並列に実行することができる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 命令キュー単位で依存関係を設定することができる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 つまり、命令キューに入っている最後の命令次第でデータを待っているのか kernel の実行を待っているのか変わるので依存関係の記述が複雑になる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 データは kernel の引数の定義に型変換され渡される。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 データ転送の際には型情報が落として渡す必要があり、型を意識したプログラミングが必要になる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 一方、Gears OS ではデータによって依存関係が決定する。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 また、データを Data Segment という単位で分割して管理しており型情報を保ったままデータの受け渡しを行うことができる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 \section{OpenMP}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 OpenMP ではループ制御構文の前にアノテーションを付ける(ソースコード:\ref{openmp})ことでコンパイラが解釈し、スレッド処理を行うように変換して並列処理を行う。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 \lstinputlisting[label=openmp, caption=OpenMP]{src/openmp.c}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 他の並列化手法に比べて既存のコードに対する変更が少なくて済む。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 しかし、この方法ではプログラム全体の並列度が上がらずアムダールの法則により性能向上が頭打ちになる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 一方、Gears OS では初めから Code Gear, Data Gear という単位でプログラムを分割して記述するのでプログラム全体の並列度を高めることができる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 \section{従来の OS}
15
94c9c506bba9 revison
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
74 従来の OS が行ってきたネットワーク管理、メモリ管理、平行制御などのメタな部分を Gears OS では Meta Code/Data Gear として定義する。
94c9c506bba9 revison
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
75 通常の Code Gear から必要な制御を推論し、Meta Code Gear を接続することで従来の OS が行ってきた制御を提供する。
94c9c506bba9 revison
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
76 このメタ計算は関数型言語で用いられる Monad に基づいて実現する。