Mercurial > hg > Papers > 2018 > parusu-master

--- a/paper/evaluation.tex	Sat Feb 10 04:33:50 2018 +0900
+++ b/paper/evaluation.tex	Sun Feb 11 12:53:53 2018 +0900
@@ -82,8 +82,8 @@
 1 CPU と 32 CPU では 約 27.1 倍の速度向上が見られた。
 ある程度の台数効果があると考えられる。

-GPU での実行は kernel のみの実行時間は 32CPU に比べて 約 7.2 倍の実行向上が見られた。
-しかし、通信時間を含めると 16CPU より遅い結果となってしまった。
+GPU での実行は kernel のみの実行時間は 32 CPU に比べて 約 7.2 倍の速度向上が見られた。
+しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。
 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。

 \section{BitonicSort}
--- a/paper/fig/WorkerRun.xbb	Sat Feb 10 04:33:50 2018 +0900
+++ b/paper/fig/WorkerRun.xbb	Sun Feb 11 12:53:53 2018 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 824.000000 309.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  4 22:16:26 2018
+%%CreationDate: Sun Feb 11 03:40:43 2018
--- a/paper/gpu.tex	Sat Feb 10 04:33:50 2018 +0900
+++ b/paper/gpu.tex	Sun Feb 11 12:53:53 2018 +0900
@@ -85,11 +85,12 @@

 % 少ないけどコードはなるべく載せたくない(メタ部分 + 複雑)
 \section{stub Code Gear による kernel の実行}
-Gears OS では stub Code Gear で CUDA による実行の切り替える。
+Gears OS では stub Code Gear で CUDA による実行を切り替える。

 stub Code Gear での切り替えの際は CUDABuffer への Data の格納、実行される kernel の読み込みを行う。
 実際に GPU で実行されるプログラムは \coderef{cudaTwice} のように記述する。

 \lstinputlisting[caption=配列の要素を二倍にする例題, label=code:cudaTwice]{./src/cudaTwice.cu}

-stub Code Gear は通常はその stub に対応した Code Gear に継続するが、 CUDA で実行する際は CUDAExectuor の Code Gear に継続する。
+通常、stub Code Gear は対応した Code Gear に継続するが、CUDA で実行する際は CUDAExectuor の Code Gear に継続する。
+
Binary file paper/master_paper.pdf has changed
Binary file slide/images/workerRun.graffle has changed
Binary file slide/images/workerRun.pdf has changed
--- a/slide/images/workerRun.svg	Sat Feb 10 04:33:50 2018 +0900
+++ b/slide/images/workerRun.svg	Sun Feb 11 12:53:53 2018 +0900
@@ -1,5 +1,5 @@
 <?xml version="1.0" encoding="UTF-8"?>
-<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="824pt" height="309pt" viewBox="0 0 824 309" version="1.1">
+<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="824pt" height="395pt" viewBox="0 0 824 395" version="1.1">
 <defs>
 <g>
 <symbol overflow="visible" id="glyph0-0">
@@ -212,7 +212,7 @@
 </g>
 </defs>
 <g id="surface1">
-<rect x="0" y="0" width="824" height="309" style="fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;"/>
+<rect x="0" y="0" width="824" height="395" style="fill:rgb(100%,100%,100%);fill-opacity:1;stroke:none;"/>
 <path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 99 204.175781 L 150.460938 204.175781 L 150.460938 236.171875 L 99 236.171875 Z M 99 204.175781 " transform="matrix(1,0,0,1,-87,-146)"/>
 <path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 150.460938 204.175781 L 201.921875 204.175781 L 201.921875 236.171875 L 150.460938 236.171875 Z M 150.460938 204.175781 " transform="matrix(1,0,0,1,-87,-146)"/>
 <path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 201.921875 204.175781 L 253.382812 204.175781 L 253.382812 236.171875 L 201.921875 236.171875 Z M 201.921875 204.175781 " transform="matrix(1,0,0,1,-87,-146)"/>
@@ -462,89 +462,89 @@
   <use xlink:href="#glyph2-12" x="664.1343" y="208.2414"/>
   <use xlink:href="#glyph2-13" x="666.7983" y="208.2414"/>
 </g>
-<path style="fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 370.457031 230.074219 L 370.054688 441 L 736.34375 441 L 736.34375 367.015625 " transform="matrix(1,0,0,1,-87,-146)"/>
-<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 370.46875 222.074219 L 367.457031 230.070312 L 373.457031 230.082031 Z M 370.46875 222.074219 " transform="matrix(1,0,0,1,-87,-146)"/>
+<path style="fill:none;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 370.460938 230.074219 L 370.054688 526.824219 L 736.34375 526.824219 L 736.34375 367.015625 " transform="matrix(1,0,0,1,-87,-146)"/>
+<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 370.472656 222.074219 L 367.460938 230.070312 L 373.460938 230.078125 Z M 370.472656 222.074219 " transform="matrix(1,0,0,1,-87,-146)"/>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-34" x="378.5724" y="252.63834"/>
-  <use xlink:href="#glyph0-14" x="387.4684" y="252.63834"/>
-  <use xlink:href="#glyph0-15" x="391.9164" y="252.63834"/>
-  <use xlink:href="#glyph0-6" x="396.3644" y="252.63834"/>
-  <use xlink:href="#glyph0-7" x="407.9164" y="252.63834"/>
-  <use xlink:href="#glyph0-8" x="417.1004" y="252.63834"/>
-  <use xlink:href="#glyph0-9" x="425.9964" y="252.63834"/>
-  <use xlink:href="#glyph0-10" x="431.0364" y="252.63834"/>
-  <use xlink:href="#glyph0-11" x="439.6284" y="252.63834"/>
-  <use xlink:href="#glyph0-9" x="447.9164" y="252.63834"/>
-  <use xlink:href="#glyph0-15" x="452.9564" y="252.63834"/>
-  <use xlink:href="#glyph0-3" x="457.4044" y="252.63834"/>
-  <use xlink:href="#glyph0-22" x="465.4044" y="252.63834"/>
-  <use xlink:href="#glyph0-23" x="477.5324" y="252.63834"/>
-  <use xlink:href="#glyph0-9" x="481.0844" y="252.63834"/>
-  <use xlink:href="#glyph0-24" x="486.1244" y="252.63834"/>
-  <use xlink:href="#glyph0-25" x="494.7164" y="252.63834"/>
+  <use xlink:href="#glyph0-34" x="350" y="331.828"/>
+  <use xlink:href="#glyph0-14" x="358.896" y="331.828"/>
+  <use xlink:href="#glyph0-15" x="363.344" y="331.828"/>
+  <use xlink:href="#glyph0-6" x="367.792" y="331.828"/>
+  <use xlink:href="#glyph0-7" x="379.344" y="331.828"/>
+  <use xlink:href="#glyph0-8" x="388.528" y="331.828"/>
+  <use xlink:href="#glyph0-9" x="397.424" y="331.828"/>
+  <use xlink:href="#glyph0-10" x="402.464" y="331.828"/>
+  <use xlink:href="#glyph0-11" x="411.056" y="331.828"/>
+  <use xlink:href="#glyph0-9" x="419.344" y="331.828"/>
+  <use xlink:href="#glyph0-15" x="424.384" y="331.828"/>
+  <use xlink:href="#glyph0-3" x="428.832" y="331.828"/>
+  <use xlink:href="#glyph0-22" x="436.832" y="331.828"/>
+  <use xlink:href="#glyph0-23" x="448.96" y="331.828"/>
+  <use xlink:href="#glyph0-9" x="452.512" y="331.828"/>
+  <use xlink:href="#glyph0-24" x="457.552" y="331.828"/>
+  <use xlink:href="#glyph0-25" x="466.144" y="331.828"/>
 </g>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-15" x="378.5724" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="383.0204" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="387.4684" y="271.086341"/>
