Mercurial > hg > Papers > 2018 > parusu-master
diff slide/slide.md @ 94:e71d4ea8a616
Fix slide
author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 13 Feb 2018 02:23:28 +0900 |
parents | 0050ad0b4dd7 |
children | 14bd1b466bcc |
line wrap: on
line diff
--- a/slide/slide.md Tue Feb 13 00:49:10 2018 +0900 +++ b/slide/slide.md Tue Feb 13 02:23:28 2018 +0900 @@ -29,7 +29,7 @@ - Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う <div style="text-align: center;"> - <img src="./images/codeGear_dataGear_dependency.svg" alt="message" width="600"> + <img src="./images/codegear-datagear-dependency.svg" alt="message" width="600"> </div> ## メタ計算 @@ -70,16 +70,6 @@ } ``` -## Context -- Context は接続可能な Code/Data Gear の集合を表現する Meta Data Gear -- 従来のOS のスレッドやプロセスに対応し、以下の要素を定義している - - 独立したメモリ空間 - - Code/Data Gear へのポインタ - - Code/Data Gear は番号で指定する - - 並列実行用の Task 情報 - - Data Gear の型情報 -- Gears OS ではメタ計算で Context を経由して Code/Data Gear にアクセスする - ## Data Gear の表現 - Data Gear は構造体を用いて定義する - メタ計算では任意の Data Gear を一律に扱うため、全ての Data Gear は共用体の中で定義される @@ -101,34 +91,29 @@ }; ``` +## Context +- Context は従来のOS のスレッドやプロセスに対応し、以下の要素をもっている Meta Data Gear + - Data Gear を確保するためのメモリ空間 + - Code Gear の名前と関数ポインタとの対応表 + - Code Gear は番号(enum)で指定する + - Code Gear が参照する Data Gear へのポインタ + - Code Gear と同じく Data Gear も番号で指定する + - 並列実行用の Task 情報 + - Data Gear の型情報 +- Gears OS ではメタ計算で Context を経由して Code/Data Gear にアクセスする + ## stub Code Gear - Data Gear にアクセスするにはContext を経由する - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある - Gears OS ではメタレベルで通常の Code Gear で必要な Data Gear を Context から取り出す処理を行う stub Code Gear を用意している -``` c -// normal level Code Gear -__code cg0(struct Context* context, struct Integer integer, struct Queue queue) { - ... -} +<div style="text-align: center;"> + <img src="./images/contextContinuation.svg" alt="message" width="600"> +</div> -// meta level stub Code Gear -__code cg0_stub(struct Context* context) { - // get data index number - Integer integer = &context->data[context->dataNum]->Integer - // get enum data - Queue* queue = &context->data[Queue]->Queue; - // continuation Code Gear - goto cg0(context, integer, queue); -} -``` -<- このページを書き換える -> ## Context での stub Code Gear の記述の問題点 -- stub Code Gear は Context から Code Gear と Data Gear の全ての組合せを展開して記述する必要がある -- しかし、 Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた - - Data Gear は番号で指定するため、 Code Gear が どの Data Gear の番号に対応しているかを記述する必要がある - - stub Code Gear を自動生成するために、同じ番号の Data Gear を使いまわす問題 +- Gears OS を実装するに連れて、stub Code Gear の記述が煩雑になる場所がでてきた - そのため Gears OS のモジュール化する仕組みとして **Interface** を導入した ## Interface @@ -139,9 +124,8 @@ ## Interface の定義 - Interface の定義には以下の内容を定義する - - 引数のData Gear 群 - - 操作(API) 実行後に継続される Code Gear - - 操作(API) である Code Gear と Code Gear に渡す引数情報 + - 操作(API)の引数群の型 + - 操作(API)自体のCode Gear の型 ``` c typedef struct Queue<Impl>{ @@ -161,7 +145,7 @@ ## Interface の実装 - Interface には複数の実装を行うことが出来る -- 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う +- 実装した Code Gear の番号を Interface の定義に代入することで実装を行う - 代入する Code Gear を入れ替えることで別の実装を表現する - 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる @@ -203,7 +187,7 @@ - ここでの **interface** は Interfaceの型で包んだData Gear、 **method** は実装した Code Gear に対応する ``` -__code code1() { +__code code1() { Queue* queue = createSingleLinkedQueue(context); Node* node = new Node(); node->color = Red; @@ -254,8 +238,7 @@ ``` ## 並列処理の構成 -- 今回は並列処理機構の実装を Interface を利用して行う -- 構成要素として以下が挙げられる +- 今回は並列処理機構である - Task - TaskManager - Worker の生成、依存関係を解決したTask を Worker に送信する @@ -265,6 +248,7 @@ - Worker 毎に POSIX Therad などのスレッドを生成し、 Code Gear を実行する - SynchronizedQueue - マルチスレッド 環境でもデータの一貫性を保証する Queue +- をInterface で実装した ## Task - Gears OS では Context が並列実行の Task に相当する @@ -285,7 +269,9 @@ <ol> <li value="0">Task を Input Data Gear として</li> TaskManager の spawn を呼び出す - <li value="1">Input Data Gear が揃っているかを確認する</li> + <li value="1">Task内の idgCountをチェックする</li> + idgCount は待っているInput Data Gear のカウンタである + そのため、カウンタが0の場合 Input Data Gear が揃っていることになる <li value="2">揃っている場合、 Worker の Queue に</li> Task を送信する </ol> @@ -295,7 +281,7 @@ ## Worker - 初期化時に Worker 用の Context を生成する -- TaskManager から送信された Task を取得して実行する +- TaskManager から送信された Task を一つずつ取得して実行する <div> <div style="float: left;"> @@ -319,23 +305,14 @@ ## Synchronized Queue - Worker で使用される Queue - Task を送信するTaskManagerと Task を取得するWorker毎で操作される -- そのためマルチスレッドでのデータの同期処理を行う -- Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する - - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較する -- この Queue は Queue Interface を実装し、 List を利用した実装を行った +- そのためマルチスレッドでのデータの同期処理を行える SynchronizedQueue を実装する +- Gears OS では CAS(Check and Set、 Compare and Swap) を使用した実装を行った + - CAS は値を更新する際に更新前の値と実際に保存されているメモリ番地の値を比較し、変化がなければ値を更新する + - メモリ番地の値が変わっているなら、もう一度 CAS を行う -``` -struct SynchronizedQueue { - struct Element* top; - struct Element* last; - struct Atomic* atomic; -}; -// Singly Linked List element -struct Element { - union Data* top; - struct Element* next; -}; -``` +<div style="text-align: center;"> + <img src="./images/synchronizedQueue.svg" alt="message" width="600"> +</div> ## 依存関係の解決 - 依存関係の解決は Data Gear がメタレベルで持っている Queue を使用する @@ -407,7 +384,7 @@ - Host、Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある - Device にデータ領域を確保するにはサイズの指定が必要 - Data Gear には Meta Data Gear でデータのサイズを持っている - - しかし、 Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう + - Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう - CUDA Buffer ではそのマッピングを行う - このマッピングは Task の stub Code Gear で行われる