# HG changeset patch # User Tatsuki IHA # Date 1492759533 -32400 # Node ID dc651be5dd346750cfcae3675a2207f3ea7e784a # Parent 439d6ddac552bb9eea1bbe82e778eb9ca1017b17 Update diff -r 439d6ddac552 -r dc651be5dd34 paper/pic/dependency.graffle Binary file paper/pic/dependency.graffle has changed diff -r 439d6ddac552 -r dc651be5dd34 paper/pic/dependency.pdf Binary file paper/pic/dependency.pdf has changed diff -r 439d6ddac552 -r dc651be5dd34 paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 439d6ddac552 -r dc651be5dd34 paper/sigos.tex --- a/paper/sigos.tex Fri Apr 21 09:23:31 2017 +0900 +++ b/paper/sigos.tex Fri Apr 21 16:25:33 2017 +0900 @@ -63,10 +63,10 @@ } % 連絡先（投稿時に必要．製版用では無視される．） -\contact{東恩納 琢偉\\ - 〒903-0213 沖縄県西原町千原1番地\\ - 琉球大学工学部情報工学科\\ - TEL: (098)895-2221\qquad FAX: (098)895-8727\\ +\contact{東恩納 琢偉 + 〒903-0213 沖縄県西原町千原1番地 + 琉球大学工学部情報工学科 + TEL: (098)895-2221\qquad FAX: (098)895-8727 email: ikkun@cr.ie.u-ryukyu.ac.jp} % 和文概要 @@ -90,10 +90,10 @@ % Introduce \section{Continuation Based C} -Gears OS の実装は本研究室で開発している CbC(Continuation based C)を用いて行われている。\\ +Gears OS の実装は本研究室で開発している CbC(Continuation based C)を用いて行われている。 CbC は処理を Code Segment を用いて分割して記述することを基本としている。 Gears OS の Code Gear はCbCを元に記述されている。 -CbC のプログラムでは C の関数の単位で Code Segment を用いて分割し、処理を記述している。\\ +CbC のプログラムでは C の関数の単位で Code Segment を用いて分割し、処理を記述している。 Code Segment は C の関数と異なり戻り値を持たない。 Code Segment の宣言は C の関数の構文と同様に行い、 型に \_\_code を使い宣言している。 Code Segment から Code Segment への移動は goto の後に移動先の Code Segment 名と引数を並べた記述する構文を用いて行う。 @@ -129,9 +129,9 @@ \newpage \section{並列性} -Code Gear が処理するのに必要な Input Data Gear と処理の実行後に出力される Output Data Gear の組を Task と呼び、Data Gear の入出力関係は Input Data Gear とOutput Data Gear によって表せられるため、図\ref{src:codeGeardataGear}のようになっており、Code Gear を実行するのに必要なデータの依存関係を明確にする。\\ +Code Gear が処理するのに必要な Input Data Gear と処理の実行後に出力される Output Data Gear の組を Task と呼び、Data Gear の入出力関係は Input Data Gear とOutput Data Gear によって表せられるため、図\ref{src:codeGeardataGear}のようになっており、Code Gear を実行するのに必要なデータの依存関係を明確にする。 また、依存関係の無い Code Gear は自動で並列に実行される。 -並列実行の際にはMeta Code Gear で記述された Task を Worker に投げることで行われる。\\ +並列実行の際にはMeta Code Gear で記述された Task を Worker に投げることで行われる。 \begin{figure}[ht] \begin{center} @@ -144,13 +144,13 @@ \section{柔軟性} %プログラムの処理が Gearという単位で分けられて記述されているって言うけど、プログラムの処理ってなに？という疑問を持つのが一般的だと思われ -G通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。\\ +G通常の処理を Computation、 Computation のための Computation を Meta Computation として扱う。 例として、 Code Gear が次に実行する Code Gear を goto で名前指定する。 この継続処理に対してMeta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。 これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対応する。 名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。 この Meta Data Gear を Context と呼び、これは従来の OS の Process や Thread を表す構造体に対応する。 -Meta Computation を使用することで以下のことが可能になる。\\ +Meta Computation を使用することで以下のことが可能になる。 \begin{itemize} \item 元の計算を保存したデータ拡張や機能の追加 \item GPU 等のさまざまなアーキテクチャでの動作 @@ -169,35 +169,50 @@ \newpage %図で言うよりも goto の説明をしたほうがわかりやすいかも、gotoがどういったものでどういう事に使われているのか、これがわかればわかるのでは？ -\chapter{GearsOSの構成} +\section{GearsOSの構成} %去年のOS研究会で構成については発表しているので、この辺はまとめてよ %い -\section{TaskManager} -Gears OS の TaskManager は WaitTaskQueue に入っている Task の依存関係を解決する。\\ -Task には Input/Output Data Gear の情報が格納されている。 -Input Data Gear は Task に必要な Data Gear で揃ったら Task は実行可能な状態になる。 -Output Data Gear は Task が Persistent Data Tree に書き出す Data Gear である。 -この Input と Output の関係が依存関係となる。\\ -TaskManager は Persistent Data Tree を監視しており、WaitTaskQueue に入っている Task の Input Data Gear が揃っているのを確認したら実行可能な Task として AcitiveTaskQueue へ移動させる。\\ -\section{Worker} -Worker は TaskQueue から Task を取得し、実行する。 -Task には実行する Code Gear と実行に必要な Code Gear の key が格納されている。 -実行に必要な Code Gear は Persistent Data Tree から key を使って取得する。\\ +Gears OS の以下の要素で並列処理を行う。 + +\begin{itemize} + \item Context(Task) + \item TaskManager + \item Worker +\end{itemize} + +Gears OS では、 Context という Meta Data Gear を通して Code Gear と Data Gear の接続を行う。 +また、 並列実行を行う際はこの Context を生成し、それを Task として実行する。 +そのため、 Context は 接続に必要な Code/Data Gear のリスト、 Data Gear を確保するためのメモリ空間、 実行する Code Gear、 Code Gear の実行に必要な Input Data Gear のカウンタ等をもっている。 + +TaskManager は Task、 Worker の生成、 Worker に 実行する Task を送信を行う。 +また、 生成した Worker の終了処理等を行う。 + +Worker は thread と 実行するTaskが入っているQueueを持っている。 +Worker は TaskManager から送信された Task を Queue から取り出し、Code Gear, Input Data Gear を取り出し、 Code Gearを実行する。 +Code Gear を実行した後は出力される Output Data Gear から依存関係を解決する。 -各 Worker は個別の Context を参照しており、 メモリ空間も独立しているのでメモリを確保する処理で他の Thread を止めることはない。 -ただし、Persistent Data Tree への書き出しは競合する可能性があるので CAS を利用してデータの一貫性を保証する必要がある。\\ -Worker が TaskQueue から Task の取得を行う Code Gear を Code \ref{src:sync_dequeue} に示す。 -Task Queue から取得した Task から実行する Code Gear と必要な Data Gear の key を Worker Context に書き込むことで実行される。\\ -Worker から取得された Task の Code Gear は並列実行される。 -並列実行される Code Gear と言っても他の Code Gear と同じである。 -これは Gears OS 自体が Code Gear によって構成されていることに起因する。 -つまり、 Gears OS を利用して書かれたプログラムで定義されている Code Gear に依存関係がないとき、全て並列に実行することができる。\\ +Gears OS の並列処理の構成を図\ref{fig:gears_structure}に示す。 +%\lstinputlisting[label=src:sync\_dequeue, caption=sync\_dequeue.c]{./src/sync\_dequeue.c} + +\section{並列処理の依存関係の解決} +Gears OS の並列処理の依存関係の解決は Data Gear に依存関係解決のための Queue をもたせることで行う。 +Queue にはその Data Gear を Input Data Gear として使用する Task(Context) が入っている。 +依存関係の解決の流れは図\ref{fig:dependency} に示す。 +Worker は Task の Code Gear を実行後、 書き出された Output Data Gear の Queue から, 依存関係にある Task を参照する。 +参照した Task には 実行に必要な Input Data Gear のカウンタをもっているので、そのカウンタのデクリメントを行う。 +カウンタが $0$ になったら Task が待っている Data Gear が揃ったことになるので、その Task を Worker に送信する。 -\lstinputlisting[label=src:sync\_dequeue, caption=sync\_dequeue.c]{./src/sync\_dequeue.c} -\chapter{GPGPU} -\section{GPGPUとは} -GPGPU とは、元々は画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術の事である。\\ -画像の編集はピクセル毎に行われるため多大な数の処理を行う必要があるが、 GPU は CPU に比べコア数が多数あり、多数のコアで同時に計算することによって CPU よりも多数の並列な処理を行う事が出来る。\\ +\begin{figure}[ht] + \begin{center} + \includegraphics[width=70mm]{pic/dependency} + \end{center} + \caption{依存関係の解決} + \label{fig:dependency} +\end{figure} + +\section{GPGPU} +GPGPU とは、元々は画像出力や画像編集などの画像処理に用いられるGPUを画像処理以外に利用する技術の事である。 +画像の編集はピクセル毎に行われるため多大な数の処理を行う必要があるが、 GPU は CPU に比べコア数が多数あり、多数のコアで同時に計算することによって CPU よりも多数の並列な処理を行う事が出来る。 これによってGPUは画像処理のような多大な処理を並列処理することで、 CPU で処理するよりも高速に並列処理することが出来る。 しかし、GPU のコアはCPUのコアに比べ複雑な計算は出来ない構造であるため単純計算しか出来ない、また一般的にユーザーから GPU 単体に直接命令を書き込むことも出来ないなどの問題点も存在する。 GPGPU は CPU によって単純計算のTaskを GPU に振り分ける事によって、 GPU の問題点を解決しつつ、高速な並列処理を行うことである。 @@ -205,8 +220,7 @@ 図\ref{fig:gpgpu}では以下の流れで処理が行われる。 \begin{itemize} \item Data Gear をPersistent Data Tree に挿入。 -\item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTas\ - k を生成。 +\item TasMannagerで実行する Code Gear と実行に必要な Data Gear へのKeyを持つTask を生成。 \item 生成したTaskをTaskQueueに挿入。 \item Workerの起動。 \item WorkerがTskQueueからTaskを取得。 @@ -223,44 +237,44 @@ \newpage % CPUからGPUにTaskを振り分ける図があってもいい -\section{CUDAとは} +\section{CUDA} %CUDAの説明 -CUDA とは NVIDIA 社が提供している並列コンピューティング用の統合開発環境で、コンパイラ、ライブラリなどの並列コンピューティングを行うのに必要なサポートを提供している。\\ -一般的にも広く使われているGPUの開発環境である。\\ -Task(kernel) は .ptx という GPU用のアセンブラに変換され、プログラム内部から直接kernel を呼び出す構文を持つ API である。さらにメモリ転送と kernel 呼び出しを自分で制御する DriverAPI の2種類をもつ。\\ +CUDA とは NVIDIA 社が提供している並列コンピューティング用の統合開発環境で、コンパイラ、ライブラリなどの並列コンピューティングを行うのに必要なサポートを提供している。 +一般的にも広く使われているGPUの開発環境である。 +Task(kernel) は .ptx という GPU用のアセンブラに変換され、プログラム内部から直接kernel を呼び出す構文を持つ API である。さらにメモリ転送と kernel 呼び出しを自分で制御する DriverAPI の2種類をもつ。 %helper_cuda.h cmakeは一つの言語のコンパイルしか出来ない、CbCはC言語としてコンパイル出来るが、C++の言語がCUDAのhelper_cuda.hなどには含まれる。 -\chapter{GPU実装} \section{CPUWoker} %そもそも実装してない？ %実装したって言えるのはtwiceとかのCudaExsampleをGPUで動かすことが出来るってだけで、WorkerによってTaskManagmentしてるとは言えないのでは？ -Worker thread で動くTaskスケジューラーである。\\ +Worker thread で動くTaskスケジューラーである。 synchronized queue からTaskのListを読み込み実行する。 Data Gear の待ち合わせの管理を行う。 CPUWorkerはreceive Task というAPIを持ち、Taskがなくなるまで繰り返す。 + \section{CUDAWorkerの実装} -CPUWorkerを再利用して作成するTaskスケジューラー。\\ -CUDAライブラリの初期化を行う以外の動作はCUDAWorker と全く同じになる。\\ -GPUへのデータ転送及びGPU側でのTaskの実行はTaskのMeta Code Gear で行われる。\\ +CPUWorkerを再利用して作成するTaskスケジューラー。 +CUDAライブラリの初期化を行う以外の動作はCUDAWorker と全く同じになる。 +GPUへのデータ転送及びGPU側でのTaskの実行はTaskのMeta Code Gear で行われる。 -\lstinputlisting[label=code_Gear&DataGear, caption=code_Gear&DataGear]{src/CUDAWorker.cbc} +\lstinputlisting[label=CUDAWorker, caption=CUDAWorker]{src/CUDAWorker.cbc} \newpage \section{CMake} -CMake はビルド自動化ツールであり、プログラムをコンパイル行う際にライブラリや動作環境によって様々な設定を行う必要がありますが、 CMake にはそれらのファイルやライブラリを探し出して実行することが出来ます。\\ +CMake はビルド自動化ツールであり、プログラムをコンパイル行う際にライブラリや動作環境によって様々な設定を行う必要がありますが、 CMake にはそれらのファイルやライブラリを探し出して実行することが出来ます。 CMake のビルドは2段階からなり、 CMake の制御ファイルの CMakeList.txt によってビルドするファイルを指定でき、指定されたファイルをビルドする際にはまずビルドに必要なライブラリやファイルを探し、通常のビルド環境用のビルドファイルを作成し、次にビルドするファイルにあったビルドを行います。 -CMake は Windows や Linux 等、複数のOS の環境に対応している他、様々なコンパイルオプションがあり、クロスコンパイルや、ユーザーがコンパイルのルールを追加することで特殊なコンパイラや OS にも対応することが出来る。\\ -Code Gear/Data Gear による GPGPU 処理の実装には CUDA専用コンパイラである nvcc とCode Gear　Data Gear のコンパイルを両立させる必要があるが、CMake は同時に1つのコンパイラしか扱えない。\\ -\verb |add_costom_command|を使うことで CUDA のコンパイラ nvcc を呼び出し、マクロを用いて、Code Gear Data Gear のコンパイルを両立させた。\\ +CMake は Windows や Linux 等、複数のOS の環境に対応している他、様々なコンパイルオプションがあり、クロスコンパイルや、ユーザーがコンパイルのルールを追加することで特殊なコンパイラや OS にも対応することが出来る。 +Code Gear/Data Gear による GPGPU 処理の実装には CUDA専用コンパイラである nvcc とCode Gear　Data Gear のコンパイルを両立させる必要があるが、CMake は同時に1つのコンパイラしか扱えない。 +\verb |add_costom_command|を使うことで CUDA のコンパイラ nvcc を呼び出し、マクロを用いて、Code Gear Data Gear のコンパイルを両立させた。 -\lstinputlisting[label=code_Gear&DataGear, caption=code_Gear&DataGear]{src/CMakeLists.txt} +\lstinputlisting[label=CMake, caption=CMake]{src/CMakeLists.txt} %今後の課題 -\chapter{結論} +\section{結論} \section{まとめ} Code Gear Data Gear を用いてCUDAを利用した並列処理プログラムを記述した。 -CUDA専用のコンパイラの nvcc と Code Gear Data Gear のコンパイラをCMakeを用いる事\\ +CUDA専用のコンパイラの nvcc と Code Gear Data Gear のコンパイラをCMakeを用いる事 で両立させた。 Gears OSでのGPUの基本的な実行を確認することができた \section{今後の課題}