# HG changeset patch # User Tatsuki IHA # Date 1518321233 -32400 # Node ID 44f592c433249c741d67e72f54e077568b8db7c6 # Parent 972eb5656f88a9474d4628a2de71b971636d7d40 Update slide diff -r 972eb5656f88 -r 44f592c43324 paper/evaluation.tex --- a/paper/evaluation.tex Sat Feb 10 04:33:50 2018 +0900 +++ b/paper/evaluation.tex Sun Feb 11 12:53:53 2018 +0900 @@ -82,8 +82,8 @@ 1 CPU と 32 CPU では 約 27.1 倍の速度向上が見られた。 ある程度の台数効果があると考えられる。 -GPU での実行は kernel のみの実行時間は 32CPU に比べて 約 7.2 倍の実行向上が見られた。 -しかし、通信時間を含めると 16CPU より遅い結果となってしまった。 +GPU での実行は kernel のみの実行時間は 32 CPU に比べて 約 7.2 倍の速度向上が見られた。 +しかし、通信時間を含めると 16 CPU より遅い結果となってしまった。 CPU、GPU の通信時間かオーバーヘッドになっている事がわかる。 \section{BitonicSort} diff -r 972eb5656f88 -r 44f592c43324 paper/fig/WorkerRun.xbb --- a/paper/fig/WorkerRun.xbb Sat Feb 10 04:33:50 2018 +0900 +++ b/paper/fig/WorkerRun.xbb Sun Feb 11 12:53:53 2018 +0900 @@ -4,5 +4,5 @@ %%HiResBoundingBox: 0.000000 0.000000 824.000000 309.000000 %%PDFVersion: 1.3 %%Pages: 1 -%%CreationDate: Sun Feb 4 22:16:26 2018 +%%CreationDate: Sun Feb 11 03:40:43 2018 diff -r 972eb5656f88 -r 44f592c43324 paper/gpu.tex --- a/paper/gpu.tex Sat Feb 10 04:33:50 2018 +0900 +++ b/paper/gpu.tex Sun Feb 11 12:53:53 2018 +0900 @@ -85,11 +85,12 @@ % 少ないけどコードはなるべく載せたくない(メタ部分 + 複雑) \section{stub Code Gear による kernel の実行} -Gears OS では stub Code Gear で CUDA による実行の切り替える。 +Gears OS では stub Code Gear で CUDA による実行を切り替える。 stub Code Gear での切り替えの際は CUDABuffer への Data の格納、実行される kernel の読み込みを行う。 実際に GPU で実行されるプログラムは \coderef{cudaTwice} のように記述する。 \lstinputlisting[caption=配列の要素を二倍にする例題, label=code:cudaTwice]{./src/cudaTwice.cu} -stub Code Gear は通常はその stub に対応した Code Gear に継続するが、 CUDA で実行する際は CUDAExectuor の Code Gear に継続する。 +通常、stub Code Gear は対応した Code Gear に継続するが、CUDA で実行する際は CUDAExectuor の Code Gear に継続する。 + diff -r 972eb5656f88 -r 44f592c43324 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 972eb5656f88 -r 44f592c43324 slide/images/workerRun.graffle Binary file slide/images/workerRun.graffle has changed diff -r 972eb5656f88 -r 44f592c43324 slide/images/workerRun.pdf Binary file slide/images/workerRun.pdf has changed diff -r 972eb5656f88 -r 44f592c43324 slide/images/workerRun.svg --- a/slide/images/workerRun.svg Sat Feb 10 04:33:50 2018 +0900 +++ b/slide/images/workerRun.svg Sun Feb 11 12:53:53 2018 +0900 @@ -1,5 +1,5 @@ - + @@ -212,7 +212,7 @@ - + @@ -462,89 +462,89 @@ - - + + - - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + - - - - - + + + + + - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - + + + + + + + + + + + + + + - - - - - - - - - - - - + + + + + + + + + + + + - - - - - - + + + + + + diff -r 972eb5656f88 -r 44f592c43324 slide/slide.html --- a/slide/slide.html Sat Feb 10 04:33:50 2018 +0900 +++ b/slide/slide.html Sun Feb 11 12:53:53 2018 +0900 @@ -87,23 +87,40 @@ -

