Mercurial > hg > Papers > 2016 > kkb-master
view paper/evaluation.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 | evaluation.tex@205805e6a6d8 |
children | 4dcfec1bf1e7 |
line wrap: on
line source
\chapter{Gears OS の評価} 現在の Gears OS には非破壊木構造を Red-Black Tree アルゴリズムに基づいて構築する Persistent Data Tree, CAS を用いてデータの一貫性を保証する TaskQueue, TaskQueue から Task を取得し並列に実行する Worker が実装されている。 つまり、依存関係のない処理ならば並列処理することが可能である。 本章では依存関係のない簡単な例題を用いて Gears OS の評価を行う。 \section{Twice} Twice は与えられた整数配列を2倍にする例題である。 以下の流れで処理は行われる。 \begin{itemize} \item 配列サイズを元に index, alignment, 配列へのポインタを持つ Data Gear に分割。 \item Data Gear を Persistent Data Tree に挿入。 \item 実行する Code Gear(Twice) と実行に必要な Data Gear への key を持つ Task を生成。 \item 生成した Task を TaskQueue に挿入。 \item Worker の起動。 \item Worker が TaskQueue から Task を取得。 \item 取得した Task を元に必要な Data Gear を Persistent Data Tree から取得。 \item 並列の処理される Code Gear(Twice) を実行。 \end{itemize} \newpage Gears OS 上に Twice を実装し、要素数$2^{17}$*1000 のデータを640個の Task に分割してコア数を変更して測定を行なった。 結果は表:\ref{table:twice}, 図:\ref{fig:twice}の通りである。 \begin{table}[!h] \begin{center} \small \begin{tabular}[htpb]{|c||c|c|c|} \hline Processor & Time(ms) \\ \hline \hline 1 CPU & 1315 \\ \hline 2 CPUs & 689 \\ \hline 4 CPUs & 366 \\ \hline 8 CPUs & 189 \\ \hline 12 CPUs & 111 \\ \hline \end{tabular} \caption{要素数$2^{17}$*1000 のデータに対する Twice} \label{table:twice} \end{center} \end{table} \begin{figure}[!h] \begin{center} \includegraphics[scale=0.9]{images/twice_640.pdf} \end{center} \caption{要素数$2^{17}$*1000 のデータに対する Twice} \label{fig:twice} \end{figure} 1 CPU と 12 CPU では約11.8倍の速度向上が見られた。 十分な台数効果が出ていることがわかる。 しかし、タスクの粒度が小さすぎると CAS の失敗が多くなり性能が出ないことがある。 Code Gear には実行時間を予測可能なものにするという特徴があるので、その性質を利用してタスクが最適な粒度なのか検査する機能が必要になると考えられる。 今回、例題に用いた Twice は依存関係のない並列処理である。 本来、並列処理には複雑な依存関係が存在するのが一般的である。 並列フレームワークには複雑な依存関係を解決しながら十分な並列度を保てることが必須なので依存関係を解決するための TaskManager の実装が必要である。