source: trunk/user/sort/sort.c @ 582

Last change on this file since 582 was 574, checked in by alain, 6 years ago

Cosmetic.

  • Property svn:executable set to *
File size: 11.8 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2// File   :  sort.c
3// Date   :  November 2013
4// Author :  Cesar Fuguet Tortolero <cesar.fuguet-tortolero@lip6.fr>
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 cores.
9// Computation is organised as a binary tree:
10// - All threads execute in parallel a buble sort on a sub-array during the
11//   the first stage of parallel sort,
12// - The number of participating threads is divided by 2 at each next stage,
13//   to make a merge sort, on two subsets of previous stage.
14//
15//       Number_of_stages = number of barriers = log2(Number_of_threads)
16//
17// Constraints :
18// - It supports up to 1024 cores: x_size, y_size, and ncores must be
19//   power of 2 (max 16*16 clusters / max 4 cores per cluster)
20// _ The array of values to be sorted (ARRAY_LENGTH) must be power of 2
21//   larger than the number of cores.
22///////////////////////////////////////////////////////////////////////////////
23
24#include <stdio.h>
25#include <stdlib.h>
26#include <pthread.h>
27#include <almosmkh.h>
28#include <hal_macros.h>
29
30#define ARRAY_LENGTH        0x100    // 256 values
31
32#define MAX_THREADS         1024     // 16 * 16 * 4
33
34#define DISPLAY_ARRAY       0
35#define INTERACTIVE_MODE    0
36
37/////////////////////////////////////////////////////////////
38// argument for the sort() function (one thread per core)
39/////////////////////////////////////////////////////////////
40
41typedef struct
42{
43    unsigned int threads;      // total number of threads
44    unsigned int thread_uid;    // thread user index (0 to threads -1)
45    unsigned int main_uid;      // main thread user index
46}
47args_t;
48
49//////////////////////////////////////////
50//      Global variables
51//////////////////////////////////////////
52
53int                 array0[ARRAY_LENGTH];    // values to sort
54int                 array1[ARRAY_LENGTH];   
55
56pthread_barrier_t   barrier;                 // synchronisation variables
57
58pthread_attr_t      attr[MAX_THREADS];       // thread attributes (one per thread)
59args_t              arg[MAX_THREADS];        // sort function arguments (one per thread)
60
61////////////////////////////////////
62static void bubbleSort(
63    int * array,
64    unsigned int length,
65    unsigned int init_pos )
66{
67    unsigned int i;
68    unsigned int j;
69    int          aux;
70
71    for(i = 0; i < length; i++)
72    {
73        for(j = init_pos; j < (init_pos + length - i - 1); j++)
74        {
75            if(array[j] > array[j + 1])
76            {
77                aux          = array[j + 1];
78                array[j + 1] = array[j];
79                array[j]     = aux;
80            }
81        }
82    }
83}  // end bubbleSort()
84
85
86/////////////////////////
87static void merge(
88    const int * src,
89    int * dst,
90    int length,
91    int init_pos_src_a,
92    int init_pos_src_b,
93    int init_pos_dst )
94{
95    int i;
96    int j;
97    int k;
98
99    i = 0;
100    j = 0;
101    k = init_pos_dst;
102
103    while((i < length) || (j < length))
104    {
105        if((i < length) && (j < length))
106        {
107            if(src[init_pos_src_a + i] < src[init_pos_src_b + j])
108            {
109                dst[k++] = src[init_pos_src_a + i];
110                i++;
111            }
112            else
113            {
114                dst[k++] = src[init_pos_src_b + j];
115                j++;
116            }
117        }
118        else if(i < length)
119        {
120            dst[k++] = src[init_pos_src_a + i];
121            i++;
122        }
123        else
124        {
125            dst[k++] = src[init_pos_src_b + j];
126            j++;
127        }
128    }
129}  // end merge()
130
131/////////////////////////
132static void sort( const args_t * ptr )
133{
134    unsigned int       i;
135    unsigned long long cycle;
136    unsigned int       cxy;
137    unsigned int       lid;
138
139    int         * src_array  = NULL;
140    int         * dst_array  = NULL;
141
142    // get core coordinates an date
143    get_core( &cxy , &lid );
144    get_cycle( &cycle );
145
146    unsigned int  thread_uid = ptr->thread_uid;
147    unsigned int  threads    = ptr->threads;
148    unsigned int  main_uid   = ptr->main_uid;
149
150    unsigned int  items      = ARRAY_LENGTH / threads;
151    unsigned int  stages     = __builtin_ctz( threads ) + 1;
152
153    printf("\n[SORT] thread[%d] : start\n", thread_uid );
154
155    bubbleSort( array0, items, items * thread_uid );
156
157    printf("\n[SORT] thread[%d] : stage 0 completed\n", thread_uid );
158
159    /////////////////////////////////
160    pthread_barrier_wait( &barrier ); 
161    printf("\n[SORT] thread[%d] exit barrier\n", thread_uid );
162
163    // the number of threads contributing to sort
164    // is divided by 2 at each next stage
165    for ( i = 1 ; i < stages ; i++ )
166    {
167        pthread_barrier_wait( &barrier );
168
169        if( (thread_uid & ((1<<i)-1)) == 0 )
170        {
171            printf("\n[SORT] thread[%d] : stage %d start\n", thread_uid , i );
172
173            if((i % 2) == 1)               // odd stage
174            {
175                src_array = array0;
176                dst_array = array1;
177            }
178            else                           // even stage
179            {
180                src_array = array1;
181                dst_array = array0;
182            }
183
184            merge( src_array, 
185                   dst_array,
186                   items << i,
187                   items * thread_uid,
188                   items * (thread_uid + (1 << (i-1))),
189                   items * thread_uid );
190
191            printf("\n[SORT] thread[%d] : stage %d completed\n", thread_uid , i );
192        }
193
194        /////////////////////////////////
195        pthread_barrier_wait( &barrier );
196        printf("\n[SORT] thread[%d] exit barrier\n", thread_uid );
197
198    }
199
200    // all threads but the main thread exit
201    if( thread_uid != main_uid ) pthread_exit( NULL );
202
203} // end sort()
204
205
206/////////////////
207void main( void )
208{
209    unsigned int           x_size;             // number of rows
210    unsigned int           y_size;             // number of columns
211    unsigned int           ncores;             // number of cores per cluster
212    unsigned int           threads;            // total number of threads
213    unsigned int           thread_uid;         // user defined thread index
214    unsigned int           main_cxy;           // cluster identifier for main
215    unsigned int           main_x;             // X coordinate for main thread
216    unsigned int           main_y;             // Y coordinate for main thread
217    unsigned int           main_lid;           // core local index for main thread
218    unsigned int           main_uid;           // thread user index for main thread
219    unsigned int           x;                  // X coordinate for a thread
220    unsigned int           y;                  // Y coordinate for a thread
221    unsigned int           lid;                // core local index for a thread
222    unsigned int           n;                  // index in array to sort
223    unsigned long long     cycle;              // current date for log
224    pthread_t              trdid;              // kernel allocated thread index (unused)
225    pthread_barrierattr_t  barrier_attr;       // barrier attributes
226
227    // compute number of threads (one thread per proc)
228    get_config( &x_size , &y_size , &ncores );
229    threads = x_size * y_size * ncores;
230
231    // get core coordinates and user index for the main thread
232    get_core( &main_cxy , & main_lid );
233    main_x   = HAL_X_FROM_CXY( main_cxy );
234    main_y   = HAL_Y_FROM_CXY( main_cxy );
235    main_uid = (((main_x * y_size) + main_y) * ncores) + main_lid; 
236
237    // checks number of threads
238    if ( (threads != 1)   && (threads != 2)   && (threads != 4)   && 
239         (threads != 8)   && (threads != 16 ) && (threads != 32)  && 
240         (threads != 64)  && (threads != 128) && (threads != 256) && 
241         (threads != 512) && (threads != 1024) )
242    {
243        printf("\n[SORT ERROR] number of cores must be power of 2\n");
244        exit( 0 );
245    }
246
247    // check array size
248    if ( ARRAY_LENGTH % threads) 
249    {
250        printf("\n[SORT ERROR] array size must be multiple of number of threads\n");
251        exit( 0 );
252    }
253
254    printf("\n[SORT] main starts on core[%x,%d] / %d thread(s) / %d values\n",
255    main_cxy, main_lid, threads, ARRAY_LENGTH );
256
257    // Barrier initialization
258    barrier_attr.x_size   = x_size; 
259    barrier_attr.y_size   = y_size;
260    barrier_attr.nthreads = ncores;
261    if( pthread_barrier_init( &barrier, &barrier_attr , threads ) )
262    {
263        printf("\n[SORT ERROR] cannot initialise barrier\n" );
264        exit( 0 );
265    }
266
267    printf("\n[SORT] main completes barrier init\n");
268
269    // Array to sort initialization
270    for ( n = 0 ; n < ARRAY_LENGTH ; n++ )
271    {
272        array0[n] = rand();
273    }
274
275#if DISPLAY_ARRAY
276printf("\n*** array before sort\n");
277for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , array0[n] );
278#endif
279
280    printf("\n[SORT] main completes array init\n");
281
282    // launch other threads to execute sort() function
283    // on cores other than the core running the main thread
284    for ( x=0 ; x<x_size ; x++ )
285    {
286        for ( y=0 ; y<y_size ; y++ )
287        {
288            for ( lid=0 ; lid<ncores ; lid++ )
289            {
290                thread_uid = (((x * y_size) + y) * ncores) + lid;
291
292                // set sort arguments for all threads
293                arg[thread_uid].threads      = threads;
294                arg[thread_uid].thread_uid   = thread_uid;
295                arg[thread_uid].main_uid     = main_uid;
296
297                // set thread attributes for all threads
298                attr[thread_uid].attributes = PT_ATTR_DETACH          |
299                                              PT_ATTR_CLUSTER_DEFINED | 
300                                              PT_ATTR_CORE_DEFINED;
301                attr[thread_uid].cxy        = HAL_CXY_FROM_XY( x , y );
302                attr[thread_uid].lid        = lid;
303
304                if( thread_uid != main_uid )
305                {
306                    if ( pthread_create( &trdid,              // not used because no join
307                                         &attr[thread_uid],   // thread attributes
308                                         &sort,               // entry function
309                                         &arg[thread_uid] ) ) // sort arguments
310                    {
311                        printf("\n[SORT ERROR] main cannot create thread %x \n", thread_uid );
312                        exit( 0 );
313                    }
314                    else
315                    {
316                        printf("\n[SORT] main created thread %x \n", thread_uid );
317                    }
318                }
319
320#if INTERACTIVE_MODE
321idbg();
322#endif
323            }
324        }
325    }
326   
327    get_cycle( &cycle );
328    printf("\n[SORT] main completes threads create at cycle %d\n", (unsigned int)cycle );
329
330#if INTERACTIVE_MODE
331idbg();
332#endif
333   
334    // the main thread run also the sort() function
335    sort( &arg[main_uid] );
336
337    // Check result
338    int    success = 1;
339    int*   res_array = ( (threads==  2) ||
340                         (threads==  8) || 
341                         (threads== 32) || 
342                         (threads==128) || 
343                         (threads==512) ) ? array1 : array0;
344   
345    for( n=0 ; n<(ARRAY_LENGTH-2) ; n++ )
346    {
347        if ( res_array[n] > res_array[n+1] )
348        {
349            printf("\n[SORT] array[%d] = %d > array[%d] = %d\n",
350            n , res_array[n] , n+1 , res_array[n+1] );
351            success = 0;
352            break;
353        }
354    }
355
356#if DISPLAY_ARRAY
357printf("\n*** array after sort\n");
358for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , res_array[n] );
359#endif
360
361    get_cycle( &cycle );
362
363    if ( success )
364    {
365        printf("\n[SORT] success at cycle %d\n", (unsigned int)cycle );
366        exit( 0 );
367    }
368    else
369    {
370        printf("\n[SORT] failure at cycle %d\n", (unsigned int)cycle );
371        exit( 1 );
372    }
373
374}  // end main()
375
376
377/*
378vim: tabstop=4 : shiftwidth=4 : expandtab
379*/
Note: See TracBrowser for help on using the repository browser.