Gears OS

+

メタ計算を用いた並列処理

+ + + +
+ +

Gears OS

+ @@ -112,13 +129,23 @@
+

Gears OS

+ + + +
+
+

Code Gear、 Data Gear

@@ -178,7 +205,7 @@
-

メタ計算

+

メタ計算

  • メタ計算 は通常の計算を実行するための計算
  • 信頼性の確保やメモリ管理、スレッド管理、CPU、GPU の資源管理等
    • @@ -294,50 +321,206 @@

    Interface の定義

    +
      +
    • Interface の定義には以下の内容を定義する +
        +
      • 引数のData Gear 群
        • +
      • 操作(API) 実行後に継続される Code Gear
        • +
      • 操作(API) である Code Gear と Code Gear に渡す引数情報
        • +
      +
      • +
    + +
    typedef struct Queue<Impl>{
+        // Data Gear parameter
+        union Data* queue;
+        union Data* data;
+        __code next(...);
+        __code whenEmpty(...);
+
+        // Code Gear
+        __code clear(Impl* queue, __code next(...));
+        __code put(Impl* queue, union Data* data, __code next(...));
+        __code take(Impl* queue, __code next(union Data*, ...));
+        __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...));
+} Queue;
+

    Interface の実装

    +
      +
    • Interface には複数の実装を行うことが出来る
      • +
    • 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う
      • +
    • 代入する Code Gear を入れ替えることで別の実装を表現する
      • +
    • 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる
      • +
    + +
    Queue* createSingleLinkedQueue(struct Context* context) {
+    struct Queue* queue = new Queue(); // Allocate Queue interface
+    struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement
+    queue->queue = (union Data*)singleLinkedQueue;
+    singleLinkedQueue->top  = new Element();
+    singleLinkedQueue->last = singleLinkedQueue->top;
+    queue->clear = C_clearSingleLinkedQueue;
+    queue->put  = C_putSingleLinkedQueue;
+    queue->take  = C_takeSingleLinkedQueue;
+    queue->isEmpty = C_isEmptySingleLinkedQueue;
+    return queue;
+}
+
    + + +
    +
    + +

    Interface の実装例

    +
      +
    • SingleLinkedQueue の put 実装
      • +
    • 引数は Queue Interface の定義にあわせる
      • +
    • 第1引数は 実装対象の Data Gear の型になる
      • +
    • 第3引数の(…) は Output Data Gear を記述する +
        +
      • … は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある
        • +
      +
      • +
    + +
    __code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) {
+    Element* element = new Element();
+    element->data = data;
+    element->next = NULL;
+    queue->last->next  = element;
+    queue->last = element;
+    goto next(...);
+}
+

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

    +
      +
    • Interface を利用した Code Gear への継続は goto interface->method で行われる
      • +
    • ここでの interface は Interfaceの型で包んだポインタ、 method は実装した Code Gear に対応
      • +
    • この構文は実際にはスクリプトで変換される +
        +
      • 変換後はメタレベルのコードになる
        • +
      +
      • +
    + +
    __code code1() {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = new Node();
+    node->color = Red;
+    goto queue->put(node, queueTest2);
+}
+
    -

    並列処理の構成

    +

    Interface を利用した Code Gear の呼び出し(スクリプト変換後)

    +
      +
    • Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す
      • +
    • この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる
      • +
    • 呼び出すCode Gear の引数情報に合わせて引数に格納
      • +
    + +
    __code code1(struct Context *context) {
+    Queue* queue = createSingleLinkedQueue(context);
+    Node* node = &ALLOCATE(context, Node)->Node;
+    node->color = Red;
+    Gearef(context, Queue)->queue = (union Data*) queue;
+    Gearef(context, Queue)->data = (union Data*) node;
+    Gearef(context, Queue)->next = C_queueTest2;
+    goto meta(context, queue->put);
+}
+
    + + +
    +
    + +

    Interface での stub Code Gear

    +
      +
    • メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される
      • +
    • Interface を実装した Code Gear は stub Code Gear の自動生成が可能である
      • +
    + +
    __code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) {
+    Element* element = &ALLOCATE(context, Element)->Element;
+    element->data = data;
+    element->next = NULL;
+    queue->last->next  = element;
+    queue->last = element;
+    goto meta(context, next);
+}
+
+// generated by script
+__code putSingleLinkedQueue_stub(struct Context* context) {
+	SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue);
+	Data* data = Gearef(context, Queue)->data;
+	enum Code next = Gearef(context, Queue)->next;
+	goto putSingleLinkedQueue(context, queue, data, next);
+} 
+
    + + +
    +
    + +

    並列処理の構成

    • 今回は並列処理を行う機構の実装を行う
    • 構成要素
      • Task(Context)
        • +
      • TaskManager +
          +
        • Worker の生成、依存関係を解決したTask を Worker に送信する
          • +
        +
      • Worker
          -
        • Queue から Task を取得し、実行する
          • -
        -
        • -
      • TaskManager -
          -
        • Persistent Data Tree を監視し、 Task の依存関係を解決する
          • +
        • SynchronizedQueue から Task を取得し、実行する
    -

    ※ TaskManager は今回未実装

    -

    Task(Context)

    +
      +
    • Gears OS では並列実行する Task を Context で表現する
      • +
    • Context Task用の情報として以下の情報をもっている +
        +
      • 実行する Code Gear
        • +
      • Input/Output Data Gear の格納場所
        • +
      • 待っている Input Data Gear の数
        • +
      +
      • +
    • 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる +
        +
      • stub Code Gear は自動生成される
        • +
      +
      • +
    + +
    __code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) {
+    output->value = input1->value + input2->value;
+    goto next(output, ...);
+}
+
    @@ -350,7 +533,7 @@
