Mercurial > hg > Members > kono > Cerium

changeset 227:d54cbfafcb82

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add sort
author gongo@localhost.localdomain
date Wed, 11 Feb 2009 11:09:39 +0900
parents 0f80d90fe40a
children c254a2bd1b34
files TaskManager/Test/test_render/Camera.cpp example/many_task/main.cc example/many_task/sort.cc example/many_task/sort.h
diffstat 4 files changed, 185 insertions(+), 24 deletions(-) [+]
line wrap: on
line diff
--- a/TaskManager/Test/test_render/Camera.cpp	Wed Feb 11 11:02:45 2009 +0900
+++ b/TaskManager/Test/test_render/Camera.cpp	Wed Feb 11 11:09:39 2009 +0900
@@ -62,7 +62,7 @@
  */
 Camera::Camera(float w, float h)
 {
-    name = (const char*)"Camera";
+    name = (char*)"Camera";
 
 
     fov  = 60.0f;
--- a/example/many_task/main.cc	Wed Feb 11 11:02:45 2009 +0900
+++ b/example/many_task/main.cc	Wed Feb 11 11:09:39 2009 +0900
@@ -5,9 +5,6 @@
 #include "TaskManager.h"
 #include "Func.h"
 #include "sort.h"
-#include "prof.h"
-
-//#define DEBUG_CHECK
 
 extern void task_init(void);
 
@@ -35,17 +32,11 @@
 static void
 show_data(void)
 {
-#if defined(DEBUG_CHECK)
-    for(int i = 0; i < data_length; i++) {
-	printf("%d\n", data[i].index);
-    }
-#else
     puts("-----------------------------------------------");
     for(int i = 0; i < data_length; i++) {
 	printf("data[%02d].index = %d\n", i, data[i].index);
     }
     puts("-----------------------------------------------");
-#endif
 }
 
 const char *help_str = "Usage: ./sort [option]\n \
@@ -86,11 +77,10 @@
     sort_init(manager->get_cpuNum(), length);
 
     st_time = getTime();
-    //StartProf(ts);
 
+    // 全ての Task が終了した後に実行する関数をセット
     manager->set_TMend(TMend);
 
-
     return 0;
 }
 
@@ -98,17 +88,6 @@
 TMend(void)
 {
     ed_time = getTime();
-    //show_data();
-#if !defined(DEBUG_CHECK)
-    //StopProf(te, ts);
-
-    //unsigned tmps, tmpe;
-    
-    // profile のコスト計算
-    //StartProf(tmps);
-    //StopProf(tmpe, tmps);
- 
-    //PrintProf((te - tmpe));
+    show_data();
     printf("Time: %0.6f\n",ed_time-st_time);
-#endif
 }
--- /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();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/many_task/sort.h	Wed Feb 11 11:09:39 2009 +0900
@@ -0,0 +1,8 @@
+// array position
+typedef struct Data {
+    int index;
+    int ptr;
+    int pad[2];
+} Data, *DataPtr;
+
+#define MAX_BLOCK_SIZE (int)(1024*16/(sizeof(Data)))