Changeset 582 for trunk


Ignore:
Timestamp:
Oct 11, 2018, 5:04:28 PM (6 years ago)
Author:
alain
Message:

New DQDT implementation supporting missing clusters
thanks to the cluster_info[x][y] array.

Location:
trunk
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/kernel/kern/cluster.c

    r580 r582  
    119119#endif
    120120
    121     // initialises DQDT
    122     cluster->dqdt_root_level = dqdt_init( info->x_size,
    123                                           info->y_size ) - 1;
    124 
    125 #if( DEBUG_CLUSTER_INIT & 1 )
    126 cycle = (uint32_t)hal_get_cycles();
    127 if( DEBUG_CLUSTER_INIT < cycle )
    128 printk("\n[DBG] %s : DQDT initialized in cluster %x / cycle %d\n",
    129 __FUNCTION__ , local_cxy , cycle );
    130 #endif
    131 
    132121    // initialises embedded PPM
    133122        error = hal_ppm_init( info );
  • trunk/kernel/kern/cluster.h

    r564 r582  
    138138    dqdt_node_t     dqdt_tbl[CONFIG_DQDT_LEVELS_NR];     /*! embedded DQDT nodes          */
    139139
     140    xptr_t          dqdt_root_xp;      /*! extended pointer on DQDT root node             */
     141
    140142    // Local process manager
    141143    pmgr_t          pmgr;              /*! embedded process manager                       */
  • trunk/kernel/kern/dqdt.c

    r564 r582  
    2525#include <hal_kernel_types.h>
    2626#include <hal_special.h>
     27#include <hal_macros.h>
    2728#include <hal_atomic.h>
    2829#include <hal_remote.h>
     
    4041extern chdev_directory_t  chdev_dir;  // defined in chdev.h / allocated in kernel_init.c
    4142
    42 /*
    4343///////////////////////////////////////////////////////////////////////////////////////////
    4444// This static recursive function traverse the DQDT quad-tree from root to bottom.
     
    4646static void dqdt_recursive_print( xptr_t  node_xp )
    4747{
    48         uint32_t i;
     48        uint32_t x;
     49        uint32_t y;
    4950    dqdt_node_t node;
    5051
     
    5960    if ( node.level > 0 )
    6061    {
    61         for ( i = 0 ; i < 4 ; i++ )
    62         {
    63             if ( node.children[i] != XPTR_NULL ) dqdt_recursive_print( node.children[i] );
     62        for ( x = 0 ; x < 2 ; x++ )
     63        {
     64            for ( y = 0 ; y < 2 ; y++ )
     65            {
     66                xptr_t iter_xp = node.children[x][y];
     67                if ( iter_xp != XPTR_NULL ) dqdt_recursive_print( iter_xp );
     68            }
    6469        }
    6570    }
    6671}
    67 */
    6872
    6973/////////////////////////
    7074void dqdt_display( void )
    7175{
    72     return;
    73 
    74 /*
    75     // build extended pointer on DQDT root node
    76         cluster_t * cluster = LOCAL_CLUSTER;
    77     uint32_t    level   = cluster->dqdt_root_level;
    78     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
     76    // get extended pointer on DQDT root node
     77        cluster_t * cluster = &cluster_manager;
     78    xptr_t      root_xp = cluster->dqdt_root_xp;
    7979
    8080    // get pointers on TXT0 chdev
     
    9595    dqdt_recursive_print( root_xp );
    9696
    97     // release lock
     97    // release TXT0 lock
    9898    remote_busylock_release( lock_xp );
    99 */
    100 
    101 }
    102 
    103 ////////////////////////////////////
    104 uint32_t dqdt_init( uint32_t x_size,
    105                     uint32_t y_size )
    106 {
    107     assert( ((x_size <= 32) && (y_size <= 32)) , "illegal mesh size\n");
     99}
     100
     101///////////////////////////////////////////////////////////////////////////////////////
     102// This static function initializes recursively, from top to bottom, the quad-tree
     103// infrastructure. The DQDT nodes are allocated as global variables in each local
     104//  cluster manager. At each level in the quad-tree, this function initializes the
     105// parent DQDT node in the cluster identified by the <cxy> and <level> arguments.
     106// A each level, it selects in each child macro-cluster the precise cluster where
     107// will be placed the the subtree root node, and call recursively itself to
     108// initialize the child node in this cluster.
     109///////////////////////////////////////////////////////////////////////////////////////
     110// @ node cxy  : cluster containing the node to initialize
     111// @ level     : level of node to be initialised
     112// @ parent_xp : extended pointer on the parent node
     113///////////////////////////////////////////////////////////////////////////////////////
     114static void dqdt_recursive_build( cxy_t    node_cxy,
     115                                  uint32_t level,
     116                                  xptr_t   parent_xp )
     117{
     118    assert( (level < 5) , __FUNCTION__, "illegal DQDT level %d\n", level );
     119 
     120    uint32_t node_x;         // node X coordinate
     121    uint32_t node_y;         // node Y coordinate
     122    uint32_t mask;           // to compute associated macro-cluster coordinates
     123    uint32_t node_base_x;    // associated macro_cluster X coordinate
     124    uint32_t node_base_y;    // associated macro_cluster y coordinate
     125    uint32_t half;           // associated macro-cluster half size
     126
     127    // get remote node cluster coordinates
     128    node_x = HAL_X_FROM_CXY( node_cxy );
     129    node_y = HAL_Y_FROM_CXY( node_cxy );
     130       
     131    // get macro-cluster mask and half-size
     132    mask   = (1 << level) - 1;
     133    half   = (level > 0) ? (1 << (level - 1)) : 0;
     134
     135    // get macro-cluster coordinates
     136    node_base_x = node_x & ~mask;
     137    node_base_y = node_y & ~mask;
     138
     139    // get pointer on local cluster manager
     140    cluster_t * cluster = LOCAL_CLUSTER;
     141
     142    // get local pointer on remote node to be initialized
     143    dqdt_node_t * node  = &cluster->dqdt_tbl[level];
     144
     145#if DEBUG_DQDT_INIT
     146printk("\n[DBG] %s : cxy(%d,%d) / level %d / mask %x / half %d / ptr %x\n",
     147__FUNCTION__, node_x, node_y, level, mask, half, node );
     148#endif
     149 
     150    // make remote node default initialisation
     151    hal_remote_memset( XPTR( node_cxy , node ) , 0 , sizeof( dqdt_node_t ) );
     152
     153    // recursive initialisation
     154    if( level == 0 )                      // terminal case
     155    {
     156        // update parent field
     157        hal_remote_s64( XPTR( node_cxy , &node->parent ) , parent_xp );
     158    }
     159    else                                  // non terminal
     160    {
     161        uint32_t x;
     162        uint32_t y;
     163        cxy_t    cxy;
     164        bool_t   found;
     165
     166        // update <level> in remote node
     167        hal_remote_s32( XPTR( node_cxy , &node->level ) , level );
     168
     169        // try to find a valid cluster in child[0][0] macro-cluster
     170        found = false;
     171        for( x = node_base_x ;
     172        (x < (node_base_x + half)) && (found == false) ; x++ )
     173        {
     174            for( y = node_base_y ;
     175            (y < (node_base_y + half)) && (found == false) ; y++ )
     176            {
     177                cxy = HAL_CXY_FROM_XY( x , y );
     178                if( cluster_is_active( cxy ) )
     179                {
     180                    // update <child[0][0]> in remote inode
     181                    hal_remote_s64( XPTR( node_cxy , &node->children[0][0] ),
     182                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     183
     184                    // udate <arity> in remote node
     185                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     186
     187                    // initialize recursively child[0][0] node
     188                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     189   
     190                    // exit loops
     191                    found = true;
     192                }
     193            }
     194        }
     195
     196        // try to find a valid cluster in child[0][1] macro-cluster
     197        found = false;
     198        for( x = node_base_x ;
     199        (x < (node_base_x + half)) && (found == false) ; x++ )
     200        {
     201            for( y = (node_base_y + half) ;
     202            (y < (node_base_y + (half<<2))) && (found == false) ; y++ )
     203            {
     204                cxy = HAL_CXY_FROM_XY( x , y );
     205                if( cluster_is_active( cxy ) )
     206                {
     207                    // update <child[0][1]> in remote inode
     208                    hal_remote_s64( XPTR( node_cxy , &node->children[0][1] ),
     209                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     210
     211                    // udate <arity> in remote node
     212                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     213
     214                    // initialize recursively child[0][1] node
     215                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     216   
     217                    // exit loops
     218                    found = true;
     219                }
     220            }
     221        }
     222           
     223        // try to find a valid cluster in child[1][0] macro-cluster
     224        found = false;
     225        for( x = (node_base_x + half) ;
     226        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
     227        {
     228            for( y = node_base_y ;
     229            (y < (node_base_y + half)) && (found == false) ; y++ )
     230            {
     231                cxy = HAL_CXY_FROM_XY( x , y );
     232                if( cluster_is_active( cxy ) )
     233                {
     234                    // update <child[1][0]> in remote inode
     235                    hal_remote_s64( XPTR( node_cxy , &node->children[1][0] ),
     236                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     237
     238                    // udate <arity> in remote node
     239                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     240
     241                    // initialize recursively child[1][0] node
     242                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     243   
     244                    // exit loops
     245                    found = true;
     246                }
     247            }
     248        }
     249
     250        // try to find a valid cluster in child[1][1] macro-cluster
     251        found = false;
     252        for( x = (node_base_x + half) ;
     253        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
     254        {
     255            for( y = (node_base_y + half) ;
     256            (y < (node_base_y + (half<<2))) && (found == false) ; y++ )
     257            {
     258                cxy = HAL_CXY_FROM_XY( x , y );
     259                if( cluster_is_active( cxy ) )
     260                {
     261                    // update <child[1][1]> in remote inode
     262                    hal_remote_s64( XPTR( node_cxy , &node->children[1][1] ),
     263                                    XPTR( cxy , &cluster->dqdt_tbl[level - 1] ) );
     264
     265                    // udate <arity> in remote node
     266                    hal_remote_atomic_add( XPTR( node_cxy , &node->arity ) , 1 );
     267
     268                    // initialize recursively child[1][1] node
     269                    dqdt_recursive_build( cxy , level-1 , XPTR( node_cxy , node ) );
     270   
     271                    // exit loops
     272                    found = true;
     273                }
     274            }
     275        }
     276    }
     277}  // end dqdt_recursive_build()
     278
     279//////////////////////
     280void dqdt_init( void )
     281{
     282    // get x_size & y_size from cluster manager
     283    cluster_t * cluster = &cluster_manager;
     284    uint32_t    x_size  = cluster->x_size;
     285    uint32_t    y_size  = cluster->y_size;
     286
     287    assert( ((x_size <= 16) && (y_size <= 16)) , "illegal mesh size\n");
    108288 
    109289    // compute level_max
    110290    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
    111291    uint32_t  y_size_ext = POW2_ROUNDUP( y_size );
    112     uint32_t  size_ext   = MAX(x_size_ext , y_size_ext);
    113     uint32_t  level_max  = (bits_log2(size_ext * size_ext) >> 1) + 1;
    114 
    115 return level_max;
    116 
    117 /*
    118         dqdt_node_t * node;
    119     cxy_t         p_cxy;         // cluster coordinates for parent node
    120     cxy_t         c_cxy;         // cluster coordinates for child node
    121     uint32_t      level;         // node level in quad tree
    122     uint32_t      mask;          // mask on node coordinates to compute existence condition
    123     uint32_t      pmask;         // mask to compute parent coordinates from child coordinates
    124     cluster_t   * cluster;       // pointer on local cluster
    125 
    126     cluster_t   * cluster = LOCAL_CLUSTER;
    127 
    128     // get cluster coordinates
    129     uint32_t    x       = HAL_X_FROM_CXY( local_cxy );
    130     uint32_t    y       = HAL_Y_FROM_CXY( local_cxy );
    131 
    132     // loop on local dqdt nodes (at most one node per level)
    133     for( level = 0 ; level < level_max ; level++ )
    134     {
    135         // get pointer on the node to be initialised
    136         node = &cluster->dqdt_tbl[level];
    137 
    138         // set default values
    139         node->level       = level;
    140         node->arity       = 0;
    141         node->threads     = 0;
    142         node->pages       = 0;
    143         node->parent      = XPTR_NULL;
    144         node->children[0] = XPTR_NULL;
    145         node->children[1] = XPTR_NULL;
    146         node->children[2] = XPTR_NULL;
    147         node->children[3] = XPTR_NULL;
    148 
    149         // compute masks depending on level : 0x1, 0x3, 0x7, 0xF, 0x1F etc.
    150         mask  = (1<<level)-1;
    151         pmask = (1<<(level+1))-1;
    152 
    153         // check the node  existence condition at each level
    154         if( ((x & mask) == 0) && ((y & mask) == 0) )
    155         {
    156             // set parent extended pointer
    157             p_cxy = HAL_CXY_FROM_XY( (x & ~pmask) , (y & ~pmask) );
    158             node->parent = XPTR( p_cxy , &cluster->dqdt_tbl[level+1] );
    159 
    160             // set child[0] extended pointer (same [x,y] coordinates)
    161             if ( level > 0 )
    162             {
    163                 c_cxy = local_cxy;
    164                 node->children[0] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    165                 node->arity++;
    166             }
    167 
    168             // set child[1] extended pointer (coordinates may overflow)
    169             if ( (level > 0) && ((y + (1<<(level-1))) < y_size) )
    170             {
    171                 c_cxy = local_cxy + HAL_CXY_FROM_XY( 0 , (1<<(level-1) );
    172                 node->children[1] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1] );
    173                 node->arity++;
    174             }
    175 
    176             // set child[2] extended pointer (coordinates may overflow)
    177             if ( (level > 0) && ((x + (1<<(level-1))) < x_size) )
    178             {
    179                 c_cxy = local_cxy + HAL_CXY_FROM_XY( (1<<(level-1)) , 0 );
    180                 node->children[2] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    181                 node->arity++;
    182             }
    183 
    184             // set child[3] extended pointer (coordinates may overflow)
    185             if ( (level > 0) &&
    186                  ((x + (1<<(level-1))) < x_size) &&
    187                  ((y + (1<<(level-1))) < y_size) )
    188             {
    189                 c_cxy = local_cxy + HAL_CXY_FROM_XY( (1<<(level-1)) , (1<<(level-1) );
    190                 node->children[3] = XPTR( c_cxy , &cluster->dqdt_tbl[level-1]);
    191                 node->arity++;
    192             }
    193         }  // end if existence condition
    194     }  // end for level
    195 
    196     return level_max;
    197 */
    198 
    199 } // end dqdt_init()
    200 
    201 /*
     292    uint32_t  size_ext   = MAX( x_size_ext , y_size_ext );
     293    uint32_t  level_max  = bits_log2( size_ext );
     294
     295    // each CP0 register the DQDT root in local cluster manager
     296    cluster->dqdt_root_xp = XPTR( 0 , &cluster->dqdt_tbl[level_max] );
     297
     298#if DEBUG_DQDT_INIT
     299if( local_cxy == 0 )
     300printk("\n[DBG] %s : x_size = %d / y_size = %d / level_max = %d\n",
     301__FUNCTION__, x_size, y_size, level_max );
     302#endif
     303   
     304    // only CP0 in cluster 0 call the recursive function to build the quad-tree
     305    if (local_cxy == 0) dqdt_recursive_build( local_cxy , level_max , XPTR_NULL );
     306
     307#if DEBUG_DQDT_INIT
     308if( local_cxy == 0 ) dqdt_display();
     309#endif
     310
     311}  // end dqdt_init()
     312
    202313///////////////////////////////////////////////////////////////////////////
    203314// This recursive function is called by the dqdt_update_threads() function.
     
    223334    if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
    224335}
    225 */
    226 
    227 /*
     336
    228337///////////////////////////////////////////////////////////////////////////
    229338// This recursive function is called by the dqdt_update_pages() function.
     
    249358    if ( parent != XPTR_NULL ) dqdt_propagate_pages( parent, increment );
    250359}
    251 */
    252360
    253361/////////////////////////////////////////////
    254 void dqdt_update_threads( int32_t increment __attribute__ ((__unused__)) )
    255 {
    256 
    257 return;
    258 
    259 /*
     362void dqdt_update_threads( int32_t increment )
     363{
    260364        cluster_t   * cluster = LOCAL_CLUSTER;
    261365    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
     
    266370    // propagate to DQDT upper levels
    267371    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment );
    268 */
    269 
    270372}
    271373
    272374///////////////////////////////////////////
    273 void dqdt_update_pages( int32_t increment  __attribute__ ((__unused__)) )
    274 {
    275 
    276 return;
    277 
    278 /*
     375void dqdt_update_pages( int32_t increment )
     376{
    279377        cluster_t   * cluster = LOCAL_CLUSTER;
    280378    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
     
    285383    // propagate to DQDT upper levels
    286384    if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment );
    287 */
    288 
    289 }
    290 
    291 /*
     385}
     386
    292387////////////////////////////////////////////////////////////////////////////////
    293388// This recursive function is called by both the dqdt_get_cluster_for_process()
     
    300395{
    301396    dqdt_node_t   node_copy;     // local copy of the current DQDT node
    302     uint32_t      i;             // index in the loop on children
    303     uint32_t      select;        // index of selected child
    304     xptr_t        child;         // extended pointer on a DQDT child node
    305     cxy_t         cxy;           // DQDT child node cluster identifier
    306     dqdt_node_t * ptr;           // pointer on a DQDT child node
     397    xptr_t        child_xp;      // extended pointer on a DQDT child node
     398    uint32_t      x;             // child node X coordinate
     399    uint32_t      y;             // child node Y coordinate
     400    uint32_t      select_x;      // selected child X coordinate
     401    uint32_t      select_y;      // selected child Y coordinate
    307402    uint32_t      load;          // load of the child (threads or pages)
    308403    uint32_t      load_min;      // current value of the minimal load
     
    316411    // analyse load for all children in non terminal node
    317412    load_min = 0xFFFFFFFF;
    318     select   = 0;
    319     for( i = 0 ; i < 4 ; i++ )
     413    select_x = 0;
     414    select_y = 0;
     415    for( x = 0 ; x < 2 ; x++ )
    320416    {
    321         child = node_copy.children[i];
    322         if( child != XPTR_NULL )
    323         {
    324             cxy  = (cxy_t)GET_CXY( child );
    325             ptr  = (dqdt_node_t *)GET_PTR( child );
    326             if( for_memory ) load = hal_remote_l32( XPTR( cxy , &ptr->pages ) );
    327             else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
    328             if( load < load_min )
    329             {
    330                 load_min = load;
    331                 select   = i;
     417        for( y = 0 ; y < 2 ; y++ )
     418        {
     419            child_xp = node_copy.children[x][y];
     420            if( child_xp != XPTR_NULL )
     421            {
     422                cxy_t         cxy  = GET_CXY( child_xp );
     423                dqdt_node_t * ptr  = GET_PTR( child_xp );
     424                if( for_memory ) load = hal_remote_l32( XPTR( cxy , &ptr->pages ) );
     425                else             load = hal_remote_l32( XPTR( cxy , &ptr->threads ) );
     426                if( load < load_min )
     427                {
     428                    load_min = load;
     429                    select_x = x;
     430                    select_y = y;
     431                }
    332432            }
    333433        }
     
    335435
    336436    // select the child with the lowest load
    337     return dqdt_select_cluster( node_copy.children[select], for_memory );
    338 }
    339 */
     437    return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory );
     438}
    340439
    341440//////////////////////////////////////////
    342441cxy_t dqdt_get_cluster_for_process( void )
    343442{
    344 
    345 return cluster_random_select();
    346 
    347 /*
    348     // build extended pointer on DQDT root node
    349         cluster_t * cluster = LOCAL_CLUSTER;
    350     uint32_t    level   = cluster->dqdt_root_level;
    351     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
    352 
    353443    // call recursive function
    354     return dqdt_select_cluster( root_xp , false );
    355 */
    356 
     444    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false );
    357445}
    358446
     
    360448cxy_t dqdt_get_cluster_for_memory( void )
    361449{
    362 
    363 return cluster_random_select();
    364  
    365 /*
    366     // build extended pointer on DQDT root node
    367         cluster_t * cluster = LOCAL_CLUSTER;
    368     uint32_t    level   = cluster->dqdt_root_level;
    369     xptr_t      root_xp = XPTR( 0 , &cluster->dqdt_tbl[level] );
    370 
    371450    // call recursive function
    372     return dqdt_select_cluster( root_xp , true );
    373 */
    374 
    375 }
    376 
     451    return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true );
     452}
     453
  • trunk/kernel/kern/dqdt.h

    r564 r582  
    3131/****************************************************************************************
    3232 * This DQDT infrastructure maintains a topological description of ressources usage
    33  * (number of threads, and number of physical pages allocated) in each cluster.
     33 * in each cluster: number of threads, and number of physical pages allocated.
    3434 *
    3535 * - If X_SIZE or Y_SIZE are equal to 1, it makes the assumption that the cluster
     
    4242 * - If both Y_SIZE and Y_SIZE are larger than 1, it makes the assumption that
    4343 *   the clusters topology is a 2D mesh. The [X,Y] coordinates of a cluster are
    44  *   obtained from the CXY identifier using the following rules :
     44 *   obtained from the CXY identifier using the Rrelevant macros.
    4545 *      X = CXY >> Y_WIDTH   /  Y = CXY & ((1<<Y_WIDTH)-1)
    46  *   If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2,
     46 * - If the mesh X_SIZE and Y_SIZE dimensions are not equal, or are not power of 2,
     47 *   or the mesh contains "holes" reported in the cluster_info[x][y] array,
    4748 *   we build the smallest two dimensionnal quad-tree covering all clusters,
    4849 *   and this tree is truncated as required.
    49  *   The root node is always implemented in cluster [0,0]
    50  *   The mesh size is supposed to contain at most 32 * 32 clusters.
    51  *   There are at most 6 DQDT nodes in a cluster
     50 * - The mesh size is supposed to contain at most 32 * 32 clusters.
     51 *   Therefore, it can exist at most 6 DQDT nodes in a given cluster:
    5252 *   . Level 0 nodes exist on all clusters and have no children.
    5353 *   . Level 1 nodes exist when both X and Y coordinates are multiple of 2
     
    5656 *   . Level 4 nodes exist when both X and Y coordinates are multiple of 16
    5757 *   . Level 5 nodes exist when both X and Y coordinates are multiple of 32
    58  *
    59  *   TODO : the cluster_info[x][y] array is not taken into account [AG].
     58 * - For nodes other than level 0, the placement is defined as follow:
     59 *   . The root node is placed in the cluster containing the core executing
     60 *     the dqdt_init() function.
     61 *   . An intermediate node (representing a given sub-tree) is placed in one
     62 *     cluster covered by the subtree, pseudo-randomly selected.
    6063 ***************************************************************************************/
    6164
     
    6467 * The max number of children is 4, but it can be smaller for some nodes.
    6568 * Level 0 nodes are the clusters, and have no children.
    66  * The root node has no parent, and is always stored in cluster[0,0].
     69 * The root node has no parent.
    6770 ***************************************************************************************/
     71
    6872typedef struct dqdt_node_s
    6973{
     
    7377    uint32_t            pages;               // current number of pages in subtree
    7478        xptr_t              parent;              // extended pointer on parent node
    75         xptr_t              children[4];         // extended pointers on children nodes
     79        xptr_t              children[2][2];      // extended pointers on children nodes
    7680}
    7781dqdt_node_t;
     
    7983
    8084/****************************************************************************************
    81  * This local function initializes the local DQDT structures.
    82  * The information describing the hardware platform topology and the cluster
    83  * indexing policy is defined by the three arguments below.
    84  * This initialisation is done in parallel, locally in each cluster, because the DQDT
    85  * is allocated as a global variable in the cluster_manager, and the local addresses
     85 * This function recursively initializes the DQDT structure from informations
     86 * stored in cluster manager (x_size, y_size and cluster_info[x][y].
     87 * It is executed in all clusters by the local CP0, to compute level_max and register
     88 * the DQDT root node in each cluster manager, but only CPO in cluster 0 build actually
     89 * the quad-tree covering all active clusters.
     90 * This initialisation can use remote_accesses, because the DQDT nodes are
     91 * allocated as global variables in the cluster_manager, and the local addresses
    8692 * are identical in all clusters.
    87  ****************************************************************************************
    88  * @ x_size   : number of clusters (containing memory and CPUs) in a row
    89  * @ y_size   : number of clusters (containing memory and CPUs) in a column
    90  * @ return the number of levels in quad-tree.
    9193 ***************************************************************************************/
    92 uint32_t dqdt_init( uint32_t x_size,
    93                     uint32_t y_size );
     94void dqdt_init( void );
    9495
    9596/****************************************************************************************
  • trunk/kernel/kern/kernel_init.c

    r580 r582  
    934934                                  &core_gid );
    935935
    936     // CP0 initializes cluster identifier
     936    // all CP0s initialize cluster identifier
    937937    if( core_lid == 0 ) local_cxy = info->cxy;
    938938
     
    954954#endif
    955955
    956     // CP0 initializes cluster info
     956    // all CP0s initialize cluster info
    957957    if( core_lid == 0 ) cluster_info_init( info );
    958958
     
    986986    }
    987987
    988     // CP0 initializes cluster manager complex structures
     988    // all CP0s initialise DQDT (only CPO in cluster 0 build the quad-tree)
     989    if( core_lid == 0 ) dqdt_init();
     990   
     991    // all CP0s initialize other cluster manager complex structures
    989992    if( core_lid == 0 )
    990993    {
  • trunk/kernel/kern/scheduler.c

    r581 r582  
    273273// @ sched   : local pointer on scheduler.
    274274////////////////////////////////////////////////////////////////////////////////////////////
    275 void sched_rpc_activate( scheduler_t * sched )
     275static void sched_rpc_activate( scheduler_t * sched )
    276276{
    277277    error_t         error;
  • trunk/kernel/kernel_config.h

    r581 r582  
    6565#define DEBUG_DEVFS_INIT               0
    6666#define DEBUG_DEVFS_MOVE               0
     67
     68#define DEBUG_DQDT_INIT                1
    6769
    6870#define DEBUG_FATFS_INIT               0
  • trunk/user/fft/fft.c

    r581 r582  
    8989#define MODE                    COSIN
    9090#define CHECK                   0
    91 #define DEBUG_MAIN              0               // trace main() function (detailed if odd)
    92 #define DEBUG_FFT1D             0               // trace FFT1D() function (detailed if odd)
     91#define DEBUG_MAIN              1               // trace main() function (detailed if odd)
     92#define DEBUG_FFT1D             1               // trace FFT1D() function (detailed if odd)
    9393#define DEBUG_ROW               0               // trace FFTRow() function (detailed if odd)
    9494#define PRINT_ARRAY             0
     
    300300    }
    301301
    302     printf("\n[FFT] main complete remote_malloc\n");
     302    printf("\n[FFT] main completes remote_malloc\n");
    303303
    304304    // arrays initialisation
     
    307307    InitT( twid );
    308308
    309     printf("\n[FFT] main complete init arrays\n");
     309    printf("\n[FFT] main complete arrays init\n");
    310310
    311311#if CHECK
     
    326326#endif
    327327
    328     // initialise distributed barrier
     328    // initialise barrier
    329329    barrierattr.x_size   = x_size;
    330330    barrierattr.y_size   = y_size;
     
    346346            for ( lid = 0 ; lid < ncores ; lid++ )
    347347            {
    348                 // compute thread continuous index
     348                // compute thread user index (continuous index)
    349349                tid = (((x * y_size) + y) * ncores) + lid;
    350350
     
    365365                                         &args[tid]) ) // pointer on function arguments
    366366                    {
    367                         printf("\n[FFT ERROR] creating thread %x\n", trdid[tid] );
     367                        printf("\n[FFT ERROR] creating thread %x\n", tid );
    368368                        exit( 0 );
    369369                    }
    370370#if DEBUG_MAIN
    371 printf("\n[FFT] main created thread %x\n", trdid[tid] );
     371printf("\n[FFT] main created thread %x on core %d in cluster(%d,%d) \n", tid, lid, x, y );
    372372#endif
    373373                }
     
    497497    MyNum = *tid;
    498498
    499     // get
     499    // BARRIER before parallel exec
     500    pthread_barrier_wait( &barrier );
     501
    500502    // initialise instrumentation
    501503    get_cycle( &parallel_start );
     
    607609}  // end SimpleDft()
    608610
    609 /////////////////
     611///////////////////////
    610612double CheckSum( void )
    611613{
Note: See TracChangeset for help on using the changeset viewer.