source: soft/giet_vm/giet_libs/barrier.c @ 481

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

Cosmetic: Improving debug.
  • Property svn:executable set to *
File size: 13.1 KB
Line 
1//////////////////////////////////////////////////////////////////////////////////
2// File     : barrier.c     
3// Date     : 01/04/2012
4// Author   : alain greiner
5// Copyright (c) UPMC-LIP6
6///////////////////////////////////////////////////////////////////////////////////
7
8#include "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->ntasks = 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 BARRIER] proc[%d,%d,%d] enters barrier_wait()\n", x, y, p );
38#endif
39
40    // compute expected sense value
41    unsigned int expected;
42    if ( barrier->sense == 0 ) expected = 1;
43    else                       expected = 0;
44
45    // parallel decrement barrier counter using atomic instructions LL/SC
46    // - input : pointer on the barrier counter (pcount)
47    // - output : counter value (count)
48    volatile unsigned int* pcount  = (unsigned int *)&barrier->count;
49    volatile unsigned int  count    = 0;  // avoid a warning
50
51    asm volatile( "addu   $2,     %1,        $0      \n"
52                  "barrier_llsc:                     \n"
53                  "ll     $8,     0($2)              \n"
54                  "addi   $9,     $8,        -1      \n"
55                  "sc     $9,     0($2)              \n"
56                  "beqz   $9,     barrier_llsc       \n"
57                  "addu   %0,     $8,        $0      \n"
58                  : "=r" (count)
59                  : "r" (pcount)
60                  : "$2", "$8", "$9", "memory" );
61
62    // the last task re-initializes count and toggle sense,
63    // waking up all other waiting tasks
64    if (count == 1)   // last task
65    {
66        barrier->count = barrier->ntasks;
67        barrier->sense = expected;
68    }
69    else              // other tasks busy waiting the sense flag
70    {
71        // polling sense flag
72        // input: pointer on the sens flag (psense)
73        // input: expected sense value (expected)
74        volatile unsigned int* psense  = (unsigned int *)&barrier->sense;
75        asm volatile ( "barrier_sense:                   \n"
76                       "lw    $3,   0(%0)                \n"
77                       "bne   $3,   %1,    barrier_sense \n"
78                       :
79                       : "r"(psense), "r"(expected)
80                       : "$3" );
81    }
82
83    asm volatile ("sync" ::: "memory");
84
85#if GIET_DEBUG_USER_BARRIER
86giet_shr_printf("[DEBUG BARRIER] proc[%d,%d,%d] exit barrier_wait()\n", x, y, p );
87#endif
88
89}
90
91///////////////////////////////////////////////////////////////////////////////////
92///////////////////////////////////////////////////////////////////////////////////
93//      SBT barrier access functions
94///////////////////////////////////////////////////////////////////////////////////
95///////////////////////////////////////////////////////////////////////////////////
96
97
98////////////////////////////////////////////////////
99void sbt_barrier_init( giet_sbt_barrier_t*  barrier,
100                       unsigned int         ntasks )
101{
102    unsigned int x;          // x coordinate for one SBT node
103    unsigned int y;          // y coordinate for one SBT node
104    unsigned int l;          // level for one SBT node
105    unsigned int x_size;     // max number of clusters in a row for the SBT
106    unsigned int y_size;     // max number of clusters in a column for the SBT
107    unsigned int levels;     // depth of the SBT (number of levels)
108
109
110    // compute SBT characteristics
111    if      ( ntasks == NB_PROCS_MAX       )  // mesh 1*1
112    {
113        x_size    = 1;
114        y_size    = 1;
115        levels    = 1;
116    }
117    else if ( ntasks == NB_PROCS_MAX * 2   )  // mesh 2*1
118    {
119        x_size    = 2;
120        y_size    = 1;
121        levels    = 2;
122    }
123    else if ( ntasks == NB_PROCS_MAX * 4   )  // mesh 2*2
124    {
125        x_size    = 2;
126        y_size    = 2;
127        levels    = 3;
128    }
129    else if ( ntasks == NB_PROCS_MAX * 8   )  // mesh 4*2
130    {
131        x_size    = 4;
132        y_size    = 2;
133        levels    = 4;
134    }
135    else if ( ntasks == NB_PROCS_MAX * 16  )  // mesh 4*4
136    {
137        x_size    = 4;
138        y_size    = 4;
139        levels    = 5;
140    }
141    else if ( ntasks == NB_PROCS_MAX * 32  )  // mesh 8*4
142    {
143        x_size    = 8;
144        y_size    = 4;
145        levels    = 6;
146    }
147    else if ( ntasks == NB_PROCS_MAX * 64  )  // mesh 8*8
148    {
149        x_size    = 8;
150        y_size    = 8;
151        levels    = 7;
152    }
153    else if ( ntasks == NB_PROCS_MAX * 128 )  // mesh 16*8
154    {
155        x_size    = 16;
156        y_size    = 8;
157        levels    = 8; 
158    }
159    else if ( ntasks == NB_PROCS_MAX * 256 )  // mesh 16*16
160    {
161        x_size    = 16;
162        y_size    = 16;
163        levels    = 9;
164    }
165    else
166    {
167        x_size    = 0;  // avoid warning
168        y_size    = 0;
169        levels    = 0;
170        giet_exit("error in tree_barrier_init() : number of tasks must be power of 2\n");
171    }
172
173    // ntasks initialisation
174    barrier->ntasks = ntasks;
175   
176#if GIET_DEBUG_USER_BARRIER
177giet_shr_printf("\n[DEBUG BARRIER] sbt_nodes allocation / ntasks = %d\n", ntasks ); 
178#endif
179
180    // allocates memory for the SBT nodes and initializes SBT nodes pointers array
181    // the number of SBT nodes in a cluster(x,y) depends on (x,y).
182    // At least 1 node / at most 9 nodes
183    for ( x = 0 ; x < x_size ; x++ )
184    {
185        for ( y = 0 ; y < y_size ; y++ )
186        {
187            for ( l = 0 ; l < levels ; l++ )             // level 0 nodes
188            {
189               
190                if ( ( (l == 0) && ((x&0x00) == 0) && ((y&0x00) == 0) ) ||
191                     ( (l == 1) && ((x&0x01) == 0) && ((y&0x00) == 0) ) ||
192                     ( (l == 2) && ((x&0x01) == 0) && ((y&0x01) == 0) ) ||
193                     ( (l == 3) && ((x&0x03) == 0) && ((y&0x01) == 0) ) ||
194                     ( (l == 4) && ((x&0x03) == 0) && ((y&0x03) == 0) ) ||
195                     ( (l == 5) && ((x&0x07) == 0) && ((y&0x03) == 0) ) ||
196                     ( (l == 6) && ((x&0x07) == 0) && ((y&0x07) == 0) ) ||
197                     ( (l == 7) && ((x&0x0F) == 0) && ((y&0x07) == 0) ) ||
198                     ( (l == 8) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
199                 {
200                     barrier->node[x][y][l] = remote_malloc( sizeof(sbt_node_t), x, y );
201
202#if GIET_DEBUG_USER_BARRIER
203giet_shr_printf("[DEBUG SBT] node[%d][%d][%d] : vaddr = %x\n",
204                x, y, l, (unsigned int)barrier->node[x][y][l] );
205#endif
206                 }
207            }
208        }
209    }
210           
211#if GIET_DEBUG_USER_BARRIER
212giet_shr_printf("\n[DEBUG SBT] SBT nodes initialisation\n"); 
213#endif
214
215    // recursively initialize all SBT nodes from root to bottom
216    sbt_build( barrier, 0, 0, levels-1, NULL );
217
218    asm volatile ("sync" ::: "memory");
219}
220
221////////////////////////////////////////////////////
222void sbt_barrier_wait( giet_sbt_barrier_t* barrier )
223{
224    // compute cluster coordinates for the calling task
225    unsigned int    x;
226    unsigned int    y;
227    unsigned int    lpid;
228    giet_proc_xyp( &x, &y, &lpid );
229
230    // recursively decrement count from bottom to root
231    sbt_decrement( barrier->node[x][y][0] );
232
233    asm volatile ("sync" ::: "memory");
234}
235
236
237/////////////////////////////////////////////
238void sbt_build( giet_sbt_barrier_t*  barrier, 
239                unsigned int         x,
240                unsigned int         y,
241                unsigned int         level,
242                sbt_node_t*          parent ) 
243{
244    // This recursive function initializes the SBT notes
245    // traversing the SBT from root to bottom
246
247    // get target node address
248    sbt_node_t* node = barrier->node[x][y][level];
249   
250    if (level == 0 )        // terminal case
251    {
252        // initializes target node
253        node->arity    = NB_PROCS_MAX;   
254        node->count    = NB_PROCS_MAX;   
255        node->sense    = 0;   
256        node->level    = 0;   
257        node->parent   = parent;
258        node->child0   = NULL;
259        node->child1   = NULL;
260
261#if GIET_DEBUG_USER_BARRIER
262giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :"
263                " arity = %d / child0 = %x / child1 = %x\n", 
264                x, y, level, 
265                node->arity, node->child0, node->child1 );
266#endif
267
268    }
269    else                   // non terminal case
270    {
271        unsigned int x0;   // x coordinate for child0
272        unsigned int y0;   // y coordinate for child0;
273        unsigned int x1;   // x coordinate for child1;
274        unsigned int y1;   // y coordinate for child1;
275
276        // the child0 coordinates are equal to the parent coordinates
277        // the child1 coordinates are incremented depending on the level value
278        if ( level & 0x1 ) // odd level => X binary tree
279        {
280            x0 = x;
281            y0 = y;
282            x1 = x + (1 << ((level-1)>>1));
283            y1 = y;
284        }   
285        else               // even level => Y binary tree
286        {
287            x0 = x;
288            y0 = y;
289            x1 = x;
290            y1 = y + (1 << ((level-1)>>1));
291        }
292
293        // initializes target node
294        node->arity    = 2;
295        node->count    = 2;
296        node->sense    = 0;   
297        node->level    = level;
298        node->parent   = parent;
299        node->child0   = barrier->node[x0][y0][level-1];
300        node->child1   = barrier->node[x1][y1][level-1];
301
302#if GIET_DEBUG_USER_BARRIER
303giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :"
304                " arity = %d / child0 = %x / child1 = %x\n", 
305                x, y, level, 
306                node->arity, node->child0, node->child1 );
307#endif
308
309        // recursive calls for children nodes
310        sbt_build( barrier , x0 , y0 , level-1 , node );
311        sbt_build( barrier , x1 , y1 , level-1 , node );
312    }
313
314}  // end sbt_build()
315
316 
317///////////////////////////////////////
318void sbt_decrement( sbt_node_t* node )
319{
320    // This recursive function decrements the distributed "count" variables,
321    // traversing the SBT from bottom to root.
322
323    // compute expected sense value (toggle)
324    unsigned int expected;
325    if ( node->sense == 0) expected = 1;
326    else                   expected = 0;
327
328    // atomic decrement
329    // - input  : count address (pcount)
330    // - output : modified counter value (count)
331    unsigned int*  pcount    = (unsigned int*)&node->count;
332    unsigned int   count     = 0;  // avoid a warning
333
334    asm volatile( "addu   $2,     %1,        $0      \n"
335                  "sbt_llsc:                         \n"
336                  "ll     $8,     0($2)              \n"
337                  "addi   $9,     $8,        -1      \n"
338                  "sc     $9,     0($2)              \n"
339                  "beqz   $9,     sbt_llsc           \n"
340                  "addu   %0,     $8,        $0      \n"
341                  : "=r" (count)
342                  : "r" (pcount)
343                  : "$2", "$8", "$9", "memory" );
344
345    if ( count == 1 )    // last task for this level
346    {
347        if ( node->parent == NULL )            // root node : call sbt_release()
348        {
349            sbt_release( node, expected );
350        }
351        else                                   // call sbt_decrement() for parent
352        {
353            sbt_decrement( node->parent );
354        }
355    }
356    else                 // not the last: busy waiting on current "sense" flag
357    {
358        // polling sense flag
359        // input: pointer on the sens flag (psense)
360        // input: expected sense value (expected)
361        volatile unsigned int* psense  = (unsigned int *)&node->sense;
362        asm volatile ( "sbt_sense:                       \n"
363                       "lw    $3,   0(%0)                \n"
364                       "bne   $3,   %1,    sbt_sense     \n"
365                       :
366                       : "r"(psense), "r"(expected)
367                       : "$3" );
368    }
369} // end sbt_decrement()
370   
371
372///////////////////////////////////
373void sbt_release( sbt_node_t* node,
374                  unsigned int expected )
375{
376    // This recursive function reset all sense and count variables
377    // traversing the SBT from root to bottom
378
379    // toggle sense flag for the target node
380    node->sense = expected;
381
382    // re-initialise count for the target node
383    node->count = node->arity;
384
385    // call recursively sbt_release() for children if not terminal
386    if ( node->level > 0 )
387    {
388        sbt_release( node->child0, expected );
389        sbt_release( node->child1, expected );
390    }
391}  // end sbt_release()
392
393// Local Variables:
394// tab-width: 4
395// c-basic-offset: 4
396// c-file-offsets:((innamespace . 0)(inline-open . 0))
397// indent-tabs-mode: nil
398// End:
399// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4
400
401// Local Variables:
402// tab-width: 4
403// c-basic-offset: 4
404// c-file-offsets:((innamespace . 0)(inline-open . 0))
405// indent-tabs-mode: nil
406// End:
407// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
408
Note: See TracBrowser for help on using the repository browser.