Mercurial > hg > Gears > Gears

changeset 360:ba5959d7901d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add bitonic_sort but not work
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Tue, 27 Jun 2017 01:29:43 +0900
parents e68080586c15
children d93dceb84c75 136ce3537438
files src/parallel_execution/context.h src/parallel_execution/examples/SortArray.cbc src/parallel_execution/examples/sort.cbc
diffstat 3 files changed, 84 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.h	Sat Jun 24 20:11:48 2017 +0900
+++ b/src/parallel_execution/context.h	Tue Jun 27 01:29:43 2017 +0900
@@ -285,10 +285,17 @@
         int value;
     } Integer;
     struct SortArray {//そもそもこれは必要なのか？
+        struct SortArray *sortArray;
         struct Integer **array;//Array arrayじゃできない？
         int loop_counter;
+        int loop_counter2;
+        int loop_counter3;
+        int d;
         enum Code make_array;
         enum Code print;
+        enum Code bitonic_sort;
+        enum Code kernel;
+        enum Code swap;
     }SortArray;
 }; // union Data end       this is necessary for context generator
 
--- a/src/parallel_execution/examples/SortArray.cbc	Sat Jun 24 20:11:48 2017 +0900
+++ b/src/parallel_execution/examples/SortArray.cbc	Tue Jun 27 01:29:43 2017 +0900
@@ -1,6 +1,13 @@
 typedef struct SortArray<Impl>{
+    SortArray *sortArray;
     Integer **array;
     int loop_counter;
-    __code print(Integer* data, Integer i, __code next(...));
-    __code make_array(Integer* data, Integer i, __code next(...));
+    int loop_counter2;
+    int loop_counter3;
+    int d;
+    __code print(struct SortArray* sortArray, __code next(...));
+    __code make_array(struct SortArray* sortArray, __code next(...));
+    __code bitonic_sort(struct SortArray* sortArray, __code next(...));
+    __code kernel(struct SortArray* sortArray, __code next(...));
+    __code swap(struct SortArray* sortArray, __code next(...));
 } SortArray;
--- a/src/parallel_execution/examples/sort.cbc	Sat Jun 24 20:11:48 2017 +0900
+++ b/src/parallel_execution/examples/sort.cbc	Tue Jun 27 01:29:43 2017 +0900
@@ -2,6 +2,7 @@
 #include <stdlib.h>
 #include "../../context.h"
 #define MAX 20
+#define LOGN 5
 
 int main(int argc, char const* argv[]) {
     struct Context* main_context = NEW(struct Context);
@@ -11,30 +12,83 @@
 }
 
 __code sort_start(struct SortArray* sortArray){
-    sortArray = new SortArray();
-    sortArray->array = (Integer**)ALLOC_ARRAY(context, Integer, MAX);//ALLOC_ARRAYはDSの配列なのでintではできない
-    sortArray->loop_counter = 0;
+    sortArray->sortArray = new SortArray();
+    sortArray->sortArray->array = (Integer**)ALLOC_ARRAY(context, Integer, MAX);//ALLOC_ARRAYはDSの配列なのでintではできない
+    sortArray->sortArray->loop_counter = 0;
+    sortArray->sortArray->loop_counter2 = 0;
+    sortArray->sortArray->loop_counter3 = 0;
+    srand((unsigned) time(NULL));
     goto meta(context, C_make_array);
 }
 
-__code make_array(struct SortArray* sortArray){
-    if (sortArray->loop_counter == MAX){
-        sortArray->loop_counter = 0;
+__code make_array(struct SortArray* sortArray){//乱数生成
+    if (sortArray->sortArray->loop_counter == MAX){//ループの終了→配列表示へ
+        sortArray->sortArray->loop_counter = 0;
         goto meta(context, C_print);
     }
     struct Integer* integer = new Integer();
-    integer->value = rand() % MAX;
-    sortArray->array[sortArray->loop_counter] = integer;
-    sortArray->loop_counter++;
+    integer->value = rand() % 20;
+    sortArray->sortArray->array[sortArray->sortArray->loop_counter] = integer;
+    sortArray->sortArray->loop_counter++;
     goto meta(context, C_make_array);
 }
 
-__code print(struct SortArray* sortArray){
-    if (sortArray->loop_counter == MAX){
-        goto meta(context, C_exit_code);
+__code print(struct SortArray* sortArray){//配列表示
+    if (sortArray->sortArray->loop_counter == MAX){//ループの終了→ソートへ       
+        printf("\n");
+        if(sortArray->sortArray->loop_counter2 > 0){//ソート終わってたら終了
+            goto meta(context, C_exit_code);
+        }
+        sortArray->sortArray->loop_counter = 0;
+        sortArray->sortArray->loop_counter2 = 0; 
+        goto meta(context, C_bitonic_sort);
     }
-    printf("%d, ", sortArray->array[sortArray->loop_counter]->value);
-    sortArray->loop_counter++;
+    
+    printf("%d, ", sortArray->sortArray->array[sortArray->sortArray->loop_counter]->value);
+    sortArray->sortArray->loop_counter++;
     goto meta(context, C_print);
 }
 
+__code bitonic_sort(struct SortArray* sortArray){//ソートの繰り返し
+    if (sortArray->sortArray->loop_counter >= LOGN){//ループの終了→配列表示へ
+        sortArray->sortArray->loop_counter = 0;
+        goto meta(context, C_print);
+    }
+    goto meta(context, C_kernel);
+}
+
+__code kernel(struct SortArray* sortArray){//ソートの中身
+    int i = sortArray->sortArray->loop_counter3;    
+    int d = 0;
+    int up;
+   
+    if (sortArray->sortArray->loop_counter2 > sortArray->sortArray->loop_counter){//ループの終了→上のループへ
+        sortArray->sortArray->loop_counter++;
+        goto meta(context, C_bitonic_sort);
+    }
+    
+    sortArray->sortArray->d = 1 << (sortArray->sortArray->loop_counter - sortArray->sortArray->loop_counter2);
+    d = sortArray->sortArray->d;
+    
+    if (i < GET_SIZE(sortArray->sortArray->array)){
+        up = ((i >> sortArray->sortArray->loop_counter) & 2) == 0;
+        if ((i & d) == 0 && (sortArray->sortArray->array[i] > sortArray->sortArray->array[i | d]) == up) {//ここ入ってない
+            goto meta(context, C_swap);
+        }
+    }
+    
+    sortArray->sortArray->loop_counter2++;
+    goto meta(context, C_kernel);
+}
+
+__code swap(struct SortArray* sortArray){//配列の要素を入れ替える
+    int i = sortArray->sortArray->loop_counter3;
+    int d = sortArray->sortArray->d;
+    
+    struct Integer *tmp = sortArray->sortArray->array[i];
+    sortArray->sortArray->array[i] = sortArray->sortArray->array[i | d];
+    sortArray->sortArray->array[i | d] = tmp;
+    
+    sortArray->sortArray->loop_counter3++;
+    goto meta(context, C_kernel);//上位のループへ
+}