- message + message
@@ -359,31 +542,25 @@

Worker

    -
  • Worker は TaskQueue から Task を取得して実行する
    • +
  • 初期化の際にスレッドと Worker 用の Context を生成する
    • +
  • TaskManager から送信された Task を取得して実行する
- - - - - - - -
-
- message -
- 		+
+
+ message +
+
    -
  1. Worker は Task Queue から Task を取り出す(1. Dequeue Task)
    2. -
  2. 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear)
    3. -
  3. Task に格納されている Code Gear を実行する
    4. -
  4. Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear)
    5. +
  5. Worker は Queue から Task を取得する
    6. +
  6. Worker Context から Task へ入れ替える
    7. +
  7. Task の Code Gear を実行
    8. +
  8. Task の Output Data Gear の書き出し
    9. +
  9. Task から WorkerContext へ入れ替える
    10. +
  10. Worker は再び Queue から Task を取得する
-
-
    -
  • Task が完了したら次の Task を取得する
    • -
+
+
@@ -391,12 +568,165 @@

Synchronized Queue

+ +
struct SynchronizedQueue {
+    struct Element* top;
+    struct Element* last;
+    struct Atomic* atomic;
+};
+// Singly Linked List element
+struct Element {
+    union Data* top;
+    struct Element* next;
+};
+
+ + + +
+ +

依存関係の解決

+ + +
+ message +
+ + +
+
+ +

並列構文

+ + +
__code code1(Integer *integer1, Integer * integer2, Integer *output) {
+    par goto add(integer1, integer2, output, __exit);
+    goto code2();
+}
+
+ + +
+
+ +

CUDA への対応

+ + +
+ message +
+ + +
+
+ +

CUDAExecutor

+ + +
typedef struct Executor<Impl>{
+    union Data* Executor;
+    struct Context* task;
+    __code next(...);
+    // method
+    __code read(Impl* executor, struct Context* task, __code next(...));
+    __code exec(Impl* executor, struct Context* task, __code next(...));
+    __code write(Impl* executor, struct Context* task, __code next(...));
+}
+
+ + +
+
+ +

