# HG changeset patch # User Tatsuki IHA # Date 1518199314 -32400 # Node ID cae61efc3f26ef406717cf4a779163a6ea15656b # Parent 800aae8618f07fe09223d99c69c4b6d894fff734 Fix diff -r 800aae8618f0 -r cae61efc3f26 paper/introduction.tex --- a/paper/introduction.tex Sat Feb 10 00:19:52 2018 +0900 +++ b/paper/introduction.tex Sat Feb 10 03:01:54 2018 +0900 @@ -1,5 +1,5 @@ \chapter{メタ計算を使った並列処理} -並列処理は現代主流のマルチコアCPU の性能を発揮するには重要なものになっている。 +並列処理は現在主流のマルチコアCPU の性能を発揮するには重要なものになっている。 しかし、並列処理のプログラミングはスレッド間の共通資源の競合など非決定的な実行を持っており、その信頼性を保証するには従来のテストやデバッグでは不十分であり、テストしきれない部分が残ってしまう。 また、マルチコア CPU 以外にも GPU や CPU と GPU を複合したヘテロジニアスなプロセッサも並列処理をする上で無視できない。 diff -r 800aae8618f0 -r cae61efc3f26 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 800aae8618f0 -r cae61efc3f26 slide/slide.html --- a/slide/slide.html Sat Feb 10 00:19:52 2018 +0900 +++ b/slide/slide.html Sat Feb 10 03:01:54 2018 +0900 @@ -87,7 +87,7 @@ @@ -112,82 +112,6 @@
-

Gears OS の並列性

- - -
- message -
- - -
-
- -

Gears OS の拡張性

- - -

等を柔軟に対応する

- - - -
- message -
- - -
-
- -

Gears OS の信頼性

- - - -
-
- -

この発表は

- - - -
-
-

Code Gear、 Data Gear

-

メタ計算

- - - -
-
- -

Meta Gear

- - -
- message -
- - -
-
-

Continuation based C

-

CbC を用いた Gears OS の記述

+

メタ計算

-
__code code1(struct Array* array, struct LoopCounter* loopCounter) {
-    ...
-    goto code2(array);
-}
-
-__code meta_code1(struct Context* context, enum Code next) {
-    goto (context->code[next])(context);
-}
-
-__code code2(struct Array* array) {
-    ...
-}
-
-
-

CbC の Gears OS サポート

+

Meta Gear

-
__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
-    ...
-    goto meta_code1(context, Code2);
-}
-
-__code code1_stub(struct Context* context) {
-    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
-}
-
-__code meta_code1(struct Context* context, enum Code next) {
-    goto (context->code[next])(context);
-}
-
-__code code2(struct Context* context, struct Array* array) {
-    ...
-}
-
+
+ message +
@@ -344,84 +213,40 @@

Context

- - - -
- -

Context

- -
/* context define */
-struct Context {
-    int codeNum;
-    __code (**code) (struct Context*);
-    void* heapStart;
-    void* heap;
-    long heapLimit;
-    int dataNum;
-    union Data **data;
-};
-
- - -
-
- -

Context

- - -
enum Code {
-    Code1,
-    Code2,
-    Code3,
-    Exit,
-};
-
-

Data Gear の表現

/* data Gear define */
 union Data {
-    struct Time {
+    struct Timer {
+        union Data* timer;
+        enum Code start;
+        enum Code end;
         enum Code next;
+    } Timer;
+    struct TimerImpl {
         double time;
-    } time;
-    struct LoopCounter {
-        int i;
-    } loopCounter;
+    } TimerImpl;
     ....
 };
@@ -430,48 +255,71 @@
-

Code Gear の stub

+

Code Gear の stub Code Gear

-
__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
-    ...
-}
-
-/* stub define */
-__code code1_stub(struct Context* context) {
-    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
-}
+
-

プロトタイプ の構成

+

Context での stub Code Gear の記述の問題点

