# HG changeset patch # User Shohei KOKUBO # Date 1455779600 -32400 # Node ID e077497754a0646ed7e2a59f828efa735b6fbe6d # Parent 4dcfec1bf1e7eaffaf06093e7d4a92dc15e43a04 revision diff -r 4dcfec1bf1e7 -r e077497754a0 slide/index.html --- a/slide/index.html Thu Feb 18 07:20:46 2016 +0900 +++ b/slide/index.html Thu Feb 18 16:13:20 2016 +0900 @@ -87,7 +87,7 @@ @@ -179,7 +179,7 @@

Code Gear は Code Segment と同等のものである。 Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。 -接続された Data Gear 以外にアクセスすることは

+接続された Data Gear 以外にアクセスすることはできない。

Data Gear はデータそのものを表す。 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。

@@ -234,7 +234,7 @@

Cerium の構成

Gears OS の構成

Worker

@@ -249,24 +249,237 @@

測定結果

Allocator

OS X(10.10.5)
2.3 GHz Intel Core i7
length：1310720
cpus/(length/task)/time +
Context の生成時にある程度の大きさのメモリ領域を確保
Context には確保したメモリ領域を指す情報(heapStart, heap, heapLimit)を格納

+ +

/* Context definition example */
+#define ALLOCATE_SIZE 1000
+
+// Code Gear Name
+enum Code {
+    Code1,
+    Code2,
+    Allocator,
+    Exit,
+};
+
+// Unique Data Gear
+enum UniqueData {
+    Allocate,
+};
+
+struct Context {
+    enum Code next;
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    union Data **data;
+};
+
+// Data Gear definition
+union Data {
+    // size: 4 byte
+    struct Data1 {
+        int i;
+    } data1;
+    // size: 5 byte
+    struct Data2 {
+        int i;
+        char c;
+    } data2;
+    // size: 8 byte
+    struct Allocate {
+        long size;
+    } allocate;
+};
+

+ + +

+ +

Allocator

Allocation を行うための情報を書き込む Data Gear が必要
- 1/10/0.164748s
- 2/10/0.230114s
- 4/10/0.479126s
- 8/10/0.553448s
- 1/81920/0.010666s
- 2/81920/0.005303s
- 4/81920/0.002657s
- 8/81920/0.002521s
- Context と同時に生成

__code initContext(struct Context* context, int num) {
+    context->heapLimit        = sizeof(union Data)*ALLOCATE_SIZE;
+    context->heapStart        = malloc(context->heapLimit);
+    context->heap             = context->heapStart;
+    context->codeNum          = Exit;
+    
+    context->code             = malloc(sizeof(__code*)*ALLOCATE_SIZE);
+    context->data             = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
+
+    context->code[Code1]      = code1_stub;
+    context->code[Code2]      = code2_stub;
+    context->code[Allocator]  = allocator_stub;
+    context->code[Exit]       = exit_code;
+    
+    context->data[Allocate]   = context->heap;
+    context->heap            += sizeof(struct Allocate);
+    
+    context->dataNum          = Allocate;
+}
+

+ + +

+ +

Allocator

メモリ領域を指すポインタを動かすことで Data Gear のメモリを確保
確保した Data Gear は基本的に破棄可能なものである
リニアにメモリを確保し、サイズを超えたら先頭に戻って再利用

+ +

Allocator

+ + +

+ +

Allocator

Allocation に必要な情報を Data Gear に書き込み、Allocator に接続する
生成した Data Gear には Context を介してアクセスすることができるが、Context を直接扱うのは好ましくない
Context から値を取り出すだけのメタレベルの Code Gear を用意

+ +

// Meta Code Gear
+__code meta(struct Context* context, enum Code next) {
+    // meta computation
+    goto (context->code[next])(context);
+}
+
+// Code Gear
+__code code1(struct Context* context, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Data1);
+    context->next  = Code2;
+    
+    goto meta(context, Allocator);
+}
+
+// Meta Code Gear(stub)
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Allocate]->allocate);
+}
+
+// Meta Code Gear
+__code allocator(struct Context* context, struct Allocate* allocate) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap                    += allocate->size;
+
+    goto meta(context, context->next);
+}
+
+// Meta Code Gear(stub)
+__code allocator_stub(struct Context* context) {
+    goto allocator(context, &context->data[Allocate]->allcate);
+}
+
+// Code Gear
+__code code2(struct Context* context, struct Data1* data1) {
+    // processing
+}
+
+// Meta Code Gear(stub)
+__code code2_stub(struct Context* context) {
+    goto code2(context, &context->data[context->dataNum]->data1);
+}
+

