Mercurial > hg > Members > Moririn

changeset 368:5506a5d61a05

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge 367 362
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Thu, 29 Jun 2017 21:50:01 +0900
parents 51b7e4eb9ade (diff) 5d45b2943265 (current diff)
children 62a88864e1e2
files src/parallel_execution/context.h
diffstat 8 files changed, 107 insertions(+), 94 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Thu Jun 29 21:45:10 2017 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Thu Jun 29 21:50:01 2017 +0900
@@ -60,7 +60,7 @@
   TARGET
       twice
   SOURCES 
-      examples/twice.cbc RedBlackTree.cbc compare.c SingleLinkedStack.cbc CPUWorker.cbc time.cbc twice.cbc TaskManagerImpl.cbc SingleLinkedQueue.cbc SynchronizedQueue.cbc SemaphoreImpl.cbc
+  examples/twice.cbc CPUWorker.cbc twice.cbc TaskManagerImpl.cbc SingleLinkedQueue.cbc SynchronizedQueue.cbc SemaphoreImpl.cbc TimeImpl.cbc
 )
 
 GearsCommand(
--- a/src/parallel_execution/SynchronizedQueue.cbc	Thu Jun 29 21:45:10 2017 +0900
+++ b/src/parallel_execution/SynchronizedQueue.cbc	Thu Jun 29 21:50:01 2017 +0900
@@ -2,12 +2,16 @@
 
 #include <stdio.h>
 
+/* 
+ * Nonnon-blocking queue of Paper: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms(https://www.research.ibm.com/people/m/michael/podc-1996.pdf).
+ */
+
 Queue* createSynchronizedQueue(struct Context* context) {
     struct Queue* queue = new Queue();
     struct SynchronizedQueue* synchronizedQueue = new SynchronizedQueue();
-    synchronizedQueue->top  = NULL;
-    synchronizedQueue->last = NULL;
-    synchronizedQueue ->queueCount = createSemaphoreImpl(context, 0);
+    synchronizedQueue->top = new Element();
+    synchronizedQueue->top->next = NULL;
+    synchronizedQueue->last = synchronizedQueue->top;
     queue->queue = (union Data*)synchronizedQueue;
     queue->take  = C_takeSynchronizedQueue;
     queue->put  = C_putSynchronizedQueue;
@@ -27,45 +31,42 @@
 
 __code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
     Element* element = new Element();
+    element->data = data;
     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);
+    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 {
-        if (__sync_bool_compare_and_swap(&queue->top, NULL, element)) {
-            queue->last = element;
-        } else {
-            goto meta(context, C_putSynchronizedQueue);
-        }
+        __sync_bool_compare_and_swap(&queue->last, last, nextElement);
     }
-    goto meta(context, C_putSynchronizedQueue1);
+    goto meta(context, C_putSynchronizedQueue);
 }
 
-__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);
-}
-
-__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, ...)) {
+__code takeSynchronizedQueue(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 {
+    struct Element* last = queue->last;
+    struct Element* nextElement = top->next;
+    if (top != queue->top) {
         goto meta(context, C_takeSynchronizedQueue);
     }
-    goto next(data, ...);
+    if (top == last) {
+        if (nextElement != NULL) {
+          __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);
 }
 
 __code isEmptySynchronizedQueue(struct SynchronizedQueue* queue, __code next(...), __code whenEmpty(...)) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/Time.cbc	Thu Jun 29 21:50:01 2017 +0900
@@ -0,0 +1,7 @@
+typedef struct Time<Impl>{
+        union Data* time;
+        __code start(Impl* time, __code next(...));
+        __code end(Impl* time, __code next(...));
+        __code next(...);
+} Queue;
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/TimeImpl.cbc	Thu Jun 29 21:50:01 2017 +0900
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <sys/time.h>
+
+#include "../context.h"
+
+Time* createTimeImpl(struct Context* context) {
+    struct Time* time = new Time();
+    struct TimeImpl* timeImpl = new TimeImpl();
+    time->time = (union Data*)timeImpl;
+    time->start = C_startTime;
+    time->end = C_endTime;
+    return time;
+}
+
+__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(...);
+}
--- a/src/parallel_execution/context.h	Thu Jun 29 21:45:10 2017 +0900
+++ b/src/parallel_execution/context.h	Thu Jun 29 21:50:01 2017 +0900
@@ -104,9 +104,14 @@
     } meta;
     struct Context Context;
     struct Time {
+        union Data* time;
+        enum Code start;
+        enum Code end;
         enum Code next;
+    } Time;
+    struct TimeImpl {
         double time;
-    } Time;
+    } TimeImpl;
     struct LoopCounter {
         int i;
     } LoopCounter;
