Papers/2016/kkb-master: slide/index.md comparison

comparison slide/index.md @ 20:e077497754a0

revision

author	Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date	Thu, 18 Feb 2016 16:13:20 +0900
parents	4dcfec1bf1e7
children	f147f579d552

comparison

equal deleted inserted replaced

-:4dcfec1bf1e7
+:e077497754a0
 Gears OS ではプログラムの単位として Gear を用いる。
 Gear は並列実行の単位、データ分割、Gear 間の接続などになる。
 Code Gear は Code Segment と同等のものである。
 Code Gear には任意の数の Data Gear を参照し、処理が完了すると任意の数の Data Gear に書き込みを行う。
-接続された Data Gear 以外にアクセスすることは
+接続された Data Gear 以外にアクセスすることはできない。
 Data Gear はデータそのものを表す。
 int や文字列などの Primitive Data Type を複数持つ構造体として定義する。
 Gear 特徴として処理やデータの構造が Code/Data Gear に閉じていることにある。
 実行後、必要なデータを Persistent Data Tree に書き出し次の Task を取得する。
 ![Gears OS の構成](./pictures/gearsos.svg)
 # Allocator
+* Context の生成時にある程度の大きさのメモリ領域を確保
+* Context には確保したメモリ領域を指す情報(heapStart, heap, heapLimit)を格納
-# 測定結果
-* OS X(10.10.5)
+``` C
-* 2.3 GHz Intel Core i7
+/* Context definition example */
-* length：1310720
+#define ALLOCATE_SIZE 1000
-* cpus/(length/task)/time
-* 1/10/0.164748s
+// Code Gear Name
-* 2/10/0.230114s
+enum Code {
-* 4/10/0.479126s
+Code1,
-* 8/10/0.553448s
+Code2,
-* 1/81920/0.010666s
+Allocator,
-* 2/81920/0.005303s
+Exit,
-* 4/81920/0.002657s
+};
-* 8/81920/0.002521s
+// 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);
+}
+// 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

Mercurial > hg > Papers > 2016 > kkb-master

comparison slide/index.md @ 20:e077497754a0