+
    +
  • Context プログラム全体で使用する Code Gear と Data Gear の集合
    • +
  • 全ての Code と Data の組合せをContext から 全て展開し、その組合せを stub Code Gear に書く必要がある
    • +
  • Gears OS を実装するに連れて、 stub Code Gear の記述が煩雑になる場所がでてきた
    • +
  • そのため Gears OS のモジュール化する仕組みとして Interface を導入した
    • +
+ + +
+
+ +

Interface

+
    +
  • Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear
    • +
  • stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である
    • +
  • Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る
    • +
  • Interface は Java のインターフェース、 Haskell の型クラスに対応する
    • +
+ + +
+
+ +

Interface の定義

+ + +
+
+ +

Interface の実装

+ + +
+
+ +

Interface を利用した Code Gear の呼び出し

+ + +
+
+ +

並列処理の構成

  • 今回は並列処理を行う機構の実装を行う
    • -
  • 必要な要素は大きく5つ +
  • 構成要素
      -
    • Context
      • -
    • TaskQueue -
        -
      • 実行される Task のリストを扱う
        • -
      -
      • -
    • Persistent Data Tree -
        -
      • Code Gear によって参照される Data Gear の管理を行う
        • -
      -
      • +
    • Task(Context)
    • Worker
        -
      • TaskQueue から Task を取得し、実行する
        • +
      • Queue から Task を取得し、実行する
    • TaskManager @@ -489,55 +337,21 @@
-

TaskQueue

-
    -
  • Task Queue は Task のリストを扱う
    • -
  • すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
    • -
  • TaskQueue は 2つで Data Gear で表現される -
      -
    • 先頭と末尾の要素を持った Queue 表す Data Gear
      • -
    • Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
      • -
    -
    • -
- -
// Data Gear define
-union Data {
-    struct Queue {
-        struct Element* first;
-        struct Element* last;
-    } queue;
-
-    struct Element {
-        struct Task* task;
-        struct Elemen* next;
-    } element
-};
-
+

Task(Context)

-

TaskQueueの操作(Enqueue)

+

TaskManger

    -
  • Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定
    • -
  • 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある
    • +
  • 初期化時に決まった数の Worker を作成
    • +
  • 依存関係を解決した Task を各 Worker の Queue に送信する
-
__code putQueue3(struct Queue* queue, struct Element* new_element) {
-    struct Element* last = queue->last;
-
-    if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
-        last->next = new_element;
-
-        goto exit();
-    } else {
-        goto putQueue3(queue, new_element);
-    }
-}
-
-
+
+ message +
@@ -567,7 +381,6 @@ - @@ -576,21 +389,43 @@
-

TaskManger

+

Synchronized Queue

    -
  • TaskManager は Task の依存関係の解決を行う
    • -
  • Thread の作成と停止も行う
    • +
  • Task Queue は Task のリストを扱う
    • +
  • Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する
    • +
  • TaskQueue は 2つで Data Gear で表現される +
      +
    • 先頭と末尾の要素を持った Queue 表す Data Gear
      • +
    • Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear
      • +
    +
-
- message -
-
-

プロトタイプの実行

+

依存関係の解決

+ + +
+
+ +

データ並列

+ + +
+
+ +

CUDA への対応

+

## CUDA Worker +## CUDA Executor

+ + +
+
+ +

Gears OS の評価

  • 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った
  • これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった
    • @@ -600,9 +435,24 @@
-

Gears OS で実行する Code Gear 例

+

実験環境

    -
  • プロトタイプのタスクの例題として Twice を実装した
    • +
  • CPU 環境 +
      +
    • Memory : 16GB
      • +
    • CPU : 6-core Intel Xeon 2.66GHZ x 2
      • +
    +
    • +
  • GPU 環境
    • +
+ + +
+
+ +

Twice

+
    +
  • タスクの例題として Twice と BitonicSort を実装した
  • Twice は与えられた整数配列を2倍にする例題である
@@ -627,19 +477,19 @@
-

並列処理の確認

-
    -
  • Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った
    • -
  • 環境 -
      -
    • Memory : 16GB
      • -
    • CPU : 6-core Intel Xeon 2.66GHZ x 2
      • -
    -
    • -
  • 要素数 : 2^17 * 1000
    • -
  • 分割数 : 640 タスク
    • -
  • 1 Task 当たりの処理量 : 2^11 * 100 elements
    • -
