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

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

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