Mercurial > hg > Members > kono > Cerium

changeset 932:f4d7cf77ec3d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sort test (add swap())
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 31 Jul 2010 00:57:46 +0900
parents 35efda39c2d9
children 736c03c301d4
files TaskManager/ChangeLog TaskManager/kernel/ppe/TaskManager.h TaskManager/kernel/schedule/SchedTask.h TaskManager/kernel/schedule/SchedTaskArray.h example/many_task/Makefile.cell example/many_task/Makefile.def example/many_task/Makefile.linux example/many_task/Makefile.macosx example/many_task/main.cc example/many_task/ppe/QuickSort.cc example/many_task/sort.cc example/many_task/spe/QuickSort.cc
diffstat 12 files changed, 169 insertions(+), 90 deletions(-) [+]
line wrap: on
line diff
--- a/TaskManager/ChangeLog	Fri Jul 30 21:46:04 2010 +0900
+++ b/TaskManager/ChangeLog	Sat Jul 31 00:57:46 2010 +0900
@@ -1,6 +1,7 @@
 2010-7-30 Shinji KONO <kono@ie.u-ryukyu.ac.jp>
 
    TASK_LIST_MAIL でない方が高速なみたい
+   sort (many_task) が、とっても遅くなっている
 
 2010-7-24 Shinji KONO <kono@ie.u-ryukyu.ac.jp>
 
--- a/TaskManager/kernel/ppe/TaskManager.h	Fri Jul 30 21:46:04 2010 +0900
+++ b/TaskManager/kernel/ppe/TaskManager.h	Sat Jul 31 00:57:46 2010 +0900
@@ -34,6 +34,10 @@
     void start_profile() { m_impl->start_profile(); }
     void show_profile() { m_impl->show_profile(); }
 
+    SchedTask *get_schedTask() {
+	return m_impl->schedTaskManager;
+    }
+
     /* functions */
     void init();
     void finish();
--- a/TaskManager/kernel/schedule/SchedTask.h	Fri Jul 30 21:46:04 2010 +0900
+++ b/TaskManager/kernel/schedule/SchedTask.h	Sat Jul 31 00:57:46 2010 +0900
@@ -93,6 +93,18 @@
       return get_output(writebuf, index);
     }
 
+    /**
+     * swap read / write buffer
+     * output が read buffer の書き換えならば、memcpy せずに
+     * swap するだけで良い。size は同じである必要がある。
+     */
+    void swap() {
+	void * tmp = readbuf;
+	readbuf = writebuf;
+	writebuf = tmp;
+    }
+
+
     // user
     HTaskPtr create_task(int cmd);
     HTaskPtr create_task(int cmd, memaddr r, long rs, memaddr w, long ws);
--- a/TaskManager/kernel/schedule/SchedTaskArray.h	Fri Jul 30 21:46:04 2010 +0900
+++ b/TaskManager/kernel/schedule/SchedTaskArray.h	Sat Jul 31 00:57:46 2010 +0900
@@ -17,6 +17,7 @@
 
     virtual ~SchedTaskArray();
 
+
 private:
     /* variables */
 
--- a/example/many_task/Makefile.cell	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/Makefile.cell	Sat Jul 31 00:57:46 2010 +0900
@@ -1,7 +1,7 @@
 include ./Makefile.def
 
 SRCS_TMP = $(wildcard *.cc)
-SRCS_EXCLUDE =  # ե
+SRCS_EXCLUDE =   # ե
 SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
 OBJS = $(SRCS:.cc=.o)
 
--- a/example/many_task/Makefile.def	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/Makefile.def	Sat Jul 31 00:57:46 2010 +0900
@@ -6,10 +6,11 @@
 
 CERIUM = ../../../Cerium
 
-OPT = -O9
+OPT = -g -O9
 # OPT = -g
 CC      = g++
-CFLAGS  =  -Wall  $(OPT)
+CFLAGS  =  -DUSE_SIMPLE_TASK -Wall  $(OPT)
+# CFLAGS  =   -Wall  $(OPT)
 
 INCLUDE = -I${CERIUM}/include/TaskManager -I. -I..
 LIBS = -L${CERIUM}/TaskManager
--- a/example/many_task/Makefile.linux	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/Makefile.linux	Sat Jul 31 00:57:46 2010 +0900
@@ -1,7 +1,7 @@
 include ./Makefile.def
 
 SRCS_TMP = $(wildcard *.cc)
-SRCS_EXCLUDE =  # ե
+SRCS_EXCLUDE =   # ե
 SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
 OBJS = $(SRCS:.cc=.o)
 
