Ignore:
Timestamp:
Jul 31, 2014, 8:47:14 PM (10 years ago)
Author:
alain
Message:

1) Introducing the SBT barrier (Sliced Binary Tree)

in the barrier.h library.

2) Introducing a new remote_malloc.h library.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/giet_libs/barrier.c

    r352 r368  
    55// Copyright (c) UPMC-LIP6
    66///////////////////////////////////////////////////////////////////////////////////
    7 // These barrier.c and barrier.h files are part of the GIET nano-kernel.
    8 // This user-level library provides a synchronisation service between several
    9 // tasks sharing the same address space in a parallel multi-tasks application.
    10 // Neither the barrier_init(), nor the barrier_wait() function require a syscall.
    11 // The barrier itself must have been allocated in a shared data segment.
    12 ///////////////////////////////////////////////////////////////////////////////////
    137
    148#include "barrier.h"
    15 
    16 ///////////////////////////////////////////////////////////////////////////////////
    17 // This function initializes the barrier: this should be done by a single task.
    18 ///////////////////////////////////////////////////////////////////////////////////
     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///////////////////////////////////////////
    1920void barrier_init( giet_barrier_t* barrier,
    20                    unsigned int    value )
    21 {
    22     barrier->init  = (volatile unsigned int)value;
    23     barrier->count = (volatile unsigned int)value;
     21                   unsigned int    ntasks )
     22{
     23    barrier->ntasks = ntasks;
     24    barrier->count  = ntasks;
     25    barrier->sense  = 0;
     26
    2427    asm volatile ("sync" ::: "memory");
    2528}
    2629
    27 
    28 ///////////////////////////////////////////////////////////////////////////////////
    29 // This blocking function uses LL/SC to decrement the barrier's counter.
    30 // Then, it uses a busy_waiting mechanism if it is not the last.
    31 ///////////////////////////////////////////////////////////////////////////////////
     30////////////////////////////////////////////
    3231void barrier_wait( giet_barrier_t* barrier )
    3332{
    34     volatile unsigned int * pcount = (unsigned int *) &barrier->count;
    35     volatile unsigned int maxcount = barrier->init;
    36     volatile unsigned int count = 0;
     33    // compute expected sense value
     34    unsigned int expected;
     35    if ( barrier->sense == 0 ) expected = 1;
     36    else                       expected = 0;
    3737
    3838    // parallel decrement barrier counter using atomic instructions LL/SC
    39     // - input : pointer on the barrier counter
    40     // - output : counter value
    41     asm volatile (
    42             "_barrier_decrement:                \n"
    43             "ll     %0,   0(%1)                 \n"
    44             "addi   $3,   %0,     -1            \n"
    45             "sc     $3,   0(%1)                 \n"
    46             "beqz   $3,   _barrier_decrement    \n"
    47             : "+r"(count)
    48             : "r"(pcount)
    49             : "$3", "memory");
    50 
    51     // the last task re-initializes the barrier counter to the max value,
     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,
    5254    // waking up all other waiting tasks
    53 
    54     if (count == 1)
    55     {
    56         // last task
    57         *pcount = maxcount;
    58     }
    59     else {
    60         // other tasks busy-wait
    61         while (*pcount != maxcount);
     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" );
    6272    }
    6373
    6474    asm volatile ("sync" ::: "memory");
    6575}
     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
    66376
    67377// Local Variables:
Note: See TracChangeset for help on using the changeset viewer.