# HG changeset patch # User Shinji KONO # Date 1280511921 -32400 # Node ID da657af64afd89522a086a02843e5f5586229937 # Parent 736c03c301d40f7a165ce180f98f30361829e595 sort fix ( not working now ) diff -r 736c03c301d4 -r da657af64afd example/many_task/README --- 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 $ */ diff -r 736c03c301d4 -r da657af64afd example/many_task/main.cc --- 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); } diff -r 736c03c301d4 -r da657af64afd example/many_task/ppe/QuickSort.cc --- 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(); diff -r 736c03c301d4 -r da657af64afd example/many_task/sort.cc --- 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 -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 (iwait_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 (iwait_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 (iwait_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); } diff -r 736c03c301d4 -r da657af64afd example/many_task/spe/QuickSort.cc --- 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; }