+

Twice の結果

+ + +
+
+ +

BitonicSort

+ + +
+
+ +

BitonicSort の結果

@@ -678,32 +528,13 @@
-

Cerium との比較

-
    -
  • Cerium は本研究室で開発していた並列プログラミングフレームワーク
    • -
  • Cerium では Task を依存関係に沿って実行することで並列実行を可能にする -
      -
    • 本来 Task はデータに依存するもので Task 間の依存関係ではデータの依存関係を保証することが出来ない
      • -
    • Gears OS の Task 中身は Code Gear になっており、必要な Input Data Gear が揃わない限り実行しないため、データの依存関係を保証できる
      • -
    -
    • -
  • Task には汎用ポインタとしてデータの受け渡しを行う -
      -
    • 型情報がなく、型の検査を行うことが出来ない
      • -
    • Gears OS では 型情報をもつ Data Gear を定義
      • -
    -
    • -
+

OpenMP との比較

-

既存の OS への対応

-
    -
  • Gears OS は従来の OS が行ってきたネットワーク管理、メモリ管理、並行制御などのメタな部分を Meta Code/Data Gear として定義
    • -
  • 通常の Code Gear から必要な制御を Meta Code Gear で行うことで従来のOSが行ってきた制御の提供を行う
    • -
+

Go との比較

