Mercurial > hg > Members > kono > Cerium
diff example/many_task/sort.cc @ 227:d54cbfafcb82
add sort
author | gongo@localhost.localdomain |
---|---|
date | Wed, 11 Feb 2009 11:09:39 +0900 |
parents | |
children | 2b114977852d |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/example/many_task/sort.cc Wed Feb 11 11:09:39 2009 +0900 @@ -0,0 +1,174 @@ +#include <stdlib.h> +#include "TaskManager.h" +#include "sort.h" +#include "Func.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_restart(void *); +static void sort_start(void); + + +/** + * set random seed + */ +static void +set_seed(void) +{ + FILE *fp; + unsigned int seed; + + if ((fp = fopen("/dev/random", "r")) == NULL) { + seed = 12345; + goto FINISH; + } + + fread(&seed, sizeof(unsigned int), 1, fp); + fclose(fp); + +FINISH: + srandom(seed); +} + +/** + * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような + * len の分割数を返す + * + * @param len sort する data の総数 + * @param num 使用する SPE の数 + * + * @return data の分割数 + * + * TODO: + * len が num 以下とか考えてません + */ +static int +get_split_num(int len, int num) +{ + if (len / num < MAX_BLOCK_SIZE) { + return num; + } else { + // 切り上げ + return (len + MAX_BLOCK_SIZE - 1) / MAX_BLOCK_SIZE; + } +} + +/** + * btask が全て終了したら、再び sort_start を実行する + * @param d 生成された btask の数 + */ +static void +sort_restart(void *d) +{ + static int cnt = 0; + int max = (int)d; + + if (++cnt == max) { + cnt = 0; + sort_start(); + } +} + +static void +sort_start(void) +{ + if (--sort_count < 0) { + 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]->add_param(block_num); + fsort[i]->add_param(i*block_num); + fsort[i]->set_cpu(SPE_ANY); + } + + // 最後の block は端数なので last_block_num を使う + { + int i = split_num-1; + + fsort[i] = manager->create_task(QUICK_SORT); + 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]->add_param(last_block_num); + fsort[i]->add_param(i*block_num); + 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); + bsort[i]->add_inData(&data[i*block_num+half_block_num], + sizeof(Data)*block_num); + bsort[i]->add_outData(&data[i*block_num+half_block_num], + sizeof(Data)*block_num); + bsort[i]->add_param(block_num); + bsort[i]->add_param(i*block_num + half_block_num); + bsort[i]->set_cpu(SPE_ANY); + } + + { + int i = half_num-1; + + bsort[i] = manager->create_task(QUICK_SORT); + bsort[i]->add_inData(&data[i*block_num+half_block_num], + sizeof(Data)*last_half_block_num); + bsort[i]->add_outData(&data[i*block_num+half_block_num], + sizeof(Data)*last_half_block_num); + bsort[i]->add_param(last_half_block_num); + bsort[i]->add_param(i*block_num + 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]->set_post(sort_restart, (void*)(half_num)); + bsort[i]->spawn(); + } + } + + for (int i = 0; i < split_num; i++) { + fsort[i]->spawn(); + } +} + +void +sort_init(int cpuNum, int length) +{ + data = (DataPtr)manager->allocate(sizeof(Data)*length); + data_length = length; + + set_seed(); + + for (int i = 0; i < length; i++) { + data[i].index = random()%10000; + data[i].ptr = 0; + } + + 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(); +}