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

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

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