CUDABuffer

+ + +
+ message +
+ + +
+
+ +

CUDA での呼び出し

+ + + +
+
+ +

Gears OS の評価

+ @@ -405,85 +735,87 @@
-

依存関係の解決

- - -
-
- -

データ並列

- - -
-
- -

CUDA への対応

-

## CUDA Worker -## CUDA Executor

- - -
-
- -

Gears OS の評価

+

Twice

-

実験環境

+

Twice の結果

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
ProcessorTime(ms)
1 CPU1181.215
2 CPUs627.914
4 CPUs324.059
8 CPUs159.932
16 CPUs85.518
32 CPUs43.496
GPU43.496
GPU(kernel only)6.018
+
-

Twice

+

BitonicSort

-
// Twice Code Gear
-__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
-    int i = loopCounter->i;
-
-    if (i < alignment) {
-        array[i+index*alignment] = array[i+index*alignment]*2;
-        loopCounter->i++;
-
-        goto twice(loopCounter, index, alignment, array);
-    }
-
-    loopCounter->i = 0;
-
-    goto exit();
-}
-
- - +
+ message
-
- -

Twice の結果

- - -
-
- -

BitonicSort

@@ -494,34 +826,48 @@ - - + + - + - + - + - + + + + + - - + + + + + + + + + +
Number of ProcessorsTime(ms)ProcessorTime(s)
1 CPU131541.416
2 CPUs68923.340
4 CPUs36611.952
8 CPUs1896.320
16 CPUs3.336
12 CPUs11132 CPUs1.872
GPU5.420
GPU(kernel only)0.163
@@ -529,12 +875,7 @@

OpenMP との比較

- - -
-
- -

Go との比較

+

## Go との比較

@@ -542,8 +883,10 @@

まとめ

@@ -552,31 +895,22 @@

今後の課題

