[257] | 1 | /////////////////////////////////////////////////////////////////////////////// |
---|
[295] | 2 | // File : main.c |
---|
| 3 | // Date : November 2013 |
---|
| 4 | // Author : Cesar Fuguet Tortolero <cesar.fuguet-tortolero@lip6.fr> |
---|
[669] | 5 | /////////////////////////////////////////////////////////////////////////////// |
---|
| 6 | // This multi-threaded application implement a multi-stage sort application. |
---|
| 7 | // The various stages are separated by synchronisation barriers. |
---|
| 8 | // There is one thread per physical processors. Computation is organised as |
---|
| 9 | // a binary tree: All threads contribute to the first stage of parallel sort |
---|
| 10 | // but, the number of participating threads is divided by 2 at each next stage. |
---|
| 11 | // Number_of_stages = number of barriers = log2(Number_of_threads) |
---|
[256] | 12 | // |
---|
[669] | 13 | // Constraints : |
---|
| 14 | // - It supports up to 1024 processors and the number of processors |
---|
| 15 | // must be a power of 2. |
---|
| 16 | // _ The array of values to be sorted (ARRAY_LENGTH) must be power of 2 |
---|
| 17 | // larger than the number of processors. |
---|
| 18 | // - This application uses a private TTY terminal, shared by all threads, |
---|
| 19 | // that is protectted by an user-level SQT lock. |
---|
[257] | 20 | /////////////////////////////////////////////////////////////////////////////// |
---|
[256] | 21 | |
---|
| 22 | #include "stdio.h" |
---|
[292] | 23 | #include "mapping_info.h" |
---|
[502] | 24 | #include "user_barrier.h" |
---|
[669] | 25 | #include "user_lock.h" |
---|
[256] | 26 | |
---|
[687] | 27 | #define ARRAY_LENGTH 0x400 |
---|
[502] | 28 | #define IPT (ARRAY_LENGTH / threads) // ITEMS PER THREAD |
---|
[257] | 29 | |
---|
[669] | 30 | // macro to use a shared TTY |
---|
| 31 | #define printf(...) lock_acquire( &tty_lock ); \ |
---|
| 32 | giet_tty_printf(__VA_ARGS__); \ |
---|
| 33 | lock_release( &tty_lock ) |
---|
[257] | 34 | |
---|
[669] | 35 | int array0[ARRAY_LENGTH]; |
---|
| 36 | int array1[ARRAY_LENGTH]; |
---|
[256] | 37 | |
---|
[669] | 38 | volatile int init_ok = 0; |
---|
| 39 | giet_barrier_t barrier[10]; |
---|
| 40 | user_lock_t tty_lock; |
---|
[257] | 41 | |
---|
[256] | 42 | void bubbleSort( |
---|
| 43 | int * array, |
---|
| 44 | unsigned int length, |
---|
| 45 | unsigned int init_pos); |
---|
| 46 | |
---|
| 47 | void merge( |
---|
| 48 | int * array, |
---|
| 49 | int * result, |
---|
| 50 | int length, |
---|
| 51 | int init_pos_a, |
---|
| 52 | int init_pos_b, |
---|
| 53 | int init_pos_result); |
---|
| 54 | |
---|
[295] | 55 | ////////////////////////////////////////// |
---|
[669] | 56 | __attribute__ ((constructor)) void main() |
---|
| 57 | ////////////////////////////////////////// |
---|
[256] | 58 | { |
---|
[381] | 59 | int * src_array = NULL; |
---|
| 60 | int * dst_array = NULL; |
---|
[256] | 61 | int i; |
---|
[502] | 62 | unsigned int x_size; |
---|
| 63 | unsigned int y_size; |
---|
| 64 | unsigned int nprocs; |
---|
| 65 | unsigned int threads; |
---|
[515] | 66 | |
---|
[669] | 67 | // each thread gets its thread_id |
---|
| 68 | int thread_id = giet_thread_id(); |
---|
| 69 | |
---|
| 70 | unsigned int time_start = giet_proctime(); |
---|
| 71 | unsigned int time_end; |
---|
| 72 | |
---|
| 73 | // each thread compute number of threads (one thread per proc) |
---|
[502] | 74 | giet_procs_number( &x_size , &y_size , &nprocs ); |
---|
| 75 | threads = x_size * y_size * nprocs; |
---|
[256] | 76 | |
---|
[669] | 77 | // thread 0 makes TTY and barrier initialisations |
---|
| 78 | // other threads wait initialisation completion. |
---|
| 79 | if ( thread_id == 0 ) |
---|
[502] | 80 | { |
---|
[669] | 81 | // request a shared TTY used by all threads |
---|
| 82 | giet_tty_alloc(1); |
---|
| 83 | |
---|
| 84 | // TTY lock initialisation |
---|
| 85 | lock_init( &tty_lock ); |
---|
[502] | 86 | |
---|
[669] | 87 | printf("\n[ SORT T0 ] Starting sort application with %d threads " |
---|
[502] | 88 | "at cycle %d\n", threads, time_start); |
---|
| 89 | |
---|
[669] | 90 | // Barriers Initialization |
---|
[502] | 91 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[292] | 92 | { |
---|
[669] | 93 | barrier_init( &barrier[i], threads >> i ); |
---|
[292] | 94 | } |
---|
| 95 | |
---|
| 96 | init_ok = 1; |
---|
[256] | 97 | } |
---|
[292] | 98 | else |
---|
| 99 | { |
---|
[669] | 100 | while( !init_ok ); |
---|
[292] | 101 | } |
---|
[256] | 102 | |
---|
[669] | 103 | // each thread checks number of tasks |
---|
| 104 | if ( (threads != 1) && (threads != 2) && (threads != 4) && |
---|
| 105 | (threads != 8) && (threads != 16 ) && (threads != 32) && |
---|
| 106 | (threads != 64) && (threads != 128) && (threads != 256) && |
---|
| 107 | (threads != 512) && (threads != 1024) ) |
---|
| 108 | { |
---|
| 109 | giet_exit("error : number of processors must be power of 2"); |
---|
| 110 | } |
---|
[256] | 111 | |
---|
[669] | 112 | |
---|
| 113 | // Each thread contribute to Array Initialization |
---|
[271] | 114 | for (i = IPT * thread_id; i < IPT * (thread_id + 1); i++) |
---|
[256] | 115 | { |
---|
[502] | 116 | array0[i] = giet_rand(); |
---|
[256] | 117 | } |
---|
| 118 | |
---|
[669] | 119 | // all threads contribute to the first stage of parallel sort |
---|
| 120 | printf("[ SORT T%d ] Stage 0: Sorting...\n\r", thread_id); |
---|
[256] | 121 | |
---|
[271] | 122 | bubbleSort(array0, IPT, IPT * thread_id); |
---|
[256] | 123 | |
---|
[669] | 124 | printf("[ SORT T%d ] Finishing Stage 0\n\r", thread_id); |
---|
[257] | 125 | |
---|
[669] | 126 | // the number of threads is divided by 2 at each next stage |
---|
[502] | 127 | for (i = 0; i < __builtin_ctz( threads ); i++) |
---|
[256] | 128 | { |
---|
[669] | 129 | barrier_wait( &barrier[i] ); |
---|
[256] | 130 | |
---|
[269] | 131 | if((thread_id % (2 << i)) != 0) |
---|
| 132 | { |
---|
[669] | 133 | printf("[ SORT T%d ] Quit\n\r", thread_id ); |
---|
[502] | 134 | giet_exit("Completed"); |
---|
[269] | 135 | } |
---|
[257] | 136 | |
---|
[669] | 137 | printf("[ SORT T%d ] Stage %d: Sorting...\n\r", thread_id, i+1); |
---|
[256] | 138 | |
---|
| 139 | if((i % 2) == 0) |
---|
| 140 | { |
---|
| 141 | src_array = &array0[0]; |
---|
| 142 | dst_array = &array1[0]; |
---|
| 143 | } |
---|
| 144 | else |
---|
| 145 | { |
---|
| 146 | src_array = &array1[0]; |
---|
| 147 | dst_array = &array0[0]; |
---|
| 148 | } |
---|
| 149 | |
---|
| 150 | merge(src_array, dst_array |
---|
[271] | 151 | , IPT << i |
---|
| 152 | , IPT * thread_id |
---|
| 153 | , IPT * (thread_id + (1 << i)) |
---|
| 154 | , IPT * thread_id |
---|
[256] | 155 | ); |
---|
| 156 | |
---|
[669] | 157 | printf("[ SORT T%d ] Finishing Stage %d\n\r", thread_id, i + 1); |
---|
[256] | 158 | } |
---|
| 159 | |
---|
| 160 | int success; |
---|
| 161 | int failure_index; |
---|
| 162 | |
---|
[257] | 163 | // Verify the resulting array |
---|
[345] | 164 | if(thread_id != 0) |
---|
| 165 | { |
---|
[502] | 166 | giet_exit("error: only thread 0 should get here"); |
---|
[345] | 167 | } |
---|
[257] | 168 | |
---|
[345] | 169 | success = 1; |
---|
| 170 | for(i=0; i<(ARRAY_LENGTH-1); i++) |
---|
[256] | 171 | { |
---|
[345] | 172 | if(dst_array[i] > dst_array[i+1]) |
---|
[256] | 173 | { |
---|
[345] | 174 | success = 0; |
---|
| 175 | failure_index = i; |
---|
| 176 | break; |
---|
[256] | 177 | } |
---|
[345] | 178 | } |
---|
[256] | 179 | |
---|
[345] | 180 | time_end = giet_proctime(); |
---|
[295] | 181 | |
---|
[669] | 182 | printf("[ SORT T0 ] Finishing sort application at cycle %d\n" |
---|
| 183 | "[ SORT T0 ] Time elapsed = %d\n", |
---|
[345] | 184 | time_end, (time_end - time_start) ); |
---|
[292] | 185 | |
---|
[345] | 186 | if (success) |
---|
| 187 | { |
---|
[502] | 188 | giet_exit("!!! Success !!!"); |
---|
[345] | 189 | } |
---|
| 190 | else |
---|
| 191 | { |
---|
[669] | 192 | printf("[ SORT T0 ] Failure!! Incorrect element: %d\n\r", |
---|
[345] | 193 | failure_index); |
---|
| 194 | for(i=0; i<ARRAY_LENGTH; i++) |
---|
[256] | 195 | { |
---|
[345] | 196 | printf("array[%d] = %d\n", i, dst_array[i]); |
---|
[256] | 197 | } |
---|
[502] | 198 | giet_exit("!!! Failure !!!"); |
---|
[256] | 199 | } |
---|
[345] | 200 | |
---|
[502] | 201 | giet_exit("Completed"); |
---|
[256] | 202 | } |
---|
| 203 | |
---|
[295] | 204 | //////////////////////////////////// |
---|
| 205 | void bubbleSort( int * array, |
---|
| 206 | unsigned int length, |
---|
| 207 | unsigned int init_pos ) |
---|
[256] | 208 | { |
---|
| 209 | int i; |
---|
| 210 | int j; |
---|
| 211 | int aux; |
---|
| 212 | |
---|
| 213 | for(i = 0; i < length; i++) |
---|
| 214 | { |
---|
| 215 | for(j = init_pos; j < (init_pos + length - i - 1); j++) |
---|
| 216 | { |
---|
| 217 | if(array[j] > array[j + 1]) |
---|
| 218 | { |
---|
| 219 | aux = array[j + 1]; |
---|
| 220 | array[j + 1] = array[j]; |
---|
| 221 | array[j] = aux; |
---|
| 222 | } |
---|
| 223 | } |
---|
| 224 | } |
---|
| 225 | } |
---|
| 226 | |
---|
[295] | 227 | ///////////// |
---|
[256] | 228 | void merge( |
---|
| 229 | int * array, |
---|
| 230 | int * result, |
---|
| 231 | int length, |
---|
| 232 | int init_pos_a, |
---|
| 233 | int init_pos_b, |
---|
| 234 | int init_pos_result) |
---|
| 235 | { |
---|
| 236 | int i; |
---|
| 237 | int j; |
---|
| 238 | int k; |
---|
| 239 | |
---|
| 240 | i = 0; |
---|
| 241 | j = 0; |
---|
| 242 | k = init_pos_result; |
---|
| 243 | |
---|
| 244 | while((i < length) || (j < length)) |
---|
| 245 | { |
---|
| 246 | if((i < length) && (j < length)) |
---|
| 247 | { |
---|
| 248 | if(array[init_pos_a + i] < array[init_pos_b + j]) |
---|
| 249 | { |
---|
| 250 | result[k++] = array[init_pos_a + i]; |
---|
| 251 | i++; |
---|
| 252 | } |
---|
| 253 | else |
---|
| 254 | { |
---|
| 255 | result[k++] = array[init_pos_b + j]; |
---|
| 256 | j++; |
---|
| 257 | } |
---|
| 258 | } |
---|
| 259 | else if(i < length) |
---|
| 260 | { |
---|
| 261 | result[k++] = array[init_pos_a + i]; |
---|
| 262 | i++; |
---|
| 263 | } |
---|
| 264 | else |
---|
| 265 | { |
---|
| 266 | result[k++] = array[init_pos_b + j]; |
---|
| 267 | j++; |
---|
| 268 | } |
---|
| 269 | } |
---|
| 270 | } |
---|
| 271 | |
---|
| 272 | /* vim: tabstop=4 : shiftwidth=4 : expandtab |
---|
| 273 | */ |
---|