# HG changeset patch # User Shohei KOKUBO # Date 1455614164 -32400 # Node ID a6188b7c727893ca635237b5a63c784fb6295870 # Parent 2d6755608f67d2f1113e7598971712a4bd779e97 revision diff -r 2d6755608f67 -r a6188b7c7278 cerium.tex --- a/cerium.tex Mon Feb 15 08:22:50 2016 +0900 +++ b/cerium.tex Tue Feb 16 18:16:04 2016 +0900 @@ -355,14 +355,101 @@ \label{fig:wordcount} \end{figure} -Cerium が複雑な並列処理を記述可能でその上、高い並列度を保てること示すため Cerium 上に Word Count を実装し、測定を行なった。 -結果は図\ref{} +\newpage + +Cerium が複雑な並列処理を記述可能でその上、高い並列度を保てること示すため Cerium 上に Word Count を実装し、100MB のテキストデータに対して測定を行なった。 +結果は表:\ref{table:word_count}, 図:\ref{fig:word_count}の通りである。 + +\begin{table}[!h] + \begin{center} + \small + \begin{tabular}[htpb]{|c||c|} + \hline + Processor & Time(ms) \\ + \hline + \hline + 1 CPU & 716 \\ + \hline + 2 CPUs & 373 \\ + \hline + 4 CPUs & 197 \\ + \hline + 8 CPUs & 105 \\ + \hline + 12 CPUs & 87 \\ + \hline + GPU & 9899 \\ + \hline + GPU(Data Parallel) & 514 \\ + \hline + \end{tabular} + \caption{100MB のテキストデータに対する WordCount} + \label{table:word_count} + \end{center} +\end{table} + +\begin{figure}[!h] + \begin{center} + \includegraphics[scale=0.8]{images/word_count.pdf} + \end{center} + \caption{100MB のテキストデータに対する WordCount} + \label{fig:word_count} +\end{figure} + +1 CPU と 12 CPU では約8.2倍の速度向上が見られた。 +複雑な並列処理でも高い並列度が保てていることがわかる。 + +GPU を用いたタスク並列による実行は実用に耐えない速度である。 +これはタスク並列による実行では小さなデータを十数回 GPU に転送する必要があるからで、GPU で高速に処理するためにはデータ転送を如何にして抑えるかが重要かわかる。 +一方、GPU を用いたデータ並列による実行速度は 1 CPU の約1.4倍となった。 +元々 WordCount は GPU に不向きな例題ではあるが、データ並列による実行ではデータ転送の回数を抑えることができるので GPU でもある程度の速度を出せることがわかる。 \subsection{FFT} FFT は信号処理や画像処理、大規模シミュレーションに至るまで幅広い分野で活用されている計算である。 バタフライ演算などの計算の性質上、大量の演算資源を持つ GPU と相性が良い。 Cerium に実装した GPU 実行機構の評価を行うために適切な例題であると考えられる。 +Cerium 上に FFT を実装し、測定を行なった結果は表:\ref{table:fft}, 図:\ref{fig:fft}の通りである。 +測定には 1MB の画像データを用いた。 + +\begin{table}[!h] + \begin{center} + \small + \begin{tabular}[htpb]{|c||c|} + \hline + Processor & Time(ms) \\ + \hline + \hline + 1 CPU & 1958 \\ + \hline + 2 CPUs & 1174 \\ + \hline + 4 CPUs & 711 \\ + \hline + 8 CPUs & 451 \\ + \hline + 12 CPUs & 373 \\ + \hline + GPU & 418 \\ + \hline + \end{tabular} + \caption{1MB の画像データに対する FFT} + \label{table:fft} + \end{center} +\end{table} + +\begin{figure}[!h] + \begin{center} + \includegraphics[scale=0.8]{images/fft.pdf} + \end{center} + \caption{1MB の画像データに対する FFT} + \label{fig:fft} +\end{figure} + +1 CPU に対して 12 CPU では約5.2倍、GPU では約4.7倍の速度向上が見られる。 +ある程度の速度向上が見られたが、CPU に劣る結果となった。 +データ転送の最適化が十分になされていない可能性があるので、GPU の実行機構を見直す必要がある。 + \section{Cerium の問題点} Cerium では Task 間の依存関係を記述することで並列処理を実現する。 しかし、本来 Task はデータが揃えば実行可能になるものである。 diff -r 2d6755608f67 -r a6188b7c7278 comparison.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/comparison.tex Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,62 @@ +\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} diff -r 2d6755608f67 -r a6188b7c7278 evaluation.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/evaluation.tex Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,83 @@ +\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 & 64 Tasks(ms) & 640 Tasks(ms) & 6400 Tasks(ms) \\ +%% \hline +%% \hline +%% 1 CPU & 1245 & 1315 & 1973 \\ +%% \hline +%% 2 CPUs & 629 & 689 & 1118 \\ +%% \hline +%% 4 CPUs & 326 & 366 & 610 \\ +%% \hline +%% 8 CPUs & 165 & 189 & 327 \\ +%% \hline +%% 12 CPUs & 121 & 111 & 114 \\ +%% \hline +%% \end{tabular} +%% \caption{要素数$2^{17}$*1000 のデータに対する Twice} +%% \label{table:twice} +%% \end{center} +%% \end{table} + +\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} + diff -r 2d6755608f67 -r a6188b7c7278 images/fft.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/fft.bb Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/fft.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 360 216 +%%CreationDate: Tue Feb 16 13:11:33 2016 + diff -r 2d6755608f67 -r a6188b7c7278 images/fft.pdf Binary file images/fft.pdf has changed diff -r 2d6755608f67 -r a6188b7c7278 images/twice.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/twice.bb Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/twice.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 360 216 +%%CreationDate: Tue Feb 16 15:51:01 2016 + diff -r 2d6755608f67 -r a6188b7c7278 images/twice.pdf Binary file images/twice.pdf has changed diff -r 2d6755608f67 -r a6188b7c7278 images/twice_640.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/twice_640.bb Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/twice_640.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 360 216 +%%CreationDate: Tue Feb 16 18:13:32 2016 + diff -r 2d6755608f67 -r a6188b7c7278 images/twice_640.pdf Binary file images/twice_640.pdf has changed diff -r 2d6755608f67 -r a6188b7c7278 images/word_count.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/word_count.bb Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: ./images/word_count.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 360 216 +%%CreationDate: Tue Feb 16 12:41:56 2016 + diff -r 2d6755608f67 -r a6188b7c7278 images/word_count.pdf Binary file images/word_count.pdf has changed diff -r 2d6755608f67 -r a6188b7c7278 intro.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/intro.tex Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,1 @@ +\chapter{並列分散環境下におけるプログラミング} diff -r 2d6755608f67 -r a6188b7c7278 master_paper.pdf Binary file master_paper.pdf has changed diff -r 2d6755608f67 -r a6188b7c7278 master_paper.tex --- a/master_paper.tex Mon Feb 15 08:22:50 2016 +0900 +++ b/master_paper.tex Tue Feb 16 18:16:04 2016 +0900 @@ -84,17 +84,12 @@ \mainmatter %chapters -\chapter{並列分散環境下におけるプログラミング} +\input{intro.tex} \input{cerium.tex} \input{cbc.tex} \input{gearsos.tex} -\chapter{比較} -\section{Cerium} -\section{従来の OS} - -\chapter{評価} -\section{Twice} - +\input{comparison.tex} +\input{evaluation.tex} \chapter{結論} %謝辞 diff -r 2d6755608f67 -r a6188b7c7278 result/box.plt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/box.plt Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,9 @@ +set term pdf +set output "word_count.pdf" +set boxwidth 0.5 relative +set style fill solid border lc rgb "black" +set ylabel "time(ms)" +set xrange[0:8] +set yrange[0:1000] +set xtics ("1 cpu" 1, "2 cpus" 2, "4 cpus" 3, "8 cpus" 4, "12 cpus" 5, "gpu" 6, "gpu(data parallel)" 7) +plot "word_count/result" u 1:($2*1000) smooth unique with boxes lw 2 lc rgb "light-cyan" notitle diff -r 2d6755608f67 -r a6188b7c7278 result/fft/result --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/fft/result Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,18 @@ +1 1.958956 +1 1.966016 +1 1.950610 +2 1.125611 +2 1.200725 +2 1.197753 +3 0.707902 +3 0.733299 +3 0.692185 +4 0.437522 +4 0.475558 +4 0.440223 +5 0.368692 +5 0.378096 +5 0.372550 +6 0.415012 +6 0.416886 +6 0.424896 diff -r 2d6755608f67 -r a6188b7c7278 result/graph.plt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/graph.plt Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,7 @@ +set term pdf +set output "twice.pdf" +set xlabel "Number of CPU" +set ylabel "time(ms)" +set grid +set xrange [1:12] +plot "twice/task_640" u 1:($2*1000) smooth unique title "204800 elements per Task" \ No newline at end of file diff -r 2d6755608f67 -r a6188b7c7278 result/twice/task_64 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/twice/task_64 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,15 @@ +1 1.246386 +1 1.246681 +1 1.244309 +2 0.628358 +2 0.631107 +2 0.629942 +4 0.327789 +4 0.327607 +4 0.325506 +8 0.165063 +8 0.165796 +8 0.166200 +12 0.122147 +12 0.121734 +12 0.120947 diff -r 2d6755608f67 -r a6188b7c7278 result/twice/task_640 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/twice/task_640 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,15 @@ +1 1.312108 +1 1.318565 +1 1.316683 +2 0.691450 +2 0.687672 +2 0.690753 +4 0.375747 +4 0.362807 +4 0.359630 +8 0.188330 +8 0.192578 +8 0.188250 +12 0.110277 +12 0.114549 +12 0.110316 diff -r 2d6755608f67 -r a6188b7c7278 result/twice/task_6400 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/twice/task_6400 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,15 @@ +1 1.986212 +1 1.967297 +1 1.966392 +2 1.122235 +2 1.148616 +2 1.084848 +4 0.616860 +4 0.593097 +4 0.621747 +8 0.317680 +8 0.344738 +8 0.321525 +12 0.112422 +12 0.112661 +12 0.117707 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/cpu_1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/cpu_1 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.718177 +0.718678 +0.714053 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/cpu_12 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/cpu_12 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.084439 +0.092542 +0.086132 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/cpu_2 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/cpu_2 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.370620 +0.373916 +0.377258 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/cpu_4 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/cpu_4 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.198103 +0.196991 +0.196469 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/cpu_8 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/cpu_8 Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.105340 +0.105016 +0.104969 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/gpu --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/gpu Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +9.881886 +9.897281 +9.919438 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/gpu_dp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/gpu_dp Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,3 @@ +0.517102 +0.513130 +0.512495 diff -r 2d6755608f67 -r a6188b7c7278 result/word_count/result --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/result/word_count/result Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,21 @@ +1 0.718177 +1 0.718678 +1 0.714053 +2 0.370620 +2 0.373916 +2 0.377258 +3 0.198103 +3 0.196991 +3 0.196469 +4 0.105340 +4 0.105016 +4 0.104969 +5 0.084439 +5 0.092542 +5 0.086132 +6 9.881886 +6 9.897281 +6 9.919438 +7 0.517102 +7 0.513130 +7 0.512495 diff -r 2d6755608f67 -r a6188b7c7278 src/openmp.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/openmp.c Tue Feb 16 18:16:04 2016 +0900 @@ -0,0 +1,4 @@ +#pragma omp parallel for +for(int i=0;i