Mercurial > hg > Papers > 2016 > parusu-sigos

changeset 17:f2f9c7110b41

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update
author Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
date Sun, 29 May 2016 19:28:03 +0900
parents f88786cba8b5
children 4c465c6fe2cc
files paper/sigos.pdf paper/sigos.tex presen/sigos.html presen/sigos.md sigos.mm
diffstat 5 files changed, 81 insertions(+), 107 deletions(-) [+]
line wrap: on
line diff
Binary file paper/sigos.pdf has changed
--- a/paper/sigos.tex	Sun May 29 16:34:28 2016 +0900
+++ b/paper/sigos.tex	Sun May 29 19:28:03 2016 +0900
@@ -328,7 +328,7 @@
     \item 並列の処理される Code Gear(Twice) を実行。
 \end{itemize}
 
-要素数$2^17$*1000 のデータを640個の Task に分割し、コア数を変更して測定を行った結果を表\ref{table:result}、図\ref{fig:result}に示す。
+要素数$2^{17}$*1000 のデータを640個の Task に分割し、コア数を変更して測定を行った結果を表\ref{table:result}、図\ref{fig:result}に示す。
 
 \begin{table}[ht]
     \begin{center}
--- a/presen/sigos.html	Sun May 29 16:34:28 2016 +0900
+++ b/presen/sigos.html	Sun May 29 19:28:03 2016 +0900
@@ -87,11 +87,21 @@
 <!-- === begin markdown block ===
 
       generated by markdown/1.2.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15]
-                on 2016-05-29 16:21:21 +0900 with Markdown engine kramdown (1.11.1)
+                on 2016-05-29 18:34:59 +0900 with Markdown engine kramdown (1.11.1)
                   using options {}
   -->
 
 <!-- _S9SLIDE_ -->
+<h2 id="gears-os">Gears OS</h2>
+<ul>
+  <li>当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて、並列性、柔軟性、信頼性を指標とした Gears OS を設計してきた</li>
+  <li>本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装し、並列処理を行う簡単な例題を用いて評価を行う</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
 <h2 id="gears-os-">Gears OS の並列性</h2>
 <ul>
   <li>Code Gear と Data Gear という Code と Data の単位を使って構成される</li>
@@ -105,7 +115,7 @@
 <h2 id="gears-os--1">Gears OS の柔軟性</h2>
 <ul>
   <li>Gear を追加することでデータ拡張や機能の追加が可能</li>
-  <li>GPU などの CPU とは異なるアーキテクチャでも同じプログラムが動く</li>
+  <li>GPU 等のさまざまなアーキテクチャでも同じプログラムが動く</li>
   <li>バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う</li>
   <li>実行時の処理の変更を可能とする</li>
 </ul>
@@ -177,7 +187,7 @@
 <ul>
   <li>Gears OS の柔軟性は Meta Computation で実現</li>
   <li>Meta Computation は通常の Computation のための Computation</li>
-  <li>並列処理の依存関係の解決、 GPUなどの別アーキテクチャでの実行のための処理など</li>
+  <li>並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理など</li>
   <li>Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現</li>
 </ul>
 
@@ -220,8 +230,7 @@
     </ul>
   </li>
   <li>Code Segment 間は <code>goto CS名</code> で移動する。この移動を継続と呼ぶ</li>
-  <li>C の関数呼び出しとは違い、 Code Segment では戻り値を持たないため、スタックに値を積まない</li>
-  <li>このような元の環境を持たない継続を計量継続と呼ぶ</li>
+  <li>C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ</li>
 </ul>
 
 <pre lang="c"><code>/* code1 define */
@@ -242,9 +251,9 @@
 <!-- _S9SLIDE_ -->
 <h2 id="context">Context</h2>
 <ul>
-  <li>Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている</li>
-  <li>Gear にアクセスする際は Context を経由する</li>
-  <li>Gears OS では Worker 毎にContext を持っている</li>
+  <li>Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている Meta Data Gear</li>
+  <li>各 Gear にアクセスする際は Context を経由する</li>
+  <li>Worker 毎にContext を持っている</li>
 </ul>
 
 
