Mercurial > hg > Papers > 2016 > parusu-sigos
changeset 20:cd38e09f980b
Fix
author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 31 May 2016 01:27:56 +0900 |
parents | a2a9d91db377 |
children | f035e77dcca3 |
files | presen/sigos.html presen/sigos.md |
diffstat | 2 files changed, 80 insertions(+), 125 deletions(-) [+] |
line wrap: on
line diff
--- a/presen/sigos.html Mon May 30 23:48:31 2016 +0900 +++ b/presen/sigos.html Tue May 31 01:27:56 2016 +0900 @@ -87,7 +87,7 @@ <!-- === begin markdown block === generated by markdown/1.2.0 on Ruby 2.3.1 (2016-04-26) [x86_64-darwin15] - on 2016-05-30 23:46:39 +0900 with Markdown engine kramdown (1.11.1) + on 2016-05-31 01:26:46 +0900 with Markdown engine kramdown (1.11.1) using options {} --> @@ -226,11 +226,11 @@ <li>Meta Data Gear は Meta Code Gear で管理されるデータ部分</li> </ul> </li> - <li>Gears は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う</li> + <li>Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う</li> </ul> <div style="text-align: center;"> - <img src="./images/meta_cg_dg.svg" alt="message" width="450" /> + <img src="./images/meta_cg_dg.svg" alt="message" width="850" /> </div> @@ -252,7 +252,11 @@ <ul> <li>Code Segment の定義は <code>__code CS名</code> で行う</li> <li>Code Segment 間は <code>goto CS名</code> で移動する。この移動を継続と呼ぶ</li> - <li>C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ</li> + <li>Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない + <ul> + <li>このような環境を持たない継続を軽量継続と呼ぶ</li> + </ul> + </li> </ul> @@ -357,8 +361,8 @@ <ul> <li>Context は <ul> - <li>実行可能な Code Gear の数を示す <strong>CodeNum</strong></li> - <li>実行可能な Code Gear のリストを示す <strong>Code</strong></li> + <li>実行可能な Code Gear の数を示す <strong>codeNum</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> @@ -448,75 +452,48 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears-os--3">Gears OS 構成</h2> +<h2 id="section-1">プロトタイプ の構成</h2> <ul> - <li>Context + <li>今回は並列処理を行う機構の実装を行う</li> + <li>必要な要素は大きく5つ <ul> - <li>Thread 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される</li> - </ul> - </li> - <li>TaskQueue - <ul> - <li>実行される Task のリストを扱う</li> + <li>Context</li> + <li>TaskQueue + <ul> + <li>実行される Task のリストを扱う</li> + </ul> + </li> + <li>Persistent Data Tree + <ul> + <li>Code Gear によって参照される Data Gear の管理を行う</li> + </ul> + </li> + <li>TaskManager + <ul> + <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li> + </ul> + </li> + <li>Worker + <ul> + <li>TaskQueue から Task を取得し、実行する</li> + </ul> + </li> </ul> </li> </ul> -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="gears-os--4">Gears OS の構成</h2> -<ul> - <li>Persistent Data Tree - <ul> - <li>Code Gear によって参照される Data Gear の管理を行う</li> - </ul> - </li> - <li>TaskManager - <ul> - <li>Persistent Data Tree を監視し、 Task の依存関係を解決する</li> - </ul> - </li> -</ul> - -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="gears-os--5">Gears OS の構成</h2> -<ul> - <li>Worker - <ul> - <li>TaskQueue から Task を取得し、実行する</li> - </ul> - </li> -</ul> - -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750" /> -</div> - </div> <div class='slide '> <!-- _S9SLIDE_ --> <h2 id="taskqueue">TaskQueue</h2> <ul> - <li>Task Queue は Task の管理を行う</li> - <li>すべての Worker の Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li> + <li>Task Queue は Task のリストを扱う</li> + <li>すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する</li> <li>TaskQueue は 2つで Data Gear で表現される <ul> <li>先頭と末尾の要素を持った Queue 表す Data Gear</li> - <li>Task と次の要素へのポインタを持った、List を表現する Element という Data Gear</li> + <li>Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear</li> </ul> </li> </ul> @@ -572,7 +549,7 @@ </ul> <div style="text-align: center;"> - <img src="./images/persistent_date_tree_2.svg" alt="message" width="700" /> + <img src="./images/persistent_date_tree_2.svg" alt="message" width="800" /> </div> @@ -596,8 +573,6 @@ struct Node* root; } tree; struct Node { - // need to tree - enum Code next; int key; // comparable data segment union Data* value; struct Node* left; @@ -629,12 +604,12 @@ </div> </td> <td> - <ul> + <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> - </ul> + </ol> </td> </tr> </tbody> @@ -680,7 +655,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-1">プロトタイプの実行</h2> +<h2 id="section-2">プロトタイプの実行</h2> <ul> <li>今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った</li> <li>これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった</li> @@ -690,7 +665,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="gears--code-gear-">Gears で実行する Code Gear 例</h2> +<h2 id="gears-os--code-gear-">Gears OS で実行する Code Gear 例</h2> <ul> <li>プロトタイプのタスクの例題として Twice を実装した</li> <li>Twice は与えられた整数配列を2倍にする例題である</li> @@ -717,7 +692,7 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-2">並列処理の確認</h2> +<h2 id="section-3">並列処理の確認</h2> <ul> <li>Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った</li> <li>環境 @@ -789,21 +764,19 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="os-">既存の OS との比較</h2> +<h2 id="os-">既存の OS への対応</h2> <ul> <li>Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義</li> - <li>通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う</li> - <li>対応表書く</li> + <li>通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う</li> </ul> </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-3">まとめ</h2> +<h2 id="section-4">まとめ</h2> <ul> - <li>Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った</li> - <li>Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li> + <li>Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った</li> <li>依存関係のない Twice を実装し、並列処理が行えることを確認した</li> </ul> @@ -811,11 +784,11 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="section-4">今後の課題</h2> +<h2 id="section-5">今後の課題</h2> <ul> <li>一般的に並列処理には依存関係が存在する <ul> - <li>複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する</li> + <li>複雑な並列処理を実行できるようにするために Task Manager の実装を行い、 依存関係のある並列処理の例題を作成し、評価する</li> </ul> </li> <li>GPUなどの他のプロセッサ演算に利用することが出来ない @@ -825,7 +798,7 @@ </li> <li>Gears OS でのデバック手法 <ul> - <li>軽量継続はスタックを積まないため、スタックトレースが見えないためその対策</li> + <li>継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案</li> <li>並列処理でのデバック手法も考案する必要がある</li> </ul> </li>
--- a/presen/sigos.md Mon May 30 23:48:31 2016 +0900 +++ b/presen/sigos.md Tue May 31 01:27:56 2016 +0900 @@ -76,10 +76,10 @@ - この Gear を Meta Code/Data Gearと呼ぶ - Meta Code Gear は Meta Computation のプログラム部分 - Meta Data Gear は Meta Code Gear で管理されるデータ部分 -- Gears は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う +- Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 接続部分は見えないように実装を行う <div style="text-align: center;"> - <img src="./images/meta_cg_dg.svg" alt="message" width="450"> + <img src="./images/meta_cg_dg.svg" alt="message" width="850"> </div> @@ -91,7 +91,8 @@ ## Continuation based C - Code Segment の定義は ``__code CS名`` で行う - Code Segment 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ -- C の関数呼び出しとは異なり、Code Segment では戻り値を持たない。このような環境を持たない継続を計量継続と呼ぶ +- Code Segment の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない + - このような環境を持たない継続を軽量継続と呼ぶ ## Continuation based C - このコードは code1、code2 の2つの Code Segment を定義している @@ -166,8 +167,8 @@ ## Context - Context は - - 実行可能な Code Gear の数を示す **CodeNum** - - 実行可能な Code Gear のリストを示す **Code** + - 実行可能な Code Gear の数を示す **codeNum** + - 実行可能な Code Gear のリストを示す **code** - Data Gear の Allocate 用の **heapStart**, **heap**, **heapLimit** - Data Gear の数を示す **dataNum** - Data Gear のリストを示す **data** @@ -236,40 +237,25 @@ } ``` -## Gears OS 構成 -- Context - - Thread 毎にContext を持っており、 TaskQueue と Persistent Data Tree は共有される -- TaskQueue - - 実行される Task のリストを扱う - -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750"> -</div> - -## Gears OS の構成 -- Persistent Data Tree - - Code Gear によって参照される Data Gear の管理を行う -- TaskManager - - Persistent Data Tree を監視し、 Task の依存関係を解決する - -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750"> -</div> - -## Gears OS の構成 -- Worker - - TaskQueue から Task を取得し、実行する - -<div style="text-align: center;"> - <img src="./images/gearsos.svg" alt="message" width="750"> -</div> +## プロトタイプ の構成 +- 今回は並列処理を行う機構の実装を行う +- 必要な要素は大きく5つ + - Context + - TaskQueue + - 実行される Task のリストを扱う + - Persistent Data Tree + - Code Gear によって参照される Data Gear の管理を行う + - TaskManager + - Persistent Data Tree を監視し、 Task の依存関係を解決する + - Worker + - TaskQueue から Task を取得し、実行する ## TaskQueue -- Task Queue は Task の管理を行う -- すべての Worker の Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する +- Task Queue は Task のリストを扱う +- すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する - TaskQueue は 2つで Data Gear で表現される - 先頭と末尾の要素を持った Queue 表す Data Gear - - Task と次の要素へのポインタを持った、List を表現する Element という Data Gear + - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear ``` c // Data Gear define @@ -312,7 +298,7 @@ - 木構造から読み出される Data Gear は Code Gear の Input Data Gear, 書き出すData Gear は Output Data Gear になる <div style="text-align: center;"> - <img src="./images/persistent_date_tree_2.svg" alt="message" width="700"> + <img src="./images/persistent_date_tree_2.svg" alt="message" width="800"> </div> ## Persistent Data Tree @@ -328,8 +314,6 @@ struct Node* root; } tree; struct Node { - // need to tree - enum Code next; int key; // comparable data segment union Data* value; struct Node* left; @@ -356,12 +340,12 @@ </div> </td> <td> - <ul> + <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> - </ul> + </ol> </td> </tr> </tbody> @@ -400,7 +384,7 @@ - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった -## Gears で実行する Code Gear 例 +## Gears OS で実行する Code Gear 例 - プロトタイプのタスクの例題として Twice を実装した - Twice は与えられた整数配列を2倍にする例題である @@ -472,23 +456,21 @@ - 型情報がなく、型の検査を行うことが出来ない - Gears OS では 型情報をもつ Data Gear を定義 -## 既存の OS との比較 +## 既存の OS への対応 - Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義 -- 通常の Code Gear から必要な制御を推論し、 Meta Code Gear を接続することで従来のOSが行ってきた制御の提供を行う -- 対応表書く +- 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う ## まとめ -- Code Gear、 Data Gear によって構成される Gears OS のプロトタイプの設計、実装を行った -- Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った +- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った - 依存関係のない Twice を実装し、並列処理が行えることを確認した ## 今後の課題 - 一般的に並列処理には依存関係が存在する - - 複雑な並列処理を実行できるようにするために依存関係のある並列処理の例題を作成し、評価する + - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、 依存関係のある並列処理の例題を作成し、評価する - GPUなどの他のプロセッサ演算に利用することが出来ない - Data Gear などのデータをGPUにマッピングするための機構が必要 - Gears OS でのデバック手法 - - 軽量継続はスタックを積まないため、スタックトレースが見えないためその対策 + - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案 - 並列処理でのデバック手法も考案する必要がある - 型情報の検査 - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを Meta Computation として実装する