Papers/2018/parusu-master: slide/slide.md annotate

author	Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp>
date	Fri, 09 Feb 2018 19:49:46 +0900
parents
children	cae61efc3f26

rev	line source
77 161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	1 title: Gears OS の並列処理
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	2 author: 伊波立樹
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	3 profile: 琉球大学理工学研究科河野研
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	4 lang: Japanese
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	5 code-engine: coderay
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	6 ## Gears OS
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	7 - 並列処理のチューニングや信頼性を保証するのは難しい
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	8 - スレッド間の共通資源の競合などの非決定的な実行
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	9 - 従来のテストやデバッグではテストしきれない部分が残ってしまう
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	10 - Gears OS では計算をノーマルレベルとメタレベルに階層化
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	11 - ノーマルレベルの計算に対してメタレベルで信頼性を保証したい
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	12 - メタレベルの計算はデータ拡張や実行環境の切り替え等の拡張性のための計算を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	13
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	14 ## Code Gear、 Data Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	15 - Gears OS は Code Gear、 Data Gear という Gear で構成される
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	16 - Code Gear はプログラムの処理そのものを表す
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	17 - Data Gear はデータそのものを表す
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	18 - Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	19 - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Input Data Gear が揃った Code Gear の並列実行を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	20
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	21 <div style="text-align: center;">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	22 <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	23 </div>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	24
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	25 ## Continuation based C
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	26 - Gears OS の実装は本研究室で開発している Continuation based C(CbC) を用いる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	27 - CbC は処理を Code Gear を用いて記述する事を基本とする
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	28
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	29 ## Continuation based C
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	30 - Code Gear の定義は ``__code CS名`` で行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	31 - Code Gear 間は ``goto CS名`` で移動する。この移動を継続と呼ぶ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	32 - Code Gear の継続は C の関数呼び出しとは異なり、戻り値を持たないためスタックの変更を行わない
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	33 - このような環境を持たない継続を軽量継続と呼ぶ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	34
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	35 ## Continuation based C
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	36 - このコードは cg0、cg1 の2つの Code Gear を定義している
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	37 - cg0 内の ``goto cg1`` でgj1 への継続を行っている
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	38 - ここで(a+b) が cg1 への入力になる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	39
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	40 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	41 __code cg0(int a, int b) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	42 goto cg1(a+b);
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	43
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	44 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	45
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	46 __code cg1(int c) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	47 goto cg2(c);
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	48 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	49 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	50
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	51 ## メタ計算
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	52 - メタ計算は通常の計算を実行するための計算
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	53 - 信頼性の確保やメモリ管理、スレッド管理、 CPU、 GPU の資源管理等
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	54 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	55
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	56 ## Meta Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	57 - メタ計算は Code Gearの接続の間に行われる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	58 - メタ計算の処理も Code/Data Gear で実現する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	59 - この Gear を Meta Code/Data Gearと呼ぶ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	60 - Meta Code Gear はメタ計算のプログラム部分
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	61 - Meta Data Gear は Meta Code Gear で管理されるデータ部分
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	62 - Gears OS は通常の Code/Data Gear から Meta Code/Data Gear 部分は見えないように実装を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	63
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	64 <div style="text-align: center;">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	65 <img src="./images/meta_cg_dg.svg" alt="message" width="850">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	66 </div>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	67
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	68 ## Context
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	69 - Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	70 - 従来のOS のスレッドやプロセスに対応
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	71 - 独立したメモリ空間を持つ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	72 - Code Gear、 Data Gear へのポインタ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	73 - 並列実行用の Task 情報
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	74 - を持つ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	75 - Gears OS ではメタ計算でこの Context を経由して Data Gear にアクセスする
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	76
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	77 ## Data Gear の表現
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	78 - Data Gear は構造体を用いて定義する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	79 - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	80 - Data Gear のメモリに確保する際のサイズ情報はこの型から決定する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	81
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	82 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	83 /* data Gear define */
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	84 union Data {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	85 struct Timer {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	86 union Data* timer;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	87 enum Code start;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	88 enum Code end;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	89 enum Code next;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	90 } Timer;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	91 struct TimerImpl {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	92 double time;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	93 } TimerImpl;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	94 ....
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	95 };
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	96 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	97
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	98 ## Code Gear の stub
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	99 - Data Gear にアクセスするにはContext を経由する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	100 - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	101 - Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	102 - stub は一種の Meta Code Gear であるため、 CbC で自動生成される
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	103 - このコードでは Array と LoopCounter が必要な code1 の stub を示している
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	104
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	105 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	106 __code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	107 ...
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	108 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	109
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	110 /* stub define */
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	111 __code code1_stub(struct Context* context) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	112 goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	113 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	114 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	115
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	116 ## Context での stub Code Gear の記述の問題点
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	117 - Context プログラム全体で使用する Code Gear と Data Gear の集合
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	118 - 全ての Code と Data の組合せをContext から全て展開し、その組合せを stub Code Gear に書く必要がある
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	119 - Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	120 - そのため Gears OS のモジュール化する仕組みとして Interface を導入した
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	121
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	122 ## Interface
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	123 - Interface はある Data Gear とそれに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	124 - これは Context より小さい集合のため、 stub Code Gear での各API で決まった形になる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	125 - Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	126 - Interface は Java のインターフェース、 Haskell の型クラスに対応する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	127 ## プロトタイプの構成
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	128 - 今回は並列処理を行う機構の実装を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	129 - 必要な要素は大きく5つ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	130 - Context
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	131 - TaskQueue
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	132 - 実行される Task のリストを扱う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	133 - Persistent Data Tree
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	134 - Code Gear によって参照される Data Gear の管理を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	135 - Worker
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	136 - TaskQueue から Task を取得し、実行する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	137 - TaskManager
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	138 - Persistent Data Tree を監視し、 Task の依存関係を解決する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	139
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	140 ※ TaskManager は今回未実装
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	141
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	142 ## TaskQueue
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	143 - Task Queue は Task のリストを扱う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	144 - すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	145 - TaskQueue は 2つで Data Gear で表現される
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	146 - 先頭と末尾の要素を持った Queue 表す Data Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	147 - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	148
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	149 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	150 // Data Gear define
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	151 union Data {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	152 struct Queue {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	153 struct Element* first;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	154 struct Element* last;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	155 } queue;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	156
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	157 struct Element {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	158 struct Task* task;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	159 struct Elemen* next;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	160 } element
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	161 };
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	162 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	163
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	164 ## TaskQueueの操作(Enqueue)
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	165 - Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	166 - 正しく最後の要素が変更できたことを CAS で保証し、末尾の変更を行う必要がある
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	167
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	168 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	169 __code putQueue3(struct Queue* queue, struct Element* new_element) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	170 struct Element* last = queue->last;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	171
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	172 if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	173 last->next = new_element;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	174
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	175 goto exit();
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	176 } else {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	177 goto putQueue3(queue, new_element);
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	178 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	179 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	180
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	181 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	182
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	183 ## Worker
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	184 - Worker は TaskQueue から Task を取得して実行する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	185
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	186 <table align='center'>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	187 <tbody>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	188 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	189 <td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	190 <div>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	191 <img src="./images/worker.svg" alt="message" width="600">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	192 </div>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	193 </td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	194 <td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	195 <ol>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	196 <li> Worker は Task Queue から Task を取り出す(1. Dequeue Task)</li>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	197 <li> 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear) </li>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	198 <li> Task に格納されている Code Gear を実行する </li>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	199 <li> Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear) </li>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	200 </ol>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	201 </td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	202 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	203 </tbody>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	204 </table>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	205
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	206 - Task が完了したら次の Task を取得する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	207
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	208 ## TaskManger
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	209 - TaskManager は Task の依存関係の解決を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	210 - Thread の作成と停止も行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	211
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	212 <div style="text-align: center;">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	213 <img src="./images/taskManager.svg" alt="message" width="800">
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	214 </div>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	215
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	216
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	217 ## プロトタイプの実行
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	218 - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	219 - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	220
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	221 ## Gears OS で実行する Code Gear 例
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	222 - プロトタイプのタスクの例題として Twice を実装した
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	223 - Twice は与えられた整数配列を2倍にする例題である
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	224
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	225 ``` c
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	226 // Twice Code Gear
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	227 __code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	228 int i = loopCounter->i;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	229
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	230 if (i < alignment) {
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	231 array[i+indexalignment] = array[i+indexalignment]*2;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	232 loopCounter->i++;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	233
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	234 goto twice(loopCounter, index, alignment, array);
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	235 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	236
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	237 loopCounter->i = 0;
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	238
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	239 goto exit();
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	240 }
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	241 ```
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	242
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	243 ## 並列処理の確認
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	244 - Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	245 - 環境
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	246 - Memory : 16GB
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	247 - CPU : 6-core Intel Xeon 2.66GHZ x 2
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	248 - 要素数 : 2^17 * 1000
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	249 - 分割数 : 640 タスク
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	250 - 1 Task 当たりの処理量 : 2^11 * 100 elements
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	251
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	252 <table border="1" align='center' width='50%'>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	253 <tbody>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	254 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	255 <td style="text-align: center;">Number of Processors</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	256 <td style="text-align: center;">Time(ms)</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	257 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	258 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	259 <td style="text-align: center;">1 CPU</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	260 <td style="text-align: right;">1315</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	261 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	262 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	263 <td style="text-align: center;">2 CPUs</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	264 <td style="text-align: right;">689</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	265 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	266 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	267 <td style="text-align: center;">4 CPUs</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	268 <td style="text-align: right;">366</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	269 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	270 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	271 <td style="text-align: center;">8 CPUs</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	272 <td style="text-align: right;">189</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	273 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	274 <tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	275 <td style="text-align: center;">12 CPUs</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	276 <td style="text-align: right;">111</td>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	277 </tr>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	278 </tbody>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	279 </table>
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	280
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	281 - 1cpu と 12cpu では 11.8 倍の向上が見られた
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	282
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	283
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	284 ## Cerium との比較
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	285 - Cerium は本研究室で開発していた並列プログラミングフレームワーク
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	286 - Cerium では Task を依存関係に沿って実行することで並列実行を可能にする
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	287 - 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	288 - Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	289 - Task には汎用ポインタとしてデータの受け渡しを行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	290 - 型情報がなく、型の検査を行うことが出来ない
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	291 - Gears OS では型情報をもつ Data Gear を定義
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	292
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	293 ## 既存の OS への対応
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	294 - Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	295 - 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	296
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	297 ## まとめ
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	298 - Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	299 - 依存関係のない Twice を実装し、並列処理が行えることを確認した
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	300
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	301 ## 今後の課題
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	302 - 一般的に並列処理には依存関係が存在する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	303 - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、依存関係のある並列処理の例題を作成し、評価する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	304 - GPUなどの他のプロセッサ演算に利用することが出来ない
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	305 - Data Gear などのデータをGPUにマッピングするための機構が必要
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	306 - Gears OS でのデバック手法
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	307 - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	308 - 並列処理でのデバック手法も考案する必要がある
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	309 - 型情報の検査
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	310 - プログラムの正しさを保証するために Data Gear の情報を検査するシステムをメタ計算として実装する
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	311 - Contextの動的生成
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	312 - 今は静的に自分で生成している
161db9fd907a Add slide Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	313 - CbC 用の Runtime をつくり、 Context を動的に生成

77

161db9fd907a Add slide