diff -r 972eb5656f88 -r 44f592c43324 slide/slide.md --- a/slide/slide.md Sat Feb 10 04:33:50 2018 +0900 +++ b/slide/slide.md Sun Feb 11 12:53:53 2018 +0900 @@ -131,9 +131,9 @@ ## Interface の定義 - Interface の定義には以下の内容を定義する - - 操作(API) である Code Gear と Code Gear に渡す引数情報 - 引数のData Gear 群 - 操作(API) 実行後に継続される Code Gear + - 操作(API) である Code Gear と Code Gear に渡す引数情報 ``` c typedef struct Queue{ @@ -155,7 +155,7 @@ - Interface には複数の実装を行うことが出来る - 実装した Code Gear を Interface で定義した Code Gear に代入することで実装を行う - 代入する Code Gear を入れ替えることで別の実装を表現する -- 実装した Data Gear の生成は関数呼び出しで行われ、 外から見るとInterface の型で扱われる +- 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる ``` Queue* createSingleLinkedQueue(struct Context* context) { @@ -175,7 +175,9 @@ ## Interface の実装例 - SingleLinkedQueue の put 実装 - 引数は Queue Interface の定義にあわせる -- 第一引数は 実装対象の Data Gear の型になる +- 第1引数は 実装対象の Data Gear の型になる +- 第3引数の(...) は Output Data Gear を記述する + - ... は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある ``` c __code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) { @@ -189,154 +191,347 @@ ``` ## Interface を利用した Code Gear の呼び出し -- Interface を利用した Code Gear への継続として `goto interface->method` を提供している +- Interface を利用した Code Gear への継続は `goto interface->method` で行われる +- ここでの **interface** は Interfaceの型で包んだポインタ、 **method** は実装した Code Gear に対応 +- この構文は実際にはスクリプトで変換される + - 変換後はメタレベルのコードになる + +``` +__code code1() { + Queue* queue = createSingleLinkedQueue(context); + Node* node = new Node(); + node->color = Red; + goto queue->put(node, queueTest2); +} +``` + +## Interface を利用した Code Gear の呼び出し(スクリプト変換後) +- Gearef マクロは Context から Interface の引数格納用の Data Gear を取り出す +- この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる +- 呼び出すCode Gear の引数情報に合わせて引数に格納 + +``` +__code code1(struct Context *context) { + Queue* queue = createSingleLinkedQueue(context); + Node* node = &ALLOCATE(context, Node)->Node; + node->color = Red; + Gearef(context, Queue)->queue = (union Data*) queue; + Gearef(context, Queue)->data = (union Data*) node; + Gearef(context, Queue)->next = C_queueTest2; + goto meta(context, queue->put); +} +``` + +## Interface での stub Code Gear +- メタ計算で格納された引数は、 stub Code Gear で Code Gear に渡される +- Interface を実装した Code Gear は stub Code Gear の自動生成が可能である + +``` c +__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) { + Element* element = &ALLOCATE(context, Element)->Element; + element->data = data; + element->next = NULL; + queue->last->next = element; + queue->last = element; + goto meta(context, next); +} + +// generated by script +__code putSingleLinkedQueue_stub(struct Context* context) { + SingleLinkedQueue* queue = (SingleLinkedQueue*)GearImpl(context, Queue, queue); + Data* data = Gearef(context, Queue)->data; + enum Code next = Gearef(context, Queue)->next; + goto putSingleLinkedQueue(context, queue, data, next); +} +``` + ## 並列処理の構成 - 今回は並列処理を行う機構の実装を行う - 構成要素 - Task(Context) + - TaskManager + - Worker の生成、依存関係を解決したTask を Worker に送信する - Worker - - Queue から Task を取得し、実行する - - TaskManager - - Persistent Data Tree を監視し、 Task の依存関係を解決する - -※ TaskManager は今回未実装 + - SynchronizedQueue から Task を取得し、実行する ## Task(Context) +- Gears OS では並列実行する Task を Context で表現する +- Context Task用の情報として以下の情報をもっている + - 実行する Code Gear + - Input/Output Data Gear の格納場所 + - 待っている Input Data Gear の数 +- 実際に実行される Code Gear の引数情報は Interface の Code Gear 実装と同等に記述できる + - stub Code Gear は自動生成される + +``` c +__code add(struct Integer* input1, struct Integer* input2, __code next(struct Integer* output, ...)) { + output->value = input1->value + input2->value; + goto next(output, ...); +} +``` ## TaskManger - 初期化時に決まった数の Worker を作成 - 依存関係を解決した Task を各 Worker の Queue に送信する
- message + message
## Worker -- Worker は TaskQueue から Task を取得して実行する +- 初期化の際にスレッドと Worker 用の Context を生成する +- TaskManager から送信された Task を取得して実行する + +
+
+ message +
+
+
    +
  1. Worker は Queue から Task を取得する
    2. +
  2. Worker Context から Task へ入れ替える
    3. +
  3. Task の Code Gear を実行
    4. +
  4. Task の Output Data Gear の書き出し
    5. +
  5. Task から WorkerContext へ入れ替える
    6. +
  6. Worker は再び Queue から Task を取得する
    7. +
