source: soft/giet_vm/giet_libs/user_barrier.c @ 501

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

Introduce user-level, distributed barriers and locks (quad-tree based).
File size: 13.2 KB
RevLine 
[501]1//////////////////////////////////////////////////////////////////////////////////
2// File     : user_barrier.c     
3// Date     : 01/04/2012
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6///////////////////////////////////////////////////////////////////////////////////
7
8#include "user_barrier.h"
9#include "malloc.h"
10#include "stdio.h"
11#include "giet_config.h"
12
13///////////////////////////////////////////////////////////////////////////////////
14//      Simple barrier access functions
15///////////////////////////////////////////////////////////////////////////////////
16
17///////////////////////////////////////////
18void barrier_init( giet_barrier_t* barrier, 
19                   unsigned int    ntasks ) 
20{
21    barrier->arity  = ntasks;
22    barrier->count  = ntasks;
23    barrier->sense  = 0;
24
25    asm volatile ("sync" ::: "memory");
26}
27
28////////////////////////////////////////////
29void barrier_wait( giet_barrier_t* barrier ) 
30{
31
32#if GIET_DEBUG_USER_BARRIER
33unsigned int x;
34unsigned int y;
35unsigned int p;
36giet_proc_xyp( &x, &y, &p );
37giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] enters barrier_wait()\n", 
38                x, y, p );
39#endif
40
41    // compute expected sense value
42    unsigned int expected;
43    if ( barrier->sense == 0 ) expected = 1;
44    else                       expected = 0;
45
46    // parallel decrement barrier counter using atomic instructions LL/SC
47    // - input : pointer on the barrier counter (pcount)
48    // - output : counter value (count)
49    volatile unsigned int* pcount  = (unsigned int *)&barrier->count;
50    volatile unsigned int  count    = 0;  // avoid a warning
51
52    asm volatile( "addu   $2,     %1,        $0      \n"
53                  "barrier_llsc:                     \n"
54                  "ll     $8,     0($2)              \n"
55                  "addi   $9,     $8,        -1      \n"
56                  "sc     $9,     0($2)              \n"
57                  "beqz   $9,     barrier_llsc       \n"
58                  "addu   %0,     $8,        $0      \n"
59                  : "=r" (count)
60                  : "r" (pcount)
61                  : "$2", "$8", "$9", "memory" );
62
63    // the last task re-initializes count and toggle sense,
64    // waking up all other waiting tasks
65    if (count == 1)   // last task
66    {
67        barrier->count = barrier->arity;
68        barrier->sense = expected;
69    }
70    else              // other tasks busy waiting the sense flag
71    {
72        // polling sense flag
73        // input: pointer on the sens flag (psense)
74        // input: expected sense value (expected)
75        unsigned int* psense  = (unsigned int *)&barrier->sense;
76        asm volatile ( "barrier_sense:                   \n"
77                       "lw    $3,   0(%0)                \n"
78                       "bne   $3,   %1,    barrier_sense \n"
79                       :
80                       : "r"(psense), "r"(expected)
81                       : "$3" );
82    }
83
84    asm volatile ("sync" ::: "memory");
85
86#if GIET_DEBUG_USER_BARRIER
87giet_shr_printf("[DEBUG USER BARRIER] proc[%d,%d,%d] exit barrier_wait()\n",
88                x, y, p );
89#endif
90
91}
92
93///////////////////////////////////////////////////////////////////////////////////
94//      SQT barrier access functions
95///////////////////////////////////////////////////////////////////////////////////
96
97///////////////////////////////////////////////////
98static
99void sqt_barrier_build( giet_sqt_barrier_t*  barrier, 
100                        unsigned int         x,
101                        unsigned int         y,
102                        unsigned int         level,
103                        sqt_node_t*          parent,
104                        unsigned int         x_size,
105                        unsigned int         y_size,
106                        unsigned int         ntasks ) 
107{
108    // This recursive function initializes the SQT nodes
109    // traversing the SQT from root to bottom
110
111    // get target node address
112    sqt_node_t* node = barrier->node[x][y][level];
113   
114    if (level == 0 )        // terminal case
115    {
116        // initializes target node
117        node->arity    = ntasks;   
118        node->count    = ntasks;   
119        node->sense    = 0;   
120        node->level    = 0;   
121        node->parent   = parent;
122        node->child[0] = NULL;
123        node->child[1] = NULL;
124        node->child[2] = NULL;
125        node->child[3] = NULL;
126
127#if GIET_DEBUG_USER_BARRIER
128giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n"
129                " parent = %x / child0 = %x / child1 = %x / child0 = %x / child1 = %x\n", 
130                x, y, level, node->arity, 
131                (unsigned int)node->parent,
132                (unsigned int)node->child[0],
133                (unsigned int)node->child[1],
134                (unsigned int)node->child[2],
135                (unsigned int)node->child[3] );
136#endif
137
138    }
139    else                   // non terminal case
140    {
141        unsigned int cx[4];   // x coordinate for children
142        unsigned int cy[4];   // y coordinate for children
143        unsigned int arity = 0;
144        unsigned int i;
145
146        // the child0 coordinates are equal to the parent coordinates
147        // other children coordinates are incremented depending on the level value
148        cx[0] = x;
149        cy[0] = y;
150
151        cx[1] = x + (1 << (level-1));
152        cy[1] = y;
153
154        cx[2] = x;
155        cy[2] = y + (1 << (level-1));
156
157        cx[3] = x + (1 << (level-1));
158        cy[3] = y + (1 << (level-1));
159
160        // initializes target node
161        for ( i = 0 ; i < 4 ; i++ )
162        {
163            if ( (cx[i] < x_size) && (cy[i] < y_size) ) 
164            {
165                node->child[i] = barrier->node[cx[i]][cy[i]][level-1];
166                arity++;
167            }
168            else  node->child[i] = NULL;
169        }
170        node->arity    = arity; 
171        node->count    = arity;
172        node->sense    = 0;
173        node->level    = level;
174        node->parent   = parent;
175
176#if GIET_DEBUG_USER_BARRIER
177giet_shr_printf("[DEBUG USER BARRIER] initialize sqt_node[%d][%d][%d] : arity = %d\n"
178                " parent = %x / child0 = %x / child1 = %x / child0 = %x / child1 = %x\n", 
179                x, y, level, node->arity, 
180                (unsigned int)node->parent,
181                (unsigned int)node->child[0],
182                (unsigned int)node->child[1],
183                (unsigned int)node->child[2],
184                (unsigned int)node->child[3] );
185#endif
186
187        // recursive calls for children nodes
188        for ( i = 0 ; i < 4 ; i++ )
189        {
190            if ( (cx[i] < x_size) && (cy[i] < y_size) ) 
191                sqt_barrier_build( barrier, 
192                                   cx[i], 
193                                   cy[i], 
194                                   level-1, 
195                                   node, 
196                                   x_size,
197                                   y_size,
198                                   ntasks );
199        }
200    }
201}  // end sqt_barrier_build()
202
203////////////////////////////////////////////////////
204void sqt_barrier_init( giet_sqt_barrier_t*  barrier,
205                       unsigned int         x_size,    // number of clusters in a row
206                       unsigned int         y_size,    // number of clusters in a col
207                       unsigned int         ntasks )   // tasks per clusters
208{
209    // check parameters
210    if ( x_size > 16 ) giet_exit("SQT BARRIER ERROR : x_size too large");
211    if ( y_size > 16 ) giet_exit("SQT BARRIER ERROR : y_size too large");
212    if ( ntasks > 8  ) giet_exit("SQT BARRIER ERROR : ntasks too large");
213   
214    // compute SQT levels
215    unsigned int levels; 
216    unsigned int side; 
217    unsigned int z = (x_size > y_size) ? x_size : y_size;
218    levels = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 3 : (z < 9) ? 4 : 5;
219    side   = (z < 2) ? 1 : (z < 3) ? 2 : (z < 5) ? 4 : (z < 9) ? 8 : 16;
220
221#if GIET_DEBUG_USER_BARRIER
222giet_shr_printf("\n[DEBUG USER BARRIER] sqt_nodes allocation\n"
223                " x_size = %d / y_size = %d / levels = %d / side = %d\n",
224                x_size , y_size , levels , side );
225#endif
226
227    // allocates memory for the SQT nodes and initializes SQT nodes pointers array
228    // the number of SQT nodes in a cluster(x,y) depends on (x,y):
229    // At least 1 node / at most 5 nodes
230    unsigned int x;          // x coordinate for one SQT node
231    unsigned int y;          // y coordinate for one SQT node
232    unsigned int l;          // level for one SQT node
233    for ( x = 0 ; x < x_size ; x++ )
234    {
235        for ( y = 0 ; y < y_size ; y++ )
236        {
237            for ( l = 0 ; l < levels ; l++ )         
238            {
239               
240                if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) ||
241                     ( (l == 1) && ((x&0x01) == 0) && ((y&0x01) == 0) ) ||
242                     ( (l == 2) && ((x&0x03) == 0) && ((y&0x03) == 0) ) ||
243                     ( (l == 3) && ((x&0x07) == 0) && ((y&0x07) == 0) ) ||
244                     ( (l == 4) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
245                 {
246                     barrier->node[x][y][l] = remote_malloc( sizeof(sqt_node_t), 
247                                                             x, y );
248
249#if GIET_DEBUG_USER_BARRIER
250giet_shr_printf("[DEBUG USER BARRIER] SQT node[%d][%d][%d] : vaddr = %x\n",
251                x, y, l, (unsigned int)barrier->node[x][y][l] );
252#endif
253                 }
254            }
255        }
256    }
257           
258    // recursively initialize all SQT nodes from root to bottom
259    sqt_barrier_build( barrier,
260                       0,       
261                       0,
262                       levels-1,
263                       NULL,
264                       x_size,
265                       y_size,
266                       ntasks );
267
268    asm volatile ("sync" ::: "memory");
269
270}  // end sqt_barrier_init
271
272
273 
274///////////////////////////////////////
275static
276void sqt_barrier_decrement( sqt_node_t* node )
277{
278    // This recursive function decrements the distributed "count" variables,
279    // traversing the SQT from bottom to root.
280    // The last arrived task reset the local node before returning.
281
282#if GIET_DEBUG_USER_BARRIER
283unsigned int    px;
284unsigned int    py;
285unsigned int    pl;
286giet_proc_xyp( &px, &py, &pl );
287giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] decrement SQT barrier node %x :\n"
288                " level = %d / arity = %d / sense = %d / count = %d\n",
289                px , py , pl , (unsigned int)node , 
290                node->level , node->arity , node->sense , node->count );
291#endif
292
293    // compute expected sense value
294    unsigned int expected;
295    if ( node->sense == 0) expected = 1;
296    else                   expected = 0;
297
298    // atomic decrement
299    // - input  : count address (pcount)
300    // - output : modified counter value (count)
301    unsigned int*  pcount    = (unsigned int*)&node->count;
302    unsigned int   count     = 0;  // avoid a warning
303
304    asm volatile( "addu   $2,     %1,        $0      \n"
305                  "sqt_llsc:                         \n"
306                  "ll     $8,     0($2)              \n"
307                  "addi   $9,     $8,        -1      \n"
308                  "sc     $9,     0($2)              \n"
309                  "beqz   $9,     sqt_llsc           \n"
310                  "addu   %0,     $8,        $0      \n"
311                  : "=r" (count)
312                  : "r" (pcount)
313                  : "$2", "$8", "$9", "memory" );
314
315    if ( count == 1 )    // last task 
316    {
317        // decrement the parent node if the current node is not the root
318        if ( node->parent != NULL )     
319            sqt_barrier_decrement( node->parent );
320
321        // reset the current node
322        node->sense = expected;
323        node->count = node->arity;
324
325#if GIET_DEBUG_USER_BARRIER
326giet_shr_printf("\n[DEBUG USER BARRIER] P[%d,%d,%d] reset SQT barrier node %x :\n"
327                " level = %d / arity = %d / sense = %d / count = %d\n",
328                px , py , pl , (unsigned int)node , 
329                node->level , node->arity , node->sense , node->count );
330#endif
331        return;
332    }
333    else                 // not the last task
334    {
335        // poll sense flag
336        // input: pointer on the sens flag (psense)
337        // input: expected sense value (expected)
338        unsigned int* psense  = (unsigned int *)&node->sense;
339        asm volatile ( "sqt_sense:                       \n"
340                       "lw    $3,   0(%0)                \n"
341                       "bne   $3,   %1,    sqt_sense     \n"
342                       :
343                       : "r"(psense), "r"(expected)
344                       : "$3" );
345        return;
346    }
347} // end sqt_decrement()
348   
349////////////////////////////////////////////////////
350void sqt_barrier_wait( giet_sqt_barrier_t* barrier )
351{
352    // compute cluster coordinates for the calling task
353    unsigned int    x;
354    unsigned int    y;
355    unsigned int    lpid;
356    giet_proc_xyp( &x, &y, &lpid );
357
358    // recursively decrement count from bottom to root
359    sqt_barrier_decrement( barrier->node[x][y][0] );
360
361    asm volatile ("sync" ::: "memory");
362
363}  // end sqt_barrier_wait()
364
365
366// Local Variables:
367// tab-width: 4
368// c-basic-offset: 4
369// c-file-offsets:((innamespace . 0)(inline-open . 0))
370// indent-tabs-mode: nil
371// End:
372// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4
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.