@@ -12,7 +12,7 @@
 TASK_OBJS = $(TASK_SRCS:.cc=.o)
 
 CC      = g++
-CFLAGS  = -g -Wall# -O9 #-DDEBUG
+# CFLAGS  = -g -Wall# -O9 #-DDEBUG
 
 INCLUDE = -I${CERIUM}/include/TaskManager -I. -I..
 LIBS = -L${CERIUM}/TaskManager -lFifoManager
--- a/example/many_task/Makefile.macosx	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/Makefile.macosx	Sat Jul 31 00:57:46 2010 +0900
@@ -2,7 +2,7 @@
 
 
 SRCS_TMP = $(wildcard *.cc)
-SRCS_EXCLUDE =  # ե
+SRCS_EXCLUDE =   # ե
 SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
 OBJS = $(SRCS:.cc=.o)
 
@@ -14,7 +14,7 @@
 
 CC      = g++
 CC += -m32
-CFLAGS  = -g -Wall# -O9 #-DDEBUG
+# CFLAGS  = -g -Wall# -O9 #-DDEBUG
 
 INCLUDE = -I${CERIUM}/include/TaskManager -I. -I..
 LIBS = -L${CERIUM}/TaskManager -lFifoManager `sdl-config --libs`
--- a/example/many_task/main.cc	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/main.cc	Sat Jul 31 00:57:46 2010 +0900
@@ -70,13 +70,17 @@
 
     task_init();
 
-    HTask *dummy = manager->create_task(Dummy);
     int cpu  = manager->get_cpuNum();
 
     // in case of -cpu 0 
     if (cpu==0) cpu = 1;
-    dummy->set_post(sort_init, (void*)cpu, (void*)length);
-    dummy->spawn();
+    if (1) {
+	HTask *dummy = manager->create_task(Dummy);
+	dummy->set_post(sort_init, (void*)cpu, (void*)length);
+	dummy->spawn();
+    } else {
+	sort_init(manager->get_schedTask(),(void*)cpu, (void*)length);
+    }
 
     st_time = getTime();
 
--- a/example/many_task/ppe/QuickSort.cc	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/ppe/QuickSort.cc	Sat Jul 31 00:57:46 2010 +0900
@@ -5,23 +5,39 @@
 SchedDefineTask(QuickSort);
 
 static void quick_sort( Data *data, int begin, int end ) ;
-static void swap( Data *data, int left, int right );
+static void
+swap( Data *data, int left, int right )
+{
+    int tmp	      = data[left].index;
+    data[left].index  = data[right].index;
+    data[right].index = tmp;
+}
 
 static int
 run(SchedTask *s, void* rbuff, void* wbuff) {
     // copy value
     int begin	= 0;
-    long end = (long)s->get_param(0);
-
-    Data *r_data = (Data*)s->get_input(rbuff, 0);
-    Data *w_data = (Data*)s->get_output(wbuff, 0);
+#if USE_SIMPLE_TASK
+    long end = s->read_size()/sizeof(Data);
+    Data *r_data = (Data*)rbuff;
+#if MEMCPY
+    Data *w_data = (Data*)wbuff;
+#endif
+#else
+    int end   = (long)s->get_param(0);
+    DataPtr r_data = (DataPtr)s->get_input(0);
+#endif
 
     //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
     //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data); 
 
     //show_data(r_data, end);
     quick_sort(r_data, begin, end-1);
+#if MEMCPY
     memcpy(w_data, r_data, sizeof(Data)*end);
+#else
+    s->swap();
+#endif
 
     return 0;
 }
@@ -45,14 +61,9 @@
 	data[p].index = pivot;
 	
 	quick_sort(data, begin, p-1);
-	quick_sort(data, p+1, end);
+	quick_sort(data, p+1, end); // tail call
     }
 }
 
-static void
-swap( Data *data, int left, int right )
-{
-    int tmp	      = data[left].index;
-    data[left].index  = data[right].index;
-    data[right].index = tmp;
-}
+
+/* end */
--- a/example/many_task/sort.cc	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/sort.cc	Sat Jul 31 00:57:46 2010 +0900
@@ -57,6 +57,68 @@
     }
 }
 