@@ -288,7 +297,7 @@
 
 <ul>
   <li>実行可能な Code Gear の数を示す <strong>CodeNum</strong></li>
-  <li>実行可能な Code Gear へのポイント <strong>Code</strong></li>
+  <li>実行可能な Code Gear へのポインタ <strong>Code</strong></li>
   <li>Data Gear の Allocate 用の <strong>heapStart</strong>, <strong>heap</strong>, <strong>heapLimit</strong></li>
   <li>Data Gear の数を示す <strong>dataNum</strong></li>
   <li>Data Gear へのポインタ <strong>data</strong></li>
@@ -324,7 +333,7 @@
 <h2 id="code-gear--stub">Code Gear の stub</h2>
 <ul>
   <li>通常 Data Gear にアクセスするにはContext を経由しなければならない</li>
-  <li>しかし、通常の Code Gear ではMeta Code Gear である Context をあまり参照したくない</li>
+  <li>しかし、通常の Code Gear ではMeta Data Gear である Context をあまり参照したくない</li>
   <li>そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する</li>
   <li>stub は一種の Meta Code Gear である</li>
 </ul>
@@ -366,7 +375,7 @@
     ...
 }
 
-__code code1_stub(struct Context* context) {
+__code code2_stub(struct Context* context) {
     goto code1(context, &amp;context-&gt;data[Node]-&gt;node.value-&gt;array);
 }
 </code></pre>
@@ -403,7 +412,6 @@
 <ul>
   <li>Context
     <ul>
-      <li>接続可能な Code/Data Gear のリスト、 TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、独立したメモリ空間を持っている</li>
       <li>Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される</li>
     </ul>
   </li>
@@ -411,7 +419,6 @@
     <ul>
       <li>CAS を利用したスレッドセーフなQueue</li>
       <li>ActiveTaskQueue と WaitTaskQueue の 2種類</li>
-      <li>ActiveTaskQueue は実行可能なTaskが挿入され, WaitTaskQueue には依存関係が解決されていないTaskが挿入される</li>
     </ul>
   </li>
 </ul>
@@ -429,12 +436,10 @@
   <li>Persistent Data Tree
     <ul>
       <li>Code Gear によって参照される Data Gear の管理を行う</li>
-      <li>Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う</li>
     </ul>
   </li>
   <li>TaskManager
     <ul>
-      <li>Task の依存関係の解決を行う</li>
       <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li>
     </ul>
   </li>
@@ -467,21 +472,6 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="context-3">Context</h2>
-<ul>
-  <li>Context は接続可能な Code/Data Gearへの参照をもっている</li>
-  <li>メインとなる Context と Worker 用 Context がある
-    <ul>
-      <li>TaskQueue と Persistent Data Tree はすべての Context で共有する</li>
-      <li>Worker 毎に作られる Temporal Data Gear のメモリ空間は Context 毎に異なる</li>
-    </ul>
-  </li>
-</ul>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
 <h2 id="taskqueue">TaskQueue</h2>
 <ul>
   <li>Task Queue は Task の管理を行う</li>
@@ -494,19 +484,7 @@
   </li>
 </ul>
 
-<pre lang="c"><code>// Code Gear Name
-enum Code {
-    PutQueue,
-    GetQueue
-};
-
-// Unique Data Gear
-enum UniqueData {
-    Queue,
-    Element
-};
-
-// Data Gear define
+<pre lang="c"><code>// Data Gear define
 union Data {
     struct Queue {
         struct Element* first;
@@ -527,7 +505,6 @@
 <h2 id="taskqueueenqueue">TaskQueueの操作(Enqueue)</h2>
 <ul>
   <li>Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定</li>
-  <li>Queue の last を追加する要素に設定</li>
   <li>正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある</li>
 </ul>
 
@@ -553,22 +530,8 @@
 <ul>
   <li>Persistent Data Tree は Data Gear の管理を行う</li>
   <li>TaskQueue と同じですべての Context で共有される</li>
-  <li>一度破壊した木構造を破壊すること無く新しい木構造を構築するため、変更して読み書き可能</li>
-  <li>非破壊木構造はルートから変更したいノードへのパスすべてをコピーし、パズ上に存在しないノードはコピー元の木構造と共有する</li>
-</ul>
-
-<div style="text-align: center;">
-    <img src="./images/persistent_date_tree.svg" alt="message" width="750" />
-</div>
-
-
-</div>
-<div class='slide '>
-<!-- _S9SLIDE_ -->
-<h2 id="persistent-data-tree-1">Persistent Data Tree</h2>
-<ul>
-  <li>木構造を構築するとき最悪なケースでは事実上の線形リストになる</li>
-  <li>そのため、挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ</li>
+  <li>挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ</li>
+  <li>Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う</li>
 </ul>
 
 
@@ -710,7 +673,7 @@
       <li>CPU : 6-core Intel Xeon 2.66GHZ x 2</li>
     </ul>
   </li>
-  <li>要素数 : 2^17</li>
+  <li>要素数 : 2^17 * 1000</li>
   <li>分割数 : 640 タスク</li>
   <li>1 Task 当たりの処理量 : 2^11 * 100 elements</li>
 </ul>
@@ -762,15 +725,39 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-3">比較</h2>
+<h2 id="cerium-">Cerium との比較</h2>
+<ul>
+  <li>Cerium は本研究室で開発していた並列プログラミングフレームワーク</li>
+  <li>Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする
+    <ul>
+      <li>本来 Task はデータに依存するもので Task 感の依存関係ではデータの依存関係を保証することが出来ない</li>
+      <li>Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる</li>
+    </ul>
+  </li>
+  <li>また Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、型の検査を行うことが出来ない
+    <ul>
+      <li>Gears OS では 型情報をもつ Data Gear を定義</li>
+    </ul>
+  </li>
+</ul>
 
 
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-4">まとめ</h2>
+<h2 id="os-">既存の OS との比較</h2>
 <ul>
-  <li>Cerium を開発して得られた知見か らCode Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li>
+  <li>Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義</li>
+  <li>通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う</li>
+</ul>
+
+
+</div>
+<div class='slide '>
+<!-- _S9SLIDE_ -->
+<h2 id="section-3">まとめ</h2>
+<ul>
+  <li>Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li>
   <li>Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li>
   <li>依存関係のない Twice を用いて並列処理を行い十分な台数効果が出ることを確認した</li>
 </ul>
@@ -779,7 +766,7 @@
 </div>
 <div class='slide '>
 <!-- _S9SLIDE_ -->
-<h2 id="section-5">今後の課題</h2>
+<h2 id="section-4">今後の課題</h2>
 <ul>
   <li>一般的に並列処理には依存関係が存在する
     <ul>
--- a/presen/sigos.md	Sun May 29 16:34:28 2016 +0900
+++ b/presen/sigos.md	Sun May 29 19:28:03 2016 +0900
@@ -3,6 +3,9 @@
 profile: 琉球大学理工学研究科情報工学専攻
 lang: Japanese
 code-engine: coderay
+## Gears OS
+- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて、並列性、柔軟性、信頼性を指標とした Gears OS を設計してきた
+- 本研究では Gears OS のプロトタイプとして並列処理機構をCbC(Continuation based C) で実装し、並列処理を行う簡単な例題を用いて評価を行う
 
 ## Gears OS の並列性
 - Code Gear と Data Gear という Code と Data の単位を使って構成される
@@ -10,7 +13,7 @@
 
 ## Gears OS の柔軟性
 - Gear を追加することでデータ拡張や機能の追加が可能
-- GPU などの CPU とは異なるアーキテクチャでも同じプログラムが動く
+- GPU 等のさまざまなアーキテクチャでも同じプログラムが動く
 - バージョンが異なる Gears OS でも Gear の共通部分を用いて通信を行う
 - 実行時の処理の変更を可能とする
 
@@ -46,7 +49,7 @@
 ## Meta Computation
 - Gears OS の柔軟性は Meta Computation で実現
 - Meta Computation は通常の Computation のための Computation
-- 並列処理の依存関係の解決、 GPUなどの別アーキテクチャでの実行のための処理など
+- 並列処理の依存関係の解決、 GPUなどのアーキテクチャでの実行のために行う処理など
 - Gears OS では Meta Computation を Meta Code Gear, Meta Data Gear で表現
 
 ## Meta Gear
@@ -69,8 +72,7 @@
 - Code Segment の定義は ``__code CS名`` で行う
     - Code Gear も同等に定義する
 - Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
-- C の関数呼び出しとは違い、 Code Segment では戻り値を持たないため、スタックに値を積まない
-- このような元の環境を持たない継続を計量継続と呼ぶ
+- C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ
 
 ``` c
 /* code1 define */
@@ -86,9 +88,9 @@
 ```
 
 ## Context
-- Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている
-- Gear にアクセスする際は Context を経由する
-- Gears OS では Worker 毎にContext を持っている
+- Context は 接続可能な Code/Data Gear のリスト、それらを結びつけるMeta Gear, 独立したメモリ空間をもっている Meta Data Gear
+- 各 Gear にアクセスする際は Context を経由する
+- Worker 毎にContext を持っている
 
 ## Context
 - 実行可能な Code Gear の名前は **enum** で定義する
@@ -120,7 +122,7 @@
 ```
 
 - 実行可能な Code Gear の数を示す **CodeNum**
-- 実行可能な Code Gear へのポイント **Code**
+- 実行可能な Code Gear へのポインタ **Code**
 - Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit**
 - Data Gear の数を示す **dataNum**
 - Data Gear へのポインタ **data**
@@ -145,7 +147,7 @@
 
 ## Code Gear の stub
 -  通常 Data Gear にアクセスするにはContext を経由しなければならない
-- しかし、通常の Code Gear ではMeta Code Gear である Context をあまり参照したくない
+- しかし、通常の Code Gear ではMeta Data Gear である Context をあまり参照したくない
 - そのため、通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
 - stub は一種の Meta Code Gear である
 
@@ -183,7 +185,7 @@
     ...
 }
 
-__code code1_stub(struct Context* context) {
+__code code2_stub(struct Context* context) {
     goto code1(context, &context->data[Node]->node.value->array);
 }
 ```
@@ -209,12 +211,10 @@
 
 ## Gears OS の構成
 - Context
-    - 接続可能な Code/Data Gear のリスト、 TaskQueue へのポインタ、 Persistent Data Tree へのポインタ、独立したメモリ空間を持っている
     - Worker 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される
 - TaskQueue
     - CAS を利用したスレッドセーフなQueue
     - ActiveTaskQueue と WaitTaskQueue の 2種類
-    - ActiveTaskQueue は実行可能なTaskが挿入され, WaitTaskQueue には依存関係が解決されていないTaskが挿入される
 
 <div style="text-align: center;">
     <img src="./images/gearsos.svg" alt="message" width="750">
@@ -223,9 +223,7 @@
 ## Gears OS の構成
 - Persistent Data Tree
     - Code Gear によって参照される Data Gear の管理を行う
-    - Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う
 - TaskManager
-    - Task の依存関係の解決を行う
     - Persistent Data Tree を監視し、 Task の依存関係を解決する
 
 <div style="text-align: center;">
@@ -242,12 +240,6 @@
     <img src="./images/gearsos.svg" alt="message" width="750">
 </div>
 
-## Context
-- Context は接続可能な Code/Data Gearへの参照をもっている
-- メインとなる Context と Worker 用 Context がある
-    - TaskQueue と Persistent Data Tree はすべての Context で共有する
-    - Worker 毎に作られる Temporal Data Gear のメモリ空間は Context 毎に異なる
-
 ## TaskQueue
 - Task Queue は Task の管理を行う
 - すべての Worker の Context で共有される
@@ -256,18 +248,6 @@
     - Task と次の要素へのポインタを持った、List を表現する Element という Data Gear
 
 ``` c
-// Code Gear Name
-enum Code {
-    PutQueue,
-    GetQueue
-};
-
-// Unique Data Gear
-enum UniqueData {
-    Queue,
-    Element
-};
-
 // Data Gear define
 union Data {
     struct Queue {
@@ -284,7 +264,6 @@
 
 ## TaskQueueの操作(Enqueue)
 - Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
-- Queue の last を追加する要素に設定
 - 正しく最後の要素が変更できたことをCAS で 保証し、末尾の変更を行う必要がある
 
 ``` c
@@ -306,6 +285,7 @@
 - Persistent Data Tree は Data Gear の管理を行う
 - TaskQueue と同じですべての Context で共有される
 - 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ
+- Persistent Data Tree への書き込みのみで Worker 間の相互作用を発生させ、目的の処理を行う
 
 ## Worker
 - Worker は TaskQueue から Task を取得して実行する
@@ -412,7 +392,7 @@
     - OS : Mac OS X 10.10.5
     - Memory : 16GB
     - CPU : 6-core Intel Xeon 2.66GHZ x 2
-- 要素数 : 2^17
+- 要素数 : 2^17 * 1000
 - 分割数 : 640 タスク
 - 1 Task 当たりの処理量 : 2^11 * 100 elements
 
@@ -454,10 +434,16 @@
 - 十分な台数効果が出てる事がわかる
 
 ## Cerium との比較
-- Cerium は本研究室で開発していた並列プログラミングフレームワークである。
-- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする。
-- Gears OS の Task は 
+- Cerium は本研究室で開発していた並列プログラミングフレームワーク
+- Cerium では Task と呼ばれる分割されたプログラムを依存関係に沿って実行することで並列実行を可能にする
+    - 本来 Task はデータに依存するもので Task 感の依存関係ではデータの依存関係を保証することが出来ない
+    - Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
+- また Task には汎用ポインタとしてデータの受け渡しを行うため、型情報がなく、型の検査を行うことが出来ない
+    - Gears OS では 型情報をもつ Data Gear を定義
 
+## 既存の OS との比較
+- Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
+- 通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う
 
 ## まとめ
 - Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った
@@ -470,10 +456,10 @@
 - GPUなどの他のプロセッサ演算に利用することが出来ない
     - Data Gear などのデータをGPUにマッピングするための機構が必要
 - Gears OS でのデバック手法
-    - 軽量継続はスタックを積まないため、スタックトレースが見えない
-    - Context から Data Gear を取得できるため、そこから現在の状況を把握することができる
-    - Context を見ることができる コードを Meta Computation として入れることで Code Gear を止めて、 Data Gear の状態を見ることができる
-    - しかし、 Gears OS は並列実行を基本とするため、 並列で動いているCode Gear に対しては綺麗にデバック出来ない
+    - 軽量継続はスタックを積まないため、スタックトレースが見えないためその対策
     - 並列処理でのデバック手法も考案する必要がある
 - 型情報の検査
     - プログラムの正しさを保証するために Data Gear 野方情報を検査するシステムを Meta Computation として実装する
+- Contextの動的生成
+    - 今は静的に自分で生成している
+    - CbC 用の Runtime をつくり、 Context を動的に生成
--- a/sigos.mm	Sun May 29 16:34:28 2016 +0900
+++ b/sigos.mm	Sun May 29 19:28:03 2016 +0900
@@ -112,6 +112,7 @@
 <node CREATED="1464433038681" ID="ID_1903319486" MODIFIED="1464433048944" TEXT="Code &#x3068; Data&#x3092;&#x7406;&#x8ad6;&#x306b;&#x5b9a;&#x7fa9;"/>
 </node>
 </node>
+<node CREATED="1464508482859" ID="ID_1478172490" MODIFIED="1464508523088" TEXT="&#x6700;&#x521d;&#x306b;&#x3042;&#x308b;&#x7a0b;&#x5ea6;&#x307e;&#x3068;&#x3081;&#x305f;&#x30b9;&#x30e9;&#x30a4;&#x30c9;(&#x53bb;&#x5e74;&#x3068;&#x306e;&#x9055;&#x3044;)&#x3092;&#x5165;&#x308c;&#x308b;"/>
 </node>
 <node CREATED="1464433060055" ID="ID_160981626" MODIFIED="1464433064591" TEXT="Gears &#x306e;&#x30a2;&#x30d7;&#x30ed;&#x30fc;&#x30c1;">
 <node CREATED="1464433065885" ID="ID_181737657" MODIFIED="1464433083653" TEXT="&#x4e26;&#x5217;&#x5b9f;&#x884c;&#x306f;Input &#x304c;&#x63c3;&#x3063;&#x305f; CG &#x304b;&#x3089;&#x5b9f;&#x884c;"/>