Cerium の問題点

Task 間の依存関係

TaskQueue

TaskQueue は Task を管理する。 -すべての Context で共有され並列にアクセスされる。 -CAS 命令を利用してアクセスすることでデータの一貫性を保証する。

TaskQueue は Task を管理する。

+ +

すべての Context で共有され、CAS 命令を利用して変更することで平行にアクセスされてもデータの一貫性を保証する。

先頭と末尾の要素へのポインタを持った Queue を表す Data Gear

+ +

Persistent Data Tree

親を取得し、親からの参照を変更して親をスタックに積み直す
自分と左右の3点のノードで回転を行うことで平衡にする
回転後も条件を満たしているか確認する必要がある

+ +

// Code Gear
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
+    struct Node* tmp = node->right;
+    struct Node* parent = 0;
+    
+    stack_pop(context->node_stack, &parent);
+
+    if (parent) {
+        if (node == parent->left)
+            parent->left = tmp;
+        else
+            parent->right = tmp;
+    } else {
+        tree->root = tmp;
+    }
+
+    stack_push(context->node_stack, &parent);
+    
+    node->right = tmp->left;
+    tmp->left = node;
+    traverse->current = tmp;
+    
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+    
+// Meta Code Gear(stub)
+__code rotateLeft_stub(struct Context* context) {
+    goto rotateLeft(context,
+                    context->data[Traverse]->traverse.current,
+                    &context->data[Tree]->tree,
+                    &context->data[Traverse]->traverse);
+}
+

+ + +

+ +

Worker

TaskQueue から Task を取得して実行
TaskQueue へのアクセスには CAS 命令を用いる
Task には実行する Code Gear と実行に必要な Data Gear の key が格納されている
Task が完了したら次の Task を取得するために GetQueue に戻ってくる必要がある
CAS に失敗したら CAS をやり直すために自分自身に継続する

+ +

// Task definication
+union Data {
+    // size: 8 byte
+    struct Task {
+        enum Code code;
+        int key;
+    } task;
+}
+

+ +

// Dequeue
+__code getQueue(struct Context* context, struct Queue* queue, struct Node* node) {
+    if (queue->first == 0)
+        return;
+
+    struct Element* first = queue->first;
+    if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) {
+        queue->count--;
+
+        context->next = GetQueue;
+        stack_push(context->code_stack, &context->next);
+
+        context->next = first->task->code;
+        node->key = first->task->key;
+
+        goto meta(context, GetTree);
+    } else {
+        goto meta(context, GetQueue);
+    }
+}
+

+ + +

+ +

Worker

Worker で実行される Code Gear は特別なものではなく、他の Code Gear と同じ記述である +
- 依存関係のない Code Gear はすべて並列に動作させることができることを意味する
- Gears OS 自体が Code Gear によって構成され、Gears OS の実装自体が Gears Programming の指針となる
+

+ +

// Code Gear
+__code twice(struct Context* context, 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 meta(context, Twice);
+    }
+
+    loopCounter->i = 0;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+// Meta Code Gear(stub)
+__code twice_stub(struct Context* context) {
+    goto twice(context,
+               &context->data[LoopCounter]->loopCounter,
+               context->data[Node]->node.value->array.index,
+               context->data[Node]->node.value->array.alignment,
+               context->data[Node]->node.value->array.array);
+}
+

+ + +

+ +

TaskManager

TaskManager は Task の依存関係の解決を行う
Worker の起動・停止も行う

+ +

// Code Gear
+__code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
+    int i = loopCounter->i;
+
+    if (i < worker->num) {
+        struct Context* worker_context = &worker->contexts[i];
+        worker_context->next = GetQueue;
+        worker_context->data[Tree] = context->data[Tree];
+        worker_context->data[ActiveQueue] = context->data[ActiveQueue];
+        pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context);
+        worker_context->thread_num = i;
+        loopCounter->i++;
+
+        goto meta(context, CreateWorker);
+    }
+
+    loopCounter->i = 0;
+    goto meta(context, TaskManager);
+}
+    
+// Meta Code Gear
+__code createWorker_stub(struct Context* context) {
+    goto createWorker(context,
+                      &context->data[LoopCounter]->loopCounter,
+                      &context->data[Worker]->worker);
+}
+

