Mercurial > hg > Game > Cerium

annotate example/many_task/ppe/QuickSort.cc @ 1508:0e1318e7caed draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
create sort test
author Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
date Tue, 18 Sep 2012 18:59:54 +0900
parents 704b9e320f1e
children 18b63e697c61
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
1 #include "QuickSort.h"
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
2 #include <stdio.h>
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
3 #include <string.h>
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
4
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
5 SchedDefineTask(QuickSort);
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
6
467
839e34d0cc3c fix all examples. test_render is not working now.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 220
diff changeset
7 static void quick_sort( Data *data, int begin, int end ) ;
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
8
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
9 static void
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
10 swap( Data *data, int left, int right )
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
11 {
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
12 Data tmp = data[left];
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
13 data[left] = data[right];
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
14 data[right] = tmp;
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
15 }
467
839e34d0cc3c fix all examples. test_render is not working now.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 220
diff changeset
16
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
17 // #define USE_MEMCPY
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
18
467
839e34d0cc3c fix all examples. test_render is not working now.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 220
diff changeset
19 static int
839e34d0cc3c fix all examples. test_render is not working now.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 220
diff changeset
20 run(SchedTask *s, void* rbuff, void* wbuff) {
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
21 // copy value
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
22 int begin = 0;
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
23 #if USE_SIMPLE_TASK
936
178fbcc81fda dead lock on spu/ppu mail
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 934
diff changeset
24 int end = s->read_size()/sizeof(Data);
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
25 Data *r_data = (Data*)rbuff;
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
26 #ifdef USE_MEMCPY
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
27 Data *w_data = (Data*)wbuff;
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
28 #endif
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
29 #else
945
9ed1c4a877ca sort example fix ( simple task accepts one param and more compatible with old task)
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 940
diff changeset
30 int end = s->get_inputSize(0)/sizeof(Data);
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
31 DataPtr r_data = (DataPtr)s->get_input(0);
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
32 #ifdef USE_MEMCPY
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
33 DataPtr w_data = (DataPtr)s->get_output(0);
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
34 #endif
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
35 #endif
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
36
938
20beb83a5a22 dead lock still remains. zombi problem?
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 936
diff changeset
37 // printf("[PPE] Quick: length:%d addr->%x \n",end, (int)rbuff);
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
38 // printf("[PPE] Quick: data[0]: %ld addr->%lx\n",sizeof(r_data),(long)r_data);
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
39
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
40 quick_sort(r_data, begin, end-1);
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
41
934
83b64b7a51bd sort fix ( not working now )
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 932
diff changeset
42 #ifdef USE_MEMCPY
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
43 memcpy(w_data, r_data, sizeof(Data)*end);
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
44 #else
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
45 s->swap();
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
46 #endif
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
47
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
48 return 0;
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
49 }
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
50
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
51 void
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
52 qsort_test(Data *data, int begin, int end ) {
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
53 quick_sort(data, begin, end);
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
54 printf("end is %d\n",end);
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
55 }
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
56
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
57 static void
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
58 quick_sort(Data *data, int begin, int end ) {
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
59
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
60 if (begin < end) {
1508
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
61 int where = (begin + end) / 2;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
62 int pivot = data[where].index;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
63 data[where].index = data[begin].index;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
64 int p = begin;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
65 int i;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
66 for (i=begin+1; i<end; i++) {
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
67 if (data[i].index < pivot) {
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
68 p++;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
69 swap(data, p, i);
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
70 }
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
71 }
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
72 data[begin].index = data[p].index;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
73 data[p].index = pivot;
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
74
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
75 quick_sort(data, begin, p-1);
0e1318e7caed create sort test
Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
parents: 1080
diff changeset
76 quick_sort(data, p+1, end); // tail call
109
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
77 }
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
78 }
028ffc9c0375 Cerium cvs version
gongo@gendarme.local
parents:
diff changeset
79
932
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
80
53ad3a61b40b sort test (add swap())
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 625
diff changeset
81 /* end */