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

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

1) Change the user sbt_barrier_init() prototype: the two (nclusters/ntasks) arguments
replace the single (ntasks) argument.
2) Introduce an explicit (channel) argument in all iuser access functions to the NIC component.
Previously, the channel registered in the task context was an implicit argument.
The channel is still registered in the task context for checking.
  • Property svn:executable set to *
File size: 13.2 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         nclusters,    // number of clusters
101                       unsigned int         ntasks )      // tasks per clusters
102{
103    unsigned int x;          // x coordinate for one SBT node
104    unsigned int y;          // y coordinate for one SBT node
105    unsigned int l;          // level for one SBT node
106    unsigned int x_size;     // max number of clusters in a row for the SBT
107    unsigned int y_size;     // max number of clusters in a column for the SBT
108    unsigned int levels;     // depth of the SBT (number of levels)
109
110    // compute SBT characteristics
111    if      ( nclusters == 1 )  // mesh 1*1
112    {
113        x_size    = 1;
114        y_size    = 1;
115        levels    = 1;
116    }
117    else if ( nclusters == 2 )  // mesh 2*1
118    {
119        x_size    = 2;
120        y_size    = 1;
121        levels    = 2;
122    }
123    else if ( nclusters == 4 )  // mesh 2*2
124    {
125        x_size    = 2;
126        y_size    = 2;
127        levels    = 3;
128    }
129    else if ( nclusters == 8 )  // mesh 4*2
130    {
131        x_size    = 4;
132        y_size    = 2;
133        levels    = 4;
134    }
135    else if ( nclusters == 16 )  // mesh 4*4
136    {
137        x_size    = 4;
138        y_size    = 4;
139        levels    = 5;
140    }
141    else if ( nclusters == 32 )  // mesh 8*4
142    {
143        x_size    = 8;
144        y_size    = 4;
145        levels    = 6;
146    }
147    else if ( nclusters == 64 )  // mesh 8*8
148    {
149        x_size    = 8;
150        y_size    = 8;
151        levels    = 7;
152    }
153    else if ( nclusters == 128 )  // mesh 16*8
154    {
155        x_size    = 16;
156        y_size    = 8;
157        levels    = 8; 
158    }
159    else if ( nclusters == 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() : nclusters must be power of 2\n");
171    }
172
173    // ntasks initialisation
174    barrier->ntasks = ntasks * nclusters;
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, ntasks );
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                unsigned int         ntasks ) 
244{
245    // This recursive function initializes the SBT notes
246    // traversing the SBT from root to bottom
247
248    // get target node address
249    sbt_node_t* node = barrier->node[x][y][level];
250   
251    if (level == 0 )        // terminal case
252    {
253        // initializes target node
254        node->arity    = ntasks;   
255        node->count    = ntasks;   
256        node->sense    = 0;   
257        node->level    = 0;   
258        node->parent   = parent;
259        node->child0   = NULL;
260        node->child1   = NULL;
261
262#if GIET_DEBUG_USER_BARRIER
263giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :"
264                " arity = %d / child0 = %x / child1 = %x\n", 
265                x, y, level, 
266                node->arity, node->child0, node->child1 );
267#endif
268
269    }
270    else                   // non terminal case
271    {
272        unsigned int x0;   // x coordinate for child0
273        unsigned int y0;   // y coordinate for child0;
274        unsigned int x1;   // x coordinate for child1;
275        unsigned int y1;   // y coordinate for child1;
276
277        // the child0 coordinates are equal to the parent coordinates
278        // the child1 coordinates are incremented depending on the level value
279        if ( level & 0x1 ) // odd level => X binary tree
280        {
281            x0 = x;
282            y0 = y;
283            x1 = x + (1 << ((level-1)>>1));
284            y1 = y;
285        }   
286        else               // even level => Y binary tree
287        {
288            x0 = x;
289            y0 = y;
290            x1 = x;
291            y1 = y + (1 << ((level-1)>>1));
292        }
293
294        // initializes target node
295        node->arity    = 2;
296        node->count    = 2;
297        node->sense    = 0;   
298        node->level    = level;
299        node->parent   = parent;
300        node->child0   = barrier->node[x0][y0][level-1];
301        node->child1   = barrier->node[x1][y1][level-1];
302
303#if GIET_DEBUG_USER_BARRIER
304giet_shr_printf("[DEBUG BARRIER] initialize sbt_node[%d][%d][%d] :"
305                " arity = %d / child0 = %x / child1 = %x\n", 
306                x, y, level, 
307                node->arity, node->child0, node->child1 );
308#endif
309
310        // recursive calls for children nodes
311        sbt_build( barrier , x0 , y0 , level-1 , node , ntasks );
312        sbt_build( barrier , x1 , y1 , level-1 , node , ntasks );
313    }
314
315}  // end sbt_build()
316
317 
318///////////////////////////////////////
319void sbt_decrement( sbt_node_t* node )
320{
321    // This recursive function decrements the distributed "count" variables,
322    // traversing the SBT from bottom to root.
323
324    // compute expected sense value (toggle)
325    unsigned int expected;
326    if ( node->sense == 0) expected = 1;
327    else                   expected = 0;
328
329    // atomic decrement
330    // - input  : count address (pcount)
331    // - output : modified counter value (count)
332    unsigned int*  pcount    = (unsigned int*)&node->count;
333    unsigned int   count     = 0;  // avoid a warning
334
335    asm volatile( "addu   $2,     %1,        $0      \n"
336                  "sbt_llsc:                         \n"
337                  "ll     $8,     0($2)              \n"
338                  "addi   $9,     $8,        -1      \n"
339                  "sc     $9,     0($2)              \n"
340                  "beqz   $9,     sbt_llsc           \n"
341                  "addu   %0,     $8,        $0      \n"
342                  : "=r" (count)
343                  : "r" (pcount)
344                  : "$2", "$8", "$9", "memory" );
345
346    if ( count == 1 )    // last task for this level
347    {
348        if ( node->parent == NULL )            // root node : call sbt_release()
349        {
350            sbt_release( node, expected );
351        }
352        else                                   // call sbt_decrement() for parent
353        {
354            sbt_decrement( node->parent );
355        }
356    }
357    else                 // not the last: busy waiting on current "sense" flag
358    {
359        // polling sense flag
360        // input: pointer on the sens flag (psense)
361        // input: expected sense value (expected)
362        volatile unsigned int* psense  = (unsigned int *)&node->sense;
363        asm volatile ( "sbt_sense:                       \n"
364                       "lw    $3,   0(%0)                \n"
365                       "bne   $3,   %1,    sbt_sense     \n"
366                       :
367                       : "r"(psense), "r"(expected)
368                       : "$3" );
369    }
370} // end sbt_decrement()
371   
372
373///////////////////////////////////
374void sbt_release( sbt_node_t* node,
375                  unsigned int expected )
376{
377    // This recursive function reset all sense and count variables
378    // traversing the SBT from root to bottom
379
380    // toggle sense flag for the target node
381    node->sense = expected;
382
383    // re-initialise count for the target node
384    node->count = node->arity;
385
386    // call recursively sbt_release() for children if not terminal
387    if ( node->level > 0 )
388    {
389        sbt_release( node->child0, expected );
390        sbt_release( node->child1, expected );
391    }
392}  // end sbt_release()
393
394// Local Variables:
395// tab-width: 4
396// c-basic-offset: 4
397// c-file-offsets:((innamespace . 0)(inline-open . 0))
398// indent-tabs-mode: nil
399// End:
400// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4
401
402// Local Variables:
403// tab-width: 4
404// c-basic-offset: 4
405// c-file-offsets:((innamespace . 0)(inline-open . 0))
406// indent-tabs-mode: nil
407// End:
408// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
409
Note: See TracBrowser for help on using the repository browser.