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

Last change on this file since 418 was 417, checked in by alain, 5 years ago

Introduce sort and pgcd applications.

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