changeset 934:da657af64afd

sort fix ( not working now )
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 31 Jul 2010 02:45:21 +0900
parents 736c03c301d4
children e54842e4d97b
files example/many_task/README example/many_task/main.cc example/many_task/ppe/QuickSort.cc example/many_task/sort.cc example/many_task/spe/QuickSort.cc
diffstat 5 files changed, 205 insertions(+), 40 deletions(-) [+]
line wrap: on
line diff
--- a/example/many_task/README	Sat Jul 31 00:58:20 2010 +0900
+++ b/example/many_task/README	Sat Jul 31 02:45:21 2010 +0900
@@ -1,3 +1,20 @@
+2010/7/31 kono
+
+bitoinc sort の一段落を待って、次のtaskを生成する方法だと、
+並列度が、
+
+    /\/\/\/\/\/\/\/\
+    \/\/\/\/\/\/\/\/
+
+と言う形になってしまう。全部、いっぺんに生成するのが楽だが、
+sort が大きい時に task の数が大きくなりすぎる。
+
+安直に、wait_for すると、そのtaskが既に終っていることがある。
+もっとひどいことに、別なtaskを待ってしまう可能性もある。
+これは、防ごうと思えば防げるが...
+
+自分で明示的にtaskを解放する方式にすると言う手もあるが...
+
 /**
  * $Id: README,v 1.1 2008/10/20 10:19:31 gongo Exp $
  */
--- a/example/many_task/main.cc	Sat Jul 31 00:58:20 2010 +0900
+++ b/example/many_task/main.cc	Sat Jul 31 02:45:21 2010 +0900
@@ -90,11 +90,14 @@
     return 0;
 }
 
+extern void check_data();
+
 void
 TMend(TaskManager *manager)
 {
     ed_time = getTime();
     //show_data();
+    check_data();
     printf("Time: %0.6f\n",ed_time-st_time);
 }
 
--- a/example/many_task/ppe/QuickSort.cc	Sat Jul 31 00:58:20 2010 +0900
+++ b/example/many_task/ppe/QuickSort.cc	Sat Jul 31 02:45:21 2010 +0900
@@ -5,14 +5,17 @@
 SchedDefineTask(QuickSort);
 
 static void quick_sort( Data *data, int begin, int end ) ;
+
 static void
 swap( Data *data, int left, int right )
 {
-    int tmp	      = data[left].index;
-    data[left].index  = data[right].index;
-    data[right].index = tmp;
+    Data tmp	      = data[left];
+    data[left]  = data[right];
+    data[right] = tmp;
 }
 
