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

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

1) Introducing the SBT barrier (Sliced Binary Tree)

in the barrier.h library.

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