# HG changeset patch # User Shohei KOKUBO # Date 1454013412 -32400 # Node ID 3e28ee215c0e05ddece3574b3ac48922dad0ae7f # Parent 851da11072235214bc95a0034330185301965fee modify twice, use OSAtomiceCompareAndSwap diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/CMakeLists.txt --- a/src/parallel_execution/CMakeLists.txt Tue Jan 26 08:50:30 2016 +0900 +++ b/src/parallel_execution/CMakeLists.txt Fri Jan 29 05:36:52 2016 +0900 @@ -12,6 +12,8 @@ origin_cs.c allocate.c compare.c + worker.c + time.c twice.c ) diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/context.c --- a/src/parallel_execution/context.c Tue Jan 26 08:50:30 2016 +0900 +++ b/src/parallel_execution/context.c Fri Jan 29 05:36:52 2016 +0900 @@ -55,6 +55,8 @@ extern __code putQueue4_stub(struct Context*); extern __code getQueue_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*); __code initContext(struct Context* context) { @@ -114,6 +116,8 @@ context->code[PutQueue4] = putQueue4_stub; context->code[GetQueue] = getQueue_stub; context->code[Twice] = twice_stub; + context->code[StartTime] = start_time_stub; + context->code[EndTime] = end_time_stub; context->code[Exit] = exit_code; context->heap = context->heapStart; @@ -139,6 +143,9 @@ context->data[Element] = context->heap; context->heap += sizeof(struct Element); + context->data[Time] = context->heap; + context->heap += sizeof(struct Time); + context->data[ActiveQueue] = context->heap; context->heap += sizeof(struct Queue); diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/context.h --- a/src/parallel_execution/context.h Tue Jan 26 08:50:30 2016 +0900 +++ b/src/parallel_execution/context.h Fri Jan 29 05:36:52 2016 +0900 @@ -2,7 +2,7 @@ #include #include "stack.h" -#define ALLOCATE_SIZE 100000 +#define ALLOCATE_SIZE 20000000 enum Code { Code1, @@ -57,6 +57,8 @@ PutQueue4, GetQueue, Twice, + StartTime, + EndTime, Exit, }; @@ -73,6 +75,7 @@ Traverse, Node, LoopCounter, + Time, Element, ActiveQueue, }; @@ -93,6 +96,9 @@ }; union Data { + struct Time { + double time; + } time; struct LoopCounter { int i; } loopCounter; @@ -115,6 +121,7 @@ } element; struct Array { int index; + int prefix; int* array; } array; struct Tree { diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/main.c --- a/src/parallel_execution/main.c Tue Jan 26 08:50:30 2016 +0900 +++ b/src/parallel_execution/main.c Fri Jan 29 05:36:52 2016 +0900 @@ -1,5 +1,5 @@ #include -#include +#include #include "context.h" #include "origin_cs.h" @@ -7,7 +7,9 @@ extern __code initContext(struct Context* context); extern void allocator(struct Context* context); -int length; +int cpu_num = 1; +int length = 1024; +int split; int* array_ptr; void print_queue(struct Element* element) { @@ -26,13 +28,19 @@ } __code code1(struct Context* context) { - puts("queue"); - print_queue(context->data[ActiveQueue]->queue.first); - puts("tree"); - print_tree(context->data[Tree]->tree.root); - puts("result"); + printf("cpus:\t\t%d\n", cpu_num); + printf("length:\t\t%d\n", length); + printf("length/task:\t%d\n", length/split); + /* puts("queue"); */ + /* print_queue(context->data[ActiveQueue]->queue.first); */ + /* puts("tree"); */ + /* print_tree(context->data[Tree]->tree.root); */ + /* puts("result"); */ - goto meta(context, CreateWorker); + context->next = CreateWorker; + stack_push(context->code_stack, &context->next); + + goto meta(context, StartTime); } __code code1_stub(struct Context* context) { @@ -43,12 +51,15 @@ int i = loopCounter->i; if (i < length) { - printf("%d\n", array->array[i]); - loopCounter->i++; + // printf("%d\n", array->array[i]); + if (array->array[i] == (i*2)) { + loopCounter->i++; + goto meta(context, Code2); + } else + puts("wrong result"); - goto meta(context, Code2); } - + goto meta(context, Exit); } @@ -59,7 +70,7 @@ __code createData1(struct Context* context, struct Allocate* allocate, struct LoopCounter* loopCounter) { int i = loopCounter->i; - if (i < length) { + if ((length/split*i) < length) { allocate->size = sizeof(struct Array); allocator(context); @@ -78,11 +89,12 @@ int i = loopCounter->i; array->index = i; + array->prefix = length/split; array->array = array_ptr; node->key = i; node->value = (union Data*)array; - + context->next = CreateTask1; goto meta(context, PutTree); @@ -186,30 +198,6 @@ goto putQueue4(context, &context->data[ActiveQueue]->queue, &context->data[context->dataNum]->element); } -__code getQueue(struct Context* context, struct Queue* queue, struct Node* node) { - if (queue->count == 0) - return; - - struct Element* first = queue->first; - if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) { - queue->count--; - - context->next = GetQueue; - stack_push(context->code_stack, &context->next); - - context->next = first->task->code; - node->key = first->task->key; - - goto meta(context, Get); - } else { - goto meta(context, GetQueue); - } -} - -__code getQueue_stub(struct Context* context) { - goto getQueue(context, &context->data[ActiveQueue]->queue, &context->data[Node]->node); -} - __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { int i = loopCounter->i; @@ -244,16 +232,31 @@ } loopCounter->i = 0; - goto meta(context, Code2); + + context->next = Code2; + stack_push(context->code_stack, &context->next); + + goto meta(context, EndTime); } __code taskManager_stub(struct Context* context) { goto taskManager(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); } +void init(int argc, char** argv) { + for (int i = 1; argv[i]; ++i) { + if (strcmp(argv[i], "-cpu") == 0) + cpu_num = (int)atoi(argv[i+1]); + else if (strcmp(argv[i], "-l") == 0) + length = (int)atoi(argv[i+1]); + else if (strcmp(argv[i], "-s") == 0) + split = (int)atoi(argv[i+1]); + } +} + + int main(int argc, char** argv) { - int cpu_num = (int)atoi(argv[1]); - length = (int)atoi(argv[2]); + init(argc, argv); array_ptr = (int*)malloc(sizeof(int)*length); @@ -262,7 +265,6 @@ struct Context* main_context = (struct Context*)malloc(sizeof(struct Context)); initContext(main_context); - //main_context->next = CreateWorker; main_context->next = CreateData1; struct Context* worker_contexts = (struct Context*)malloc(sizeof(struct Context)*cpu_num); diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/time.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/time.c Fri Jan 29 05:36:52 2016 +0900 @@ -0,0 +1,33 @@ +#include +#include + +#include "context.h" +#include "origin_cs.h" + +__code start_time(struct Context* context, struct Time* time) { + struct timeval tv; + gettimeofday(&tv, NULL); + + time->time = tv.tv_sec + (double)tv.tv_usec*1e-6; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code start_time_stub(struct Context* context) { + goto start_time(context, &context->data[Time]->time); +} + +__code end_time(struct Context* context, struct Time* time) { + struct timeval tv; + gettimeofday(&tv, NULL); + + printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time); + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code end_time_stub(struct Context* context) { + goto end_time(context, &context->data[Time]->time); +} diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/twice.c --- a/src/parallel_execution/twice.c Tue Jan 26 08:50:30 2016 +0900 +++ b/src/parallel_execution/twice.c Fri Jan 29 05:36:52 2016 +0900 @@ -3,15 +3,27 @@ #include "context.h" #include "origin_cs.h" -__code twice(struct Context* context, int index, int* array) { - printf("No.%d %p\n", context->thread_num, context->thread); - array[index] = array[index]*2; +__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int prefix, int* array) { + int i = loopCounter->i; + + if (i < prefix) { + array[i+index*prefix] = array[i+index*prefix]*2; + loopCounter->i++; + + goto meta(context, Twice); + } + + loopCounter->i = 0; stack_pop(context->code_stack, &context->next); goto meta(context, context->next); } __code twice_stub(struct Context* context) { - goto twice(context, context->data[Node]->node.value->array.index, context->data[Node]->node.value->array.array); + goto twice(context, + &context->data[LoopCounter]->loopCounter, + context->data[Node]->node.value->array.index, + context->data[Node]->node.value->array.prefix, + context->data[Node]->node.value->array.array); } diff -r 851da1107223 -r 3e28ee215c0e src/parallel_execution/worker.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/worker.c Fri Jan 29 05:36:52 2016 +0900 @@ -0,0 +1,29 @@ +#include + +#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)) { + if (OSAtomicCompareAndSwapPtr(first, first->next, (void*)&queue->first)) { + queue->count--; + + context->next = GetQueue; + stack_push(context->code_stack, &context->next); + + context->next = first->task->code; + node->key = first->task->key; + + goto meta(context, Get); + } else { + goto meta(context, GetQueue); + } +} + +__code getQueue_stub(struct Context* context) { + goto getQueue(context, &context->data[ActiveQueue]->queue, &context->data[Node]->node); +}