+ + +

+ +

TaskQueue

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

+ +

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

// Code Gear Name
+enum Code {
+    PutQueue,
+    GetQueue,
+};
+
+// Unique Data Gear
+enum UniqueData {
+    Queue,
+    Element,
+};
+
+// Queue definication
+union Data {
+    // size: 20 byte
+    struct Queue {
+        struct Element* first;
+        struct Element* last;
+        int count;
+    } queue;
+    // size: 16 byte
+    struct Element {
+        struct Task* task;
+        struct Element* next;
+    } element;
+}
+

+ + +

+ +

TaskQueue の操作(Enqueue)

Enqueue は Queue の最後の要素を取り出し、次の要素に追加する要素を設定
Queue を表す Data Gear が指す末尾を追加する要素に設定
正しく最後の要素が取り出せたことを保証して末尾の変更を行う必要がある

+ +

// Enqueue
+__code putQueue(struct Context* context, 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;
+        queue->count++;
+        
+        goto meta(context, context->next);
+    } else {
+        goto meta(context, PutQueue);
+    }
+}
+

+ + +

+ +

Persistent Data Tree

Data Gear の管理を行う
複数の Context で共有
一度構築した木構造を破壊することなく新しい木構造を構築するので平行して読み書き可能
非破壊木構造の基本的な戦略はルートから変更したいノードへのパスをすべてコピーし、パス上に存在しないノードはコピー元の木構造と共有する

+ +

非破壊木構造

