[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 | |
---|
[502] | 28 | #define ARRAY_LENGTH 4096 |
---|
| 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; |
---|
| 87 | giet_procs_number( &x_size , &y_size , &nprocs ); |
---|
| 88 | threads = x_size * y_size * nprocs; |
---|
[256] | 89 | |
---|
[502] | 90 | if ( (threads != 1) && (threads != 2) && (threads != 4) && |
---|
| 91 | (threads != 8) && (threads != 16 ) && (threads != 32) && |
---|
| 92 | (threads != 64) && (threads != 128) && (threads != 256) && |
---|
| 93 | (threads != 512) && (threads != 1024) ) |
---|
| 94 | { |
---|
| 95 | task0_printf("[SORT ERROR] Number of processors must be power of 2\n" |
---|
| 96 | " x_size = %d / y_size = %d / nprocs = %d\n", |
---|
| 97 | x_size , y_size , nprocs ); |
---|
| 98 | giet_exit("error"); |
---|
| 99 | } |
---|
| 100 | |
---|
| 101 | task0_printf("\n[ Thread 0 ] Starting sort application with %d threads " |
---|
| 102 | "at cycle %d\n", threads, time_start); |
---|
| 103 | |
---|
[269] | 104 | /////////////////////////// |
---|
| 105 | // Barriers Initialization |
---|
[256] | 106 | |
---|
[292] | 107 | if (thread_id == 0) |
---|
[256] | 108 | { |
---|
[502] | 109 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[292] | 110 | { |
---|
[502] | 111 | barrier_init(&barrier[i], threads >> i); |
---|
[292] | 112 | } |
---|
| 113 | |
---|
| 114 | init_ok = 1; |
---|
[256] | 115 | } |
---|
[292] | 116 | else |
---|
| 117 | { |
---|
| 118 | while(!init_ok); |
---|
| 119 | } |
---|
[256] | 120 | |
---|
[269] | 121 | //////////////////////// |
---|
| 122 | // Array Initialization |
---|
[256] | 123 | |
---|
[271] | 124 | for (i = IPT * thread_id; i < IPT * (thread_id + 1); i++) |
---|
[256] | 125 | { |
---|
[502] | 126 | array0[i] = giet_rand(); |
---|
[256] | 127 | } |
---|
| 128 | |
---|
[257] | 129 | /////////////////////////////////// |
---|
| 130 | // Parallel sort of array elements |
---|
[256] | 131 | |
---|
[295] | 132 | printf("[ Thread %d ] Stage 0: Sorting...\n\r", thread_id); |
---|
[257] | 133 | |
---|
[271] | 134 | bubbleSort(array0, IPT, IPT * thread_id); |
---|
[256] | 135 | |
---|
[269] | 136 | printf("[ Thread %d ] Finishing Stage 0\n\r", thread_id); |
---|
[257] | 137 | |
---|
[502] | 138 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[256] | 139 | { |
---|
| 140 | barrier_wait(&barrier[i]); |
---|
| 141 | |
---|
[269] | 142 | if((thread_id % (2 << i)) != 0) |
---|
| 143 | { |
---|
[295] | 144 | printf("[ Thread %d ] Quit\n\r", thread_id ); |
---|
[502] | 145 | giet_exit("Completed"); |
---|
[269] | 146 | } |
---|
[257] | 147 | |
---|
[295] | 148 | printf("[ Thread %d ] Stage %d: Sorting...\n\r", thread_id, i+1); |
---|
[256] | 149 | |
---|
| 150 | if((i % 2) == 0) |
---|
| 151 | { |
---|
| 152 | src_array = &array0[0]; |
---|
| 153 | dst_array = &array1[0]; |
---|
| 154 | } |
---|
| 155 | else |
---|
| 156 | { |
---|
| 157 | src_array = &array1[0]; |
---|
| 158 | dst_array = &array0[0]; |
---|
| 159 | } |
---|
| 160 | |
---|
| 161 | merge(src_array, dst_array |
---|
[271] | 162 | , IPT << i |
---|
| 163 | , IPT * thread_id |
---|
| 164 | , IPT * (thread_id + (1 << i)) |
---|
| 165 | , IPT * thread_id |
---|
[256] | 166 | ); |
---|
| 167 | |
---|
[269] | 168 | printf("[ Thread %d ] Finishing Stage %d\n\r", thread_id, i + 1); |
---|
[256] | 169 | } |
---|
| 170 | |
---|
| 171 | int success; |
---|
| 172 | int failure_index; |
---|
| 173 | |
---|
[257] | 174 | ////////////////////////////// |
---|
| 175 | // Verify the resulting array |
---|
[345] | 176 | |
---|
| 177 | if(thread_id != 0) |
---|
| 178 | { |
---|
[502] | 179 | giet_exit("error: only thread 0 should get here"); |
---|
[345] | 180 | } |
---|
[257] | 181 | |
---|
[345] | 182 | success = 1; |
---|
| 183 | for(i=0; i<(ARRAY_LENGTH-1); i++) |
---|
[256] | 184 | { |
---|
[345] | 185 | if(dst_array[i] > dst_array[i+1]) |
---|
[256] | 186 | { |
---|
| 187 | |
---|
[345] | 188 | success = 0; |
---|
| 189 | failure_index = i; |
---|
| 190 | break; |
---|
[256] | 191 | } |
---|
[345] | 192 | } |
---|
[256] | 193 | |
---|
[345] | 194 | time_end = giet_proctime(); |
---|
[295] | 195 | |
---|
[345] | 196 | printf("[ Thread 0 ] Finishing sort application at cycle %d\n" |
---|
| 197 | "[ Thread 0 ] Time elapsed = %d\n", |
---|
| 198 | time_end, (time_end - time_start) ); |
---|
[292] | 199 | |
---|
[345] | 200 | if (success) |
---|
| 201 | { |
---|
[502] | 202 | giet_exit("!!! Success !!!"); |
---|
[345] | 203 | } |
---|
| 204 | else |
---|
| 205 | { |
---|
| 206 | printf("[ Thread 0 ] Failure!! Incorrect element: %d\n\r", |
---|
| 207 | failure_index); |
---|
| 208 | for(i=0; i<ARRAY_LENGTH; i++) |
---|
[256] | 209 | { |
---|
[345] | 210 | printf("array[%d] = %d\n", i, dst_array[i]); |
---|
[256] | 211 | } |
---|
[502] | 212 | giet_exit("!!! Failure !!!"); |
---|
[256] | 213 | } |
---|
[345] | 214 | |
---|
[502] | 215 | giet_exit("Completed"); |
---|
[256] | 216 | } |
---|
| 217 | |
---|
[295] | 218 | //////////////////////////////////// |
---|
| 219 | void bubbleSort( int * array, |
---|
| 220 | unsigned int length, |
---|
| 221 | unsigned int init_pos ) |
---|
[256] | 222 | { |
---|
| 223 | int i; |
---|
| 224 | int j; |
---|
| 225 | int aux; |
---|
| 226 | |
---|
| 227 | for(i = 0; i < length; i++) |
---|
| 228 | { |
---|
| 229 | for(j = init_pos; j < (init_pos + length - i - 1); j++) |
---|
| 230 | { |
---|
| 231 | if(array[j] > array[j + 1]) |
---|
| 232 | { |
---|
| 233 | aux = array[j + 1]; |
---|
| 234 | array[j + 1] = array[j]; |
---|
| 235 | array[j] = aux; |
---|
| 236 | } |
---|
| 237 | } |
---|
| 238 | } |
---|
| 239 | } |
---|
| 240 | |
---|
[295] | 241 | ///////////// |
---|
[256] | 242 | void merge( |
---|
| 243 | int * array, |
---|
| 244 | int * result, |
---|
| 245 | int length, |
---|
| 246 | int init_pos_a, |
---|
| 247 | int init_pos_b, |
---|
| 248 | int init_pos_result) |
---|
| 249 | { |
---|
| 250 | int i; |
---|
| 251 | int j; |
---|
| 252 | int k; |
---|
| 253 | |
---|
| 254 | i = 0; |
---|
| 255 | j = 0; |
---|
| 256 | k = init_pos_result; |
---|
| 257 | |
---|
| 258 | while((i < length) || (j < length)) |
---|
| 259 | { |
---|
| 260 | if((i < length) && (j < length)) |
---|
| 261 | { |
---|
| 262 | if(array[init_pos_a + i] < array[init_pos_b + j]) |
---|
| 263 | { |
---|
| 264 | result[k++] = array[init_pos_a + i]; |
---|
| 265 | i++; |
---|
| 266 | } |
---|
| 267 | else |
---|
| 268 | { |
---|
| 269 | result[k++] = array[init_pos_b + j]; |
---|
| 270 | j++; |
---|
| 271 | } |
---|
| 272 | } |
---|
| 273 | else if(i < length) |
---|
| 274 | { |
---|
| 275 | result[k++] = array[init_pos_a + i]; |
---|
| 276 | i++; |
---|
| 277 | } |
---|
| 278 | else |
---|
| 279 | { |
---|
| 280 | result[k++] = array[init_pos_b + j]; |
---|
| 281 | j++; |
---|
| 282 | } |
---|
| 283 | } |
---|
| 284 | } |
---|
| 285 | |
---|
| 286 | /* vim: tabstop=4 : shiftwidth=4 : expandtab |
---|
| 287 | */ |
---|