+
+
+ +## Synchronized Queue +- Worker で使用される Queue +- TaskManager を経由して Task を送信するスレッドと Task を取得するスレッドで操作される +- そのためマルチスレッドでのデータの一貫性を保証する必要がある +- Gears OS では CAS(Check and Set、 Compare and Swap) を使用した Synchronized Queue として実装する +- この Queue は Queue Interface を実装し、 List を利用した実装を行った + +``` +struct SynchronizedQueue { + struct Element* top; + struct Element* last; + struct Atomic* atomic; +}; +// Singly Linked List element +struct Element { + union Data* top; + struct Element* next; +}; +``` + +## 依存関係の解決 +- 依存関係の解決は Data Gear にメタレベルで依存関係解決用の Queueをもたせることで行う +- Code Gear を実行した後、 Output Data Gear を書き出す処理を行う +- 書き出し処理は Data Gear の Queue から依存関係にある Task を参照する +- Task には実行に必要な Input Data Gear のカウンタを持っているため、そのカウンタをデクリメントする +- カウンタが0になったら Input Data Gear が揃ったことになるため、TaskManager を経由して Worker に送信する + +
+ message +
+ +## 並列構文 +- 並列実行の Task の生成は新しく Context を生成し、実行する Code Gear、待ち合わせる Input Data Gear の数、Input/Output Data Gear への参照を設定する +- この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述は好ましくない +- Task の設定の記述は煩雑な記述であるが、並列実行サれることを除けば通常の CbC の goto 文と同等である +- そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した +- par goto 構文には引数として Input/Output Data Gear等を渡す + - スクリプトによって Code Gear の Input/Output の数を解析する + +``` c +__code code1(Integer *integer1, Integer * integer2, Integer *output) { + par goto add(integer1, integer2, output, __exit); + goto code2(); +} +``` - +## CUDA への対応 +- Gears OS は GPU での実行もサポートする +- GPU で性能を出すためには GPU に合わせた並列プログラミングが必要になる +- 今回は CUDA への実行のサポートをおこなった +- CUDA へ GPU を Device、 CPU を Host として定義する +- CUDA は処理の最小の単位を thread とし、それをまとめた block を展開し Device 上で実行されるプログラム(Kernel)を実行する +- 今回 CUDAWorker、CUDAExecutor、 CUDABuffer を使用して CUDA に合わせた Code Gear を提供する + +
+ message +
+ +## CUDAExecutor +- CUDA Executor は Executor Interface を実装した以下の Code Gear を持つ + - HostからDevice へのデータの送信(read) + - kernel の実行(exec) + - Device から Host へのデータの書き出し(write) + +``` c +typedef struct Executor{ + union Data* Executor; + struct Context* task; + __code next(...); + // method + __code read(Impl* executor, struct Context* task, __code next(...)); + __code exec(Impl* executor, struct Context* task, __code next(...)); + __code write(Impl* executor, struct Context* task, __code next(...)); +} +``` + +## CUDABuffer +- Host、 Device 間でデータのやり取りをする際、 Gears OS での Data Gear をDevice 用にマッピングする必要がある + - Device にデータ領域を確保するにはサイズの指定が必要 + - Data Gear には Meta Data Gear でデータのサイズを持っている + - だが、Data Gear の要素の中に Data Gear へのポインタがあるとポインタ分でサイズ計算してしまうため、 GPU では参照できなくなってしまう +- CUDA Buffer ではそのマッピングを行う + - このマッピングは Task の stub Code Gear で行われる + +
+ message +
+ +## CUDA での呼び出し +- Gears OS では stub Code Gear で CUDA による実行を切り替える +- stub Code Gear で CUDABuffer でのマッピング、 実行する kernel の読み込みを行う +- stub Code Gear は CUDA で実行する際は CUDAExecutor の Code Gear に継続する + +## Gears OS の評価 +- 並列処理のタスクの例題として Twice と BitonicSort を実装し、 以下の環境で測定を行った +- CPU 環境 + - Model : Dell PowerEdgeR630 + - Memory : 768GB + - CPU : 2 x 18-Core Intel Xeon 2.30GHz +- GPU 環境 + - GPU : GeForce GTX 1070 + - Cores : 1920 + - ClockSpeed : 1683MHz + - Memory Size : 8GB GDDR5 + - Memory Bandwidth : 256GB/s + +## Twice +- Twice は与えられた整数配列を2倍にする例題である +- 並列実行の依存関係がなく、並列度が高い課題である +- 要素数 2^27 +- CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する +- GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開 + +## Twice の結果 +
- - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
-
- message -
- 		-
    -
  1. Worker は Task Queue から Task を取り出す(1. Dequeue Task)
    2. -
  2. 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear)
    3. -
  3. Task に格納されている Code Gear を実行する
    4. -
  4. Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear)
    5. -
