Mercurial > hg > Papers > 2018 > parusu-master

changeset 16:77c129874cfa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
UPdate
author Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date Sat, 27 Jan 2018 17:13:05 +0900
parents 7b64596f5964
children 1d1b6eacac0a
files paper/fig/sendTask.graffle paper/fig/sendTask.pdf paper/fig/sendTask.xbb paper/gearsOS.tex paper/master_paper.pdf paper/parallelism_gears.tex paper/reference.bib
diffstat 7 files changed, 72 insertions(+), 13 deletions(-) [+]
line wrap: on
line diff
Binary file paper/fig/sendTask.graffle has changed
Binary file paper/fig/sendTask.pdf has changed
--- a/paper/fig/sendTask.xbb	Wed Jan 24 03:52:00 2018 +0900
+++ b/paper/fig/sendTask.xbb	Sat Jan 27 17:13:05 2018 +0900
@@ -1,8 +1,8 @@
 %%Title: fig/sendTask.pdf
 %%Creator: extractbb 20170318
-%%BoundingBox: 0 0 1028 162
-%%HiResBoundingBox: 0.000000 0.000000 1028.000000 162.000000
+%%BoundingBox: 0 0 1043 171
+%%HiResBoundingBox: 0.000000 0.000000 1043.000000 171.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Jan 21 06:07:39 2018
+%%CreationDate: Thu Jan 25 15:41:12 2018
 
--- a/paper/gearsOS.tex	Wed Jan 24 03:52:00 2018 +0900
+++ b/paper/gearsOS.tex	Sat Jan 27 17:13:05 2018 +0900
@@ -30,7 +30,7 @@
 \end{figure}
 
 \section{Continuation based C}
-Gears OS の実装は本研究室で開発されているCbC (Continuation based C) を用いて行う。
+Gears OS の実装は本研究室で開発されている CbC(Continuation based C) を用いて行う。
 CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。
 CbC の処理系として llvm/clang\cite{kaito-lola} と gcc\cite{nobu-prosym} による実装などが存在する。
 
@@ -38,12 +38,12 @@
 CbC の Code Gear は \_\_code という型を持つ関数として記述する。
 Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。
 そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。
-Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear への引数として入出力を与える。
+Code Gear から次の Code Gear への遷移は goto 文による継続で処理を行い、次の Code Gear への引数として入出力を与える。
 \coderef{cg1}内の goto cg1 (a+b); が継続にあたり、 (a+b) がcg1 への入力になる。
 
 \lstinputlisting[caption=CodeSegmentの軽量継続, label=code:cg1]{./src/cg1.cbc}
 
-CbC の goto による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。
+CbC の goto 文による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。
 この継続を軽量継続と呼ぶ。
 \coderef{cg1} は cs0 から cs1 へ継続したあとには cs0 へ戻らずに処理を続ける。
 
@@ -51,7 +51,7 @@
     \begin{center}
         \includegraphics[scale=1.0]{./fig/goto.pdf}
     \end{center}
-    \caption{goto による Code Gearの軽量継続}
+    \caption{goto 文による Code Gearの軽量継続}
     \label{fig:cg1}
 \end{figure}
 
Binary file paper/master_paper.pdf has changed
--- a/paper/parallelism_gears.tex	Wed Jan 24 03:52:00 2018 +0900
+++ b/paper/parallelism_gears.tex	Sat Jan 27 17:13:05 2018 +0900
@@ -1,6 +1,14 @@
 \chapter{Gears OSの並列処理}
 \section{並列処理の構成}
 
+\section{Task}
+Gears OS の Task は Context で表現される。
+Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている。
+
+実行される Code Gear の例を \coderef{codeGearExample} に示す。
+
+\lstinputlisting[caption=並列実行される Code Gear の例, label=code:codeGearExample]{./src/codeGearExample.cbc}
+
 \section{TaskManager}
 Gears OS の TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。
 \coderef{taskManagerInterface} に TaskManager の Interface を示す。
@@ -137,7 +145,7 @@
 この破綻は末尾の要素が必ず末尾を示していると仮定しているためである。
 しかし、データ挿入の際は2度の CAS の間に他のスレッドが割り込む場合がある。
 そこで、末尾の要素は必ずしも末尾を示さないと仮定して要素の取出しと挿入の処理を記述する。