diff -r 4dcfec1bf1e7 -r e077497754a0 slide/index.md --- a/slide/index.md Thu Feb 18 07:20:46 2016 +0900 +++ b/slide/index.md Thu Feb 18 16:13:20 2016 +0900 @@ -61,7 +61,7 @@ Code Gear は Code Segment と同等のものである。 Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。 -接続された Data Gear 以外にアクセスすることは +接続された Data Gear 以外にアクセスすることはできない。 Data Gear はデータそのものを表す。 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。 @@ -106,18 +106,205 @@ ![Gears OS の構成](./pictures/gearsos.svg) # Allocator +* Context の生成時にある程度の大きさのメモリ領域を確保 +* Context には確保したメモリ領域を指す情報(heapStart, heap, heapLimit)を格納 +``` C +/* Context definition example */ +#define ALLOCATE_SIZE 1000 + +// Code Gear Name +enum Code { + Code1, + Code2, + Allocator, + Exit, +}; + +// Unique Data Gear +enum UniqueData { + Allocate, +}; + +struct Context { + enum Code next; + int codeNum; + __code (**code) (struct Context*); + void* heapStart; + void* heap; + long heapLimit; + int dataNum; + union Data **data; +}; + +// Data Gear definition +union Data { + // size: 4 byte + struct Data1 { + int i; + } data1; + // size: 5 byte + struct Data2 { + int i; + char c; + } data2; + // size: 8 byte + struct Allocate { + long size; + } allocate; +}; +``` + +# Allocator +* Allocation を行うための情報を書き込む Data Gear が必要 + * Context と同時に生成 +``` C +__code initContext(struct Context* context, int num) { + context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; + context->heapStart = malloc(context->heapLimit); + context->heap = context->heapStart; + context->codeNum = Exit; + + context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); + context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); + + context->code[Code1] = code1_stub; + context->code[Code2] = code2_stub; + context->code[Allocator] = allocator_stub; + context->code[Exit] = exit_code; + + context->data[Allocate] = context->heap; + context->heap += sizeof(struct Allocate); + + context->dataNum = Allocate; +} +``` + +# Allocator +* メモリ領域を指すポインタを動かすことで Data Gear のメモリを確保 +* 確保した Data Gear は基本的に破棄可能なものである +* リニアにメモリを確保し、サイズを超えたら先頭に戻って再利用 + +![Allocator](./pictures/allocation.svg) + +# Allocator +* Allocation に必要な情報を Data Gear に書き込み、Allocator に接続する +* 生成した Data Gear には Context を介してアクセスすることができるが、Context を直接扱うのは好ましくない +* Context から値を取り出すだけのメタレベルの Code Gear を用意 + +``` C +// Meta Code Gear +__code meta(struct Context* context, enum Code next) { + // meta computation + goto (context->code[next])(context); +} + +// Code Gear +__code code1(struct Context* context, struct Allocate* allocate) { + allocate->size = sizeof(struct Data1); + context->next = Code2; + + goto meta(context, Allocator); +} -# 測定結果 -* OS X(10.10.5) -* 2.3 GHz Intel Core i7 -* length：1310720 -* cpus/(length/task)/time - * 1/10/0.164748s - * 2/10/0.230114s - * 4/10/0.479126s - * 8/10/0.553448s - * 1/81920/0.010666s - * 2/81920/0.005303s - * 4/81920/0.002657s - * 8/81920/0.002521s \ No newline at end of file +// Meta Code Gear(stub) +__code code1_stub(struct Context* context) { + goto code1(context, &context->data[Allocate]->allocate); +} + +// Meta Code Gear +__code allocator(struct Context* context, struct Allocate* allocate) { + context->data[++context->dataNum] = context->heap; + context->heap += allocate->size; + + goto meta(context, context->next); +} + +// Meta Code Gear(stub) +__code allocator_stub(struct Context* context) { + goto allocator(context, &context->data[Allocate]->allcate); +} + +// Code Gear +__code code2(struct Context* context, struct Data1* data1) { + // processing +} + +// Meta Code Gear(stub) +__code code2_stub(struct Context* context) { + goto code2(context, &context->data[context->dataNum]->data1); +} +``` + +# TaskQueue +TaskQueue は Task を管理する。 +すべての Context で共有され並列にアクセスされる。 +CAS 命令を利用してアクセスすることでデータの一貫性を保証する。 + +* 先頭と末尾の要素へのポインタを持った Queue を表す Data Gear +* Task と次の要素へのポインタを持った Element を表す Data Gear +``` C +// Code Gear Name +enum Code { + PutQueue, + GetQueue, +}; + +// Unique Data Gear +enum UniqueData { + Queue, + Element, +}; + +// Queue definication +union Data { + // size: 20 byte + struct Queue { + struct Element* first; + struct Element* last; + int count; + } queue; + // size: 16 byte + struct Element { + struct Task* task; + struct Element* next; + } element; +} +``` + +# TaskQueue の操作(Enqueue) +* Enqueue は Queue の最後の要素を取り出し、次の要素に追加する要素を設定 +* Queue を表す Data Gear が指す末尾を追加する要素に設定 +* 正しく最後の要素が取り出せたことを保証して末尾の変更を行う必要がある + +``` C +// Enqueue +__code putQueue(struct Context* context, 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; + queue->count++; + + goto meta(context, context->next); + } else { + goto meta(context, PutQueue); + } +} +``` + +# Persistent Data Tree +* Data Gear の管理を行う +* 複数の Context で共有 +* 一度構築した木構造を破壊することなく新しい木構造を構築するので平行して読み書き可能 +* 非破壊木構造の基本的な戦略はルートから変更したいノードへのパスをすべてコピーし、パス上に存在しないノードはコピー元の木構造と共有する + +![非破壊木構造](./pictures/tree.svg) + +# Persistent Data Tree +* 木構造を構築するとき最悪なケースでは事実上の線形リストになり、計算量が O(n) となる +* 挿入・削除・検索における処理時間を保証するために Red-Black Tree アルゴリズムを用いて木構造の平衡性を保つ +* Red-Black Tree では変更したノードからルートに上りながら条件を満たすように色の変更や木の回転を行う +* Code Gear の継続では呼び出し元に戻ることが出来ないので Context に辿ったパスを記憶するためのスタックを準備する。 + +```C diff -r 4dcfec1bf1e7 -r e077497754a0 slide/pictures/allocation.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/pictures/allocation.svg Thu Feb 18 16:13:20 2016 +0900 @@ -0,0 +1,396 @@ + + diff -r 4dcfec1bf1e7 -r e077497754a0 slide/pictures/tree.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/pictures/tree.svg Thu Feb 18 16:13:20 2016 +0900 @@ -0,0 +1,230 @@ + +