source: soft/giet_vm/giet_common/kernel_barriers.c @ 548

Last change on this file since 548 was 495, checked in by alain, 10 years ago

Introduce quad tree for distributed locks and barriers.
File size: 13.9 KB
Line 
1//////////////////////////////////////////////////////////////////////////////
2// File     : kernel_barriers.c
3// Date     : 19/01/2015
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6//////////////////////////////////////////////////////////////////////////////
7
8#include "kernel_barriers.h"
9#include "giet_config.h"
10#include "hard_config.h"
11#include "utils.h"
12#include "tty0.h"
13#include "kernel_malloc.h"
14#include "io.h"
15
16///////////////////////////////////////////////////////////////////////////////
17//      Simple barrier access functions
18///////////////////////////////////////////////////////////////////////////////
19
20//////////////////////////////////////////////////////
21void _simple_barrier_init( simple_barrier_t*  barrier,
22                           unsigned int       ntasks )
23{
24
25#if GIET_DEBUG_SIMPLE_BARRIER
26unsigned int    gpid = _get_procid();
27unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
28unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
29unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
30_printf("[DEBUG SIMPLE_BARRIER] proc[%d,%d,%d] enters _simple_barrier_init()"
31               " / vaddr = %x / ntasks = %d\n",
32               px, py, pl, (unsigned int)barrier , ntasks );
33#endif
34
35    barrier->ntasks = ntasks;
36    barrier->count  = ntasks;
37    barrier->sense  = 0;
38
39    asm volatile ("sync" ::: "memory");
40
41}  // end simple_barrier_init()
42
43//////////////////////////////////////////////////////
44void _simple_barrier_wait( simple_barrier_t*  barrier )
45{
46
47#if GIET_DEBUG_SIMPLE_BARRIER
48unsigned int    gpid = _get_procid();
49unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
50unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
51unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
52_printf("[DEBUG SIMPLE_BARRIER] proc[%d,%d,%d] enters _simple_barrier_wait()"
53               " / vaddr = %x / ntasks = %d / count = %d / sense = %d\n",
54               px, py, pl , (unsigned int)barrier , barrier->ntasks ,
55               barrier->count , barrier->sense );
56#endif
57
58    // compute expected sense value
59    unsigned int expected;
60    if ( barrier->sense == 0 ) expected = 1;
61    else                       expected = 0;
62
63    // decrement local "count"
64    unsigned int count = _atomic_increment( &barrier->count, -1 );
65
66    // the last task re-initializes count and toggle sense,
67    // waking up all other waiting tasks
68    if (count == 1)   // last task
69    {
70        barrier->count = barrier->ntasks;
71        barrier->sense = expected;
72    }
73    else              // other tasks poll the sense flag
74    {
75        while ( ioread32( &barrier->sense ) != expected ) asm volatile ("nop");
76    }
77
78    asm volatile ("sync" ::: "memory");
79
80#if GIET_DEBUG_SIMPLE_BARRIER
81_printf("[DEBUG SIMPLE_BARRIER] proc[%d,%d,%d] exit simple barrier_wait()\n",
82               px, py, pl );
83#endif
84
85} // end _simple_barrier_wait()
86
87
88
89
90////////////////////////////////////////////////////////////////////////////////
91//      SQT barrier access functions
92////////////////////////////////////////////////////////////////////////////////
93
94////////////////////////////////////////////////////////////////////////////////
95// This recursive function is called by the _sqt_barrier_init() function
96// to initializes the SQT nodes (mainly the parent and child pointers).
97// It traverses the SQT from top to bottom.
98// The SQT can be uncomplete (when xmax or ymax are not power of 2),
99// and the recursion stops when the (x,y) coordinates exceed the footprint.
100////////////////////////////////////////////////////////////////////////////////
101static 
102void _sqt_barrier_build( sqt_barrier_t*      barrier,   // barrier pointer
103                         unsigned int        x,         // node x coordinate
104                         unsigned int        y,         // node y coordinate
105                         unsigned int        level,     // node level
106                         sqt_barrier_node_t* parent,    // parent node
107                         unsigned int        xmax,     // SQT X size
108                         unsigned int        ymax )   // SQT Y size
109{
110
111#if GIET_DEBUG_SQT_BARRIER
112unsigned int    gpid = _get_procid();
113unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
114unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
115unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
116#endif
117
118    // get target node pointer
119    sqt_barrier_node_t* node = barrier->node[x][y][level];
120   
121    if (level == 0 )        // terminal case
122    {
123        // initializes target node
124        node->arity    = NB_PROCS_MAX;   
125        node->count    = NB_PROCS_MAX;
126        node->sense    = 0;
127        node->level    = 0;
128        node->parent   = parent;
129        node->child[0] = NULL;
130        node->child[1] = NULL;
131        node->child[2] = NULL;
132        node->child[3] = NULL;
133
134#if GIET_DEBUG_SQT_BARRIER
135_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] initialises SQT node[%d,%d,%d] :\n"
136      " parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
137      px , py , pl , x , y , level , 
138      (unsigned int)node->parent , 
139      (unsigned int)node->child[0] , 
140      (unsigned int)node->child[1] , 
141      (unsigned int)node->child[2] , 
142      (unsigned int)node->child[3] );
143#endif
144
145    }
146    else                  // non terminal case
147    {
148        unsigned int cx[4];      // x coordinate for children
149        unsigned int cy[4];      // y coordinate for children
150        unsigned int arity = 0;  // number of children
151        unsigned int i;          // child index
152
153        // the child0 coordinates are equal to the parent coordinates
154        // other child coordinates are incremented depending on the level value
155        cx[0] = x;
156        cy[0] = y;
157
158        cx[1] = x + (1 << (level-1));
159        cy[1] = y;
160
161        cx[2] = x;
162        cy[2] = y + (1 << (level-1));
163
164        cx[3] = x + (1 << (level-1));
165        cy[3] = y + (1 << (level-1));
166
167        // initializes target node
168        for ( i = 0 ; i < 4 ; i++ )
169        {
170            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
171            {
172                node->child[i] = barrier->node[cx[i]][cy[i]][level-1];
173                arity++;
174            }
175            else  node->child[i] = NULL;
176        }
177        node->arity    = arity; 
178        node->count    = arity;
179        node->sense    = 0;
180        node->level    = level;
181        node->parent   = parent;
182
183#if GIET_DEBUG_SQT_BARRIER
184_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] initialises SQT node[%d,%d,%d] : \n"
185      " parent = %x / childO = %x / child1 = %x / child2 = %x / child3 = %x\n",
186      px , py , pl , x , y , level , 
187      (unsigned int)node->parent ,
188      (unsigned int)node->child[0] , 
189      (unsigned int)node->child[1] , 
190      (unsigned int)node->child[2] , 
191      (unsigned int)node->child[3] );
192#endif
193
194        // recursive calls for children nodes
195        for ( i = 0 ; i < 4 ; i++ )
196        {
197            if ( (cx[i] < xmax) && (cy[i] < ymax) ) 
198                _sqt_barrier_build( barrier, 
199                                    cx[i], 
200                                    cy[i], 
201                                    level-1, 
202                                    node, 
203                                    xmax, 
204                                    ymax );
205        }
206    }
207}  // end _sqt_barrier_build()
208
209///////////////////////////////////////////////////////////////////////////////
210// This external function initialises the distributed SQT barrier.
211// It allocates memory for the distributed SQT nodes in clusters,
212// and initializes the SQT nodes pointers array (stored in cluster[0][0].
213// The SQT can be "uncomplete" as SQT barrier nodes are only build in clusters
214// containing processors, and contained in the mesh (X_SIZE/Y_SIZE).
215// The actual number of SQT barriers nodes in a cluster[x][y] depends on (x,y):
216// At least 1 node / at most 5 nodes per cluster:
217// - barrier arbitrating between all processors of   1 cluster  has level 0,
218// - barrier arbitrating between all processors of   4 clusters has level 1,
219// - barrier arbitrating between all processors of  16 clusters has level 2,
220// - barrier arbitrating between all processors of  64 clusters has level 3,
221// - barrier arbitrating between all processors of 256 clusters has level 4,
222///////////////////////////////////////////////////////////////////////////////
223void _sqt_barrier_init( sqt_barrier_t*  barrier )
224{
225    unsigned int levels;
226    unsigned int xmax;
227    unsigned int ymax;
228
229    // compute the smallest covering SQT
230    _get_sqt_footprint( &xmax, &ymax, &levels );
231
232#if GIET_DEBUG_SQT_BARRIER
233unsigned int    gpid = _get_procid();
234unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
235unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
236unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
237_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] initialises SQT barrier %x : \n"
238               " xmax = %d / ymax = %d / levels = %d\n",
239               px , py , pl , (unsigned int)barrier , 
240               xmax , ymax , levels );
241#endif
242
243    unsigned int x;              // x coordinate for one SQT node
244    unsigned int y;              // y coordinate for one SQT node
245    unsigned int l;              // level for one SQT node
246
247    for ( x = 0 ; x < xmax ; x++ )
248    {
249        for ( y = 0 ; y < ymax ; y++ )
250        {
251            for ( l = 0 ; l < levels ; l++ )           
252            {
253               
254                if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) ||
255                     ( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) ||
256                     ( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) ||
257                     ( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) ||
258                     ( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
259                 {
260                     barrier->node[x][y][l] = 
261                     (sqt_barrier_node_t*)_remote_malloc( sizeof(sqt_barrier_node_t),
262                                                          x, y );
263
264#if GIET_DEBUG_SQT_BARRIER
265_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] allocates SQT node[%d,%d,%d]"
266               " : vaddr = %x\n",
267               px , py , pl , x , y , l , (unsigned int)barrier->node[x][y][l] );
268#endif
269                 }
270            }
271        }
272    }
273           
274    // recursively initialize SQT nodes from root to bottom
275    _sqt_barrier_build( barrier,       // pointer on the SQT barrier descriptor
276                        0,             // cluster X coordinate
277                        0,             // cluster Y coordinate
278                        levels-1,      // level in SQT
279                        NULL,          // pointer on the parent node
280                        xmax,          // SQT footprint X size
281                        ymax );        // SQT footprint Y size
282
283    asm volatile ("sync" ::: "memory");
284
285} // end _sqt_barrier_init()
286
287///////////////////////////////////////////////////////////////////////////////
288// This recursive function is called by the _sqt_barrier_wait().
289// It decrements the distributed count variables,
290// traversing the SQT from bottom to root.
291// The last arrived task reset the local node before returning.
292///////////////////////////////////////////////////////////////////////////////
293static 
294void _sqt_barrier_decrement( sqt_barrier_node_t* node )
295{
296
297#if GIET_DEBUG_SQT_BARRIER
298unsigned int    gpid = _get_procid();
299unsigned int    px   = gpid >> (Y_WIDTH + P_WIDTH);
300unsigned int    py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
301unsigned int    pl   = gpid & ((1<<P_WIDTH)-1);
302_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] decrement SQT barrier node %x :\n"
303        " level = %d / arity = %d / sense = %d / count = %d\n",
304        px , py , pl , (unsigned int)node , 
305        node->level , node->arity , node->sense , node->count );
306#endif
307
308    // compute expected sense value
309    unsigned int expected;
310    if ( node->sense == 0 ) expected = 1;
311    else                    expected = 0;
312
313    // decrement local "count"
314    unsigned int count = _atomic_increment( &node->count, -1 );
315
316    if ( count == 1 )    // last task
317    {
318        // decrement the parent node if the current node is not the root
319        if ( node->parent != NULL )     
320            _sqt_barrier_decrement( node->parent );
321
322        // reset the current node
323        node->sense = expected;
324        node->count = node->arity;
325
326#if GIET_DEBUG_SQT_BARRIER
327_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] reset SQT barrier node %x :\n"
328        " level = %d / arity = %d / sense = %d / count = %d\n",
329        px , py , pl , (unsigned int)node , 
330        node->level , node->arity , node->sense , node->count );
331#endif
332        return;
333    }
334    else                 // not the last task
335    {
336        // poll the local "sense" flag
337        while ( ioread32( &node->sense ) != expected ) asm volatile ("nop");
338
339        return;
340    }
341}  // end _sqt_barrier_decrement()
342
343////////////////////// initialises NIC & CMA RX channel, and /////////////////////////////////////////////////////////
344// This external blocking function waits until all procesors reach the barrier.
345// Returns only when the barrier has been taken.
346///////////////////////////////////////////////////////////////////////////////
347void _sqt_barrier_wait( sqt_barrier_t*  barrier )
348{
349    // get cluster coordinates
350    unsigned int gpid = _get_procid();
351    unsigned int px   = (gpid >> (Y_WIDTH + P_WIDTH)) & ((1<<X_WIDTH)-1);
352    unsigned int py   = (gpid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
353
354#if GIET_DEBUG_SQT_BARRIER
355unsigned int pl = gpid & ((1<<P_WIDTH)-1);
356_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] enters SQT barrier %x at cycle %d\n",
357        px , py , pl , (unsigned int)barrier , _get_proctime() ); 
358#endif
359
360   // decrement the barrier counters
361    _sqt_barrier_decrement( barrier->node[px][py][0] );
362
363#if GIET_DEBUG_SQT_BARRIER
364_printf("\n[DEBUG SQT_BARRIER] P[%d,%d,%d] exit SQT barrier %x at cycle %d\n",
365        px , py , pl , (unsigned int)barrier , _get_proctime() ); 
366#endif
367
368    asm volatile ("sync" ::: "memory");
369
370}  // end _sqt_barrier_wait()
371
372
373
374// Local Variables:
375// tab-width: 4
376// c-basic-offset: 4
377// c-file-offsets:((innamespace . 0)(inline-open . 0))
378// indent-tabs-mode: nil
379// End:
380// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
381
Note: See TracBrowser for help on using the repository browser.