@@ -194,7 +199,6 @@
     struct SynchronizedQueue {
         struct Element* top;
         struct Element* last;
-        struct Semaphore* queueCount;
     } SynchronizedQueue;
     // Stack Interface
     struct Stack {
--- a/src/parallel_execution/examples/calc.cbc	Thu Jun 29 21:45:10 2017 +0900
+++ b/src/parallel_execution/examples/calc.cbc	Thu Jun 29 21:50:01 2017 +0900
@@ -157,7 +157,6 @@
     task->maxOdg = task->odg + 3;
     tasks[2] = task;
 
-    //goto taskManager->setWaitTask(createTask1);
     taskManager->contexts = tasks;
     // goto crateTask1();
     taskManager->next1 = C_createTask1;
--- a/src/parallel_execution/examples/twice.cbc	Thu Jun 29 21:45:10 2017 +0900
+++ b/src/parallel_execution/examples/twice.cbc	Thu Jun 29 21:50:01 2017 +0900
@@ -48,7 +48,7 @@
     while(! cuda_initialized) {};
 #endif
 #endif
-    goto meta(context, C_createTask1);
+    goto meta(context, C_code1);
 }
 
 __code initDataGears_stub(struct Context* context) {
@@ -81,17 +81,14 @@
     /* puts("tree"); */
     /* print_tree(context->data[Tree]->tree.root); */
     /* puts("result"); */
-
-    time->next = C_code2;
-    goto meta(context, C_code2);
+    time->time = (union Data*)createTimeImpl(context);
+    time->next = C_createTask1;
+    goto meta(context, time->time->Time.start);
+    //goto meta(context, C_createTask1);
     //goto meta(context, C_exit_code);
     //goto meta(context, C_start_time);
 }
 
-__code code1_stub(struct Context* context) {
-    goto code1(context, Gearef(context, Time));
-}
-
 __code code2(struct LoopCounter* loopCounter) {
     int i = loopCounter->i;
 
@@ -108,29 +105,39 @@
     goto meta(context, C_exit_code);
 }
 
-__code createTask1(struct LoopCounter* loopCounter, struct TaskManager* taskManager) {
+__code createTask1(struct LoopCounter* loopCounter, struct TaskManager* taskManager, struct Time* time) {
     int i = loopCounter->i;
 
     if ((length/split*i) < length) {
-        taskManager->next = C_createTask2;
-        goto meta(context, taskManager->taskManager->TaskManager.createTask);
+        goto meta(context, C_createTask2);
     }
 
     loopCounter->i = 0;
-    taskManager->next = C_code1;
+    taskManager->next = time->time->Time.end;
+    time->next = C_code2;
 #if ( defined(USE_CUDAWorker) && defined(USE_CUDA_MAIN_THREAD))
 sleep(5);
 #endif
     goto meta(context, taskManager->taskManager->TaskManager.shutdown);
 }
 
-__code createTask2(LoopCounter* loopCounter, TaskManager* taskManager,struct Context* task, LoopCounter* loopCounter2, Array* array) {
+__code createTask2(struct LoopCounter* loopCounter, struct TaskManager* taskManager) {
+    struct Context** tasks = (struct Context**)ALLOC_ARRAY(context, Context, 1);
+
     int i = loopCounter->i;
+    LoopCounter* loopCounter2 = &ALLOCATE_DATA_GEAR(context, LoopCounter)->LoopCounter;
+    Array* array = &ALLOCATE_DATA_GEAR(context, Array)->Array;
     array->index = i;
     array->prefix = length/split;
     array->array = array_ptr;
     array->size = length;
     loopCounter2->i = 0;
+    loopCounter->i++;
+
+    // par goto twice(loopCounter2, array, __exit);
+    struct Context* task = NEW(struct Context);
+    initContext(task);
+    task->taskManager = &taskManager->taskManager->TaskManager;
     task->idgCount = 0;
     if (gpu_num) {
 #ifdef USE_CUDAWorker
@@ -142,24 +149,18 @@
     } else {
         task->next = C_twice;
     }
+    task->idg = task->dataNum;
     task->data[task->dataNum] = (union Data*)loopCounter2;
     task->data[task->dataNum+1] = (union Data*)array;
-    task->odg = task->dataNum + 2;
+    task->maxIdg = task->idg + 2;
+    task->odg = task->maxIdg;
     task->maxOdg = task->odg;
-    taskManager->next = C_createTask1;
-    loopCounter->i++;
-    goto meta(context, taskManager->taskManager->TaskManager.spawn);
-}
+    tasks[0] = task;
 
-__code createTask2_stub(struct Context* context) {
-    LoopCounter* loopCounter = &ALLOCATE(context, LoopCounter)->LoopCounter;
-    Array* array = &ALLOCATE(context, Array)->Array;
-    goto createTask2(context,
-            Gearef(context, LoopCounter),
-            Gearef(context, TaskManager),
-            Gearef(context, TaskManager)->context,
-            loopCounter,
-            array);
+    taskManager->contexts = tasks;
+    // goto crateTask1();
+    taskManager->next1 = C_createTask1;
+    goto meta(context, taskManager->taskManager->TaskManager.spawnTasks);
 }
 
 void init(int argc, char** argv) {
--- a/src/parallel_execution/time.cbc	Thu Jun 29 21:45:10 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,30 +0,0 @@
-#include <stdio.h>
-#include <sys/time.h>
-
-#include "../context.h"
-
-__code start_time(struct Time* time) {
-    struct timeval tv;
-    gettimeofday(&tv, NULL);
-
-    time->time = tv.tv_sec + (double)tv.tv_usec*1e-6;
-
-    goto meta(context, time->next);
-}
-
-__code start_time_stub(struct Context* context) {
-    goto start_time(context, &context->data[D_Time]->Time);
-}
-
-__code end_time(struct Time* time) {
-    struct timeval tv;
-    gettimeofday(&tv, NULL);
-
-    printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time);
-
-    goto meta(context, time->next);
-}
-
-__code end_time_stub(struct Context* context) {
-    goto end_time(context, Gearef(context, Time));
-}