-  <use xlink:href="#glyph0-5" x="391.9164" y="271.086341"/>
-  <use xlink:href="#glyph0-1" x="396.0604" y="271.086341"/>
+  <use xlink:href="#glyph0-15" x="350" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="354.448" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="358.896" y="350.276001"/>
+  <use xlink:href="#glyph0-5" x="363.344" y="350.276001"/>
+  <use xlink:href="#glyph0-1" x="367.488" y="350.276001"/>
 </g>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-2" x="403.4684" y="271.086341"/>
-  <use xlink:href="#glyph0-3" x="412.0604" y="271.086341"/>
-  <use xlink:href="#glyph0-4" x="420.0604" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="428.3644" y="271.086341"/>
-  <use xlink:href="#glyph0-6" x="432.8124" y="271.086341"/>
-  <use xlink:href="#glyph0-7" x="444.3644" y="271.086341"/>
-  <use xlink:href="#glyph0-8" x="453.5484" y="271.086341"/>
-  <use xlink:href="#glyph0-9" x="462.4444" y="271.086341"/>
-  <use xlink:href="#glyph0-10" x="467.4844" y="271.086341"/>
-  <use xlink:href="#glyph0-11" x="476.0764" y="271.086341"/>
-  <use xlink:href="#glyph0-9" x="484.3644" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="489.4044" y="271.086341"/>
-  <use xlink:href="#glyph0-26" x="493.8524" y="271.086341"/>
-  <use xlink:href="#glyph0-27" x="500.0764" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="509.6764" y="271.086341"/>
-  <use xlink:href="#glyph0-17" x="514.1244" y="271.086341"/>
+  <use xlink:href="#glyph0-2" x="374.896" y="350.276001"/>
+  <use xlink:href="#glyph0-3" x="383.488" y="350.276001"/>
+  <use xlink:href="#glyph0-4" x="391.488" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="399.792" y="350.276001"/>
+  <use xlink:href="#glyph0-6" x="404.24" y="350.276001"/>
+  <use xlink:href="#glyph0-7" x="415.792" y="350.276001"/>
+  <use xlink:href="#glyph0-8" x="424.976" y="350.276001"/>
+  <use xlink:href="#glyph0-9" x="433.872" y="350.276001"/>
+  <use xlink:href="#glyph0-10" x="438.912" y="350.276001"/>
+  <use xlink:href="#glyph0-11" x="447.504" y="350.276001"/>
+  <use xlink:href="#glyph0-9" x="455.792" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="460.832" y="350.276001"/>
+  <use xlink:href="#glyph0-26" x="465.28" y="350.276001"/>
+  <use xlink:href="#glyph0-27" x="471.504" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="481.104" y="350.276001"/>
+  <use xlink:href="#glyph0-17" x="485.552" y="350.276001"/>
 </g>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-7" x="528.0284" y="271.086341"/>
-  <use xlink:href="#glyph0-18" x="537.2124" y="271.086341"/>
-  <use xlink:href="#glyph0-4" x="542.5404" y="271.086341"/>
-  <use xlink:href="#glyph0-10" x="550.8444" y="271.086341"/>
-  <use xlink:href="#glyph0-18" x="559.4364" y="271.086341"/>
-  <use xlink:href="#glyph0-15" x="564.7644" y="271.086341"/>
-  <use xlink:href="#glyph0-6" x="569.2124" y="271.086341"/>
-  <use xlink:href="#glyph0-7" x="580.7644" y="271.086341"/>
-  <use xlink:href="#glyph0-8" x="589.9484" y="271.086341"/>
-  <use xlink:href="#glyph0-9" x="598.8444" y="271.086341"/>
-  <use xlink:href="#glyph0-10" x="603.8844" y="271.086341"/>
-  <use xlink:href="#glyph0-11" x="612.4764" y="271.086341"/>
-  <use xlink:href="#glyph0-9" x="620.7644" y="271.086341"/>
-  <use xlink:href="#glyph0-12" x="625.8044" y="271.086341"/>
+  <use xlink:href="#glyph0-7" x="499.456" y="350.276001"/>
+  <use xlink:href="#glyph0-18" x="508.64" y="350.276001"/>
+  <use xlink:href="#glyph0-4" x="513.968" y="350.276001"/>
+  <use xlink:href="#glyph0-10" x="522.272" y="350.276001"/>
+  <use xlink:href="#glyph0-18" x="530.864" y="350.276001"/>
+  <use xlink:href="#glyph0-15" x="536.192" y="350.276001"/>
+  <use xlink:href="#glyph0-6" x="540.64" y="350.276001"/>
+  <use xlink:href="#glyph0-7" x="552.192" y="350.276001"/>
+  <use xlink:href="#glyph0-8" x="561.376" y="350.276001"/>
+  <use xlink:href="#glyph0-9" x="570.272" y="350.276001"/>
+  <use xlink:href="#glyph0-10" x="575.312" y="350.276001"/>
+  <use xlink:href="#glyph0-11" x="583.904" y="350.276001"/>
+  <use xlink:href="#glyph0-9" x="592.192" y="350.276001"/>
+  <use xlink:href="#glyph0-12" x="597.232" y="350.276001"/>
 </g>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-35" x="378.5724" y="289.53434"/>