+ + +

+ +

Gears OS の評価

Red-Black Tree アルゴリズムに基づいて非破壊木構造で構築される Persistent Data Tree
CAS 命令を用いてアクセスすることで並列に動作させてもデータの一貫性を保証する TaskQueue
TaskQueue から Task を取得し実行する Worker

+ +

Gears OS を用いて依存関係のない並列処理を実行可能な状態となった

+ +

簡単な並列処理の例題を実装し、評価を行う

+ + +

+ +

Twice

依存関係のない簡単な例題として Twice を実装した

+ +

Twice は与えられた整数配列を2倍にする例題である

+ +

配列のサイズを元に処理範囲と処理量を決める index, alignment, 配列へのポインタを持つ Data Gear に分割
Data Gear を Persistent Data Tree に挿入
実行する Code Gear(Twice) と実行に必要な Data Gear の key を持つ Task を生成
生成した Task を TaskQueue に挿入
Worker の起動
Worker が TaskQueue から Task を取得
取得した Task を元に必要な Data Gear を Persistent Data Tree から取得
Code Gear(Twice) を実行

+ + +

+ +

Result

要素数：2¹⁷ * 1000 elements
分割数：640 tasks
1 Task 当たりの処理量：2¹¹ * 100 elements

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Number of Processors	Time(ms)
1 CPU	1315
2 CPUs	689
4 CPUs	366
8 CPUs	189
12 CPUs	111

+ + + + + +

+ +

1 CPU と 12 CPU で約11.8倍の速度向上を確認した

+ +

十分な台数効果が出ていることがわかる

+ + +

+ +

まとめ

Cerium を開発して得られた知見から Code/Data Segment を持つ Gears OS を設計した
基本的な機能として Allocator, TaskQueue, Persistent Data Tree, Worker を実装した
実装した基本的な機能を組み合わせ Gears OS のプロトタイプを作成し、依存関係のない簡単な並列処理の例題を実装した
Gears OS がオーバーヘッドにならず、十分な台数効果が出ることを確認した
Gears OS の実装自体が Gears OS を用いて並列処理を記述する際の指針となるように実装した

+ + +

+ +

今後の課題

一般的に並列処理には依存関係が存在する。 +複雑な並列処理を実行できるようにするために依存関係を解決する TaskManager を実装する必要がある
GPU など他のプロセッサを演算に利用することができない。 +Code/Data Segment を用いて各プロセッサにのアーキテクチャにマッピングした実行機構を実装する必要がある
Data Segment 専用の構文を用意するべきである。 +いまの実装では必要ない Data Segment を持つ場合がある。 +実行可能な Code Segment のリストから推論し必要な Data Segment のみを持つようにする必要がある
Data Segment の型情報を検査する機能がない。 +型シグネチャを導入し、プログラムの正しさを保証する型システムを Gears OS 上に実装する必要がある

²⁰

Processor	Time(ms)
1 CPU	6143
2 CPUs	4633
4 CPUs	2577
8 CPUs	1630
12 CPUs	1318
GPU	155

¹⁷

¹¹

Number of Processors	Time(ms)
1 CPU	1315
2 CPUs	689
4 CPUs	366
8 CPUs	189
12 CPUs	111

Cerium における GPGPU への対応

Cerium における GPGPU への対応

Bitonic Sort を用いた Cerium の評価

Bitonic Sort を用いた Cerium の評価

Bitonic Sort を用いた Cerium の評価

Cerium の問題点

TaskQueue

Persistent Data Tree

Worker

Worker

TaskManager

Gears OS の評価

Twice

Result

まとめ

今後の課題