- 		ProcessorTime(ms)
1 CPU1181.215
2 CPUs627.914
4 CPUs324.059
8 CPUs159.932
16 CPUs85.518
32 CPUs43.496
GPU43.496
GPU(kernel only)6.018
-- Task が完了したら次の Task を取得する -## Synchronized Queue -- Task Queue は Task のリストを扱う -- Thread で共有されるため、 Compare And Swap(CAS) を使用した Synchronized Queue として実装する -- TaskQueue は 2つで Data Gear で表現される - - 先頭と末尾の要素を持った Queue 表す Data Gear - - Task と次の要素へのポインタを持った、リスト構造を表現する Element という Data Gear - -## 依存関係の解決 - -## データ並列 - -## CUDA への対応 -## CUDA Worker -## CUDA Executor - -## Gears OS の評価 -- 今回 Gears OS の構成要素である Persistent Data Tree, TaskQueue, Worker の実装を行った -- これにより、 Gears OS を用いて依存関係のない並列処理の実行が可能になった - -## 実験環境 -- CPU 環境 - - Memory : 16GB - - CPU : 6-core Intel Xeon 2.66GHZ x 2 -- GPU 環境 - -## Twice -- タスクの例題として Twice と BitonicSort を実装した -- Twice は与えられた整数配列を2倍にする例題である - -``` c -// Twice Code Gear -__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) { - int i = loopCounter->i; - - if (i < alignment) { - array[i+index*alignment] = array[i+index*alignment]*2; - loopCounter->i++; - - goto twice(loopCounter, index, alignment, array); - } - - loopCounter->i = 0; - - goto exit(); -} -``` - -## Twice の結果 +- 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた +- GPU での実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上 + - 通信時間を含めると 16 CPU より遅い + - 通信時間がオーバーヘッドになっている ## BitonicSort +- 並列処理向けのソートアルゴリズム +- 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする +- 要素数 2^24 +- CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する +- GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開 + +
+ message +
## BitonicSort の結果 - - + + - + - + - + - + + + + + - - + + + + + + + + + +
Number of ProcessorsTime(ms)ProcessorTime(s)
1 CPU131541.416
2 CPUs68923.340
4 CPUs36611.952
8 CPUs1896.320
16 CPUs3.336
12 CPUs11132 CPUs1.872
GPU5.420
GPU(kernel only)0.163
-- 1cpu と 12cpu では 11.8 倍の向上が見られた +- 1 CPU と 32 CPU で約22.12倍の速度向上 +- GPU は通信時間を含めると 8 CPU の役1.16倍、 kernel のみの実行では 32 CPU の役11.48倍になった +- 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった ## OpenMP との比較 - ## Go との比較 ## まとめ -- Code Gear、 Data Gear によって構成される Gears OS の基本的な機能として TaskQueue、 Persistent Data Tree、 Worker の実装を行った -- 依存関係のない Twice を実装し、並列処理が行えることを確認した +- Gears OS の並列処理機構の実装を行った +- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった +- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった +- 2つの例題である程度の台数効果が出ることを確認した ## 今後の課題 -- 一般的に並列処理には依存関係が存在する - - 複雑な並列処理を実行できるようにするために Task Manager の実装を行い、 依存関係のある並列処理の例題を作成し、評価する -- GPUなどの他のプロセッサ演算に利用することが出来ない - - Data Gear などのデータをGPUにマッピングするための機構が必要 -- Gears OS でのデバック手法 - - 継続はスタックを積まないため、スタックトレースを使わないデバック手法の考案 - - 並列処理でのデバック手法も考案する必要がある -- 型情報の検査 - - プログラムの正しさを保証するために Data Gear の情報を検査するシステムを メタ計算 として実装する -- Contextの動的生成 - - 今は静的に自分で生成している - - CbC 用の Runtime をつくり、 Context を動的に生成 +- Gears OS の並列処理の信頼性の保証、チューニングを行う +- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する + - 証明はCbC のプログラムヲ証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある + - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う +- OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。 + - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう + - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成セずに関数呼出しを行う等の最適化が必要 +- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった + - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持サれているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデーの通信を行う