+// #define USE_MEMCPY
+
 static int
 run(SchedTask *s, void* rbuff, void* wbuff) {
     // copy value
@@ -20,12 +23,15 @@
 #if USE_SIMPLE_TASK
     long end = s->read_size()/sizeof(Data);
     Data *r_data = (Data*)rbuff;
-#if MEMCPY
+#ifdef USE_MEMCPY
     Data *w_data = (Data*)wbuff;
 #endif
 #else
     int end   = (long)s->get_param(0);
     DataPtr r_data = (DataPtr)s->get_input(0);
+#ifdef USE_MEMCPY
+    DataPtr w_data = (DataPtr)s->get_output(0);
+#endif
 #endif
 
     //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
@@ -33,7 +39,7 @@
 
     //show_data(r_data, end);
     quick_sort(r_data, begin, end-1);
-#if MEMCPY
+#ifdef USE_MEMCPY
     memcpy(w_data, r_data, sizeof(Data)*end);
 #else
     s->swap();
--- a/example/many_task/sort.cc	Sat Jul 31 00:58:20 2010 +0900
+++ b/example/many_task/sort.cc	Sat Jul 31 02:45:21 2010 +0900
@@ -2,19 +2,14 @@
 #include "SchedTask.h"
 #include "sort.h"
 #include "Func.h"
+#include <string.h>
 
-DataPtr data; // sort array
-int data_length;
-static int sort_count; // sort 完了に必要な回数
-static int split_num; // data の分割数
-static int half_num;
-static int block_num; // 一つのタスクで sort する data 数
-static int last_block_num;
-static int half_block_num;
-static int last_half_block_num;
+static void sort_start(SchedTask *);
+extern void check_data();
 
-static void sort_restart(SchedTask *, void *, void *);
-static void sort_start(SchedTask *);
+static DataPtr data;
+static  int data_length;
+static  int cpuNum;
 
 /**
  * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような
@@ -39,6 +34,89 @@
     }
 }	
 
+
+HTaskPtr *fsort;
+HTaskPtr *bsort;
+
+#define ALL_TASK
+
+#ifdef ALL_TASK
+
+static void
+sort_start(SchedTask *manager)
+{
+    int split_num = get_split_num(data_length, cpuNum); // data の分割数
+    int half_num = split_num-1;
+    static int sort_count = split_num; // sort 完了に必要な回数
+
+    // 一つのタスクで sort する data 数
+    int block_num = (data_length + split_num -1)/split_num;
+    int half_block_num = block_num/2;
+
+    int last_block_num = data_length - (split_num-1)*block_num;
+    int last_half_block_num = half_block_num+(last_block_num/2);
+
+    while (--sort_count > 0)  {
+
+	for (int i = 0; i < split_num-1; i++) {
+	    fsort[i] = manager->create_task(QUICK_SORT,
+		(memaddr)&data[i*block_num], sizeof(Data)*block_num,
+		(memaddr)&data[i*block_num], sizeof(Data)*block_num);
+	    if (i>0 && bsort[i-1]) {
+		fsort[i]->wait_for(bsort[i-1]);
+	    }
+	    if (i<split_num-2 && bsort[i]) {
+		fsort[i]->wait_for(bsort[i]);
+	    }
+	    fsort[i]->set_cpu(SPE_ANY);
+	}
+
+	// 最後の block は端数なので last_block_num を使う
+	{
+	    int i = split_num-1;
+
+	    fsort[i] = manager->create_task(QUICK_SORT,
+		(memaddr)&data[i*block_num], sizeof(Data)*last_block_num,
+		(memaddr)&data[i*block_num], sizeof(Data)*last_block_num);
+	    if (i>0 && bsort[i-1]) {
+		fsort[i]->wait_for(bsort[i-1]);
+	    }
+	    fsort[i]->set_cpu(SPE_ANY);
+       }
+
+	if (split_num > 1) {
+
+	    for (int i = 0; i < half_num-1; i++) {
+		bsort[i] = manager->create_task(QUICK_SORT,
+		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num,
+		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num);
+		bsort[i]->set_cpu(SPE_ANY);
+	    }
+
+	    {
+		int i = half_num-1;
+
+		bsort[i] = manager->create_task(QUICK_SORT,
+		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
+		    (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
+		bsort[i]->set_cpu(SPE_ANY);	
+	    }
+	    
+	    for (int i = 0; i < half_num; i++) {
+		bsort[i]->wait_for(fsort[i]);
+		bsort[i]->wait_for(fsort[i+1]);
+		bsort[i]->spawn();
+	    }
+	}
+
+	for (int i = 0; i < split_num; i++) {
+	    fsort[i]->spawn();
+	}
+    }
+}
+
+#else
+
 /**
  * btask が全て終了したら、再び sort_start を実行する
  * @param d 生成された btask の数
@@ -47,31 +125,47 @@
 sort_restart(SchedTask *s, void *d, void *e)
 {
     static int cnt = 0;
-//    static int ccc = 0;
+    static int ccc = 0;
     long max = (long)d;
 
     if (++cnt == max) {	
+        printf("restarted %d %% %ld\n",ccc++,max);
 	cnt = 0;
-// printf("restarted %d\n",ccc++);
 	sort_start(s);
     }
 }
-
 #ifdef USE_SIMPLE_TASK
 
 static void
 sort_start(SchedTask *manager)
 {
+    int split_num = get_split_num(data_length, cpuNum); // data の分割数
+    int half_num = split_num-1;
+    static int sort_count = split_num; // sort 完了に必要な回数
+
+    // 一つのタスクで sort する data 数
+    int block_num = (data_length + split_num -1)/split_num;
+    int half_block_num = block_num/2;
+
+    int last_block_num = data_length - (split_num-1)*block_num;
+    int last_half_block_num = half_block_num+(last_block_num/2);
+
     if (--sort_count < 0) {
+	check_data();
 	return;
     }
 
-    HTaskPtr fsort[split_num];
 
     for (int i = 0; i < split_num-1; i++) {
 	fsort[i] = manager->create_task(QUICK_SORT,
 	    (memaddr)&data[i*block_num], sizeof(Data)*block_num,
 	    (memaddr)&data[i*block_num], sizeof(Data)*block_num);
+	if (i>0 && bsort[i-1]) {
+	    fsort[i]->wait_for(bsort[i-1]);
+	}
+	if (i<split_num-2 && bsort[i]) {
+	    fsort[i]->wait_for(bsort[i]);
+	}
 	fsort[i]->set_cpu(SPE_ANY);
     }
 
@@ -82,11 +176,13 @@
 	fsort[i] = manager->create_task(QUICK_SORT,
 	    (memaddr)&data[i*block_num], sizeof(Data)*last_block_num,
 	    (memaddr)&data[i*block_num], sizeof(Data)*last_block_num);
+	if (i>0 && bsort[i-1]) {
+	    fsort[i]->wait_for(bsort[i-1]);
+	}
 	fsort[i]->set_cpu(SPE_ANY);
    }
 
     if (split_num > 1) {
-	HTaskPtr bsort[half_num];
 
 	for (int i = 0; i < half_num-1; i++) {
 	    bsort[i] = manager->create_task(QUICK_SORT,
@@ -107,12 +203,12 @@
 	for (int i = 0; i < half_num; i++) {
 	    bsort[i]->wait_for(fsort[i]);
 	    bsort[i]->wait_for(fsort[i+1]);
-	    bsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
 	    bsort[i]->spawn();
 	}
     }
 
     for (int i = 0; i < split_num; i++) {
+	fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
 	fsort[i]->spawn();
     }
 }
@@ -122,17 +218,35 @@
 static void
 sort_start(SchedTask *manager)
 {
+    int split_num = get_split_num(data_length, cpuNum); // data の分割数
+    int half_num = split_num-1;
+    static int sort_count = split_num; // sort 完了に必要な回数
+
+    // 一つのタスクで sort する data 数
+    int block_num = (data_length + split_num -1)/split_num;
+    int half_block_num = block_num/2;
+
+    int last_block_num = data_length - (split_num-1)*block_num;
+    int last_half_block_num = half_block_num+(last_block_num/2);
+
+
     if (--sort_count < 0) {
+	check_data();
 	return;
     }
 
-    HTaskPtr fsort[split_num];
 
     for (int i = 0; i < split_num-1; i++) {
 	fsort[i] = manager->create_task(QUICK_SORT);
 	fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*block_num);
 	fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*block_num);
 	fsort[i]->set_param(0,(memaddr)block_num);
+	if (i>0 && bsort[i-1]) {
+	    fsort[i]->wait_for(bsort[i-1]);
+	}
+	if (i<split_num-2 && bsort[i]) {
+	    fsort[i]->wait_for(bsort[i]);
+	}
 	fsort[i]->set_cpu(SPE_ANY);
     }
 
@@ -144,6 +258,9 @@
 	fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*last_block_num);
 	fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*last_block_num);
 	fsort[i]->set_param(0,(memaddr)last_block_num);
+	if (i>0 && bsort[i-1]) {
+	    fsort[i]->wait_for(bsort[i-1]);
+	}
 	fsort[i]->set_cpu(SPE_ANY);
    }
 
@@ -175,41 +292,51 @@
 	for (int i = 0; i < half_num; i++) {
 	    bsort[i]->wait_for(fsort[i]);
 	    bsort[i]->wait_for(fsort[i+1]);
-	    bsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
 	    bsort[i]->spawn();
 	}
     }
 
     for (int i = 0; i < split_num; i++) {
+	fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager);
 	fsort[i]->spawn();
     }
 }
 #endif
+#endif
+
+void check_data()
+{
+    int flag = 1;
+    for(int i=0; i< data_length-1;i++) {
+	if (data[i].index>data[i+1].index)  {
+	    printf("Data are not sorted at %d. %d > %d \n",i, data[i].index,data[i+1].index);
+	    flag = 0;
+	    break;
+	}
+    }
+    if (flag) printf("Data are sorted\n");
+}
 
 void
 sort_init(SchedTask *manager, void *a, void *b)
 {
-    int cpuNum = (int)a;
+    cpuNum = (int)a;
     int length = (int)b;
 
     data = (DataPtr)manager->allocate(sizeof(Data)*length);
     data_length = length;
 
+    int split_num = get_split_num(data_length, cpuNum); // data の分割数
+    int half_num = split_num-1;
+    fsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*split_num);
+    bsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*half_num);
+    memset((void*)bsort,0, sizeof(HTaskPtr)*half_num);
+
     for (int i = 0; i < length; i++) { 
         data[i].index = manager->get_random()%10000;
-        data[i].ptr   = 0;
+        data[i].ptr   = i;
     }
 
-    split_num = get_split_num(length, cpuNum);
-    half_num = split_num-1;
-    sort_count = split_num;
-
-    block_num = (length + split_num -1)/split_num;
-    half_block_num = block_num/2;
-
-    last_block_num = length - (split_num-1)*block_num;
-    last_half_block_num = half_block_num+(last_block_num/2);
-
     sort_start(manager);
 }
 
--- a/example/many_task/spe/QuickSort.cc	Sat Jul 31 00:58:20 2010 +0900
+++ b/example/many_task/spe/QuickSort.cc	Sat Jul 31 02:45:21 2010 +0900
@@ -5,14 +5,17 @@
 SchedDefineTask(QuickSort);
 
 static void quick_sort( Data *data, int begin, int end ) ;
+
 static void
 swap( Data *data, int left, int right )
 {
-    int tmp	      = data[left].index;
-    data[left].index  = data[right].index;
-    data[right].index = tmp;
+    Data tmp	      = data[left];
+    data[left]  = data[right];
+    data[right] = tmp;
 }
 
+// #define USE_MEMCPY
+
 static int
 run(SchedTask *s, void* rbuff, void* wbuff) {
     // copy value
@@ -20,9 +23,15 @@
 #if USE_SIMPLE_TASK
     long end = s->read_size()/sizeof(Data);
     Data *r_data = (Data*)rbuff;
+#ifdef USE_MEMCPY
+    Data *w_data = (Data*)wbuff;
+#endif
 #else
     int end   = (long)s->get_param(0);
     DataPtr r_data = (DataPtr)s->get_input(0);
+#ifdef USE_MEMCPY
+    DataPtr w_data = (DataPtr)s->get_output(0);
+#endif
 #endif
 
     //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
@@ -30,8 +39,11 @@
 
     //show_data(r_data, end);
     quick_sort(r_data, begin, end-1);
+#ifdef USE_MEMCPY
+    memcpy(w_data, r_data, sizeof(Data)*end);
+#else
     s->swap();
-    // memcpy(w_data, r_data, sizeof(Data)*end);
+#endif
 
     return 0;
 }