diff -r 800aae8618f0 -r cae61efc3f26 slide/slide.md --- a/slide/slide.md Sat Feb 10 00:19:52 2018 +0900 +++ b/slide/slide.md Sat Feb 10 03:01:54 2018 +0900 @@ -3,20 +3,20 @@ profile: 琉球大学理工学研究科 河野研 lang: Japanese code-engine: coderay + ## Gears OS - 並列処理のチューニングや信頼性を保証するのは難しい - スレッド間の共通資源の競合などの非決定的な実行 - 従来のテストやデバッグではテストしきれない部分が残ってしまう - Gears OS では計算をノーマルレベルとメタレベルに階層化 - - ノーマルレベルの計算に対してメタレベルで信頼性を保証したい - - メタレベルの計算はデータ拡張や実行環境の切り替え等の拡張性のための計算を行う + - 信頼性と拡張性をメタレベルで保証する ## Code Gear、 Data Gear - Gears OS は Code Gear、 Data Gear という Gear で構成される - Code Gear はプログラムの処理そのものを表す - Data Gear はデータそのものを表す -- Code Gear は必要な Input Data Gear が揃ったら実行し、 Output Data Gear を生成する -- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、 Input Data Gear が揃った Code Gear の並列実行を行う +- Code Gear は必要な Input Data Gear が揃ったら実行し、Output Data Gear を生成する +- Code Gear と Input / Output Data Gear の対応から依存関係を解決し、Input Data Gear が揃った Code Gear の並列実行を行う
message @@ -50,8 +50,9 @@ ## メタ計算 - メタ計算 は通常の計算を実行するための計算 -- 信頼性の確保やメモリ管理、スレッド管理、 CPU、 GPU の資源管理等 +- 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等 - Gears OS のメタ計算は通常の計算とは別の階層のメタレベルで行われる +- メタレベルは Code/Data Gear に対応して Meta Code/Data Gear で行われる ## Meta Gear - メタ計算 は Code Gearの接続の間に行われる @@ -95,22 +96,12 @@ }; ``` -## Code Gear の stub +## Code Gear の stub Code Gear - Data Gear にアクセスするにはContext を経由する - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある -- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub を用意する -- stub は一種の Meta Code Gear であるため、 CbC で自動生成される -- このコードでは Array と LoopCounter が必要な code1 の stub を示している +- Gears OS では通常の Code Gear で必要な Data Gear を Context から取り出す stub Code Gear を用意する ``` c -__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { - ... -} - -/* stub define */ -__code code1_stub(struct Context* context) { - goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter); -} ``` ## Context での stub Code Gear の記述の問題点 @@ -121,64 +112,36 @@ ## Interface - Interface はある Data Gear と それに対する操作(API) を行う Code Gear の集合を表現する Meta Data Gear -- これは Context より小さい集合のため、 stub Code Gear での各API で決まった形になる +- stub Code Gear は実装した Code Gear で決まった形になるため、自動生成が可能である - Interface を導入することで、 Stack や Queue などのデータ構造を使用と実装に分けて記述することが出来る - Interface は Java のインターフェース、 Haskell の型クラスに対応する -## プロトタイプ の構成 + +## Interface の定義 + +## Interface の実装 + +## Interface を利用した Code Gear の呼び出し + +## 並列処理の構成 - 今回は並列処理を行う機構の実装を行う -- 必要な要素は大きく5つ - - Context - - TaskQueue - - 実行される Task のリストを扱う - - Persistent Data Tree - - Code Gear によって参照される Data Gear の管理を行う +- 構成要素 + - Task(Context) - Worker - - TaskQueue から Task を取得し、実行する + - Queue から Task を取得し、実行する - TaskManager - Persistent Data Tree を監視し、 Task の依存関係を解決する ※ TaskManager は今回未実装 -## TaskQueue -- Task Queue は Task のリストを扱う -- すべての Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する -- TaskQueue は 2つで Data Gear で表現される - - 先頭と末尾の要素を持った Queue 表す Data Gear - - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear - -``` c -// Data Gear define -union Data { - struct Queue { - struct Element* first; - struct Element* last; - } queue; +## Task(Context) - struct Element { - struct Task* task; - struct Elemen* next; - } element -}; -``` - -## TaskQueueの操作(Enqueue) -- Task を挿入する場合 Queue の last から最後の要素を取り出し、次の要素に新しく挿入する要素を設定 -- 正しく最後の要素が変更できたことを CAS で 保証し、末尾の変更を行う必要がある +## TaskManger +- 初期化時に決まった数の Worker を作成 +- 依存関係を解決した Task を各 Worker の Queue に送信する -``` c -__code putQueue3(struct Queue* queue, struct Element* new_element) { - struct Element* last = queue->last; - - if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) { - last->next = new_element; - - goto exit(); - } else { - goto putQueue3(queue, new_element); - } -} - -``` +
+ message +
## Worker - Worker は TaskQueue から Task を取得して実行する @@ -202,24 +165,35 @@
- - Task が完了したら次の Task を取得する -## TaskManger -- TaskManager は Task の依存関係の解決を行う -- Thread の作成と停止も行う +## Synchronized Queue +- Task Queue は Task のリストを扱う +- Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する +- TaskQueue は 2つで Data Gear で表現される + - 先頭と末尾の要素を持った Queue 表す Data Gear + - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear -
- message -
+## 依存関係の解決 + +## データ並列 +## CUDA への対応 +## CUDA Worker +## CUDA Executor -## プロトタイプの実行 +## Gears OS の評価 - 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った - これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった -## Gears OS で実行する Code Gear 例 -- プロトタイプのタスクの例題として Twice を実装した +## 実験環境 +- CPU 環境 + - Memory : 16GB + - CPU : 6-core Intel Xeon 2.66GHZ x 2 +- GPU 環境 + +## Twice +- タスクの例題として Twice と BitonicSort を実装した - Twice は与えられた整数配列を2倍にする例題である ``` c @@ -240,14 +214,11 @@ } ``` -## 並列処理の確認 -- Twice を使用し、Gears OS が実際に並列処理されているかどうかの確認を行った -- 環境 - - Memory : 16GB - - CPU : 6-core Intel Xeon 2.66GHZ x 2 -- 要素数 : 2^17 * 1000 -- 分割数 : 640 タスク -- 1 Task 当たりの処理量 : 2^11 * 100 elements +## Twice の結果 + +## BitonicSort + +## BitonicSort の結果 @@ -280,19 +251,9 @@ - 1cpu と 12cpu では 11.8 倍の向上が見られた +## OpenMP との比較 -## Cerium との比較 -- 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が行ってきた制御の提供を行う +## Go との比較 ## まとめ - Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った