+#ifdef USE_SIMPLE_TASK
+
+static void
+sort_start(SchedTask *manager)
+{
+    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,
+	    (memaddr)&data[i*block_num], sizeof(Data)*block_num,
+	    (memaddr)&data[i*block_num], sizeof(Data)*block_num);
+	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);
+	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,
+		(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]->set_post(sort_restart, (void*)(half_num),(void*)manager);
+	    bsort[i]->spawn();
+	}
+    }
+
+    for (int i = 0; i < split_num; i++) {
+	fsort[i]->spawn();
+    }
+}
+
+#else
+
 static void
 sort_start(SchedTask *manager)
 {
@@ -122,6 +184,7 @@
 	fsort[i]->spawn();
     }
 }
+#endif
 
 void
 sort_init(SchedTask *manager, void *a, void *b)
--- a/example/many_task/spe/QuickSort.cc	Fri Jul 30 21:46:04 2010 +0900
+++ b/example/many_task/spe/QuickSort.cc	Sat Jul 31 00:57:46 2010 +0900
@@ -1,81 +1,63 @@
 #include "QuickSort.h"
 #include <stdio.h>
 #include <string.h>
-#include "SpeProfile.h"
 
 SchedDefineTask(QuickSort);
 
-static void bubble_sort(DataPtr data, int begin, int end);
-static void quick_sort(DataPtr data, int begin, int end);
-
-static void swap(Data *data, int left, int right);
-
-static int
-run(SchedTask *smanager, void* rbuff, void* wbuff) {
-    int begin = 0;
-    int end   = (long)smanager->get_param(0);
-    DataPtr r_data = (DataPtr)smanager->get_input(0);
-    DataPtr w_data = (DataPtr)smanager->get_output(0);
-    //SpeProfile *prof = new SpeProfile;
-
-    //prof->ProfStart();
-    if (0) 
-	bubble_sort(r_data, begin, end-1);
-    else 
-	quick_sort(r_data, begin, end-1);
-    memcpy(w_data, r_data, sizeof(Data)*end);
-    //prof->ProfStop();
-    //prof->ProfPrint();
-
-    //delete prof;
-    return 0;
-}
-
+static void quick_sort( Data *data, int begin, int end ) ;
 static void
-bubble_sort(DataPtr data, int begin, int end)
-{
-    for (int i = 0; i < end; i++) {
-	for (int j = end; j > i; j--) {
-	    if (data[j].index < data[j-1].index) {
-		swap(data, j, j-1);
-	    }
-	}
-    }
-}
-
-
-static void
-quick_sort(DataPtr data, int begin, int end)
-{
-    if (begin < end) {
-
-	int where = (begin + end) / 2;
-	int pivot = data[where].index;
-	data[where].index = data[begin].index;
-	int p = begin;
-
-	for (int i = begin+1; i <= end; i++) {
-	    if (data[i].index < pivot) { 
-		p++; 
-		swap(data, p, i); 
-	    }
-	}
-
-	data[begin].index = data[p].index;
-	data[p].index = pivot;
-	
-	quick_sort(data, begin, p-1);
-	quick_sort(data, p+1, end);
-    }
-}
-
-
-static void
-swap(Data *data, int left, int right)
+swap( Data *data, int left, int right )
 {
     int tmp	      = data[left].index;
     data[left].index  = data[right].index;
     data[right].index = tmp;
 }
 
+static int
+run(SchedTask *s, void* rbuff, void* wbuff) {
+    // copy value
+    int begin	= 0;
+#if USE_SIMPLE_TASK
+    long end = s->read_size()/sizeof(Data);
+    Data *r_data = (Data*)rbuff;
+#else
+    int end   = (long)s->get_param(0);
+    DataPtr r_data = (DataPtr)s->get_input(0);
+#endif
+
+    //printf("[PPE] Quick: length:%d addr->%x \n",end, (int*)rbuff);
+    //printf("[PPE] Quick: data[0]: %d addr->%x\n",sizeof(r_data),r_data); 
+
+    //show_data(r_data, end);
+    quick_sort(r_data, begin, end-1);
+    s->swap();
+    // memcpy(w_data, r_data, sizeof(Data)*end);
+
+    return 0;
+}
+
+static void 
+quick_sort( Data *data, int begin, int end ) {
+
+    if (begin < end) {
+	int where = (begin + end) / 2;
+	int pivot = data[where].index;
+	data[where].index = data[begin].index;
+	int p = begin;
+	int i;
+	for (i=begin+1; i<=end; i++) {
+	    if (data[i].index < pivot) { 
+		p++; 
+		swap(data, p, i); 
+	    }
+	}
+	data[begin].index = data[p].index;
+	data[p].index = pivot;
+	
+	quick_sort(data, begin, p-1);
+	quick_sort(data, p+1, end); // tail call
+    }
+}
+
+
 /* end */