changeset 90:4b5bf5b40970

put queue
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 06:47:35 +0900
parents 00d4c6fa4969
children 1e074c3878c7
files src/parallel_execution/CMakeLists.txt src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/main.c
diffstat 4 files changed, 218 insertions(+), 33 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Tue Jan 19 18:05:15 2016 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Tue Jan 26 06:47:35 2016 +0900
@@ -4,7 +4,7 @@
 
 set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang)
 
-add_executable(bitonic_sort
+add_executable(twice
                main.c
                context.c
                rb_tree.c
--- a/src/parallel_execution/context.c	Tue Jan 19 18:05:15 2016 +0900
+++ b/src/parallel_execution/context.c	Tue Jan 26 06:47:35 2016 +0900
@@ -45,6 +45,14 @@
 extern __code deleteCase6_stub(struct Context*);
 extern __code createWorker_stub(struct Context*);
 extern __code taskManager_stub(struct Context*);
+extern __code createData1_stub(struct Context*);
+extern __code createData2_stub(struct Context*);
+extern __code createTask1_stub(struct Context*);
+extern __code createTask2_stub(struct Context*);
+extern __code putQueue1_stub(struct Context*);
+extern __code putQueue2_stub(struct Context*);
+extern __code putQueue3_stub(struct Context*);
+extern __code putQueue4_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initContext(struct Context* context) {
@@ -63,7 +71,7 @@
     /* context->code[Find]       = find; */
     /* context->code[Not_find]   = not_find; */
     /* context->code[Code6]      = code6; */
-    context->code[Put]        = put_stub;
+    context->code[PutTree]        = put_stub;
     context->code[Replace]    = replaceNode_stub;
     context->code[Insert]     = insertNode_stub;
     context->code[RotateL]    = rotateLeft_stub;
@@ -94,6 +102,14 @@
     /* context->code[DeleteCase6]   = deleteCase6_stub; */
     context->code[CreateWorker]  = createWorker_stub;
     context->code[TaskManager]   = taskManager_stub;
+    context->code[CreateData1]   = createData1_stub;
+    context->code[CreateData2]   = createData2_stub;
+    context->code[CreateTask1]   = createTask1_stub;
+    context->code[CreateTask2]   = createTask2_stub;
+    context->code[PutQueue1]     = putQueue1_stub;
+    context->code[PutQueue2]     = putQueue2_stub;
+    context->code[PutQueue3]     = putQueue3_stub;
+    context->code[PutQueue4]     = putQueue4_stub;
     context->code[Exit]       = exit_code;
     
     context->heap = context->heapStart;
@@ -113,8 +129,8 @@
     context->data[LoopCounter] = context->heap;
     context->heap += sizeof(struct LoopCounter);
 
-    context->data[WaitQueue] = context->heap;
-    context->heap += sizeof(struct Queue);
+    context->data[Element] = context->heap;
+    context->heap += sizeof(struct Element);
 
     context->data[ActiveQueue] = context->heap;
     context->heap += sizeof(struct Queue);
@@ -125,10 +141,11 @@
     worker->num = 0;
     worker->contexts = 0;
 
-    struct Allocate* allocate = &contexts->data[Allocate]->allocate;
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
     allocate->size = 0;
 
     struct Tree* tree = &context->data[Tree]->tree;
+    context->tree = tree;
     tree->root = 0;
     tree->current = 0;
 
@@ -141,10 +158,15 @@
     struct LoopCounter* counter = &context->data[LoopCounter]->loopCounter;
     counter->i = 0;
 
-    struct Queue* waitQueue = &context->data[WaitQueue]->queue;
-    waitQueue->first = 0;
-    waitQueue->last = 0;
-    waitQueue->count = 0;
+    struct Element* element = &context->data[Element]->element;
+    element->task = 0;
+    element->next = 0;
+
+    struct Queue* activeQueue = &context->data[ActiveQueue]->queue;
+    context->activeQueue = activeQueue;
+    activeQueue->first = 0;
+    activeQueue->last = 0;
+    activeQueue->count = 0;
     
     context->node_stack = stack_init(sizeof(struct Node*), 100);
     context->code_stack = stack_init(sizeof(enum Code), 100);
--- a/src/parallel_execution/context.h	Tue Jan 19 18:05:15 2016 +0900
+++ b/src/parallel_execution/context.h	Tue Jan 26 06:47:35 2016 +0900
@@ -2,7 +2,7 @@
 #include <pthread.h>
 #include "stack.h"
 
-#define ALLOCATE_SIZE 1000
+#define ALLOCATE_SIZE 100000
 
 enum Code {
     Code1,
@@ -14,7 +14,7 @@
     Not_find,
     Code6,
     Allocator,
-    Put,
+    PutTree,
     Replace,
     Insert,
     Compare,
@@ -47,6 +47,14 @@
     DeleteCase6,
     CreateWorker,
     TaskManager,
+    CreateData1,
+    CreateData2,
+    CreateTask1,
+    CreateTask2,
+    PutQueue1,
+    PutQueue2,
+    PutQueue3,
+    PutQueue4,
     Exit,
 };
 
@@ -62,7 +70,7 @@
     Tree,
     Node,
     LoopCounter,
-    WaitQueue,
+    Element,
     ActiveQueue,
 };
 
@@ -78,9 +86,8 @@
     stack_ptr node_stack;
     int dataNum;
     union Data **data;
-    struct Queue* waitQueue;
     struct Queue* activeQueue;
-    struct Tree* Tree;
+    struct Tree* tree;
 };
 
 union Data {
@@ -88,20 +95,26 @@
         int i;
     } loopCounter;
     struct Worker {
-        //enum DataType type;
         int num;
         struct Context* contexts;
     } worker;
+    struct Task {
+        enum Code code;
+        int key;
+    } task;
+    struct Queue {
+        struct Element* first;
+        struct Element* last;
+        int count;
+    } queue;
+    struct Element {
+        struct Task* task;
+        struct Element* next;
+    } element;
     struct Array {
-        //enum DataType type;
-        int size;
+        int index;
         int* array;
     } array;
-    struct Spots {
-        //enum DataType type;
-        int x;
-        int y;
-    } spot;
     struct Tree {
         enum Code next;
         struct Node* root;
@@ -112,7 +125,7 @@
         // need to tree
         enum Code next;
         int key; // comparable data segment
-        int value;
+        union Data* value;
         struct Node* left;
         struct Node* right;
         // need to balancing
--- a/src/parallel_execution/main.c	Tue Jan 19 18:05:15 2016 +0900
+++ b/src/parallel_execution/main.c	Tue Jan 26 06:47:35 2016 +0900
@@ -5,23 +5,167 @@
 #include "origin_cs.h"
 
 extern __code initContext(struct Context* context);
+extern void allocator(struct Context* context);
 
-int a;
+int length;
+int* array_ptr;
+
+void print_queue(struct Element* element) {
+    while (element) {
+        printf("%d\n", element->task->key);
+        element = element->next;
+    }
+}
+
+void print_tree(struct Node* node) {
+    if (node != 0) {
+        printf("%d\n", node->value->array.index);
+        print_tree(node->left);
+        print_tree(node->right);
+    }
+}
 
 __code code1(struct Context* context) {
-    if(__sync_bool_compare_and_swap(&a, 10, 0)) {
-        puts("success");
-        a = 10;
-    } else {
-        puts("failure");
-        goto meta(context, Code1);
-    }
+    print_queue(context->activeQueue->first);
+    puts("");
+    print_tree(context->tree->root);
+
+    goto meta(context, Exit);
 }
 
 __code code1_stub(struct Context* context) {
     goto code1(context);
 }
 
+__code createData1(struct Context* context, struct Allocate* allocate, struct LoopCounter* loopCounter) {
+    int i = loopCounter->i;
+
+    if (i < length) {
+        allocate->size = sizeof(struct Array);
+        allocator(context);
+
+        goto meta(context, CreateData2);
+    }
+
+    goto meta(context, Code1);
+}
+        
+__code createData1_stub(struct Context* context) {
+    goto createData1(context, &context->data[Allocate]->allocate, &context->data[LoopCounter]->loopCounter);
+}
+
+__code createData2(struct Context* context, struct LoopCounter* loopCounter, struct Array* array, struct Node* node) {
+    int i = loopCounter->i;
+
+    array->index = i;
+    array->array = array_ptr;
+
+    node->key = i;
+    node->value = (union Data*)array;
+
+    context->next = CreateTask1;
+
+    goto meta(context, PutTree);
+}
+
+__code createData2_stub(struct Context* context) {
+    goto createData2(context,
+                     &context->data[LoopCounter]->loopCounter,
+                     &context->data[context->dataNum]->array,
+                     &context->data[Node]->node);
+}
+
+__code createTask1(struct Context* context, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Task);
+    allocator(context);
+
+    goto meta(context, CreateTask2);
+}
+
+__code createTask1_stub(struct Context* context) {
+    goto createTask1(context, &context->data[Allocate]->allocate);
+}
+
+__code createTask2(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Element* element) {
+    int i = loopCounter->i;
+    
+    task->code = Code1;
+    task->key = i;
+    
+    element->task = task;
+
+    context->next = CreateData1;
+    loopCounter->i++;
+    
+    goto meta(context, PutQueue1);
+}
+
+__code createTask2_stub(struct Context* context) {
+    goto createTask2(context,
+                     &context->data[LoopCounter]->loopCounter,
+                     &context->data[context->dataNum]->task,
+                     &context->data[Element]->element);
+}
+
+__code putQueue1(struct Context* context, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Element);
+    allocator(context);
+
+    goto meta(context, PutQueue2);
+}
+
+__code putQueue1_stub(struct Context* context) {
+    goto putQueue1(context, &context->data[Allocate]->allocate);
+}
+
+__code putQueue2(struct Context* context, struct Element* new_element, struct Element* element, struct Queue* queue) {
+    new_element->task = element->task;
+
+    if (queue->first)
+        goto meta(context, PutQueue3);
+    else
+        goto meta(context, PutQueue4);
+}
+
+__code putQueue2_stub(struct Context* context) {
+    goto putQueue2(context,
+                   &context->data[context->dataNum]->element,
+                   &context->data[Element]->element,
+                   &context->data[ActiveQueue]->queue);
+}
+
+__code putQueue3(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, PutQueue3);
+    }
+}
+
+__code putQueue3_stub(struct Context* context) {
+    goto putQueue3(context, &context->data[ActiveQueue]->queue, &context->data[context->dataNum]->element);
+}
+
+__code putQueue4(struct Context* context, struct Queue* queue, struct Element* new_element) {
+    if (__sync_bool_compare_and_swap(&queue->first, 0, new_element)) {
+        queue->last = new_element;
+        queue->count++;
+        
+        goto meta(context, context->next);
+    } else {
+        goto meta(context, PutQueue3);
+    }
+}
+
+__code putQueue4_stub(struct Context* context) {
+    goto putQueue4(context, &context->data[ActiveQueue]->queue, &context->data[context->dataNum]->element);
+}
+
 __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
     int i = loopCounter->i;
 
@@ -61,12 +205,18 @@
 }
 
 int main(int argc, char** argv) {
-    a = 10;
     int cpu_num = (int)atoi(argv[1]);
+    length = (int)atoi(argv[2]);
+
+    array_ptr = (int*)malloc(sizeof(int)*length);
+
+    for(int i=0; i<length; i++)
+        array_ptr[i]=i;
 
     struct Context* main_context = (struct Context*)malloc(sizeof(struct Context));
     initContext(main_context);
-    main_context->next = CreateWorker;
+    //main_context->next = CreateWorker;
+    main_context->next = CreateData1;
 
     struct Context* worker_contexts = (struct Context*)malloc(sizeof(struct Context)*cpu_num);