# HG changeset patch # User Tatsuki IHA # Date 1517401543 -32400 # Node ID bc7ea5774f6b4bca0455d576d3d5701eeecbf6ba # Parent 9d2a0a73598683c7b27f487dd71a8b2b2ed0d009 Add dataparallel section diff -r 9d2a0a735986 -r bc7ea5774f6b paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 9d2a0a735986 -r bc7ea5774f6b paper/parallelism_gears.tex --- a/paper/parallelism_gears.tex Tue Jan 30 07:00:42 2018 +0900 +++ b/paper/parallelism_gears.tex Wed Jan 31 21:25:43 2018 +0900 @@ -13,7 +13,7 @@ \section{Task} Gears OS では 並列実行する Task を Context で表現する。 Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている。 -Task は Input Data Gear が揃っているかを TaskManager で判断し、Worker に送信される。 +Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を Worker に送信する。 Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。 実行される Code Gear の例を \coderef{codeGearExample} に示す。 @@ -220,3 +220,38 @@ \section{待ち機構} \section{データ並列} +並列プログラミングを行う際、並列化の方式としてタスク並列とデータ並列の2つがある。 +Gears OS の並列処理は Task(Context) を使用したタスク並列により実現されている。 + +タスク並列は処理をタスクに分割し、各タスク間に依存関係のないものを集め、それを並列化する。 +Gears OS では依存関係を Input/Output Data Gear から解析を行い、依存関係が解決された Code Gear から実行される。 +一方でデータ並列は処理対象のデータが十分な数のサブデータへ分割することが可能で、各サブデータに行う処理が同じ場合に有効な並列処理手法である。 +このデータ並列は GPGPU と相性が良く、ヘテロジニアスな環境でも実行できる Gears OS でもサポートを行った。 + +Gears OS でデータ並列実行を行う場合、\coderef{iteratePargoto} のようにpar goto 文の引数にデータ並列用の構文として iterate を入れて実行する。 +iterate は複数の数値を引数とし、数値の値がデータの分割数、数値の個数が次元数になる。 + +\lstinputlisting[caption=par goto によるデータ並列, label=code:iteratePargoto]{./src/iteratePargoto.cbc} + +Gears OS は データ並列用の par goto を実行した場合、 データ並列用に Task が生成される。 +この Task には \coderef{iteratorInterface} の Iterator Interface を実装した Data Gear を持たせる。 +このデータ並列用の Task は Input Data Gear が揃うまでは通常の Task 同等として扱う。 +依存関係が解決され、実行可能な Task になった際に、 Iterator Interface の exec を呼ぶ。 +exec では par goto で渡された次元、数値分 Task を コピーし、インデックスを割り当てる処理を行う。 +この index は コピーされた Task の Input Data Gear として扱われ、Code Gear 内では通常の Data Gear として利用される。 +\coderef{iterateTaskExec} は1次元で 数値$4$ を渡した場合の Task 実行を示している。 +コピーされた Task は通常の Task と同じように TaskManager を通して Worker に送信される。 + +\lstinputlisting[caption=Iterator Interface の定義, label=code:iteratorInterface]{./src/iteratorInterface.h} + +\begin{figure}[htbp] + \begin{center} + \includegraphics[scale=0.6]{./fig/iterateTaskExec.pdf} + \end{center} + \caption{1次元、数値$4$のデータ並列用 Task の実行} + \label{fig:iterateTaskExec} +\end{figure} + +通常の Task であれば、実行後に Output Data Gear を書き出す処理に入るが、 データ並列用の Task はコピーされた全てのTask 実行後に Output Data Gear の書き出しを行う。 +その判断と処理を行うのが Iterator Interface の barrier である。 +barrier は コピーされた Task 実行後に呼ばれ、Output Data Gear が書き出せる状態なら書き出し処理を行う Code Gear に継続し、書き出せる状態でないなら Worker に操作を移譲するCode Gear に継続する。