source: soft/giet_vm/applications/sort/main.c @ 523

Last change on this file since 523 was 515, checked in by alain, 10 years ago

Cosmetic.

  • Property svn:executable set to *
File size: 7.0 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2// File   :  main.c
3// Date   :  November 2013
4// Author :  Cesar Fuguet Tortolero <cesar.fuguet-tortolero@lip6.fr>
5//
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//
11//      Constraints :
12//
13//      - It supports up to 1024 processors and the number of processors
14//        must be a power of 2.
15//
16//      _ The array of values to be sorted (ARRAY_LENGTH) must be power of 2
17//        larger than the number of processors.
18//
19//      - This application must be executed on a cache coherent architecture.
20//
21///////////////////////////////////////////////////////////////////////////////
22
23#include "stdio.h"
24#include "mapping_info.h"
25#include "hard_config.h"
26#include "user_barrier.h"
27
28#define ARRAY_LENGTH    0x1000
29#define IPT             (ARRAY_LENGTH / threads) // ITEMS PER THREAD
30
31////////////////////////////////////////////////////////////////////////////////
32// Processors other than 0 display algorithm state if VERBOSE non zero
33
34#define VERBOSE         1
35
36////////////////////////////////////////////////////////////////////////////////
37// Define printf according to verbosity option and number of available TTY
38
39#if (VERBOSE == 1)
40#   define printf(...)     giet_shr_printf(__VA_ARGS__)
41#else     
42#   define printf(...)
43#endif
44
45#define task0_printf(...) if(thread_id == 0) giet_shr_printf(__VA_ARGS__)
46
47int array0[ARRAY_LENGTH];
48int array1[ARRAY_LENGTH];
49
50volatile int init_ok = 0;
51
52void bubbleSort(
53        int * array,
54        unsigned int length,
55        unsigned int init_pos);
56
57void 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
65///////////////////////////////////////////////////////
66// This application supports at most 1024 processors
67// Number of barriers = log2(threads)
68
69giet_barrier_t barrier[10];
70
71//////////////////////////////////////////
72__attribute__ ((constructor)) void sort()
73{
74    int thread_id = giet_thread_id();
75    int * src_array = NULL;
76    int * dst_array = NULL;
77    int i;
78   
79    unsigned int time_start = giet_proctime();
80    unsigned int time_end;   
81
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
88    giet_procs_number( &x_size , &y_size , &nprocs );
89    threads = x_size * y_size * nprocs;
90
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
105    ///////////////////////////
106    // Barriers Initialization
107
108    if (thread_id == 0)
109    {
110        for (i = 0; i < __builtin_ctz( threads ); i++)
111        {
112            barrier_init(&barrier[i], threads >> i);
113        }
114
115        init_ok = 1;
116    }
117    else
118    {
119        while(!init_ok);
120    }
121
122    ////////////////////////
123    // Array Initialization
124
125    for (i = IPT * thread_id; i < IPT * (thread_id + 1); i++)
126    {
127        array0[i] = giet_rand();
128    }
129
130    ///////////////////////////////////
131    // Parallel sort of array elements
132
133    printf("[ Thread %d ] Stage 0: Sorting...\n\r", thread_id);
134
135    bubbleSort(array0, IPT, IPT * thread_id);
136
137    printf("[ Thread %d ] Finishing Stage 0\n\r", thread_id);
138
139    for (i = 0; i < __builtin_ctz( threads ); i++)
140    {
141        barrier_wait(&barrier[i]);
142
143        if((thread_id % (2 << i)) != 0)
144        {
145            printf("[ Thread %d ] Quit\n\r", thread_id );
146            giet_exit("Completed");
147        }
148
149        printf("[ Thread %d ] Stage %d: Sorting...\n\r", thread_id, i+1);
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
163                , IPT << i
164                , IPT * thread_id
165                , IPT * (thread_id + (1 << i))
166                , IPT * thread_id
167                );
168
169        printf("[ Thread %d ] Finishing Stage %d\n\r", thread_id, i + 1);
170    }
171
172    int success;
173    int failure_index;
174
175    //////////////////////////////
176    // Verify the resulting array
177   
178    if(thread_id != 0)
179    {
180        giet_exit("error: only thread 0 should get here");
181    }
182
183    success = 1;
184    for(i=0; i<(ARRAY_LENGTH-1); i++)
185    {
186        if(dst_array[i] > dst_array[i+1])
187        {
188
189            success = 0;
190            failure_index = i;
191            break;
192        }
193    }
194
195    time_end = giet_proctime();
196
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) );
200
201    if (success)
202    {
203        giet_exit("!!! Success !!!");
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++)
210        {
211            printf("array[%d] = %d\n", i, dst_array[i]);
212        }
213        giet_exit("!!!  Failure !!!");
214    }
215
216    giet_exit("Completed");
217}
218
219////////////////////////////////////
220void bubbleSort( int *        array,
221                 unsigned int length,
222                 unsigned int init_pos )
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
242/////////////
243void 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*/
Note: See TracBrowser for help on using the repository browser.