-  <use xlink:href="#glyph0-14" x="387.4684" y="289.53434"/>
-  <use xlink:href="#glyph0-15" x="391.9164" y="289.53434"/>
-  <use xlink:href="#glyph0-16" x="396.3644" y="289.53434"/>
-  <use xlink:href="#glyph0-7" x="405.5484" y="289.53434"/>
-  <use xlink:href="#glyph0-9" x="414.7324" y="289.53434"/>
-  <use xlink:href="#glyph0-7" x="419.7724" y="289.53434"/>
-  <use xlink:href="#glyph0-15" x="428.9564" y="289.53434"/>
-  <use xlink:href="#glyph0-16" x="433.4044" y="289.53434"/>
-  <use xlink:href="#glyph0-10" x="442.5884" y="289.53434"/>
-  <use xlink:href="#glyph0-9" x="451.1804" y="289.53434"/>
-  <use xlink:href="#glyph0-1" x="456.2204" y="289.53434"/>
+  <use xlink:href="#glyph0-35" x="350" y="368.724"/>
+  <use xlink:href="#glyph0-14" x="358.896" y="368.724"/>
+  <use xlink:href="#glyph0-15" x="363.344" y="368.724"/>
+  <use xlink:href="#glyph0-16" x="367.792" y="368.724"/>
+  <use xlink:href="#glyph0-7" x="376.976" y="368.724"/>
+  <use xlink:href="#glyph0-9" x="386.16" y="368.724"/>
+  <use xlink:href="#glyph0-7" x="391.2" y="368.724"/>
+  <use xlink:href="#glyph0-15" x="400.384" y="368.724"/>
+  <use xlink:href="#glyph0-16" x="404.832" y="368.724"/>
+  <use xlink:href="#glyph0-10" x="414.016" y="368.724"/>
+  <use xlink:href="#glyph0-9" x="422.608" y="368.724"/>
+  <use xlink:href="#glyph0-1" x="427.648" y="368.724"/>
 </g>
 <g style="fill:rgb(0%,0%,0%);fill-opacity:1;">
-  <use xlink:href="#glyph0-2" x="463.6284" y="289.53434"/>
-  <use xlink:href="#glyph0-3" x="472.2204" y="289.53434"/>
-  <use xlink:href="#glyph0-4" x="480.2204" y="289.53434"/>
-  <use xlink:href="#glyph0-5" x="488.5244" y="289.53434"/>
-  <use xlink:href="#glyph0-12" x="492.6684" y="289.53434"/>
-  <use xlink:href="#glyph0-36" x="496.8124" y="289.53434"/>
+  <use xlink:href="#glyph0-2" x="435.056" y="368.724"/>
+  <use xlink:href="#glyph0-3" x="443.648" y="368.724"/>
+  <use xlink:href="#glyph0-4" x="451.648" y="368.724"/>
+  <use xlink:href="#glyph0-5" x="459.952" y="368.724"/>
+  <use xlink:href="#glyph0-12" x="464.096" y="368.724"/>
+  <use xlink:href="#glyph0-36" x="468.24" y="368.724"/>
 </g>
 </g>
 </svg>
--- a/slide/slide.html	Sat Feb 10 04:33:50 2018 +0900
+++ b/slide/slide.html	Sun Feb 11 12:53:53 2018 +0900
@@ -87,23 +87,40 @@
 <!-- === begin markdown block ===

       generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16]
-                on 2018-02-10 02:47:53 +0900 with Markdown engine kramdown (1.13.2)
+                on 2018-02-11 12:53:21 +0900 with Markdown engine kramdown (1.13.2)
                   using options {}
   -->

 <!-- _S9SLIDE_ -->
-<h2 id="gears-os">Gears OS</h2>
+<h2 id="section">メタ計算を用いた並列処理</h2>
 <ul>
-  <li>並列処理のチューニングや信頼性を保証するのは難しい
+  <li>並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている</li>
+  <li>しかし、並列処理のチューニングや信頼性を保証するのは難しい
     <ul>
       <li>スレッド間の共通資源の競合などの非決定的な実行</li>
       <li>従来のテストやデバッグではテストしきれない部分が残ってしまう</li>
+      <li>GPU などのアーキテクチャに合わせた並列プログラミングの記述</li>
+    </ul>
+  </li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="gears-os">Gears OS</h2>
+<ul>
+  <li>本研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している</li>
+  <li>Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される
+    <ul>
+      <li>Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う</li>
     </ul>
   </li>
-  <li>Gears OS では計算をノーマルレベルとメタレベルに階層化
+  <li>Gears OS では計算をノーマルレベルとメタレベルに階層化</li>
+  <li>信頼性と拡張性をメタレベルで保証する
     <ul>
-      <li>ノーマルレベルの計算に対してメタレベルで信頼性を保証したい</li>
-      <li>メタレベルの計算はデータ拡張や実行環境の切り替え等の拡張性のための計算を行う</li>
+      <li>並列処理の信頼性を通常の計算(ノーマルレベル) に保証</li>
+      <li>CPU、GPU などの実行環境の切り替え、データ拡張等のを提供</li>
     </ul>
   </li>
 </ul>
@@ -112,13 +129,23 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
+<h2 id="gears-os-1">Gears OS</h2>
+<ul>
+  <li>本研究ではGears OS の並列処理機構、並列処理構文(par goto)の実装、Gears OS を実装するにつれて必要なったモジュール化の導入を行う</li>
+  <li>また、並列処理を行う例題を用いて評価、 Open MP、 Go 言語との比較を行う</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
 <h2 id="code-gear-data-gear">Code Gear、 Data Gear</h2>
 <ul>
   <li>Gears OS は Code Gear、 Data Gear という Gear で構成される</li>
   <li>Code Gear はプログラムの処理そのものを表す</li>
   <li>Data Gear はデータそのものを表す</li>
-  <li>Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する</li>
-  <li>Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Input Data Gear が揃った Code Gear の並列実行を行う</li>
+  <li>Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する</li>
+  <li>Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う</li>
 </ul>

 <div style="text-align: center;">
@@ -178,7 +205,7 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section">メタ計算</h2>
+<h2 id="section-1">メタ計算</h2>
 <ul>
   <li>メタ計算 は通常の計算を実行するための計算</li>
   <li>信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等</li>
