Mercurial > hg > GearsTemplate

changeset 169:ea7b11f3e717

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Using Queue Interface
author Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp>
date Tue, 22 Nov 2016 09:48:37 +0900
parents fa7419e2c67c
children ee7134f3bef1
files src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/dependency.c src/parallel_execution/main.c src/parallel_execution/queue.c src/parallel_execution/worker.c
diffstat 6 files changed, 84 insertions(+), 79 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.c	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/context.c	Tue Nov 22 09:48:37 2016 +0900
@@ -7,8 +7,8 @@
 extern __code code1_stub(struct Context*);
 extern __code code2_stub(struct Context*);
 extern __code code3_stub(struct Context*);
-extern __code code4(struct Context*);
-extern __code code5(struct Context*);
+extern __code code4_stub(struct Context*);
+extern __code code5_stub(struct Context*);
 extern __code find(struct Context*);
 extern __code not_find(struct Context*);
 extern __code code6(struct Context*);
@@ -58,12 +58,21 @@
 extern __code putQueue2_stub(struct Context*);
 extern __code putQueue3_stub(struct Context*);
 extern __code putQueue4_stub(struct Context*);
-extern __code getQueue_stub(struct Context*);
+extern __code getTask1_stub(struct Context*);
+extern __code getTask2_stub(struct Context*);
 extern __code spawnTask_stub(struct Context*);
 extern __code twice_stub(struct Context*);
 extern __code start_time_stub(struct Context*);
 extern __code end_time_stub(struct Context*);
 extern __code exit_code(struct Context*);
+extern __code clearSingleLinkedQueue_stub(struct Context*);
+extern __code putSingleLinkedQueue_stub(struct Context *);
+extern __code takeSingleLinkedQueue_stub(struct Context *);
+extern __code isEmptySingleLinkedQueue_stub(struct Context *);
+extern __code clearSynchronizedQueue_stub(struct Context*);
+extern __code putSynchronizedQueue_stub(struct Context *);
+extern __code takeSynchronizedQueue_stub(struct Context *);
+extern __code isEmptySynchronizedQueue_stub(struct Context *);
 
 __code initContext(struct Context* context) {
     context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
@@ -74,39 +83,44 @@
 
     context->codeNum = Exit;
 
-    context->code[C_code1]      = code1_stub;
-    context->code[C_code2]      = code2_stub;
-    context->code[C_put]       = put_stub;
-    context->code[C_replaceNode]       = replaceNode_stub;
-    context->code[C_replaceNode1]      = replaceNode1_stub;
-    context->code[C_insertNode]        = insertNode_stub;
-    context->code[C_rotateLeft]       = rotateLeft_stub;
-    context->code[C_rotateLeft1]       = rotateLeft1_stub;
-    context->code[C_rotateRight]       = rotateRight_stub;
-    context->code[C_rotateRight1]       = rotateRight1_stub;
-    context->code[C_insertCase1]   = insertCase1_stub;
-    context->code[C_insertCase2]   = insertCase2_stub;
-    context->code[C_insertCase3]   = insertCase3_stub;
-    context->code[C_insertCase4]   = insertCase4_stub;
-    context->code[C_insertCase5]   = insertCase5_stub;
-    context->code[C_insertCase51]   = insertCase51_stub;
-    context->code[C_stackClear]    = stackClear_stub;
-    context->code[C_get]           = get_stub;
-    context->code[C_search]        = search_stub;
+    context->code[C_code1]        = code1_stub;
+    context->code[C_code2]        = code2_stub;
+    context->code[C_put]          = put_stub;
+    context->code[C_replaceNode]  = replaceNode_stub;
+    context->code[C_replaceNode1] = replaceNode1_stub;
+    context->code[C_insertNode]   = insertNode_stub;
+    context->code[C_rotateLeft]   = rotateLeft_stub;
+    context->code[C_rotateLeft1]  = rotateLeft1_stub;
+    context->code[C_rotateRight]  = rotateRight_stub;
+    context->code[C_rotateRight1] = rotateRight1_stub;
+    context->code[C_insertCase1]  = insertCase1_stub;
+    context->code[C_insertCase2]  = insertCase2_stub;
+    context->code[C_insertCase3]  = insertCase3_stub;
+    context->code[C_insertCase4]  = insertCase4_stub;
+    context->code[C_insertCase5]  = insertCase5_stub;
+    context->code[C_insertCase51] = insertCase51_stub;
+    context->code[C_stackClear]   = stackClear_stub;
+    context->code[C_get]          = get_stub;
+    context->code[C_search]       = search_stub;
 
-    context->code[C_clearSingleLinkedStack] = clearSingleLinkedStack_stub;
-    context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub;
-    context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub;
-    context->code[C_pop2SingleLinkedStack] = pop2SingleLinkedStack_stub;
-    context->code[C_getSingleLinkedStack] = getSingleLinkedStack_stub;
-    context->code[C_get2SingleLinkedStack] = get2SingleLinkedStack_stub;
+    context->code[C_clearSingleLinkedStack]   = clearSingleLinkedStack_stub;
+    context->code[C_pushSingleLinkedStack]    = pushSingleLinkedStack_stub;
+    context->code[C_popSingleLinkedStack]     = popSingleLinkedStack_stub;
+    context->code[C_pop2SingleLinkedStack]    = pop2SingleLinkedStack_stub;
+    context->code[C_getSingleLinkedStack]     = getSingleLinkedStack_stub;
+    context->code[C_get2SingleLinkedStack]    = get2SingleLinkedStack_stub;
     context->code[C_isEmptySingleLinkedStack] = isEmptySingleLinkedStack_stub;
 
-    context->code[C_clearSingleLinkedQueue] = clearSingleLinkedQueue_stub;
-    context->code[C_putSingleLinkedQueue] = putSingleLinkedQueue_stub;
-    context->code[C_takeSingleLinkedQueue] = takeSingleLinkedQueue_stub;
+    context->code[C_clearSingleLinkedQueue]   = clearSingleLinkedQueue_stub;
+    context->code[C_putSingleLinkedQueue]     = putSingleLinkedQueue_stub;
+    context->code[C_takeSingleLinkedQueue]    = takeSingleLinkedQueue_stub;
     context->code[C_isEmptySingleLinkedQueue] = isEmptySingleLinkedQueue_stub;
 
+    context->code[C_clearSynchronizedQueue]   = clearSynchronizedQueue_stub;
+    context->code[C_putSynchronizedQueue]     = putSynchronizedQueue_stub;
+    context->code[C_takeSynchronizedQueue]    = takeSynchronizedQueue_stub;
+    context->code[C_isEmptySynchronizedQueue] = isEmptySynchronizedQueue_stub;
+
     /* context->code[Delete]        = delete_stub; */
     /* context->code[Delete1]       = delete1_stub; */
     /* context->code[Delete2]       = delete2_stub; */
@@ -133,7 +147,8 @@
     context->code[PutQueue2]     = putQueue2_stub;
     context->code[PutQueue3]     = putQueue3_stub;
     context->code[PutQueue4]     = putQueue4_stub;
-    context->code[GetQueue]      = getQueue_stub;
+    context->code[C_getTask1]    = getTask1_stub;
+    context->code[C_getTask2]    = getTask2_stub;
     context->code[SpawnTask]     = spawnTask_stub;
     context->code[Twice]         = twice_stub;
     context->code[StartTime]     = start_time_stub;
@@ -173,15 +188,8 @@
 
     ALLOC_DATA(context, Time);
 
-    struct Queue* activeQueue = ALLOC_DATA_TYPE(context, ActiveQueue, Queue);
-    activeQueue->first = 0;
-    activeQueue->last = 0;
-    activeQueue->count = 0;
-
-    struct Queue* waitQueue = ALLOC_DATA_TYPE(context, WaitQueue, Queue);
-    waitQueue->first = 0;
-    waitQueue->last = 0;
-    waitQueue->count = 0;
+    context->data[D_ActiveQueue] = createSynchronizedQueue(context)
+    context->data[D_WaitQueue]   = createSynchronizedQueue(context)
 
     context->dataNum = D_Queue;
 }
