# HG changeset patch # User Tatsuki IHA # Date 1500476583 -32400 # Node ID ed48cf95acabdeaead1b4ba15a0c2ec0ed88fb1e # Parent 678e6992c8ae2d0f3b31e99d9e40a902f203f800 Update diff -r 678e6992c8ae -r ed48cf95acab 2017/2017_06_27/slide.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2017/2017_06_27/slide.md Thu Jul 20 00:03:03 2017 +0900 @@ -0,0 +1,72 @@ +title: Gears OS +author: Tatsuki IHA +profile: +lang: Japanese +code-engine: coderay + +## 研究目的 +- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している +- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う. +- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。 +- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。 +- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行を検証をメタ計算として記述することで、 並列処理の信頼性を保証する。 + +## 今週 +- synchornized Queue のバグ + +## synchornized Queue のバグ +- たとえば要素が一つだけの場合で事故る ↓ が同時に動くとtopが null になる + - take は top を top->next に cas する(つまりnull) + - put は last を element に cas し, last->next に element をいれる + - putもtakeも１つの変数をcasするようにしたほうが良いか + +``` c +__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) { + Element* element = new Element(); + element->next = NULL; + element->data = data; + if (queue->top) { + Element* last = queue->last; + if (__sync_bool_compare_and_swap(&queue->last, last, element)) { + last->next = element; + } else { + goto meta(context, C_putSynchronizedQueue); + } + } else { + if (__sync_bool_compare_and_swap(&queue->top, NULL, element)) { + queue->last = element; + } else { + goto meta(context, C_putSynchronizedQueue); + } + } + goto meta(context, C_putSynchronizedQueue1); +} + +__code putSynchronizedQueue1(struct SynchronizedQueue* queue, struct Semaphore* semaphore, __code next(...)) { + semaphore->semaphore = (union Data*)queue->queueCount; + semaphore->next = next; + goto meta(context, queue->queueCount->v); +} +``` + +``` c +__code takeSynchronizedQueue(struct SynchronizedQueue* queue, struct Semaphore* semaphore) { + semaphore->semaphore = (union Data*)queue->queueCount; + semaphore->next = C_takeSynchronizedQueue1; + goto meta(context, queue->queueCount->p); +} + +__code takeSynchronizedQueue1(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) { + struct Element* top = queue->top; + if (__sync_bool_compare_and_swap(&queue->top, top, top->next)) { + data = top->data; + } else { + goto meta(context, C_takeSynchronizedQueue); + } + goto next(data, ...); +} +``` + +## synchornized Queue のバグ + +https://www.research.ibm.com/people/m/michael/podc-1996.pdf とりあえず diff -r 678e6992c8ae -r ed48cf95acab 2017/2017_07_04/slide.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2017/2017_07_04/slide.md Thu Jul 20 00:03:03 2017 +0900 @@ -0,0 +1,155 @@ +title: Gears OS +author: Tatsuki IHA +profile: +lang: Japanese +code-engine: coderay + +## 研究目的 +- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している +- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う. +- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。 +- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。 +- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行を検証をメタ計算として記述することで、 並列処理の信頼性を保証する。 + +## 今週 +- synchornized Queue の修正 +- Time interface + +## synchornized Queue +- ダミーElement を作る +- dequeue で行う cas はtopの変更 + +
+ message +
+ +- inqueue で行う cas は末尾のnextを変更とlastの変更 + +
+ message +
+ +## synchornized Queue +- inqueue では2回CAS が必要なため CAS の間で構造が壊れる可能性がある +- なので, inqueue では末尾の要素の next のみを確実にCASする +- last のCAS は inqueue と dequeue 両方で行う + +``` c +__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) { + Element* element = new Element(); + element->data = data; + element->next = NULL; + Element* last = queue->last; + Element* nextElement = last->next; + if (last != queue->last) { + goto meta(context, C_putSynchronizedQueue); + } + if (nextElement == NULL) { + if (__sync_bool_compare_and_swap(&last->next, nextElement, element)) { + __sync_bool_compare_and_swap(&queue->last, last, element); + goto next(...); + } + } else { + // nextElement が Null 出ない場合, last を nextElement に cas する + __sync_bool_compare_and_swap(&queue->last, last, nextElement); + } + goto meta(context, C_putSynchronizedQueue); +} +``` + +```c +__code takeSynchronizedQueue(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) { + struct Element* top = queue->top; + struct Element* last = queue->last; + struct Element* nextElement = top->next; + if (top != queue->top) { + goto meta(context, C_takeSynchronizedQueue); + } + if (top == last) { + if (nextElement != NULL) { + // nextElement が Null 出ない場合, last を nextElement に cas する + __sync_bool_compare_and_swap(&queue->last, last, nextElement); + } + } else { + if (__sync_bool_compare_and_swap(&queue->top, top, nextElement)) { + data = nextElement->data; + goto next(data, ...); + } + } + goto meta(context, C_takeSynchronizedQueue); +} +``` + +## Time interface +- 前に実行時間を図るために使っていた CodeGear をinterface化しました + +``` c +typedef struct Time{ + union Data* time; + __code start(Impl* time, __code next(...)); + __code end(Impl* time, __code next(...)); + __code next(...); +} Queue; + +``` + +``` c +__code startTime(struct TimeImpl* time, __code next(...)) { + struct timeval tv; + gettimeofday(&tv, NULL); + + time->time = tv.tv_sec + (double)tv.tv_usec*1e-6; + + goto next(...); +} + +__code endTime(struct TimeImpl* time, __code next(...)) { + struct timeval tv; + gettimeofday(&tv, NULL); + + printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time); + + goto next(...); +} +``` + +## Time interface +- 試しに twice を測定しました +- 測った範囲はTask の生成から, TaskManager の shutdown(pthread_join) まで +- 環境 firefly +- 要素数: 10^9 +- タスク数: 1000 +- 1タスク辺りの処理量: 10^6 + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Number of ProcessorsTime(ms)
1 CPU9322
2 CPUs4734
4 CPUs2674
8 CPUs1408
12 CPUs902
+ +## 来週の予定 +- bitonic sort を並列化 +- CAS の部分をmetaに切り分け diff -r 678e6992c8ae -r ed48cf95acab 2017/2017_07_11/slide.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2017/2017_07_11/slide.md Thu Jul 20 00:03:03 2017 +0900 @@ -0,0 +1,102 @@ +title: Gears OS +author: Tatsuki IHA +profile: +lang: Japanese +code-engine: coderay + +## 研究目的 +- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している +- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う. +- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。 +- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。 +- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行を検証をメタ計算として記述することで、 並列処理の信頼性を保証する。 + +## 今週 +- bitonic sort を並列化 + - その際に iterator 的なものが欲しくなったのでそのお話 + +## Iterator +- bitonic sort は基本的には swap を並列に走らせているだけ + - 単純に, 何かしらの配列を Output するような構造 +- 記述が面倒 +- Cerium の Itearte が欲しくなった + +
+ message +
+ +## Cerium の Iterate +- Cerium は Taskを準備する際にiterateに繰り返す数を渡すことで実現 +- iterateを設定していると, 実行する際に SchedTaskの multi_dimension が呼ばれる + +``` C++ +void +SchedTask::multi_dimension(TaskListPtr list, void* read, void* write,TaskObjectRun run) { + long min = scheduler->min_cpu(); + long max = scheduler->max_cpu(); + long id = scheduler->id; + long lx = list->x; + long ly = list->y; + long lz = list->z; + + x=y=z=0; + + long cpu=min; + for (;;cpu++) { + if (cpu>max) cpu = min; + if (cpu==id) { + run(this, read,write); + } + if (++x>=lx) { + x=0; + if (++y>=ly) { + y=0; + if (++z>=lz) { + break; + } + } + } + } +} +``` + +## Gears ではどうするか +- par goto にオプションを付ける + +``` c +par goto Add(input1, input2, output1, _exit, iterate(x, y, z)) +``` + +``` c +struct Context* task = NEW(struct Context); +initContext(task); +... +task->dim_flag = 1; +task->x = x; +task->y = y; +task->z = z; +``` + +## Gears の実装 +- Active になるまでは1つのTaskとして処理 +- Active になると, 指定した数のTaskを生成して Worker に送信する + +``` +__code dimensionTaskSpawn(struct TaskManagerImpl* taskManager, struct Queue* queue, struct LoopCounter* loopCounter, struct Context* task, __code next(...)) { + int i = loopCounter->i; + int dimCount = task->x * task->y * task->z; + // TODO: implement 3-dimension + if(i < dimCount) { + loopCounter->i++; + struct Context* dimTask = cloneTask(task); + task->workerId = taskManager->sendWorkerIndex; + struct Queue* tasks = taskManager->workers[task->workerId]->tasks; + pthread_mutex_unlock(&taskManager->mutex); + tasks->put(dimTask, next(...)); + } + goto next(...); +} +``` + +## 来週の予定 +- まだ DG の待ち合わせを考えてないのでそれを考える diff -r 678e6992c8ae -r ed48cf95acab 2017/2017_07_18/slide.md --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/2017/2017_07_18/slide.md Thu Jul 20 00:03:03 2017 +0900 @@ -0,0 +1,89 @@ +title: Gears OS +author: Tatsuki IHA +profile: +lang: Japanese +code-engine: coderay + +## 研究目的 +- 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している +- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う. +- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。 +- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。 +- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の検証をメタ計算として記述することで、 並列処理の信頼性を保証する。 + +## 今週 +- Task の iterator + + +## Iterator interface +- Context に Iterator 用の変数を複数用意するのもあれなのでInterface を作った + +``` c +typedef struct Iterator{ + union Data* iterator; + struct Context* task; + __code exec(Impl* iterator, struct TaskManager* taskManager, struct Context* task, __code next(...)); + __code barrier(Impl* iterator, struct Context* task, __code next(...), __code whenWait(...)); + __code whenWait(...); + __code next(...); +} Iterator; +``` + +## Iterator implements +- 試しに一次元を処理する物を実装 +- Iterator を設定しているTaskが active なtaskになると exec が呼ばれ, Task を copy する + - copy している理由はまだ手を付けていない index を扱うため +- Iteratorで繰り返し処理されるTaskを待つのはbarrierで行う + - task が iterate されていても, されていなくても, normal レベルからは同じ task に見える + - Worker の meta 計算で, 実行後のTaskが iterate な Task なら barrierを呼ぶ + +``` c +struct OneDimIterator { + int x; + int count; + struct LoopCounter *loopCounter; +} OneDimIterator; + +Iterator* createOneDimIterator(struct Context* context, int x) { + struct Iterator* iterator = new Iterator(); + struct OneDimIterator* oneDimIterator = new OneDimIterator(); + iterator->iterator = (union Data*)oneDimIterator; + iterator->exec = C_execOneDimIterator; + iterator->barrier = C_barrierOneDimIterator; + oneDimIterator->x = x; + oneDimIterator->count = x; + oneDimIterator->loopCounter = new LoopCounter(); + oneDimIterator->loopCounter->i = 0; + return iterator; +} + +__code execOneDimIterator(struct OneDimIterator* iterator, struct TaskManager* taskManager, struct Context* task, __code next(...)) { + if (iterator->loopCounter->i == iterator->count) { + iterator->loopCounter->i = 0; + goto next(...); + } + + // create iterate task + struct Context* iterate_task = NEW(struct Context); + *iterate_task = *task; + iterate_task->iterate = 1; + iterator->loopCounter->i++; + + // spawn iterate task + taskManager->taskManager = (union Data*)task->taskManager; + taskManager->context = iterate_task; + taskManager->next = C_execOneDimIterator; + goto meta(context, task->taskManager->spawn); +} + +__code barrierOneDimIterator(struct OneDimIterator* iterator, struct Context* task, __code next(...), __code whenWait(...)) { + if (__sync_fetch_and_sub(&iterator->count, 1) == 1) { + goto next(...); + } + goto whenWait(...); +} +``` + +## まだ手を付けていない +- index にどうやってアクセスするか + - 普通に考えたらiterate する task の Code Gear の input になる