@@ -294,50 +321,206 @@
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="interface-">Interface の定義</h2>
+<ul>
+  <li>Interface の定義には以下の内容を定義する
+    <ul>
+      <li>引数のData Gear 群</li>
+      <li>操作(API) 実行後に継続される Code Gear</li>
+      <li>操作(API) である Code Gear と Code Gear に渡す引数情報</li>
+    </ul>
+  </li>
+</ul>
+
+<pre lang="c"><code>typedef struct Queue&lt;Impl&gt;{
+        // Data Gear parameter
+        union Data* queue;
+        union Data* data;
+        __code next(...);
+        __code whenEmpty(...);
+
+        // Code Gear
+        __code clear(Impl* queue, __code next(...));
+        __code put(Impl* queue, union Data* data, __code next(...));
+        __code take(Impl* queue, __code next(union Data*, ...));
+        __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...));
+} Queue;
+</code></pre>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="interface--1">Interface の実装</h2>
+<ul>
+  <li>Interface には複数の実装を行うことが出来る</li>
+  <li>実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う</li>
+  <li>代入する Code Gear を入れ替えることで別の実装を表現する</li>
+  <li>実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる</li>
+</ul>
+
+<pre><code>Queue* createSingleLinkedQueue(struct Context* context) {
+    struct Queue* queue = new Queue(); // Allocate Queue interface
+    struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement
+    queue-&gt;queue = (union Data*)singleLinkedQueue;
+    singleLinkedQueue-&gt;top  = new Element();
+    singleLinkedQueue-&gt;last = singleLinkedQueue-&gt;top;
+    queue-&gt;clear = C_clearSingleLinkedQueue;
+    queue-&gt;put  = C_putSingleLinkedQueue;
+    queue-&gt;take  = C_takeSingleLinkedQueue;
+    queue-&gt;isEmpty = C_isEmptySingleLinkedQueue;
+    return queue;
+}
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface--2">Interface の実装例</h2>
+<ul>
+  <li>SingleLinkedQueue の put 実装</li>
+  <li>引数は Queue Interface の定義にあわせる</li>
+  <li>第1引数は 実装対象の Data Gear の型になる</li>
+  <li>第3引数の(…) は Output Data Gear を記述する
+    <ul>
+      <li>… は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある</li>
+    </ul>
+  </li>
+</ul>
+
+<pre lang="c"><code>__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
+    Element* element = new Element();
+    element-&gt;data = data;
+    element-&gt;next = NULL;
+    queue-&gt;last-&gt;next  = element;
+    queue-&gt;last = element;
+    goto next(...);
+}
+</code></pre>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="interface--code-gear-">Interface を利用した Code Gear の呼び出し</h2>
+<ul>
+  <li>Interface を利用した Code Gear への継続は <code>goto interface-&gt;method</code> で行われる</li>
+  <li>ここでの <strong>interface</strong>  は Interfaceの型で包んだポインタ、 <strong>method</strong> は実装した Code Gear に対応</li>
+  <li>この構文は実際にはスクリプトで変換される
+    <ul>
+      <li>変換後はメタレベルのコードになる</li>
+    </ul>
+  </li>
+</ul>
+
+<pre><code>__code code1() {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = new Node();
+    node-&gt;color = Red;
+    goto queue-&gt;put(node, queueTest2);
+}
+</code></pre>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-1">並列処理の構成</h2>
+<h2 id="interface--code-gear--1">Interface を利用した Code Gear の呼び出し(スクリプト変換後)</h2>
+<ul>
+  <li>Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す</li>
+  <li>この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる</li>
+  <li>呼び出すCode Gear の引数情報に合わせて引数に格納</li>
+</ul>
+
+<pre><code>__code code1(struct Context *context) {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = &amp;ALLOCATE(context, Node)-&gt;Node;
+    node-&gt;color = Red;
+    Gearef(context, Queue)-&gt;queue = (union Data*) queue;
+    Gearef(context, Queue)-&gt;data = (union Data*) node;
+    Gearef(context, Queue)-&gt;next = C_queueTest2;
+    goto meta(context, queue-&gt;put);
+}
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="interface--stub-code-gear">Interface での stub Code Gear</h2>
+<ul>
+  <li>メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される</li>
+  <li>Interface を実装した Code Gear は stub Code Gear の自動生成が可能である</li>
+</ul>
+
+<pre lang="c"><code>__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) {
+    Element* element = &amp;ALLOCATE(context, Element)-&gt;Element;
+    element-&gt;data = data;
+    element-&gt;next = NULL;
+    queue-&gt;last-&gt;next  = element;
+    queue-&gt;last = element;
+    goto meta(context, next);
+}
+
+// generated by script
+__code putSingleLinkedQueue_stub(struct Context* context) {
+	SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue);
+	Data* data = Gearef(context, Queue)-&gt;data;
+	enum Code next = Gearef(context, Queue)-&gt;next;
+	goto putSingleLinkedQueue(context, queue, data, next);
+}
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-2">並列処理の構成</h2>
 <ul>
   <li>今回は並列処理を行う機構の実装を行う</li>
   <li>構成要素
     <ul>
       <li>Task(Context)</li>
+      <li>TaskManager
+        <ul>
+          <li>Worker の生成、依存関係を解決したTask を Worker に送信する</li>
+        </ul>
+      </li>
       <li>Worker
         <ul>
-          <li>Queue から Task を取得し、実行する</li>
-        </ul>
-      </li>
-      <li>TaskManager
-        <ul>
-          <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li>
+          <li>SynchronizedQueue から Task を取得し、実行する</li>
         </ul>
       </li>
     </ul>
   </li>
 </ul>

-<p>※ TaskManager は今回未実装</p>
-

 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="taskcontext">Task(Context)</h2>
+<ul>
+  <li>Gears OS では並列実行する Task を Context で表現する</li>
+  <li>Context Task用の情報として以下の情報をもっている
+    <ul>
+      <li>実行する Code Gear</li>
+      <li>Input/Output Data Gear の格納場所</li>
+      <li>待っている Input Data Gear の数</li>
+    </ul>
+  </li>
+  <li>実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる
+    <ul>
+      <li>stub Code Gear は自動生成される</li>
+    </ul>
+  </li>
+</ul>
+
+<pre lang="c"><code>__code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) {
+    output-&gt;value = input1-&gt;value + input2-&gt;value;
+    goto next(output, ...);
+}
+</code></pre>


 </div>
@@ -350,7 +533,7 @@
 </ul>

 <div style="text-align: center;">
-    <img src="./images/taskManager.svg" alt="message" width="800" />
+    <img src="./images/sendTask.svg" alt="message" width="800" />
 </div>


@@ -359,31 +542,25 @@
 <!-- _S9SLIDE_ -->
 <h2 id="worker">Worker</h2>
 <ul>
-  <li>Worker は TaskQueue から Task を取得して実行する</li>
+  <li>初期化の際にスレッドと Worker 用の Context を生成する</li>
+  <li>TaskManager から送信された Task を取得して実行する</li>
 </ul>

-<table align="center">
-  <tbody>
-    <tr>
-      <td>
-        <div>
-            <img src="./images/worker.svg" alt="message" width="600" />
-        </div>
-     </td>
-     <td>
+<div>
+    <div style="float: left;">
+        <img src="./images/workerRun.svg" alt="message" width="600" />
+    </div>
+    <div style="float: left; font-size=100%;">
         <ol>
-            <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
-            <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
-            <li> Task に格納されている Code Gear を実行する </li>
-            <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
+            <li>Worker は Queue から Task を取得する</li>
+            <li>Worker Context から Task へ入れ替える</li>
+            <li>Task の Code Gear を実行</li>
+            <li>Task の Output Data Gear の書き出し</li>
+            <li>Task から WorkerContext へ入れ替える</li>
+            <li>Worker は再び Queue から Task を取得する</li>
         </ol>
-     </td>
-    </tr>
-  </tbody>
-</table>
-<ul>
-  <li>Task が完了したら次の Task を取得する</li>
-</ul>
+    </div>
+</div>


 </div>
@@ -391,12 +568,165 @@
 <!-- _S9SLIDE_ -->
 <h2 id="synchronized-queue">Synchronized Queue</h2>
 <ul>