--- a/src/parallel_execution/context.h	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/context.h	Tue Nov 22 09:48:37 2016 +0900
@@ -90,7 +90,8 @@
     PutQueue2,
     PutQueue3,
     PutQueue4,
-    GetQueue,
+    C_GetTask1,
+    C_GetTask2,
     C_clearSingleLinkedStack,
     C_pushSingleLinkedStack,
     C_popSingleLinkedStack,
@@ -181,11 +182,11 @@
         struct Queue* waitI;
         int idsCount;
     } Task;
+    // Queue Interface
     struct Queue {
         union Data* queue;
         union Data* data;
         enum Code whenEmpty;
-
         enum Code clear;
         enum Code put;
         enum Code take;
@@ -202,8 +203,7 @@
         union Data* stack;
         union Data* data;
         union Data* data1;
-        enum Code whenEmpty;
-
+        enum Code whenEmpty; 
         enum Code clear;
         enum Code push;
         enum Code pop;
--- a/src/parallel_execution/dependency.c	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/dependency.c	Tue Nov 22 09:48:37 2016 +0900
@@ -30,26 +30,25 @@
 
 __code meta_spawnTask(struct Context* context, struct Queue* queue, enum Code next) {
     context->data[D_Queue] = (union Data *)queue;
-    goto (context->code[next])(context);
+    goto meta(context, context->next);
 }
 
-__code spawnTask(struct Context* context, struct Task* task, struct Element* element, struct Queue* activeQueue, struct Queue* waitQueue) {
-    //printf("spawn Task\n");
-    element->data = (union Data *)task;
-    if (task->waitI->count == task->idsCount) {
-        //printf("put ActiveQueue\n");
+__code spawnTask(struct Context* context, struct Element* element, struct Queue* activeQueue, struct Queue* waitQueue) {
+    struct Queue *queue;
+    if (task->idsCount == 0) {
         // enqueue activeQueue
-        goto meta_spawnTask(context, activeQueue, PutQueue1);
+        queue = activeQueue;
     } else {
-        //printf("put WaitQueue\n");
         // enqueue waitQueue
-        goto meta_spawnTask(context, waitQueue, PutQueue1);
+        queue = waitQueue;
     }
+    queue->data = element->data;
+    queue->next = context->next;
+    goto meta_spawnTask(context, queue, queue->put);
 }
 
 __code spawnTask_stub(struct Context* context) {
     goto spawnTask(context,
-            &context->data[context->dataNum-2]->task,
             &context->data[D_Element]->element,
             &context->data[D_ActiveQueue]->queue,
             &context->data[D_WaitQueue]->queue);
--- a/src/parallel_execution/main.c	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/main.c	Tue Nov 22 09:48:37 2016 +0900
@@ -111,7 +111,7 @@
             Gearef(context, Tree));
 }
 
-__code createTask1(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Queue* waitMe, struct Queue* waitI, struct Element* element, struct Queue* activeQueue) {
+__code createTask1(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Queue* waitMe, struct Queue* waitI, struct Element* element) {
     int i = loopCounter->i;
 
     waitMe->first = 0;
@@ -145,11 +145,9 @@
             task,
             waitMe,
             waitI,
-            &context->data[D_Element]->element,
-            &context->data[D_ActiveQueue]->Queue);
+            &context->data[D_Element]->element);
 }
 
-
 //__code createTask4(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Queue* waitMe, struct OdsQueue* waitI, struct Element* element, struct Queue* activeQueue) {
 //    int i = loopCounter->i;
 //
--- a/src/parallel_execution/queue.c	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/queue.c	Tue Nov 22 09:48:37 2016 +0900
@@ -7,7 +7,8 @@
     struct Queue* queue = &ALLOCATE(context, Queue)->queue;
     struct SingleLinkedQueue* singleLinkedQueue = &ALLOCATE(context, SingleLinkedQueue)->singleLinkedQueue;
     queue->queue = (union Data*)singleLinkedQueue;
-    singleLinkedQueue->top = NULL;
+    singleLinkedQueue->top  = NULL;
+    singleLinkedQueue->last = NULL;
     queue->take  = C_takeSingleLinkedQueue;
     queue->put  = C_putSingleLinkedQueue;
     queue->isEmpty = C_isEmptySingleLinkedQueue;
@@ -97,7 +98,8 @@
     struct Queue* queue = &ALLOCATE(context, Queue)->queue;
     struct SingleLinkedQueue* singleLinkedQueue = &ALLOCATE(context, SingleLinkedQueue)->singleLinkedQueue;
     queue->queue = (union Data*)singleLinkedQueue;
-    singleLinkedQueue->top = NULL;
+    singleLinkedQueue->top  = NULL;
+    singleLinkedQueue->last = NULL;
     queue->take  = C_takeSynchronizedQueue;
     queue->put  = C_putSynchronizedQueue;
     queue->isEmpty = C_isEmptySynchronizedQueue;
--- a/src/parallel_execution/worker.c	Tue Nov 22 04:21:11 2016 +0900
+++ b/src/parallel_execution/worker.c	Tue Nov 22 09:48:37 2016 +0900
@@ -3,27 +3,25 @@
 #include "context.h"
 #include "origin_cs.h"
 
-__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--;
+__code getTask1(struct Context* context, struct Queue* queue) {
+    queue->next = GetTask2;
+    goto meta(context, queue->take);
+}
 
-        context->next = GetQueue;
-        node->key = ((struct Task *)(first->data))->key;
-
-        struct Traverse *t = &context->data[D_Traverse]->Traverse;
-        t->next = ((struct Task *)(first->data))->code;
-        goto meta(context, C_get);
-    } else {
-        goto meta(context, GetQueue);
-    }
+__code getTask1_stub(struct Context* context) {
+    goto getTask1(context, &context->data[D_ActiveQueue]->queue);
 }
 
-__code getQueue_stub(struct Context* context) {
-    goto getQueue(context, &context->data[D_ActiveQueue]->queue, &context->data[D_Node]->node);
+__code getTask2(struct Context* context, struct Task* task, struct Node* node) {
+    node->key = task->key;
+
+    struct Traverse *t = &context->data[D_Traverse]->Traverse;
+    t->next = task->code;
+    goto meta(context, C_get);
+}
+
+__code getTask2_stub(struct Context* context) {
+    goto getTask2(context, &(context->data[D_ActiveQueue]->queue.data->task), &context->data[D_Node]->node);
 }
 
 #ifdef USE_CUDA