[626] | 1 | //================================================================================================= |
---|
| 2 | // File : main.c |
---|
| 3 | // |
---|
| 4 | // Date : 08/2011 |
---|
| 5 | // |
---|
| 6 | // Author : Cesar Fuguet Tortolero |
---|
| 7 | // :<cesar.fuguet-tortolero@lip6.fr> |
---|
| 8 | // |
---|
| 9 | // Description: Sort application using the GIET operating system. |
---|
| 10 | // This application uses the barrier routines to apply a sort algorithm |
---|
| 11 | // in several stages. |
---|
| 12 | //================================================================================================= |
---|
| 13 | |
---|
| 14 | #include "stdio.h" |
---|
| 15 | #include "hard_config.h" |
---|
| 16 | |
---|
| 17 | #define ARRAY_LENGTH (1 << 10) // 1024 ITEMS |
---|
| 18 | #define IPP (ARRAY_LENGTH / total_procs) // ITEMS PER PROCESSOR |
---|
| 19 | #define VERBOSE 1 |
---|
| 20 | |
---|
| 21 | #if (VERBOSE == 1) |
---|
| 22 | #define printf(...) _tty_printf(__VA_ARGS__) |
---|
| 23 | #define puts(...) _tty_puts(__VA_ARGS__) |
---|
| 24 | #else |
---|
| 25 | #define printf(...) |
---|
| 26 | #define puts(...) |
---|
| 27 | #endif |
---|
| 28 | |
---|
| 29 | #define task0_printf(...) if(thread_id == 0) _tty_printf(__VA_ARGS__) |
---|
| 30 | |
---|
| 31 | int array0[ARRAY_LENGTH]; |
---|
| 32 | int array1[ARRAY_LENGTH]; |
---|
| 33 | |
---|
| 34 | volatile int init_ok = 0; |
---|
| 35 | |
---|
| 36 | void bubbleSort(int * array, unsigned int length, unsigned int init_pos); |
---|
| 37 | void merge(int * array, int * result, int length, int init_pos_a, int init_pos_b, int init_pos_result); |
---|
| 38 | |
---|
| 39 | void main() |
---|
| 40 | { |
---|
| 41 | int total_procs = NB_PROCS_MAX * X_SIZE * Y_SIZE; |
---|
| 42 | int proc_id = _procid(); |
---|
| 43 | int lid = proc_id % NB_PROCS_MAX; |
---|
| 44 | int cluster_xy = proc_id / NB_PROCS_MAX; |
---|
| 45 | int x = (cluster_xy >> Y_WIDTH); |
---|
| 46 | int y = (cluster_xy ) & ((1 << Y_WIDTH) - 1); |
---|
| 47 | |
---|
| 48 | int thread_id = ((x * Y_SIZE) + y) * NB_PROCS_MAX + lid; |
---|
| 49 | |
---|
| 50 | int * src_array; |
---|
| 51 | int * dst_array; |
---|
| 52 | int i; |
---|
| 53 | |
---|
| 54 | while((thread_id != 0) && (init_ok == 0)); |
---|
| 55 | |
---|
| 56 | /**************************************************************************/ |
---|
| 57 | /* Hello World */ |
---|
| 58 | |
---|
[629] | 59 | task0_printf("\n[ PROC_%d_%d_%d ] Starting SORT application\n",x,y,lid); |
---|
[626] | 60 | |
---|
[629] | 61 | task0_printf("[ PROC_%d_%d_%d ] MESH %d x %d x %d processors\n", |
---|
| 62 | x,y,lid, X_SIZE, Y_SIZE, NB_PROCS_MAX); |
---|
[626] | 63 | |
---|
| 64 | /**************************************************************************/ |
---|
[629] | 65 | /* Barriers Initialisation */ |
---|
[626] | 66 | |
---|
| 67 | if (thread_id == 0) |
---|
| 68 | { |
---|
| 69 | for (i = 0; i < __builtin_ctz(total_procs); i++) |
---|
| 70 | { |
---|
[629] | 71 | printf("[ PROC_%d_%d_%d ] Initializing barrier %d with %d\n", |
---|
| 72 | x,y,lid, i, total_procs >> i); |
---|
[626] | 73 | |
---|
| 74 | _barrier_init(i, total_procs >> i); |
---|
| 75 | } |
---|
[629] | 76 | printf("\n"); |
---|
[626] | 77 | asm volatile ("sync"); |
---|
| 78 | init_ok = 1; |
---|
| 79 | } |
---|
| 80 | |
---|
| 81 | /**************************************************************************/ |
---|
[629] | 82 | /* Array Initialisation */ |
---|
[626] | 83 | |
---|
| 84 | for (i = IPP * thread_id; i < IPP * (thread_id + 1); i++) |
---|
| 85 | { |
---|
| 86 | array0[i] = _rand(); |
---|
| 87 | } |
---|
| 88 | |
---|
| 89 | asm volatile ("sync"); |
---|
| 90 | _barrier_wait(0); |
---|
| 91 | |
---|
| 92 | /**************************************************************************/ |
---|
| 93 | /* Parallel sorting of array pieces */ |
---|
| 94 | |
---|
[629] | 95 | printf("[ PROC_%d_%d_%d ] Stage 0: Starting...\n\r", x,y,lid); |
---|
[626] | 96 | bubbleSort(array0, IPP, IPP * thread_id); |
---|
[629] | 97 | printf("[ PROC_%d_%d_%d ] Stage 0: Finishing...\n\r", x,y,lid); |
---|
[626] | 98 | |
---|
| 99 | for (i = 0; i < __builtin_ctz(total_procs); i++) |
---|
| 100 | { |
---|
| 101 | asm volatile ("sync"); |
---|
| 102 | _barrier_wait(i); |
---|
| 103 | |
---|
| 104 | if((thread_id % (2 << i)) != 0) _exit(); |
---|
| 105 | |
---|
[629] | 106 | printf("[ PROC_%d_%d_%d ] Stage %d: Starting...\n\r", x,y,lid, i+1); |
---|
[626] | 107 | |
---|
| 108 | if((i % 2) == 0) |
---|
| 109 | { |
---|
| 110 | src_array = &array0[0]; |
---|
| 111 | dst_array = &array1[0]; |
---|
| 112 | } |
---|
| 113 | else |
---|
| 114 | { |
---|
| 115 | src_array = &array1[0]; |
---|
| 116 | dst_array = &array0[0]; |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | merge(src_array, dst_array |
---|
| 120 | , IPP << i |
---|
| 121 | , IPP * thread_id |
---|
| 122 | , IPP * (thread_id + (1 << i)) |
---|
| 123 | , IPP * thread_id |
---|
| 124 | ); |
---|
| 125 | |
---|
[629] | 126 | printf("[ PROC_%d_%d_%d ] Stage %d: Finishing...\n\r", x,y,lid, i+1); |
---|
[626] | 127 | } |
---|
| 128 | |
---|
| 129 | int success; |
---|
| 130 | int failure_index; |
---|
| 131 | |
---|
| 132 | if(thread_id == 0) |
---|
| 133 | { |
---|
| 134 | success = 1; |
---|
| 135 | |
---|
| 136 | for(i=0; i<(ARRAY_LENGTH-1); i++) |
---|
| 137 | { |
---|
| 138 | if(dst_array[i] > dst_array[i+1]) |
---|
| 139 | { |
---|
| 140 | |
---|
| 141 | success = 0; |
---|
| 142 | failure_index = i; |
---|
| 143 | break; |
---|
| 144 | } |
---|
| 145 | } |
---|
| 146 | |
---|
| 147 | if (success) |
---|
| 148 | { |
---|
[629] | 149 | printf("[ PROC_%d_%d_%d ] Success!!\n\r", x,y,lid); |
---|
[626] | 150 | } |
---|
| 151 | else |
---|
| 152 | { |
---|
| 153 | printf("Failure!! Incorrect element: %d\n\r", failure_index); |
---|
| 154 | |
---|
| 155 | |
---|
| 156 | for(i=0; i<ARRAY_LENGTH; i++) |
---|
| 157 | { |
---|
| 158 | printf("array[%d] = %d\n", i, dst_array[i]); |
---|
| 159 | } |
---|
| 160 | } |
---|
| 161 | } |
---|
| 162 | |
---|
| 163 | _exit(); |
---|
| 164 | } |
---|
| 165 | |
---|
| 166 | void bubbleSort(int * array, unsigned int length, unsigned int init_pos) |
---|
| 167 | { |
---|
| 168 | int i; |
---|
| 169 | int j; |
---|
| 170 | int aux; |
---|
| 171 | |
---|
| 172 | for(i = 0; i < length; i++) |
---|
| 173 | { |
---|
| 174 | for(j = init_pos; j < (init_pos + length - i - 1); j++) |
---|
| 175 | { |
---|
| 176 | if(array[j] > array[j + 1]) |
---|
| 177 | { |
---|
| 178 | aux = array[j + 1]; |
---|
| 179 | array[j + 1] = array[j]; |
---|
| 180 | array[j] = aux; |
---|
| 181 | } |
---|
| 182 | } |
---|
| 183 | } |
---|
| 184 | } |
---|
| 185 | |
---|
| 186 | void merge(int * array, int * result, int length, int init_pos_a, int init_pos_b, int init_pos_result) |
---|
| 187 | { |
---|
| 188 | int i; |
---|
| 189 | int j; |
---|
| 190 | int k; |
---|
| 191 | |
---|
| 192 | i = 0; |
---|
| 193 | j = 0; |
---|
| 194 | k = init_pos_result; |
---|
| 195 | |
---|
| 196 | while((i < length) || (j < length)) |
---|
| 197 | { |
---|
| 198 | if((i < length) && (j < length)) |
---|
| 199 | { |
---|
| 200 | if(array[init_pos_a + i] < array[init_pos_b + j]) |
---|
| 201 | { |
---|
| 202 | result[k++] = array[init_pos_a + i]; |
---|
| 203 | i++; |
---|
| 204 | } |
---|
| 205 | else |
---|
| 206 | { |
---|
| 207 | result[k++] = array[init_pos_b + j]; |
---|
| 208 | j++; |
---|
| 209 | } |
---|
| 210 | } |
---|
| 211 | else if(i < length) |
---|
| 212 | { |
---|
| 213 | result[k++] = array[init_pos_a + i]; |
---|
| 214 | i++; |
---|
| 215 | } |
---|
| 216 | else |
---|
| 217 | { |
---|
| 218 | result[k++] = array[init_pos_b + j]; |
---|
| 219 | j++; |
---|
| 220 | } |
---|
| 221 | } |
---|
| 222 | } |
---|
| 223 | |
---|
| 224 | /* vim: tabstop=4 : shiftwidth=4 : expandtab |
---|
| 225 | */ |
---|