-  <li>Task Queue は Task のリストを扱う</li>
-  <li>Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li>
-  <li>TaskQueue は 2つで Data Gear で表現される
+  <li>Worker で使用される Queue</li>
+  <li>TaskManager を経由して Task を送信するスレッドと Task を取得するスレッドで操作される</li>
+  <li>そのためマルチスレッドでのデータの一貫性を保証する必要がある</li>
+  <li>Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する</li>
+  <li>この Queue は Queue Interface を実装し、 List を利用した実装を行った</li>
+</ul>
+
+<pre><code>struct SynchronizedQueue {
+    struct Element* top;
+    struct Element* last;
+    struct Atomic* atomic;
+};
+// Singly Linked List element
+struct Element {
+    union Data* top;
+    struct Element* next;
+};
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-3">依存関係の解決</h2>
+<ul>
+  <li>依存関係の解決は Data Gear にメタレベルで依存関係解決用の Queueをもたせることで行う</li>
+  <li>Code Gear を実行した後、 Output Data Gear を書き出す処理を行う</li>
+  <li>書き出し処理は Data Gear の Queue から依存関係にある Task を参照する</li>
+  <li>Task には実行に必要な Input Data Gear のカウンタを持っているため、そのカウンタをデクリメントする</li>
+  <li>カウンタが0になったら Input Data Gear が揃ったことになるため、TaskManager を経由して Worker に送信する</li>
+</ul>
+
+<div style="text-align: center;">
+    <img src="./images/dependency.svg" alt="message" width="600" />
+</div>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-4">並列構文</h2>
+<ul>
+  <li>並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する</li>
+  <li>この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない</li>
+  <li>Task の設定の記述は煩雑な記述であるが、並列実行サれることを除けば通常の CbC の goto 文と同等である</li>
+  <li>そこで Context を直接参照しない並列構文、 <strong>par goto</strong> 構文を新たに考案した</li>
+  <li>par goto 構文には引数として Input/Output Data Gear等を渡す
     <ul>
-      <li>先頭と末尾の要素を持った Queue 表す Data Gear</li>
-      <li>Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear</li>
+      <li>スクリプトによって Code Gear の Input/Output の数を解析する</li>
+    </ul>
+  </li>
+</ul>
+
+<pre lang="c"><code>__code code1(Integer *integer1, Integer * integer2, Integer *output) {
+    par goto add(integer1, integer2, output, __exit);
+    goto code2();
+}
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="cuda-">CUDA への対応</h2>
+<ul>
+  <li>Gears OS は GPU での実行もサポートする</li>
+  <li>GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる</li>
+  <li>今回は CUDA への実行のサポートをおこなった</li>
+  <li>CUDA へ GPU を Device、 CPU を Host として定義する</li>
+  <li>CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する</li>
+  <li>今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する</li>
+</ul>
+
+<div style="text-align: center;">
+    <img src="./images/cudaArchitecture.svg" alt="message" width="500" />
+</div>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="cudaexecutor">CUDAExecutor</h2>
+<ul>
+  <li>CUDA Executor は Executor Interface を実装した以下の Code Gear を持つ
+    <ul>
+      <li>HostからDevice へのデータの送信(read)</li>
+      <li>kernel の実行(exec)</li>
+      <li>Device から Host へのデータの書き出し(write)</li>
+    </ul>
+  </li>
+</ul>
+
+<pre lang="c"><code>typedef struct Executor&lt;Impl&gt;{
+    union Data* Executor;
+    struct Context* task;
+    __code next(...);
+    // method
+    __code read(Impl* executor, struct Context* task, __code next(...));
+    __code exec(Impl* executor, struct Context* task, __code next(...));
+    __code write(Impl* executor, struct Context* task, __code next(...));
+}
+</code></pre>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="cudabuffer">CUDABuffer</h2>
+<ul>
+  <li>Host、 Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある
+    <ul>
+      <li>Device にデータ領域を確保するにはサイズの指定が必要</li>
+      <li>Data Gear には Meta Data Gear でデータのサイズを持っている</li>
+      <li>だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう</li>
+    </ul>
+  </li>
+  <li>CUDA Buffer ではそのマッピングを行う
+    <ul>
+      <li>このマッピングは Task の stub Code Gear で行われる</li>
+    </ul>
+  </li>
+</ul>
+
+<div style="text-align: center;">
+    <img src="./images/cudaDataArchitecture.svg" alt="message" width="500" />
+</div>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="cuda--1">CUDA での呼び出し</h2>
+<ul>
+  <li>Gears OS では stub Code Gear で CUDA による実行を切り替える</li>
+  <li>stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う</li>
+  <li>stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="gears-os-">Gears OS の評価</h2>
+<ul>
+  <li>並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った</li>
+  <li>CPU 環境
+    <ul>
+      <li>Model : Dell PowerEdgeR630</li>
+      <li>Memory : 768GB</li>
+      <li>CPU : 2 x 18-Core Intel Xeon 2.30GHz</li>
+    </ul>
+  </li>
+  <li>GPU 環境
+    <ul>
+      <li>GPU : GeForce GTX 1070</li>
+      <li>Cores : 1920</li>
+      <li>ClockSpeed : 1683MHz</li>
+      <li>Memory Size : 8GB GDDR5</li>
+      <li>Memory Bandwidth :  256GB/s</li>
     </ul>
   </li>
 </ul>
@@ -405,85 +735,87 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-2">依存関係の解決</h2>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="section-3">データ並列</h2>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="cuda-">CUDA への対応</h2>
-<p>## CUDA Worker
-## CUDA Executor</p>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="gears-os-">Gears OS の評価</h2>
+<h2 id="twice">Twice</h2>
 <ul>
-  <li>今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った</li>
-  <li>これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった</li>
+  <li>Twice は与えられた整数配列を2倍にする例題である</li>
+  <li>並列実行の依存関係がなく、並列度が高い課題である</li>
+  <li>要素数 2^27</li>
+  <li>CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する</li>
+  <li>GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開</li>
 </ul>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-4">実験環境</h2>
+<h2 id="twice-">Twice の結果</h2>
+<table border="1" align="center" width="50%">
+  <tbody>
+    <tr>
+      <td style="text-align: center;">Processor</td>
+      <td style="text-align: center;">Time(ms)</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">1 CPU</td>
+      <td style="text-align: right;">1181.215</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">2 CPUs</td>
+      <td style="text-align: right;">627.914</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">4 CPUs</td>
+      <td style="text-align: right;">324.059</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">8 CPUs</td>
+      <td style="text-align: right;">159.932</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">16 CPUs</td>
+      <td style="text-align: right;">85.518</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">32 CPUs</td>
+      <td style="text-align: right;">43.496</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU</td>
+      <td style="text-align: right;">43.496</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU(kernel only)</td>
+      <td style="text-align: right;">6.018</td>
+    </tr>
+  </tbody>
+</table>
+
 <ul>
-  <li>CPU 環境
+  <li>1 CPU と 32 CPU では 約27.1倍の速度向上が見られた</li>
+  <li>GPU での実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上
     <ul>
