Mercurial > hg > Papers > 2016 > kkb-master

annotate paper/evaluation.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 evaluation.tex@205805e6a6d8
children 4dcfec1bf1e7
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{Gears OS の評価}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 現在の Gears OS には非破壊木構造を Red-Black Tree アルゴリズムに基づいて構築する Persistent Data Tree, CAS を用いてデータの一貫性を保証する TaskQueue, TaskQueue から Task を取得し並列に実行する Worker が実装されている。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 つまり、依存関係のない処理ならば並列処理することが可能である。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
14
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
5 本章では依存関係のない簡単な例題を用いて Gears OS の評価を行う。
13
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 \section{Twice}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 Twice は与えられた整数配列を2倍にする例題である。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 以下の流れで処理は行われる。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 \begin{itemize}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 \item 配列サイズを元に index, alignment, 配列へのポインタを持つ Data Gear に分割。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 \item Data Gear を Persistent Data Tree に挿入。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 \item 実行する Code Gear(Twice) と実行に必要な Data Gear への key を持つ Task を生成。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 \item 生成した Task を TaskQueue に挿入。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 \item Worker の起動。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 \item Worker が TaskQueue から Task を取得。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \item 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 \item 並列の処理される Code Gear(Twice) を実行。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 \end{itemize}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 \newpage
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 Gears OS 上に Twice を実装し、要素数$2^{17}$*1000 のデータを640個の Task に分割してコア数を変更して測定を行なった。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 結果は表:\ref{table:twice}, 図:\ref{fig:twice}の通りである。
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 \begin{table}[!h]
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 \begin{center}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 \small
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 \begin{tabular}[htpb]{|c||c|c|c|}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 Processor & Time(ms) \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 1 CPU & 1315 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 2 CPUs & 689 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 4 CPUs & 366 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 8 CPUs & 189 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 12 CPUs & 111 \\
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 \hline
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 \end{tabular}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 \caption{要素数$2^{17}$*1000 のデータに対する Twice}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 \label{table:twice}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 \end{center}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 \end{table}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 \begin{figure}[!h]
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 \begin{center}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 \includegraphics[scale=0.9]{images/twice_640.pdf}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 \end{center}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 \caption{要素数$2^{17}$*1000 のデータに対する Twice}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 \label{fig:twice}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 \end{figure}
a6188b7c7278 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59
14
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
60 1 CPU と 12 CPU では約11.8倍の速度向上が見られた。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
61 十分な台数効果が出ていることがわかる。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
62 しかし、タスクの粒度が小さすぎると CAS の失敗が多くなり性能が出ないことがある。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
63 Code Gear には実行時間を予測可能なものにするという特徴があるので、その性質を利用してタスクが最適な粒度なのか検査する機能が必要になると考えられる。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
64
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
65 今回、例題に用いた Twice は依存関係のない並列処理である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
66 本来、並列処理には複雑な依存関係が存在するのが一般的である。
205805e6a6d8 revision
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
67 並列フレームワークには複雑な依存関係を解決しながら十分な並列度を保てることが必須なので依存関係を解決するための TaskManager の実装が必要である。