Mercurial > hg > Papers > 2016 > kkb-master

annotate paper/conclusion.tex @ 16:958634b9fa32

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
make paper directory
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2016 16:59:46 +0900
parents conclusion.tex@205805e6a6d8
children 4dcfec1bf1e7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
14
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{結論}
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 先行研究である Cerium の開発を通して得られた知見を元に Code Segment, Data Segment によって構成される Gears OS の設計・実装を行なった。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 実装には本研究室で開発している CbC(Continuation based C)を用いた。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 Code Segment は処理、Data Segment はデータの単位である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 Code Segment は戻り値を持たないので、関数呼び出しのようにスタックに値を積む必要がなくスタックは変更されない。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 このようなスタックに積まない継続を軽量継続と呼び、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行える。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 プログラムを Code/Data Segment で分割して記述することで並列度を高めることができる。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 Gears OS を Code/Data Segment の考えに基づいて設計を行なった。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 Gears OS には Code/Data Segment と同等なものとして Code/Data Gear を定義した。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 Code Gear はプログラムの処理そのもので、Data Gear は int や文字列などの Primitive Data Type を複数持っている構造体として表現する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 Code Gear は任意の数の Data Gear を参照し、任意の数の Data Gear に書き込みを行う。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 Gear の特徴として処理やデータ構造が Code/Data Gear に閉じている。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 これにより実行時間、メモリ使用量などを予測可能なものにする。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 Gears OS の基本的な機能として Allocator, TaskQueue, Persistent Data Tree, Worker の実装を行なった。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 Gears OS では Context に情報が格納される。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 格納される情報には接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear を確保するためのメモリ空間などがある。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 Context はスレッドごとに存在し、それぞれが異なる Context を参照している。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 Allocator は Context が持っているメモリ空間のアドレスを変更し、Temporal Data Gear の確保を行う。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 確保される Data Gear は処理後には必要なくなるものなのでリニアに確保するだけの単純な処理である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 TaskQueue は並列処理される Task を管理する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 Gears OS で Task は実行する Code Gear と実行に必要な Data Gear の組で表現する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 TaskQueue はすべての Context で共有され、マルチスレッドでデータの一貫性を保つために Compare and Swap(CAS) を用いた。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 Persistent Data Tree は Data Gear を管理する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 非破壊木構造で構成され、Red-Black Tree アルゴリズムによって平衡性が保たれる。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 Persistent Data Tree はすべての Context で共有される。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 非破壊木構造なので読み書きを平行して行うことができる。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 Gears OS では Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 Worker は Task を並列処理する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 個別の Context を参照しているので、メモリ空間が独立しておりメモリを確保する処理で他の Worker を止めることはない。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 CAS を用いて TaskQueue にアクセスし、Task を取得する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 取得した Task の情報を元に Persistent Data Tree から Data Gear を取得し、Code Gear を実行する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 また、Gears OS 自体が Code/Data Segment を用いたプログラミングの指針となるように実装を行った。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 Gears OS を用いて簡単な例題を実装し、評価を行った。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 与えられた要素を2倍にする Twice という依存関係がない並列処理の例題を Gears OS 上に実装した。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 1 CPU と 12 CPU で約11.8倍の速度向上を確認し、Gears OS を用いることで十分な並列処理性能を引き出せることを示した。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 \section{今後の課題}
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 例題として Twice を用いて並列処理の性能を示したが、Twice は依存関係がない並列処理である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 本来、並列処理には依存関係が存在する。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 複雑な並列処理を行えるようにするために依存関係を解決する TaskManager の実装が必要である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 Gears OS 上でマルチコア CPU を用いた実行を可能にしたが、GPU などの他のプロセッサを演算に用いることができない。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 Code/Data Segment を用いて各プロセッサのアーキテクチャにマッピングした実行機構を実装し、演算に利用できるようにする必要がある。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 型情報を残すために Data Segment を定義しているが Data Segment の型情報を検査していない。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 プログラムの正しさを保証するために Data Segment の型情報を検査する型システムを Gears OS 上に実装する必要がある。