-      <li>Memory : 16GB</li>
-      <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li>
+      <li>通信時間を含めると 16 CPU より遅い</li>
+      <li>通信時間がオーバーヘッドになっている</li>
     </ul>
   </li>
-  <li>GPU 環境</li>
 </ul>


 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="twice">Twice</h2>
+<h2 id="bitonicsort">BitonicSort</h2>
 <ul>
-  <li>タスクの例題として Twice と BitonicSort を実装した</li>
-  <li>Twice は与えられた整数配列を2倍にする例題である</li>
+  <li>並列処理向けのソートアルゴリズム</li>
+  <li>決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする</li>
+  <li>要素数 2^24</li>
+  <li>CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する</li>
+  <li>GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開</li>
 </ul>

-<pre lang="c"><code>// Twice Code Gear
-__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
-    int i = loopCounter-&gt;i;
-
-    if (i &lt; alignment) {
-        array[i+index*alignment] = array[i+index*alignment]*2;
-        loopCounter-&gt;i++;
-
-        goto twice(loopCounter, index, alignment, array);
-    }
-
-    loopCounter-&gt;i = 0;
-
-    goto exit();
-}
-</code></pre>
-
-
+<div style="text-align: center;">
+    <img src="./images/bitonicNetwork.svg" alt="message" width="500" />
 </div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="twice-">Twice の結果</h2>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="bitonicsort">BitonicSort</h2>


 </div>
@@ -494,34 +826,48 @@
 <table border="1" align="center" width="50%">
   <tbody>
     <tr>
-      <td style="text-align: center;">Number of Processors</td>
-      <td style="text-align: center;">Time(ms)</td>
+      <td style="text-align: center;">Processor</td>
+      <td style="text-align: center;">Time(s)</td>
     </tr>
     <tr>
       <td style="text-align: center;">1 CPU</td>
-      <td style="text-align: right;">1315</td>
+      <td style="text-align: right;">41.416</td>
     </tr>
     <tr>
       <td style="text-align: center;">2 CPUs</td>
-      <td style="text-align: right;">689</td>
+      <td style="text-align: right;">23.340</td>
     </tr>
     <tr>
       <td style="text-align: center;">4 CPUs</td>
-      <td style="text-align: right;">366</td>
+      <td style="text-align: right;">11.952</td>
     </tr>
     <tr>
       <td style="text-align: center;">8 CPUs</td>
-      <td style="text-align: right;">189</td>
+      <td style="text-align: right;">6.320</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">16 CPUs</td>
+      <td style="text-align: right;">3.336</td>
     </tr>
     <tr>
-      <td style="text-align: center;">12 CPUs</td>
-      <td style="text-align: right;">111</td>
+      <td style="text-align: center;">32 CPUs</td>
+      <td style="text-align: right;">1.872</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU</td>
+      <td style="text-align: right;">5.420</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU(kernel only)</td>
+      <td style="text-align: right;">0.163</td>
     </tr>
   </tbody>
 </table>

 <ul>
-  <li>1cpu と 12cpu では 11.8 倍の向上が見られた</li>
+  <li>1 CPU と 32 CPU で約22.12倍の速度向上</li>
+  <li>GPU は通信時間を含めると 8 CPU の役1.16倍、 kernel のみの実行では 32 CPU の役11.48倍になった</li>
+  <li>現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった</li>
 </ul>


@@ -529,12 +875,7 @@
 <div class='slide '>
 <!-- _S9SLIDE_ -->
 <h2 id="openmp-">OpenMP との比較</h2>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="go-">Go との比較</h2>
+<p>## Go との比較</p>


 </div>
@@ -542,8 +883,10 @@
 <!-- _S9SLIDE_ -->
 <h2 id="section-5">まとめ</h2>
 <ul>
-  <li>Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li>
-  <li>依存関係のない Twice を実装し、並列処理が行えることを確認した</li>
+  <li>Gears OS の並列処理機構の実装を行った</li>
+  <li>Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった</li>
+  <li>par goto  構文を導入することで、ノーマルレベルで並列処理の記述が可能になった</li>
+  <li>2つの例題である程度の台数効果が出ることを確認した</li>
 </ul>


@@ -552,31 +895,22 @@
 <!-- _S9SLIDE_ -->
 <h2 id="section-6">今後の課題</h2>
 <ul>
-  <li>一般的に並列処理には依存関係が存在する
+  <li>Gears OS の並列処理の信頼性の保証、チューニングを行う</li>
+  <li>Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する
     <ul>
-      <li>複雑な並列処理を実行できるようにするために Task Manager の実装を行い、  依存関係のある並列処理の例題を作成し、評価する</li>
-    </ul>
-  </li>
-  <li>GPUなどの他のプロセッサ演算に利用することが出来ない
-    <ul>
-      <li>Data Gear などのデータをGPUにマッピングするための機構が必要</li>
+      <li>証明はCbC のプログラムヲ証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある</li>
+      <li>モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う</li>
     </ul>
   </li>
-  <li>Gears OS でのデバック手法
+  <li>OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。
     <ul>
-      <li>継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案</li>
-      <li>並列処理でのデバック手法も考案する必要がある</li>
+      <li>par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう</li>
+      <li>モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要</li>
     </ul>
   </li>
-  <li>型情報の検査
+  <li>現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった
     <ul>
-      <li>プログラムの正しさを保証するために Data Gear の情報を検査するシステムを メタ計算 として実装する</li>
-    </ul>
-  </li>
-  <li>Contextの動的生成
-    <ul>
-      <li>今は静的に自分で生成している</li>
-      <li>CbC 用の Runtime をつくり、 Context を動的に生成</li>
+      <li>Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う</li>
     </ul>
   </li>
 </ul>
--- a/slide/slide.md	Sat Feb 10 04:33:50 2018 +0900
+++ b/slide/slide.md	Sun Feb 11 12:53:53 2018 +0900
@@ -131,9 +131,9 @@

 ## Interface の定義
 - Interface の定義には以下の内容を定義する
-    - 操作(API) である Code Gear と Code Gear に渡す引数情報
     - 引数のData Gear 群
     - 操作(API) 実行後に継続される Code Gear
