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

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

Major evolution of the malloc library, to provide two new services:

  • all allocated blocks are aligned, and the size is a power of 2.
  • the remote-malloc() function allows the application to explicitely define the cluster(x,y).

We keep only the close-fit allocation policy.
These services were required to implement the distributed SBT barrier.
  • Property svn:executable set to *
File size: 13.0 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    // 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, 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#if GIET_DEBUG_SBT
250giet_shr_printf("[DEBUG SBT] initialize node[%d][%d][%d] :"
251                " arity = %d / child0 = %x / child1 = %x\n", 
252                x, y, level, 
253                node->arity, node->child0, node->child1 );
254#endif
255
256    }
257    else                   // non terminal case
258    {
259        unsigned int x0;   // x coordinate for child0
260        unsigned int y0;   // y coordinate for child0;
261        unsigned int x1;   // x coordinate for child1;
262        unsigned int y1;   // y coordinate for child1;
263
264        // the child0 coordinates are equal to the parent coordinates
265        // the child1 coordinates are incremented depending on the level value
266        if ( level & 0x1 ) // odd level => X binary tree
267        {
268            x0 = x;
269            y0 = y;
270            x1 = x + (1 << ((level-1)>>1));
271            y1 = y;
272        }   
273        else               // even level => Y binary tree
274        {
275            x0 = x;
276            y0 = y;
277            x1 = x;
278            y1 = y + (1 << ((level-1)>>1));
279        }
280
281        // initializes target node
282        node->arity    = 2;
283        node->count    = 2;
284        node->sense    = 0;   
285        node->level    = level;
286        node->parent   = parent;
287        node->child0   = barrier->node[x0][y0][level-1];
288        node->child1   = barrier->node[x1][y1][level-1];
289
290#if GIET_DEBUG_SBT
291giet_shr_printf("[DEBUG SBT] initialize node[%d][%d][%d] :"
292                " arity = %d / child0 = %x / child1 = %x\n", 
293                x, y, level, 
294                node->arity, node->child0, node->child1 );
295#endif
296
297        // recursive calls for children nodes
298        sbt_build( barrier , x0 , y0 , level-1 , node );
299        sbt_build( barrier , x1 , y1 , level-1 , node );
300    }
301
302}  // end sbt_build()
303
304 
305///////////////////////////////////////
306void sbt_decrement( sbt_node_t* node )
307{
308    // This recursive function decrements the distributed "count" variables,
309    // traversing the SBT from bottom to root.
310
311    // compute expected sense value (toggle)
312    unsigned int expected;
313    if ( node->sense == 0) expected = 1;
314    else                   expected = 0;
315
316    // atomic decrement
317    // - input  : count address (pcount)
318    // - output : modified counter value (count)
319    unsigned int*  pcount    = (unsigned int*)&node->count;
320    unsigned int   count     = 0;  // avoid a warning
321
322    asm volatile( "addu   $2,     %1,        $0      \n"
323                  "sbt_llsc:                         \n"
324                  "ll     $8,     0($2)              \n"
325                  "addi   $9,     $8,        -1      \n"
326                  "sc     $9,     0($2)              \n"
327                  "beqz   $9,     sbt_llsc           \n"
328                  "addu   %0,     $8,        $0      \n"
329                  : "=r" (count)
330                  : "r" (pcount)
331                  : "$2", "$8", "$9", "memory" );
332
333    if ( count == 1 )    // last task for this level
334    {
335        if ( node->parent == NULL )            // root node : call sbt_release()
336        {
337            sbt_release( node, expected );
338        }
339        else                                   // call sbt_decrement() for parent
340        {
341            sbt_decrement( node->parent );
342        }
343    }
344    else                 // not the last: busy waiting on current "sense" flag
345    {
346        // polling sense flag
347        // input: pointer on the sens flag (psense)
348        // input: expected sense value (expected)
349        volatile unsigned int* psense  = (unsigned int *)&node->sense;
350        asm volatile ( "sbt_sense:                       \n"
351                       "lw    $3,   0(%0)                \n"
352                       "bne   $3,   %1,    sbt_sense     \n"
353                       :
354                       : "r"(psense), "r"(expected)
355                       : "$3" );
356    }
357} // end sbt_decrement()
358   
359
360///////////////////////////////////
361void sbt_release( sbt_node_t* node,
362                  unsigned int expected )
363{
364    // This recursive function reset all sense and count variables
365    // traversing the SBT from root to bottom
366
367    // toggle sense flag for the target node
368    node->sense = expected;
369
370    // re-initialise count for the target node
371    node->count = node->arity;
372
373    // call recursively sbt_release() for children if not terminal
374    if ( node->level > 0 )
375    {
376        sbt_release( node->child0, expected );
377        sbt_release( node->child1, expected );
378    }
379}  // end sbt_release()
380
381// Local Variables:
382// tab-width: 4
383// c-basic-offset: 4
384// c-file-offsets:((innamespace . 0)(inline-open . 0))
385// indent-tabs-mode: nil
386// End:
387// vim: filetype=c:expandtab:shiftwidth=4:tabsroot=4:softtabsroot=4
388
389// Local Variables:
390// tab-width: 4
391// c-basic-offset: 4
392// c-file-offsets:((innamespace . 0)(inline-open . 0))
393// indent-tabs-mode: nil
394// End:
395// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
396
Note: See TracBrowser for help on using the repository browser.