-\coderef{putSynchronizedQueue} が要素の挿入の処理の一部である。
+\coderef{putSynchronizedQueue} は要素の挿入の処理の一部である。
 末尾の要素が末尾を示さない場合の処理は\coderef{putSynchronizedQueue} の 13-16 行目に記述している。
 変数 nextElement は 末尾要素の次の要素を示しており、NULL ではない場合は末尾を差していない状態ということになる。
 その場合は、末尾の要素をnextElement に CAS を行う。
@@ -146,6 +154,41 @@
 \lstinputlisting[caption=SynchronizedQueue による要素の挿入, label=code:putSynchronizedQueue]{./src/putSynchronizedQueue.cbc}
 
 \section{依存関係の解決}
-\section{並列処理の記述}
-\section{Iterator}
+Gears OS は並列処理の依存関係を Input と Output の Data Gear と Code Gear の関係で解決する。
+Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。
+
+Data Gear は メタレベルで 依存関係解決のための Queue を持っている。
+この Queue にはその Data Gear を Input Data Gear として使用する Task(Context)が入っている。
+
+依存関係の解決の流れを\figref{dependency} に示す。
+Worker は Task の Code Gear を実行後、Output Data Gear の 書き出し処理を行う。
+書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。
+参照した Task には実行に必要な Input Data Gear のカウンタをもっているので、そのカウンタのデクリメントを行う。
+カウンタが $0$ になったら Task が待っている Input Data Gear が揃ったことになるので、その Task を TaskManager 経由で 実行される Worker に送信する。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.6]{./fig/dependency.pdf}
+    \end{center}
+    \caption{依存関係の解決処理}
+    \label{fig:dependency}
+\end{figure}
+
+\section{並列構文}
+Gears OS では並列実行する Task の設定をメタレベルで \coderef{metaCreateTask} のように行っている。
+\coderef{metaCreateTask} では実行する Code Gear、待ち合わせ中の Input Data Gear の数、 Input/Output Data Gear への参照等の設定を記述している。
+これらの記述は Context などを含む煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である。
+そこで、 Context を直接用いないノーマルレベルの並列構文である par goto 文を用意した。
+\coderef{parGotoCreateTask}に par goto文による記述例を示す。
+この記述はスクリプトにより、Task で実行される Code Gear の Input/Output の数を解析し、\coderef{metaCreateTask} に変換される。
+
+\lstinputlisting[caption=メタレベルによる Task の生成, label=code:metaCreateTask]{./src/metaCreateTask.cbc}
+\lstinputlisting[caption=par goto による並列実行, label=code:parGotoCreateTask]{./src/parGotoCreateTask.cbc}
+
+par goto で生成された Task は \_\_exit に継続することで終了する。
+Gears OS の Task は Output Data Gear を生成した時点で終了するので、 par goto では直接 \_\_exit に継続するのではなく、Output Data Gear への書き出し処理に継続される。
+これにより Code Gear と Data Gear の依存関係をノーマルレベルで記述できるようになる。
+
 \section{待ち機構}
+
+\section{データ並列}
--- a/paper/reference.bib	Wed Jan 24 03:52:00 2018 +0900
+++ b/paper/reference.bib	Sat Jan 27 17:13:05 2018 +0900
@@ -1,3 +1,21 @@
+@inproceedings{queue,
+    author = {Michael, Maged M. and Scott, Michael L.},
+    title = {Simple, Fast, and Practical Non-blocking and Blocking Concurrent Queue Algorithms},
+    booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing},
+    series = {PODC '96},
+    year = {1996},
+    isbn = {0-89791-800-2},
+    location = {Philadelphia, Pennsylvania, USA},
+    pages = {267--275},
+    numpages = {9},
+    url = {http://doi.acm.org/10.1145/248052.248106},
+    doi = {10.1145/248052.248106},
+    acmid = {248106},
+    publisher = {ACM},
+    address = {New York, NY, USA},
+    keywords = {compare_and_swap, concurrent queue, lock-free, multiprogramming, non-blocking},
+} 
+
 @article{moggi-monad,
     author     = {Moggi, Eugenio},
     title      = {Notions of Computation and Monads},
@@ -23,7 +41,6 @@
     booktitle = "第53回プログラミング・シンポジウム予稿集",
     year  = "2012",
     volume = "2012",
-    number = "",
     pages = "69--78",
     month = "jan"
 }
@@ -34,8 +51,7 @@
     booktitle = "第59回プログラミング・シンポジウム予稿集",
     year  = "2018",
     volume = "2018",
-    number = "",
-    pages = "69--78",
+    pages = "197--206",
     month = "jan"
 }