# HG changeset patch # User e135704 # Date 1487104028 -32400 # Node ID 094f2573edf1cdae67a8b719ee924522f7de825a # Parent e4c33c7f162fc6ac9d635bf51c317c9f30f81c89 modifi table diff -r e4c33c7f162f -r 094f2573edf1 paper/main.aux --- a/paper/main.aux Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.aux Wed Feb 15 05:27:08 2017 +0900 @@ -3,54 +3,48 @@ \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} \newlabel{chap:introduction}{{1}{1}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第2章}概要}{2}} +\citation{cbc-lola} +\citation{opencl} +\citation{cuda} +\@writefile{toc}{\contentsline {chapter}{\numberline {第2章}GearsOS}{2}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\newlabel{chap:concept}{{2}{2}} -\@writefile{toc}{\contentsline {section}{\numberline {2.1}Cudaの例題}{2}} -\@writefile{toc}{\contentsline {section}{\numberline {2.2}GPUプログラミングの問題点}{2}} -\@writefile{toc}{\contentsline {section}{\numberline {2.3}Meta計算によるGPU並列実行の制御}{2}} -\citation{cbc-lola} -\@writefile{toc}{\contentsline {chapter}{\numberline {第3章}GearsOS}{3}} -\@writefile{lof}{\addvspace {10\p@ }} -\@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {3.1}Continuation Baseed C}{3}} -\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces gotoによる Code Segment 間の接続}}{3}} -\newlabel{fig:cbc_goto}{{3.1}{3}} -\@writefile{toc}{\contentsline {section}{\numberline {3.2}並列性}{3}} -\@writefile{toc}{\contentsline {section}{\numberline {3.3}柔軟性}{4}} -\@writefile{toc}{\contentsline {section}{\numberline {3.4}Gears でのMeta computation の実行}{4}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}Gears OSの構成}{5}} +\@writefile{toc}{\contentsline {section}{\numberline {2.1}Continuation Baseed C}{2}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces gotoによる Code Segment 間の接続}}{2}} +\newlabel{fig:cbc_goto}{{2.1}{2}} +\@writefile{toc}{\contentsline {section}{\numberline {2.2}Code Gear と Data Gear}{2}} +\@writefile{toc}{\contentsline {section}{\numberline {2.3}並列性}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {2.4}柔軟性}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {2.5}Gears でのMeta computation の実行}{3}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第3章}Gears OSの構成}{4}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {4.1}Queue}{5}} -\@writefile{toc}{\contentsline {section}{\numberline {4.2}Red Black Tree}{5}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces 木構造の非破壊的編集}}{6}} -\newlabel{fig:persistent_data_tree}{{4.1}{6}} -\@writefile{toc}{\contentsline {section}{\numberline {4.3}TaskManager}{6}} -\@writefile{toc}{\contentsline {section}{\numberline {4.4}Worker}{7}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}GPGPU}{8}} +\@writefile{toc}{\contentsline {section}{\numberline {3.1}TaskManager}{4}} +\@writefile{toc}{\contentsline {section}{\numberline {3.2}Worker}{4}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}GPGPU}{5}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {5.1}GPGPUとは}{8}} -\@writefile{lof}{\contentsline {figure}{\numberline {5.1}{\ignorespaces Gears OS による GPGPU}}{9}} -\newlabel{fig:gpgpu}{{5.1}{9}} -\@writefile{toc}{\contentsline {section}{\numberline {5.2}CUDAでの実行}{9}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第6章}GPU 実装}{10}} +\@writefile{toc}{\contentsline {section}{\numberline {4.1}GPGPUとは}{5}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces Gears OS による GPGPU}}{6}} +\newlabel{fig:gpgpu}{{4.1}{6}} +\@writefile{toc}{\contentsline {section}{\numberline {4.2}CUDAでの実行}{6}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}GPU 実装}{7}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {6.1}GPUWoker の実装}{10}} -\@writefile{toc}{\contentsline {section}{\numberline {6.2}性能評価}{10}} -\@writefile{toc}{\contentsline {section}{\numberline {6.3}比較}{10}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第7章}今後の課題}{11}} +\@writefile{toc}{\contentsline {section}{\numberline {5.1}GPUWoker の実装}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {5.2}CUDATwiceの実装}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {5.3}CMake}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {5.4}性能評価}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {5.5}比較}{7}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第6章}今後の課題}{8}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {7.1}GPU並列実行}{11}} +\@writefile{toc}{\contentsline {section}{\numberline {6.1}GPU並列実行}{8}} \citation{*} \bibstyle{junsrt} \bibdata{reference} -\@writefile{toc}{\contentsline {chapter}{\numberline {第8章}結論}{12}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第7章}結論}{9}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {8.1}まとめ}{12}} -\@writefile{toc}{\contentsline {section}{\numberline {8.2}今後の課題}{12}} +\@writefile{toc}{\contentsline {section}{\numberline {7.1}まとめ}{9}} +\@writefile{toc}{\contentsline {section}{\numberline {7.2}今後の課題}{9}} diff -r e4c33c7f162f -r 094f2573edf1 paper/main.dvi Binary file paper/main.dvi has changed diff -r e4c33c7f162f -r 094f2573edf1 paper/main.lof --- a/paper/main.lof Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.lof Wed Feb 15 05:27:08 2017 +0900 @@ -1,11 +1,9 @@ +\addvspace {10\p@ } +\addvspace {10\p@ } +\contentsline {figure}{\numberline {2.1}{\ignorespaces gotoによる Code Segment 間の接続}}{2} +\addvspace {10\p@ } +\addvspace {10\p@ } +\contentsline {figure}{\numberline {4.1}{\ignorespaces Gears OS による GPGPU}}{6} \addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } -\contentsline {figure}{\numberline {3.1}{\ignorespaces gotoによる Code Segment 間の接続}}{3} -\addvspace {10\p@ } -\contentsline {figure}{\numberline {4.1}{\ignorespaces 木構造の非破壊的編集}}{6} -\addvspace {10\p@ } -\contentsline {figure}{\numberline {5.1}{\ignorespaces Gears OS による GPGPU}}{9} -\addvspace {10\p@ } -\addvspace {10\p@ } -\addvspace {10\p@ } diff -r e4c33c7f162f -r 094f2573edf1 paper/main.log --- a/paper/main.log Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.log Wed Feb 15 05:27:08 2017 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.14159265-p3.6-141210-2.6 (utf8.euc) (TeX Live 2015) (preloaded format=platex 2015.11.28) 14 FEB 2017 18:37 +This is e-pTeX, Version 3.14159265-p3.6-141210-2.6 (utf8.euc) (TeX Live 2015) (preloaded format=platex 2015.11.28) 15 FEB 2017 04:09 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -170,40 +170,36 @@ ] 第 2 章 LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <17.28> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 105. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 101. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <17.28> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 105. -LaTeX Font Info: Try loading font information for OMS+cmr on input line 110. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 101. -(/usr/local/texlive/2015/texmf-dist/tex/latex/base/omscmr.fd -File: omscmr.fd 2014/09/29 v2.5h Standard LaTeX font definitions -) -LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <12> not available -(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 110. - [2 - -] -第 3 章 - -LaTeX Warning: Citation `cbc-lola' on page 3 undefined on input line 141. +LaTeX Warning: Citation `cbc-lola' on page 2 undefined on input line 102. File: ./pic/cbc_goto.pdf Graphic file (type pdf) <./pic/cbc_goto.pdf> -LaTeX Warning: Reference `fig:CG_Flexibility' on page 3 undefined on input line - 168. - -[3 - -] [4] -第 4 章 - -LaTeX Warning: Reference `src:sync_enqueue' on page 5 undefined on input line 1 -99. +LaTeX Warning: Citation `opencl' on page 2 undefined on input line 121. -LaTeX Warning: Reference `src:sync_enqueue' on page 5 undefined on input line 2 -00. +LaTeX Warning: Citation `cuda' on page 2 undefined on input line 121. + +[2 + +] + +LaTeX Warning: Reference `fig:CG_Flexibility' on page 3 undefined on input line + 146. + +[3] +第 3 章 + +LaTeX Warning: Reference `src:sync_enqueue' on page 4 undefined on input line 1 +61. + + +LaTeX Warning: Reference `src:sync_enqueue' on page 4 undefined on input line 1 +62. ! Package Listings Error: File `./src/sync_enqueue(.c)' not found. @@ -215,16 +211,12 @@ ! Undefined control sequence. \\lst@inputlisting ...}}\reserved@a }\lst@doendpe \@newlistfalse \ignorespaces -l.202 ...e, caption=Enqueue]{./src/sync_enqueue.c} +l.164 ...e, caption=Enqueue]{./src/sync_enqueue.c} ? -File: ./pic/persistent_date_tree.pdf Graphic file (type pdf) -<./pic/persistent_date_tree.pdf> [5 -] [6] - -LaTeX Warning: Reference `src:sync_dequeue' on page 7 undefined on input line 2 -47. +LaTeX Warning: Reference `src:sync_dequeue' on page 4 undefined on input line 1 +81. ! Package Listings Error: File `./src/sync_dequeue(.c)' not found. @@ -236,28 +228,38 @@ ! Undefined control sequence. \\lst@inputlisting ...}}\reserved@a }\lst@doendpe \@newlistfalse \ignorespaces -l.250 ...e, caption=GetTask]{./src/sync_dequeue.c} +l.184 ...e, caption=GetTask]{./src/sync_dequeue.c} ? -[7] +[4 + +] +第 4 章 +LaTeX Font Info: Try loading font information for OMS+cmr on input line 203. + +(/usr/local/texlive/2015/texmf-dist/tex/latex/base/omscmr.fd +File: omscmr.fd 2014/09/29 v2.5h Standard LaTeX font definitions +) +LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <12> not available +(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 203. +File: pic/gearsos.pdf Graphic file (type pdf) + + [5 + +] [6] 第 5 章 -File: pic/gearsosgpgpu.pdf Graphic file (type pdf) - [8 +[7 -] [9] +] 第 6 章 -[10 +[8 ] 第 7 章 -[11 +No file main.bbl. +[9 -] -第 8 章 -No file main.bbl. -[12 - -] [13 +] [10 ] (./main.aux) @@ -265,12 +267,12 @@ ) Here is how much of TeX's memory you used: - 2113 strings out of 493777 - 29373 string characters out of 6151333 - 123772 words of memory out of 5000000 - 5591 multiletter control sequences out of 15000+600000 + 2112 strings out of 493777 + 29303 string characters out of 6151333 + 122772 words of memory out of 5000000 + 5590 multiletter control sequences out of 15000+600000 14180 words of font info for 55 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 26i,5n,40p,573b,317s stack positions out of 5000i,500n,10000p,200000b,80000s + 26i,5n,40p,573b,313s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on main.dvi (17 pages, 31464 bytes). +Output written on main.dvi (14 pages, 25052 bytes). diff -r e4c33c7f162f -r 094f2573edf1 paper/main.lot --- a/paper/main.lot Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.lot Wed Feb 15 05:27:08 2017 +0900 @@ -5,4 +5,3 @@ \addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } -\addvspace {10\p@ } diff -r e4c33c7f162f -r 094f2573edf1 paper/main.pdf Binary file paper/main.pdf has changed diff -r e4c33c7f162f -r 094f2573edf1 paper/main.tex --- a/paper/main.tex Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.tex Wed Feb 15 05:27:08 2017 +0900 @@ -96,58 +96,19 @@ %序論の目安としては1枚半ぐらい． %英語発表者は，最終予稿の「はじめに」の英訳などを載せてもいいかも． - -\chapter{概要} -% 研究内容の概要、要するに序論で書いた問題点と解決方法の要点をまとめて紹介するところ。なのでCudaの例題を紹介するのはここでいいのか疑問。 - -\label{chap:concept} - -\section{Cudaの例題} -Cuda による GPU 処理の例題として twice を用いて評価する。tiwce は与えられた整数配列を2倍にする例題である。 -以下の流れで処理は行われる。 -% kkbさんのtwiceの説明なので TaskQueueとWorkerは書いていいのか謎 -\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} - -\section{GPUプログラミングの問題点} -%GPU処理をするにはCPUで計算を行う場合とは違い、GPUは単純な計算しか出来ないが多数のコアを持つ演算ユニットであり、CPUのように直接命令を送ることが出来ない。 -%そのためCPU からGPUへのデータの送信、また計算結果をGPUから受け取る事によってGPU処理は成り立っている。 -%しかし、使用するコア数が増えるとCPUとコアの間でのデータの受取の回数が増えるため送受信の時間が増大する、これによって送受信の時間がボトルネックとなり処理を並列化するして速くしたとしても、データの受信時間分だけ計算時間が長くなってしまう。 -%上の問題点はGPUプログラミング全てに言える問題点であるから、今回のGearsによる実装で解決出来ているものでは無いので載せないの方がいい？ - -%問題点2 -%また並列処理では、処理の実行中に並列に実行されている他の処理によって使用している値の書き換えが起こり、これによって処理が正しく行われない可能性がある。 -%問題点3 -%kernelが取り扱うDataのsupportが必要 これはもしかしたらGPUに直接Dataを送れないってことかも -%GPUの処理実行のデータの話 - -%GPUでのデータのサポート話 -\section{Meta計算によるGPU並列実行の制御} -%Gears のmetaな部分によってどうやって問題点を解決しているのかを書く -Gears OS は処理と Data の記述を Code Gear と Data Gear に分けて書く事によって -%Gears OSはCode GearとData Gearの2つに分けることによって、 \chapter{GearsOS} \section{Continuation Baseed C} -Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行う。\\ -CbC は処理を Code Segment を用いて記述することを基本としているため、 Gears OS の Code Gear を記述するのに適している。 -CbC のプログラムでは C の関数の代わりに Code Segment を用いてい処理を記述している。 +Gears OS の実装は本研究室で開発している CbC(Continuation based C)\cite{cbc-lola}を用いて行われている。。\\ +CbC は処理を Code Segment を用いて分割して記述することを基本としている。、 Gears OS の Code Gear はCbCを元に記述されている。 +CbC のプログラムでは C の関数の単位で Code Segment を用いて分割し、処理を記述している。 Code Segment は C の関数と異なり戻り値を持たない。 -Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使うことで宣言できる。 -Code Segment から Code Segment への移動は goto の後に Code Segment 名と引数を並べた記述するという構文を用いて行う。 -この goto による処理の遷移を継続と呼ぶ。 図\ref{fig:cbc_goto} は Code Segment 間の継続関係を表している。 -C では関数呼び出しを行うたび、関数の引数の値がスタックに積まれていくが、Code Segment では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要が無い。 -このようなスタックに値を積まない継続、つまり呼び出し元の環境を持たない継続を軽量継続と呼ぶ。 -軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。 +Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使い宣言している。 +Code Segment から Code Segment への移動は goto の後に移動先の Code Segment 名と引数を並べた記述する構文を用いて行う。 +この goto による処理の遷移を継続と呼び、C での関数呼び出しにあたり、C では関数の引数の値がスタックに積まれていくが、Code Segment の goto では戻り値を持たないため、スタックに値を積んでいく必要がなくスタックを変更する必要がない。 +このようなスタックに積まない継続を軽量継続と呼び、呼び出し元の環境を持たない。 +図\ref{fig:cbc_goto} は Code Segment 間の接続関係を表している。 + \begin{figure}[ht] \begin{center} \includegraphics[width=70mm]{./pic/cbc_goto.pdf} @@ -155,13 +116,31 @@ \caption{gotoによる Code Segment 間の接続} \label{fig:cbc_goto} \end{figure} + +\section{Code Gear と Data Gear} +Code Gear はプログラムの実行コードそのものであり、OpenCL\cite{opencl}/CUDA\cite{cuda} の kernel に相当する。 + +Code Gear は処理の基本として、 Input Data Gear を参照し、一つまたは複数の Output Data Gear に書き込む。また、接続された Data Gear 以外には参照を行わない。 +Input Data Gear と Output Data Gear の2つによって、Code Gear の Data に対する依存関係を解決し、 Code Gear の並列実行を可能とする。 + + +Code Gear はCbCを元に記述されており、処理の移行はfunction callではないので、呼び出し元に戻る概念はない。 +その代わりに、次に実行する Code Gear を軽量継続の goto で指定する。 + +Data Gear は、int や文字列などの Primitive Data Type の組み合わせ（struct）である。 +Data Gearは様々な型を持つunionとして定義される。 + +Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることにある。 +これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。 \section{並列性} + %Gearsの特性を活かせての並列性とは？ %Code Gear Data Gear にわけられることによって依存関係が解決されていること %並列性と柔軟性は2つともSegment毎に分けられていることで成り立つわけだから、説明する際に2つでSegmentによって分けられるって事説明するのか？同じ事説明してるけど % 並列処理するの問題、並列化刷ることによって依存関係のあるプログラムがあると並列化出来ない、ということだけど、依存関係ってもっとわかりやすく言うとなに？->要するに、Aの処理を行うにはBの処理を施した値を使わないといけないとかそういうこと、逆に依存関係が無い処理は同時に並列処理していいわけだけど、ソレはつまりここでいう並列性とは、並列化し易いとかそういうことでいいんだろうか、　依存関係の無い形、Gearという分けられた単位にはほかとの依存関係は無い、わけではなくて、あるけど、　　処理毎に分けることによって、依存している物を明確にしているって言うところが強みである。 -Gears OS はCode Gear Data Gear によってプログラムを Gear という単位によって分けられ、Gear 毎に依存関係が明確化されている。そのため並列化を行う場合、並列処理を行う Gear の依存関係に沿って容易に並列化することが出来る。 +Code Gear は Task を実行するのに必要な Input Data Gear と Task を実行し出力される Output Data Gear の組によって + \section{柔軟性} %プログラムの処理が Gearという単位で分けられて記述されているって言うけど、プログラムの処理ってなに？という疑問を持つのが一般的だと思われ Code Gear Data Gear はCbCを用いて記述されており、その特徴としてプログラムの処理が Gear という単位で分けられて記述されていることである。\\ @@ -178,57 +157,13 @@ \chapter{Gears OSの構成} -\section{Queue} -Gears OS における Task Queue は Synchronized Queue で実現される。 -メインとなる Context と Worker 用 の Context で共有され、 Worker が TaskQueue から Task を取得し、実行することで並列処理を行う。 -Gears OS の Queue は Queue を表す Data Gear と List を表現する Element という名前の Data Gear を組み合わせて表現する。 -Queue を表す Data Gear には List 構造の先頭の Element を指す first, 末尾の Element を指す last, Element の個数を示す count が格納される。 -Element を表す Data Gear は、Task を示す task、 次の Element を示す next が格納される。 - -Queue に対して操作を行う場合、 Queue 自体の Data Gear を書き換える。 -Task を 挿入する場合、 新しく Element を生成し、 Queue の last から List 構造の末尾に新しい Element を追加し、 Queue の last を書き換える。 -Task を 取得する場合、 Queue の first から List 構造を最初の要素を取り出し、 取り出した要素の次の要素の参照を Queue の first に書き込む。 - -Gears OS の TaskQueue はマルチスレッドでの操作を想定しているため、データの一貫性を保証する必要がある。 -そのため、データの一貫性を並列実行時でも保証するために Compare and Swap(CAS) を利用して Queue の操作を行っている。 -CAS はデータの比較・置換をアトミックに行う命令である。 -メモリからデータの読みだし、変更、メモリへのデータの書き出しという一連の処理を CAS を利用することで処理の間に他のスレッドがメモリに変更を加えないことを保証することができる。 -CAS に失敗した場合は置換を行わず、再びデータの呼び出しから始める。 Code \ref{src:sync_enqueue} に CAS を使用した Task 挿入を示している。 Code \ref{src:sync_enqueue} は 2つのCode Gear を定義しており、 putQueue3 は Queue に要素がある場合、 putQueue4 は Queue に要素がない場合の Task 挿入を示している。 \lstinputlisting[label=src:sync_enqueue, caption=Enqueue]{./src/sync_enqueue.c} -\section{Red Black Tree} -Gears OS は Persistent Data Gear の管理に木構造を用いる。 -この木構造は非破壊的で構成される。 -非破壊木構造とは図\ref{fig:persistent_data_tree}のように一度構築した木構造を破壊すること無く新しい木構造を構築することで、木構造を編集する方法である。 -非破壊木構造は木構造を書き換えることなく編集を行うため、読み書きを平行して行うことが可能である。 -\begin{figure}[ht] - \begin{center} - \includegraphics[width=80mm]{./pic/persistent_date_tree.pdf} - \end{center} - \caption{木構造の非破壊的編集} - \label{fig:persistent_data_tree} -\end{figure} - -Gears OS では Data Tree として木構造を利用する。 -その場合、普通に木構造を構築するだけでは偏った木構造が構築される可能性がある。 -最悪なケースでは線形リストになり、計算量が O(n) となる。 - -そのため、挿入・削除・検索における処理時間を保証するため Red-Black Tree を用いて木構造の平衡性を保証する。 -Red-Black Tree は通常の二分探索木としての条件の他に以下の条件を持つ。 - -\begin{itemize} - \item 各ノードは赤または黒の色を持つ。 - \item ルートの色は黒である。 - \item 赤ノードは2つの黒ノードを子として持つ(赤ノードが続くことはない)。 - \item ルートから最下位ノードへのパスに含まれる黒ノードの数はどの最下位ノードでも一定である。 -\end{itemize} - -これらの条件によってルートから最も遠い最下位ノードへのパスの長さはルートから最も近い最下位ノードへのパスの長さの2倍に収まることが保証される。 \section{TaskManager} Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。 Task には Input/Output Data Gear の情報が格納されている。 @@ -258,13 +193,12 @@ \chapter{GPGPU} \section{GPGPUとは} -GPGPUとは、元々は画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術の事である。\\ -画像の編集はピクセル毎に行われるため多大な数の処理を行う必要があるが、GPUはCPUに比べコア数が多数あり、多数のコアで同時に計算することによってCPUよりも多数の並列な処理を行う事が出来る。\\ -これによってGPUは画像処理のような多大な処理を並列処理することで、CPUで処理するよりも高速に並列処理することが出来る。 -しかし、GPUのコアはCPUのコアに比べ複雑な計算は出来ない構造であるため単純計算しか出来ない、また一般的にユーザーからGPU単体に直接命令を書き込むことも出来ないなどの問題点も存在する。 -GPGPUはCPUによって単純計算のTaskをGPUに振り分ける事によって、GPUの問題点を解決しつつ、高速な並列処理を行うことである。 -またData Gear へのアクセスは接続されたCode Gear からのみであるから、処理中に\\ -変数が書き変わる事がない。 +GPGPU とは、元々は画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術の事である。\\ +画像の編集はピクセル毎に行われるため多大な数の処理を行う必要があるが、 GPU は CPU に比べコア数が多数あり、多数のコアで同時に計算することによって CPU よりも多数の並列な処理を行う事が出来る。\\ +これによってGPUは画像処理のような多大な処理を並列処理することで、 CPU で処理するよりも高速に並列処理することが出来る。 +しかし、GPU のコアはCPUのコアに比べ複雑な計算は出来ない構造であるため単純計算しか出来ない、また一般的にユーザーから GPU 単体に直接命令を書き込むことも出来ないなどの問題点も存在する。 +GPGPU は CPU によって単純計算のTaskを GPU に振り分ける事によって、 GPU の問題点を解決しつつ、高速な並列処理を行うことである。 +また Data Gear へのアクセスは接続された Code Gear からのみであるから、処理中に変数が書き変わる事がない。 図\ref{fig:gpgpu}では以下の流れで処理が行われる。 \begin{itemize} \item Data Gear をPersistent Data Tree に挿入。 @@ -279,7 +213,7 @@ \begin{figure}[ht] \centering - \includegraphics[width=90mm]{pic/gearsosgpgpu.pdf} + \includegraphics[width=90mm]{pic/gearsos.pdf} \caption{Gears OS による GPGPU} \label{fig:gpgpu} \end{figure} @@ -287,8 +221,8 @@ % CPUからGPUにTaskを振り分ける図があってもいい \section{CUDAでの実行} -%CMakeの話を入れるならここかな -CUDAで処理を行うには +%CUDAの説明 +CUDA とは NVIDIA が提供している並列コンピューティングアーキテクチャで %helper_cuda.h cmakeは一つの言語のコンパイルしか出来ない、CbCはC言語としてコンパイル出来るが、C++の言語がCUDAのhelper_cuda.hなどには含まれる。 \chapter{GPU 実装} @@ -296,6 +230,11 @@ \section{GPUWoker の実装} %そもそも実装してない？ %実装したって言えるのはtwiceとかのCudaExsampleをGPUで動かすことが出来るってだけで、WorkerによってTaskManagmentしてるとは言えないのでは？ + +\section{CUDATwiceの実装} + +\section{CMake} + \section{性能評価} \section{比較} diff -r e4c33c7f162f -r 094f2573edf1 paper/main.toc --- a/paper/main.toc Tue Feb 14 18:58:18 2017 +0900 +++ b/paper/main.toc Wed Feb 15 05:27:08 2017 +0900 @@ -1,27 +1,24 @@ \contentsline {chapter}{\numberline {第1章}GearsOSでのGPU実行}{1} -\contentsline {chapter}{\numberline {第2章}概要}{2} -\contentsline {section}{\numberline {2.1}Cudaの例題}{2} -\contentsline {section}{\numberline {2.2}GPUプログラミングの問題点}{2} -\contentsline {section}{\numberline {2.3}Meta計算によるGPU並列実行の制御}{2} -\contentsline {chapter}{\numberline {第3章}GearsOS}{3} -\contentsline {section}{\numberline {3.1}Continuation Baseed C}{3} -\contentsline {section}{\numberline {3.2}並列性}{3} -\contentsline {section}{\numberline {3.3}柔軟性}{4} -\contentsline {section}{\numberline {3.4}Gears でのMeta computation の実行}{4} -\contentsline {chapter}{\numberline {第4章}Gears OSの構成}{5} -\contentsline {section}{\numberline {4.1}Queue}{5} -\contentsline {section}{\numberline {4.2}Red Black Tree}{5} -\contentsline {section}{\numberline {4.3}TaskManager}{6} -\contentsline {section}{\numberline {4.4}Worker}{7} -\contentsline {chapter}{\numberline {第5章}GPGPU}{8} -\contentsline {section}{\numberline {5.1}GPGPUとは}{8} -\contentsline {section}{\numberline {5.2}CUDAでの実行}{9} -\contentsline {chapter}{\numberline {第6章}GPU 実装}{10} -\contentsline {section}{\numberline {6.1}GPUWoker の実装}{10} -\contentsline {section}{\numberline {6.2}性能評価}{10} -\contentsline {section}{\numberline {6.3}比較}{10} -\contentsline {chapter}{\numberline {第7章}今後の課題}{11} -\contentsline {section}{\numberline {7.1}GPU並列実行}{11} -\contentsline {chapter}{\numberline {第8章}結論}{12} -\contentsline {section}{\numberline {8.1}まとめ}{12} -\contentsline {section}{\numberline {8.2}今後の課題}{12} +\contentsline {chapter}{\numberline {第2章}GearsOS}{2} +\contentsline {section}{\numberline {2.1}Continuation Baseed C}{2} +\contentsline {section}{\numberline {2.2}Code Gear と Data Gear}{2} +\contentsline {section}{\numberline {2.3}並列性}{3} +\contentsline {section}{\numberline {2.4}柔軟性}{3} +\contentsline {section}{\numberline {2.5}Gears でのMeta computation の実行}{3} +\contentsline {chapter}{\numberline {第3章}Gears OSの構成}{4} +\contentsline {section}{\numberline {3.1}TaskManager}{4} +\contentsline {section}{\numberline {3.2}Worker}{4} +\contentsline {chapter}{\numberline {第4章}GPGPU}{5} +\contentsline {section}{\numberline {4.1}GPGPUとは}{5} +\contentsline {section}{\numberline {4.2}CUDAでの実行}{6} +\contentsline {chapter}{\numberline {第5章}GPU 実装}{7} +\contentsline {section}{\numberline {5.1}GPUWoker の実装}{7} +\contentsline {section}{\numberline {5.2}CUDATwiceの実装}{7} +\contentsline {section}{\numberline {5.3}CMake}{7} +\contentsline {section}{\numberline {5.4}性能評価}{7} +\contentsline {section}{\numberline {5.5}比較}{7} +\contentsline {chapter}{\numberline {第6章}今後の課題}{8} +\contentsline {section}{\numberline {6.1}GPU並列実行}{8} +\contentsline {chapter}{\numberline {第7章}結論}{9} +\contentsline {section}{\numberline {7.1}まとめ}{9} +\contentsline {section}{\numberline {7.2}今後の課題}{9} diff -r e4c33c7f162f -r 094f2573edf1 paper/pic/gearsos.pdf Binary file paper/pic/gearsos.pdf has changed