[257] | 1 | /////////////////////////////////////////////////////////////////////////////// |
---|
[295] | 2 | // File : main.c |
---|
| 3 | // Date : November 2013 |
---|
| 4 | // Author : Cesar Fuguet Tortolero <cesar.fuguet-tortolero@lip6.fr> |
---|
[256] | 5 | // |
---|
[257] | 6 | // Description : |
---|
| 7 | // |
---|
| 8 | // Sort application using the GIET-VM OS. This application uses the |
---|
| 9 | // barrier routines to apply a sort algorithm in several stages. |
---|
| 10 | // |
---|
[502] | 11 | // Constraints : |
---|
[257] | 12 | // |
---|
[502] | 13 | // - It supports up to 1024 processors and the number of processors |
---|
| 14 | // must be a power of 2. |
---|
[257] | 15 | // |
---|
[502] | 16 | // _ The array of values to be sorted (ARRAY_LENGTH) must be power of 2 |
---|
| 17 | // larger than the number of processors. |
---|
[257] | 18 | // |
---|
[502] | 19 | // - This application must be executed on a cache coherent architecture. |
---|
[257] | 20 | // |
---|
| 21 | /////////////////////////////////////////////////////////////////////////////// |
---|
[256] | 22 | |
---|
| 23 | #include "stdio.h" |
---|
[292] | 24 | #include "mapping_info.h" |
---|
[256] | 25 | #include "hard_config.h" |
---|
[502] | 26 | #include "user_barrier.h" |
---|
[256] | 27 | |
---|
[515] | 28 | #define ARRAY_LENGTH 0x1000 |
---|
[502] | 29 | #define IPT (ARRAY_LENGTH / threads) // ITEMS PER THREAD |
---|
[257] | 30 | |
---|
| 31 | //////////////////////////////////////////////////////////////////////////////// |
---|
[502] | 32 | // Processors other than 0 display algorithm state if VERBOSE non zero |
---|
[257] | 33 | |
---|
[256] | 34 | #define VERBOSE 1 |
---|
| 35 | |
---|
[295] | 36 | //////////////////////////////////////////////////////////////////////////////// |
---|
[502] | 37 | // Define printf according to verbosity option and number of available TTY |
---|
[257] | 38 | |
---|
[256] | 39 | #if (VERBOSE == 1) |
---|
[295] | 40 | # define printf(...) giet_shr_printf(__VA_ARGS__) |
---|
[318] | 41 | #else |
---|
[257] | 42 | # define printf(...) |
---|
[256] | 43 | #endif |
---|
| 44 | |
---|
[295] | 45 | #define task0_printf(...) if(thread_id == 0) giet_shr_printf(__VA_ARGS__) |
---|
[257] | 46 | |
---|
[256] | 47 | int array0[ARRAY_LENGTH]; |
---|
| 48 | int array1[ARRAY_LENGTH]; |
---|
| 49 | |
---|
[345] | 50 | volatile int init_ok = 0; |
---|
[256] | 51 | |
---|
| 52 | void bubbleSort( |
---|
| 53 | int * array, |
---|
| 54 | unsigned int length, |
---|
| 55 | unsigned int init_pos); |
---|
| 56 | |
---|
| 57 | void merge( |
---|
| 58 | int * array, |
---|
| 59 | int * result, |
---|
| 60 | int length, |
---|
| 61 | int init_pos_a, |
---|
| 62 | int init_pos_b, |
---|
| 63 | int init_pos_result); |
---|
| 64 | |
---|
[502] | 65 | /////////////////////////////////////////////////////// |
---|
| 66 | // This application supports at most 1024 processors |
---|
| 67 | // Number of barriers = log2(threads) |
---|
[257] | 68 | |
---|
[502] | 69 | giet_barrier_t barrier[10]; |
---|
[256] | 70 | |
---|
[295] | 71 | ////////////////////////////////////////// |
---|
[256] | 72 | __attribute__ ((constructor)) void sort() |
---|
| 73 | { |
---|
[269] | 74 | int thread_id = giet_thread_id(); |
---|
[381] | 75 | int * src_array = NULL; |
---|
| 76 | int * dst_array = NULL; |
---|
[256] | 77 | int i; |
---|
[292] | 78 | |
---|
| 79 | unsigned int time_start = giet_proctime(); |
---|
| 80 | unsigned int time_end; |
---|
[256] | 81 | |
---|
[502] | 82 | // compute number of threads (one thread per proc) |
---|
| 83 | unsigned int x_size; |
---|
| 84 | unsigned int y_size; |
---|
| 85 | unsigned int nprocs; |
---|
| 86 | unsigned int threads; |
---|
[515] | 87 | |
---|
[502] | 88 | giet_procs_number( &x_size , &y_size , &nprocs ); |
---|
| 89 | threads = x_size * y_size * nprocs; |
---|
[256] | 90 | |
---|
[502] | 91 | if ( (threads != 1) && (threads != 2) && (threads != 4) && |
---|
| 92 | (threads != 8) && (threads != 16 ) && (threads != 32) && |
---|
| 93 | (threads != 64) && (threads != 128) && (threads != 256) && |
---|
| 94 | (threads != 512) && (threads != 1024) ) |
---|
| 95 | { |
---|
| 96 | task0_printf("[SORT ERROR] Number of processors must be power of 2\n" |
---|
| 97 | " x_size = %d / y_size = %d / nprocs = %d\n", |
---|
| 98 | x_size , y_size , nprocs ); |
---|
| 99 | giet_exit("error"); |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | task0_printf("\n[ Thread 0 ] Starting sort application with %d threads " |
---|
| 103 | "at cycle %d\n", threads, time_start); |
---|
| 104 | |
---|
[269] | 105 | /////////////////////////// |
---|
| 106 | // Barriers Initialization |
---|
[256] | 107 | |
---|
[292] | 108 | if (thread_id == 0) |
---|
[256] | 109 | { |
---|
[502] | 110 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[292] | 111 | { |
---|
[502] | 112 | barrier_init(&barrier[i], threads >> i); |
---|
[292] | 113 | } |
---|
| 114 | |
---|
| 115 | init_ok = 1; |
---|
[256] | 116 | } |
---|
[292] | 117 | else |
---|
| 118 | { |
---|
| 119 | while(!init_ok); |
---|
| 120 | } |
---|
[256] | 121 | |
---|
[269] | 122 | //////////////////////// |
---|
| 123 | // Array Initialization |
---|
[256] | 124 | |
---|
[271] | 125 | for (i = IPT * thread_id; i < IPT * (thread_id + 1); i++) |
---|
[256] | 126 | { |
---|
[502] | 127 | array0[i] = giet_rand(); |
---|
[256] | 128 | } |
---|
| 129 | |
---|
[257] | 130 | /////////////////////////////////// |
---|
| 131 | // Parallel sort of array elements |
---|
[256] | 132 | |
---|
[295] | 133 | printf("[ Thread %d ] Stage 0: Sorting...\n\r", thread_id); |
---|
[257] | 134 | |
---|
[271] | 135 | bubbleSort(array0, IPT, IPT * thread_id); |
---|
[256] | 136 | |
---|
[269] | 137 | printf("[ Thread %d ] Finishing Stage 0\n\r", thread_id); |
---|
[257] | 138 | |
---|
[502] | 139 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[256] | 140 | { |
---|
| 141 | barrier_wait(&barrier[i]); |
---|
| 142 | |
---|
[269] | 143 | if((thread_id % (2 << i)) != 0) |
---|
| 144 | { |
---|
[295] | 145 | printf("[ Thread %d ] Quit\n\r", thread_id ); |
---|
[502] | 146 | giet_exit("Completed"); |
---|
[269] | 147 | } |
---|
[257] | 148 | |
---|
[295] | 149 | printf("[ Thread %d ] Stage %d: Sorting...\n\r", thread_id, i+1); |
---|
[256] | 150 | |
---|
| 151 | if((i % 2) == 0) |
---|
| 152 | { |
---|
| 153 | src_array = &array0[0]; |
---|
| 154 | dst_array = &array1[0]; |
---|
| 155 | } |
---|
| 156 | else |
---|
| 157 | { |
---|
| 158 | src_array = &array1[0]; |
---|
| 159 | dst_array = &array0[0]; |
---|
| 160 | } |
---|
| 161 | |
---|
| 162 | merge(src_array, dst_array |
---|
[271] | 163 | , IPT << i |
---|
| 164 | , IPT * thread_id |
---|
| 165 | , IPT * (thread_id + (1 << i)) |
---|
| 166 | , IPT * thread_id |
---|
[256] | 167 | ); |
---|
| 168 | |
---|
[269] | 169 | printf("[ Thread %d ] Finishing Stage %d\n\r", thread_id, i + 1); |
---|
[256] | 170 | } |
---|
| 171 | |
---|
| 172 | int success; |
---|
| 173 | int failure_index; |
---|
| 174 | |
---|
[257] | 175 | ////////////////////////////// |
---|
| 176 | // Verify the resulting array |
---|
[345] | 177 | |
---|
| 178 | if(thread_id != 0) |
---|
| 179 | { |
---|
[502] | 180 | giet_exit("error: only thread 0 should get here"); |
---|
[345] | 181 | } |
---|
[257] | 182 | |
---|
[345] | 183 | success = 1; |
---|
| 184 | for(i=0; i<(ARRAY_LENGTH-1); i++) |
---|
[256] | 185 | { |
---|
[345] | 186 | if(dst_array[i] > dst_array[i+1]) |
---|
[256] | 187 | { |
---|
| 188 | |
---|
[345] | 189 | success = 0; |
---|
| 190 | failure_index = i; |
---|
| 191 | break; |
---|
[256] | 192 | } |
---|
[345] | 193 | } |
---|
[256] | 194 | |
---|
[345] | 195 | time_end = giet_proctime(); |
---|
[295] | 196 | |
---|
[345] | 197 | printf("[ Thread 0 ] Finishing sort application at cycle %d\n" |
---|
| 198 | "[ Thread 0 ] Time elapsed = %d\n", |
---|
| 199 | time_end, (time_end - time_start) ); |
---|
[292] | 200 | |
---|
[345] | 201 | if (success) |
---|
| 202 | { |
---|
[502] | 203 | giet_exit("!!! Success !!!"); |
---|
[345] | 204 | } |
---|
| 205 | else |
---|
| 206 | { |
---|
| 207 | printf("[ Thread 0 ] Failure!! Incorrect element: %d\n\r", |
---|
| 208 | failure_index); |
---|
| 209 | for(i=0; i<ARRAY_LENGTH; i++) |
---|
[256] | 210 | { |
---|
[345] | 211 | printf("array[%d] = %d\n", i, dst_array[i]); |
---|
[256] | 212 | } |
---|
[502] | 213 | giet_exit("!!! Failure !!!"); |
---|
[256] | 214 | } |
---|
[345] | 215 | |
---|
[502] | 216 | giet_exit("Completed"); |
---|
[256] | 217 | } |
---|
| 218 | |
---|
[295] | 219 | //////////////////////////////////// |
---|
| 220 | void bubbleSort( int * array, |
---|
| 221 | unsigned int length, |
---|
| 222 | unsigned int init_pos ) |
---|
[256] | 223 | { |
---|
| 224 | int i; |
---|
| 225 | int j; |
---|
| 226 | int aux; |
---|
| 227 | |
---|
| 228 | for(i = 0; i < length; i++) |
---|
| 229 | { |
---|
| 230 | for(j = init_pos; j < (init_pos + length - i - 1); j++) |
---|
| 231 | { |
---|
| 232 | if(array[j] > array[j + 1]) |
---|
| 233 | { |
---|
| 234 | aux = array[j + 1]; |
---|
| 235 | array[j + 1] = array[j]; |
---|
| 236 | array[j] = aux; |
---|
| 237 | } |
---|
| 238 | } |
---|
| 239 | } |
---|
| 240 | } |
---|
| 241 | |
---|
[295] | 242 | ///////////// |
---|
[256] | 243 | void merge( |
---|
| 244 | int * array, |
---|
| 245 | int * result, |
---|
| 246 | int length, |
---|
| 247 | int init_pos_a, |
---|
| 248 | int init_pos_b, |
---|
| 249 | int init_pos_result) |
---|
| 250 | { |
---|
| 251 | int i; |
---|
| 252 | int j; |
---|
| 253 | int k; |
---|
| 254 | |
---|
| 255 | i = 0; |
---|
| 256 | j = 0; |
---|
| 257 | k = init_pos_result; |
---|
| 258 | |
---|
| 259 | while((i < length) || (j < length)) |
---|
| 260 | { |
---|
| 261 | if((i < length) && (j < length)) |
---|
| 262 | { |
---|
| 263 | if(array[init_pos_a + i] < array[init_pos_b + j]) |
---|
| 264 | { |
---|
| 265 | result[k++] = array[init_pos_a + i]; |
---|
| 266 | i++; |
---|
| 267 | } |
---|
| 268 | else |
---|
| 269 | { |
---|
| 270 | result[k++] = array[init_pos_b + j]; |
---|
| 271 | j++; |
---|
| 272 | } |
---|
| 273 | } |
---|
| 274 | else if(i < length) |
---|
| 275 | { |
---|
| 276 | result[k++] = array[init_pos_a + i]; |
---|
| 277 | i++; |
---|
| 278 | } |
---|
| 279 | else |
---|
| 280 | { |
---|
| 281 | result[k++] = array[init_pos_b + j]; |
---|
| 282 | j++; |
---|
| 283 | } |
---|
| 284 | } |
---|
| 285 | } |
---|
| 286 | |
---|
| 287 | /* vim: tabstop=4 : shiftwidth=4 : expandtab |
---|
| 288 | */ |
---|