+    - 操作(API) である Code Gear と Code Gear に渡す引数情報

 ``` c
 typedef struct Queue<Impl>{
@@ -155,7 +155,7 @@
 - Interface には複数の実装を行うことが出来る
 - 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う
 - 代入する Code Gear を入れ替えることで別の実装を表現する
-- 実装した Data Gear の生成は関数呼び出しで行われ、 外から見るとInterface の型で扱われる
+- 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる

 ```
 Queue* createSingleLinkedQueue(struct Context* context) {
@@ -175,7 +175,9 @@
 ## Interface の実装例
 - SingleLinkedQueue の put 実装
 - 引数は Queue Interface の定義にあわせる
-- 第一引数は 実装対象の Data Gear の型になる
+- 第1引数は 実装対象の Data Gear の型になる
+- 第3引数の(...) は Output Data Gear を記述する
+    -  ... は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある

 ``` c
 __code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
@@ -189,154 +191,347 @@
 ```

 ## Interface を利用した Code Gear の呼び出し
-- Interface を利用した Code Gear への継続として `goto interface->method` を提供している
+- Interface を利用した Code Gear への継続は `goto interface->method` で行われる
+- ここでの **interface**  は Interfaceの型で包んだポインタ、 **method** は実装した Code Gear に対応
+- この構文は実際にはスクリプトで変換される
+    - 変換後はメタレベルのコードになる
+
+```
+__code code1() {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = new Node();
+    node->color = Red;
+    goto queue->put(node, queueTest2);
+}
+```
+
+## Interface を利用した Code Gear の呼び出し(スクリプト変換後)
+- Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す
+- この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる
+- 呼び出すCode Gear の引数情報に合わせて引数に格納
+
+```
+__code code1(struct Context *context) {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = &ALLOCATE(context, Node)->Node;
+    node->color = Red;
+    Gearef(context, Queue)->queue = (union Data*) queue;
+    Gearef(context, Queue)->data = (union Data*) node;
+    Gearef(context, Queue)->next = C_queueTest2;
+    goto meta(context, queue->put);
+}
+```
+
+## Interface での stub Code Gear
+- メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される
+- Interface を実装した Code Gear は stub Code Gear の自動生成が可能である
+
+``` c
+__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) {
+    Element* element = &ALLOCATE(context, Element)->Element;
+    element->data = data;
+    element->next = NULL;
+    queue->last->next  = element;
+    queue->last = element;
+    goto meta(context, next);
+}
+
+// generated by script
+__code putSingleLinkedQueue_stub(struct Context* context) {
+	SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue);
+	Data* data = Gearef(context, Queue)->data;
+	enum Code next = Gearef(context, Queue)->next;
+	goto putSingleLinkedQueue(context, queue, data, next);
+}
+```
+
 ## 並列処理の構成
 - 今回は並列処理を行う機構の実装を行う
 - 構成要素
     - Task(Context)
+    - TaskManager
+        - Worker の生成、依存関係を解決したTask を Worker に送信する
     - Worker
-        -  Queue から Task を取得し、実行する
-    - TaskManager
-        - Persistent Data Tree を監視し、 Task の依存関係を解決する
-
-※ TaskManager は今回未実装
+        - SynchronizedQueue から Task を取得し、実行する

 ## Task(Context)
+- Gears OS では並列実行する Task を Context で表現する
+- Context Task用の情報として以下の情報をもっている
+    - 実行する Code Gear
+    - Input/Output Data Gear の格納場所
+    - 待っている Input Data Gear の数
+- 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる
+    - stub Code Gear は自動生成される
+
+``` c
+__code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) {
+    output->value = input1->value + input2->value;
+    goto next(output, ...);
+}
+```

 ## TaskManger
 - 初期化時に決まった数の Worker を作成
 - 依存関係を解決した Task を各 Worker の Queue に送信する

 <div style="text-align: center;">
-    <img src="./images/taskManager.svg" alt="message" width="800">
+    <img src="./images/sendTask.svg" alt="message" width="800">
 </div>

 ## Worker
-- Worker は TaskQueue から Task を取得して実行する
+- 初期化の際にスレッドと Worker 用の Context を生成する
+- TaskManager から送信された Task を取得して実行する
+
+<div>
+    <div style="float: left;">
+        <img src="./images/workerRun.svg" alt="message" width="600">
+    </div>
+    <div style="float: left; font-size=100%;">
+        <ol>
+            <li>Worker は Queue から Task を取得する</li>
+            <li>Worker Context から Task へ入れ替える</li>
+            <li>Task の Code Gear を実行</li>
+            <li>Task の Output Data Gear の書き出し</li>
+            <li>Task から WorkerContext へ入れ替える</li>
+            <li>Worker は再び Queue から Task を取得する</li>
+        </ol>
+    </div>
+</div>
+
+## Synchronized Queue
+- Worker で使用される Queue
+- TaskManager を経由して Task を送信するスレッドと Task を取得するスレッドで操作される
+- そのためマルチスレッドでのデータの一貫性を保証する必要がある
+- Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する
+- この Queue は Queue Interface を実装し、 List を利用した実装を行った
+
+```
+struct SynchronizedQueue {
+    struct Element* top;
+    struct Element* last;
+    struct Atomic* atomic;
+};
+// Singly Linked List element
+struct Element {
+    union Data* top;
+    struct Element* next;
+};
+```
+
+## 依存関係の解決
+- 依存関係の解決は Data Gear にメタレベルで依存関係解決用の Queueをもたせることで行う
+- Code Gear を実行した後、 Output Data Gear を書き出す処理を行う
+- 書き出し処理は Data Gear の Queue から依存関係にある Task を参照する
+- Task には実行に必要な Input Data Gear のカウンタを持っているため、そのカウンタをデクリメントする
+- カウンタが0になったら Input Data Gear が揃ったことになるため、TaskManager を経由して Worker に送信する
+
+<div style="text-align: center;">
+    <img src="./images/dependency.svg" alt="message" width="600">
+</div>
+
+## 並列構文
+- 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する
+- この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない
+- Task の設定の記述は煩雑な記述であるが、並列実行サれることを除けば通常の CbC の goto 文と同等である
+- そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した
+- par goto 構文には引数として Input/Output Data Gear等を渡す
+    - スクリプトによって Code Gear の Input/Output の数を解析する
+
+``` c
+__code code1(Integer *integer1, Integer * integer2, Integer *output) {
+    par goto add(integer1, integer2, output, __exit);
+    goto code2();
+}
+```

-<table align='center'>
+## CUDA への対応
+- Gears OS は GPU での実行もサポートする
+- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる
+- 今回は CUDA への実行のサポートをおこなった
+- CUDA へ GPU を Device、 CPU を Host として定義する
+- CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する
+- 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する
+
+<div style="text-align: center;">
+    <img src="./images/cudaArchitecture.svg" alt="message" width="500">
+</div>
+
+## CUDAExecutor
+- CUDA Executor は Executor Interface を実装した以下の Code Gear を持つ
+    - HostからDevice へのデータの送信(read)
+    - kernel の実行(exec)
+    - Device から Host へのデータの書き出し(write)
+
+``` c
+typedef struct Executor<Impl>{
+    union Data* Executor;
+    struct Context* task;
+    __code next(...);
+    // method
+    __code read(Impl* executor, struct Context* task, __code next(...));
+    __code exec(Impl* executor, struct Context* task, __code next(...));
+    __code write(Impl* executor, struct Context* task, __code next(...));
+}
+```
+
+## CUDABuffer
+- Host、 Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある
+    - Device にデータ領域を確保するにはサイズの指定が必要
+    - Data Gear には Meta Data Gear でデータのサイズを持っている
+    - だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう
+- CUDA Buffer ではそのマッピングを行う
+    - このマッピングは Task の stub Code Gear で行われる
+
+<div style="text-align: center;">
+    <img src="./images/cudaDataArchitecture.svg" alt="message" width="500">
+</div>
+
+## CUDA での呼び出し
+- Gears OS では stub Code Gear で CUDA による実行を切り替える
+- stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う
+- stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する
+
+## Gears OS の評価
+- 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った
+- CPU 環境
+    - Model : Dell PowerEdgeR630
+    - Memory : 768GB
+    - CPU : 2 x 18-Core Intel Xeon 2.30GHz
+- GPU 環境
+    - GPU : GeForce GTX 1070
+    - Cores : 1920
+    - ClockSpeed : 1683MHz
+    - Memory Size : 8GB GDDR5
+    - Memory Bandwidth :  256GB/s
+
+## Twice
+- Twice は与えられた整数配列を2倍にする例題である
+- 並列実行の依存関係がなく、並列度が高い課題である
+- 要素数 2^27
+- CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する
+- GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開
+
+## Twice の結果
+<table  border="1" align='center' width='50%'>
   <tbody>
     <tr>
-      <td>
-        <div>
-            <img src="./images/worker.svg" alt="message" width="600">
-        </div>
-     </td>
-     <td>
-        <ol>
-            <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
-            <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
-            <li> Task に格納されている Code Gear を実行する </li>
-            <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
-        </ol>
-     </td>
+      <td style="text-align: center;">Processor</td>
+      <td style="text-align: center;">Time(ms)</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">1 CPU</td>
+      <td style="text-align: right;">1181.215</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">2 CPUs</td>
+      <td style="text-align: right;">627.914</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">4 CPUs</td>
+      <td style="text-align: right;">324.059</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">8 CPUs</td>
+      <td style="text-align: right;">159.932</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">16 CPUs</td>
+      <td style="text-align: right;">85.518</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">32 CPUs</td>
+      <td style="text-align: right;">43.496</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU</td>
+      <td style="text-align: right;">43.496</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU(kernel only)</td>
+      <td style="text-align: right;">6.018</td>
     </tr>
   </tbody>
 </table>
-- Task が完了したら次の Task を取得する

-## Synchronized Queue
-- Task Queue は Task のリストを扱う
-- Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
-- TaskQueue は 2つで Data Gear で表現される
-    - 先頭と末尾の要素を持った Queue 表す Data Gear
-    - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
-
-## 依存関係の解決
-
-## データ並列
-
-## CUDA への対応
-## CUDA Worker
-## CUDA Executor
-
-## Gears OS の評価
-- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
-- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
-
-## 実験環境
-- CPU 環境
-    - Memory : 16GB
-    - CPU : 6-core Intel Xeon 2.66GHZ x 2
-- GPU 環境
-
-## Twice
-- タスクの例題として Twice と BitonicSort を実装した
-- Twice は与えられた整数配列を2倍にする例題である
-
-``` c
-// Twice Code Gear
-__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
-    int i = loopCounter->i;
-
-    if (i < alignment) {
-        array[i+index*alignment] = array[i+index*alignment]*2;
-        loopCounter->i++;
-
-        goto twice(loopCounter, index, alignment, array);
-    }
-
-    loopCounter->i = 0;
-
-    goto exit();
-}
-```
-
-## Twice の結果
+- 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた
+- GPU での実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上
+    - 通信時間を含めると 16 CPU より遅い
+    - 通信時間がオーバーヘッドになっている

 ## BitonicSort
+- 並列処理向けのソートアルゴリズム
+- 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする
+- 要素数 2^24
+- CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する
+- GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開
+
+<div style="text-align: center;">
+    <img src="./images/bitonicNetwork.svg" alt="message" width="500">
+</div>

 ## BitonicSort の結果

 <table  border="1" align='center' width='50%'>
   <tbody>
     <tr>
-      <td style="text-align: center;">Number of Processors</td>
-      <td style="text-align: center;">Time(ms)</td>
+      <td style="text-align: center;">Processor</td>
+      <td style="text-align: center;">Time(s)</td>
     </tr>
     <tr>
       <td style="text-align: center;">1 CPU</td>
-      <td style="text-align: right;">1315</td>
+      <td style="text-align: right;">41.416</td>
     </tr>
     <tr>
       <td style="text-align: center;">2 CPUs</td>
-      <td style="text-align: right;">689</td>
+      <td style="text-align: right;">23.340</td>
     </tr>
     <tr>
       <td style="text-align: center;">4 CPUs</td>
-      <td style="text-align: right;">366</td>
+      <td style="text-align: right;">11.952</td>
     </tr>
     <tr>
       <td style="text-align: center;">8 CPUs</td>
-      <td style="text-align: right;">189</td>
+      <td style="text-align: right;">6.320</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">16 CPUs</td>
+      <td style="text-align: right;">3.336</td>
     </tr>
     <tr>
-      <td style="text-align: center;">12 CPUs</td>
-      <td style="text-align: right;">111</td>
+      <td style="text-align: center;">32 CPUs</td>
+      <td style="text-align: right;">1.872</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU</td>
+      <td style="text-align: right;">5.420</td>
+    </tr>
+    <tr>
+      <td style="text-align: center;">GPU(kernel only)</td>
+      <td style="text-align: right;">0.163</td>
     </tr>
   </tbody>
 </table>

-- 1cpu と 12cpu では 11.8 倍の向上が見られた
+- 1 CPU と 32 CPU で約22.12倍の速度向上
+- GPU は通信時間を含めると 8 CPU の役1.16倍、 kernel のみの実行では 32 CPU の役11.48倍になった
+- 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった

 ## OpenMP との比較
-
 ## Go との比較

 ## まとめ
-- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
-- 依存関係のない Twice を実装し、並列処理が行えることを確認した
+- Gears OS の並列処理機構の実装を行った
+- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった
+- par goto  構文を導入することで、ノーマルレベルで並列処理の記述が可能になった
+- 2つの例題である程度の台数効果が出ることを確認した

 ## 今後の課題
-- 一般的に並列処理には依存関係が存在する
-    - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、  依存関係のある並列処理の例題を作成し、評価する
-- GPUなどの他のプロセッサ演算に利用することが出来ない
-    - Data Gear などのデータをGPUにマッピングするための機構が必要
-- Gears OS でのデバック手法
-    - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案
-    - 並列処理でのデバック手法も考案する必要がある
-- 型情報の検査
-    - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを メタ計算 として実装する
-- Contextの動的生成
-    - 今は静的に自分で生成している
-    - CbC 用の Runtime をつくり、 Context を動的に生成
+- Gears OS の並列処理の信頼性の保証、チューニングを行う
+- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する
+    - 証明はCbC のプログラムヲ証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある
+    - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う
+- OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。
+    - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう
+    - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要
+- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった
+    - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う