source: trunk/kernel/kern/dqdt.c @ 649

Last change on this file since 649 was 637, checked in by alain, 5 years ago

Introduce the non-standard pthread_parallel_create() system call
and re-write the <fft> and <sort> applications to improve the
intrinsic paralelism in applications.

File size: 24.3 KB
RevLine 
[1]1/*
2 * dqdt.c - Distributed Quaternary Decision Tree implementation.
[19]3 *
[637]4 * Author : Alain Greiner (2016,2017,2018,2019)
[1]5 *
6 * Copyright (c)  UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
[14]24#include <kernel_config.h>
[457]25#include <hal_kernel_types.h>
[1]26#include <hal_special.h>
[582]27#include <hal_macros.h>
[1]28#include <hal_atomic.h>
29#include <hal_remote.h>
[583]30#include <thread.h>
[1]31#include <printk.h>
[438]32#include <chdev.h>
[1]33#include <cluster.h>
34#include <bits.h>
35#include <dqdt.h>
36
37
[438]38///////////////////////////////////////////////////////////////////////////////////////////
39//      Extern variables
40///////////////////////////////////////////////////////////////////////////////////////////
[1]41
[438]42extern chdev_directory_t  chdev_dir;  // defined in chdev.h / allocated in kernel_init.c
43
44///////////////////////////////////////////////////////////////////////////////////////////
45// This static recursive function traverse the DQDT quad-tree from root to bottom.
46///////////////////////////////////////////////////////////////////////////////////////////
47static void dqdt_recursive_print( xptr_t  node_xp )
[1]48{
[582]49        uint32_t x;
50        uint32_t y;
[438]51    dqdt_node_t node;
[1]52
[438]53    // get node local copy
54    hal_remote_memcpy( XPTR( local_cxy , &node ), node_xp , sizeof(dqdt_node_t) );
[1]55
[438]56    // display node content
[637]57        nolock_printk("- [%d,%x] : threads %x / pages %x / clusters %d / cores %d / parent_cxy %x\n",
58                  node.level, GET_CXY( node_xp ),
59                  node.threads, node.pages,
60                  node.clusters, node.cores,
61                  GET_CXY( node.parent ) );
[1]62
63    // recursive call on children if node is not terminal
[438]64    if ( node.level > 0 )
[1]65    {
[582]66        for ( x = 0 ; x < 2 ; x++ )
[1]67        {
[582]68            for ( y = 0 ; y < 2 ; y++ )
69            {
70                xptr_t iter_xp = node.children[x][y];
71                if ( iter_xp != XPTR_NULL ) dqdt_recursive_print( iter_xp );
72            }
[1]73        }
74    }
[19]75}
76
[564]77/////////////////////////
[485]78void dqdt_display( void )
[438]79{
[582]80    // get extended pointer on DQDT root node
81        cluster_t * cluster = &cluster_manager;
82    xptr_t      root_xp = cluster->dqdt_root_xp;
[438]83
84    // get pointers on TXT0 chdev
85    xptr_t    txt0_xp  = chdev_dir.txt_tx[0];
86    cxy_t     txt0_cxy = GET_CXY( txt0_xp );
87    chdev_t * txt0_ptr = GET_PTR( txt0_xp );
88
[564]89    // get extended pointer on remote TXT0 lock
[438]90    xptr_t  lock_xp = XPTR( txt0_cxy , &txt0_ptr->wait_lock );
91
[564]92    // get TXT0 lock
93    remote_busylock_acquire( lock_xp );
[438]94
95    // print header
96    nolock_printk("\n***** DQDT state\n\n");
97
98    // call recursive function
99    dqdt_recursive_print( root_xp );
100
[582]101    // release TXT0 lock
[564]102    remote_busylock_release( lock_xp );
[438]103}
104
[582]105///////////////////////////////////////////////////////////////////////////////////////
106// This static function initializes recursively, from top to bottom, the quad-tree
107// infrastructure. The DQDT nodes are allocated as global variables in each local
[583]108// cluster manager. At each level in the quad-tree, this function initializes the
109// node identified by the <cxy> and <level> arguments, selects in each child
110// macro-cluster the precise cluster where will be placed the subtree root node,
111// and call recursively itself to initialize the child node in the selected cluster.
[582]112///////////////////////////////////////////////////////////////////////////////////////
113// @ node cxy  : cluster containing the node to initialize
114// @ level     : level of node to be initialised
115// @ parent_xp : extended pointer on the parent node
116///////////////////////////////////////////////////////////////////////////////////////
117static void dqdt_recursive_build( cxy_t    node_cxy,
118                                  uint32_t level,
119                                  xptr_t   parent_xp )
[1]120{
[637]121    assert( (level <= 5) , __FUNCTION__, "illegal DQDT level %d\n", level );
[582]122 
123    uint32_t node_x;         // node X coordinate
124    uint32_t node_y;         // node Y coordinate
125    uint32_t mask;           // to compute associated macro-cluster coordinates
126    uint32_t node_base_x;    // associated macro_cluster X coordinate
127    uint32_t node_base_y;    // associated macro_cluster y coordinate
128    uint32_t half;           // associated macro-cluster half size
[583]129    uint32_t cores;          // number of cores in macro cluster
130    uint32_t clusters;       // number of clusters in macro cluster
[1]131
[583]132    // get node cluster coordinates
[582]133    node_x = HAL_X_FROM_CXY( node_cxy );
134    node_y = HAL_Y_FROM_CXY( node_cxy );
135       
136    // get macro-cluster mask and half-size
137    mask   = (1 << level) - 1;
138    half   = (level > 0) ? (1 << (level - 1)) : 0;
[564]139
[582]140    // get macro-cluster coordinates
141    node_base_x = node_x & ~mask;
142    node_base_y = node_y & ~mask;
[1]143
[582]144    // get pointer on local cluster manager
145    cluster_t * cluster = LOCAL_CLUSTER;
[1]146
[583]147    // build local and extended pointer on node to be initialized
148    dqdt_node_t * node_ptr = &cluster->dqdt_tbl[level];
149    xptr_t        node_xp  = XPTR( node_cxy , node_ptr );
[1]150
[582]151#if DEBUG_DQDT_INIT
[637]152printk("\n[%s] thread[%x,%x] : cxy(%d,%d) / level %d / mask %x / half %d / ptr %x\n",
[583]153__FUNCTION__, node_x, node_y, level, mask, half, node_ptr );
[582]154#endif
155 
156    // make remote node default initialisation
[583]157    hal_remote_memset( node_xp , 0 , sizeof( dqdt_node_t ) );
[582]158
[583]159    // initialize <parent> field
160    hal_remote_s64( XPTR( node_cxy , &node_ptr->parent ) , parent_xp );
161
162    // initialize <level> field
163    hal_remote_s32( XPTR( node_cxy , &node_ptr->level ) , level );
164
[582]165    // recursive initialisation
[583]166    if( level == 0 )                      // terminal case : cluster
[1]167    {
[583]168        // initialize <clusters> field in node
169        hal_remote_s32( XPTR( node_cxy , &node_ptr->clusters ) , 1 );
170
171        // initialize <cores> field in node
172        cores = hal_remote_l32( XPTR ( node_cxy , &cluster->cores_nr ) );
173        hal_remote_s32( XPTR( node_cxy , &node_ptr->cores ) , cores );
[582]174    }
[583]175    else                                  // non terminal : macro-cluster
[582]176    {
[583]177        bool_t        found;
178        uint32_t      x;
179        uint32_t      y;
180        cxy_t         child_cxy;
181        xptr_t        child_xp;
182        dqdt_node_t * child_ptr =  &cluster->dqdt_tbl[level-1];
[1]183
[583]184        // search an active cluster in child[0][0] macro-cluster
[582]185        found = false; 
186        for( x = node_base_x ; 
187        (x < (node_base_x + half)) && (found == false) ; x++ )
[1]188        {
[582]189            for( y = node_base_y ; 
190            (y < (node_base_y + half)) && (found == false) ; y++ )
191            {
[583]192                child_cxy = HAL_CXY_FROM_XY( x , y );
193
194                if( cluster_is_active( child_cxy ) )
[582]195                {
[583]196                    // initialize recursively selected child[0][0] node
197                    dqdt_recursive_build( child_cxy , level-1 , node_xp );
[1]198
[583]199                    // build extended pointer on child[0][0] node
200                    child_xp = XPTR( child_cxy , child_ptr );
[582]201
[583]202                    // update <cores> field in node
203                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
204                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );
205
206                    // update <clusters> field in node
207                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
208                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );
209
210                    // update <child[0][0]> field in node
211                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][0] ), child_xp );
212
213                    // udate <arity> field in node
214                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
[582]215   
216                    // exit loops
217                    found = true;
218                }
[1]219            }
[582]220        }
[1]221
[583]222        // search an active cluster in child[0][1] macro-cluster
[582]223        found = false; 
224        for( x = node_base_x ; 
225        (x < (node_base_x + half)) && (found == false) ; x++ )
226        {
227            for( y = (node_base_y + half) ; 
[583]228            (y < (node_base_y + (half<<1))) && (found == false) ; y++ )
[1]229            {
[583]230                child_cxy = HAL_CXY_FROM_XY( x , y );
231
232                if( cluster_is_active( child_cxy ) )
[582]233                {
[583]234                    // initialize recursively selected child[0][1] node
235                    dqdt_recursive_build( child_cxy , level-1 , node_xp );
[582]236
[583]237                    // build extended pointer on child[0][1] node
238                    child_xp = XPTR( child_cxy , child_ptr );
[582]239
[583]240                    // update <cores> field in node
241                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
242                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );
243
244                    // update <clusters> field in node
245                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
246                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );
247
248                    // update <child[0][1]> field in node
249                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][1] ), child_xp );
250
251                    // udate <arity> field in node
252                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
[582]253   
254                    // exit loops
255                    found = true;
256                }
[1]257            }
[582]258        }
[583]259
260        // search an active cluster in child[1][0] macro-cluster
[582]261        found = false; 
[583]262        for( x = (node_base_x +half) ; 
[582]263        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
264        {
265            for( y = node_base_y ; 
266            (y < (node_base_y + half)) && (found == false) ; y++ )
267            {
[583]268                child_cxy = HAL_CXY_FROM_XY( x , y );
269
270                if( cluster_is_active( child_cxy ) )
[582]271                {
[583]272                    // initialize recursively selected child[1][0] node
273                    dqdt_recursive_build( child_cxy , level-1 , node_xp );
[1]274
[583]275                    // build extended pointer on child[1][0] node
276                    child_xp = XPTR( child_cxy , child_ptr );
[582]277
[583]278                    // update <cores> field in node
279                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
280                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );
281
282                    // update <clusters> field in node
283                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
284                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );
285
286                    // update <child[1][0]> field in node
287                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][0] ), child_xp );
288
289                    // udate <arity> field in node
290                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
[582]291   
292                    // exit loops
293                    found = true;
294                }
[1]295            }
[582]296        }
[1]297
[583]298        // search an active cluster in child[1][1] macro-cluster
[582]299        found = false; 
300        for( x = (node_base_x + half) ; 
301        (x < (node_base_x + (half<<1))) && (found == false) ; x++ )
302        {
303            for( y = (node_base_y + half) ; 
[583]304            (y < (node_base_y + (half<<1))) && (found == false) ; y++ )
[1]305            {
[583]306                child_cxy = HAL_CXY_FROM_XY( x , y );
307
308                if( cluster_is_active( child_cxy ) )
[582]309                {
[583]310                    // initialize recursively selected child[1][1] node
311                    dqdt_recursive_build( child_cxy , level-1 , node_xp );
[582]312
[583]313                    // build extended pointer on child[1][1] node
314                    child_xp = XPTR( child_cxy , child_ptr );
[582]315
[583]316                    // update <cores> field in node
317                    cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) );
318                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores );
319
320                    // update <clusters> field in node
321                    clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) );
322                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters );
323
324                    // update <child[1][1]> field in node
325                    hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][1] ), child_xp );
326
327                    // udate <arity> field in node
328                    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 );
[582]329   
330                    // exit loops
331                    found = true;
332                }
[1]333            }
[582]334        }
335    }
336}  // end dqdt_recursive_build()
[1]337
[582]338//////////////////////
339void dqdt_init( void )
340{
[637]341    // get x_size & y_size
342    cluster_t * cluster = LOCAL_CLUSTER;
[582]343    uint32_t    x_size  = cluster->x_size;
344    uint32_t    y_size  = cluster->y_size;
[1]345
[582]346    assert( ((x_size <= 16) && (y_size <= 16)) , "illegal mesh size\n");
347 
348    // compute level_max
349    uint32_t  x_size_ext = POW2_ROUNDUP( x_size );
350    uint32_t  y_size_ext = POW2_ROUNDUP( y_size );
351    uint32_t  size_ext   = MAX( x_size_ext , y_size_ext );
352    uint32_t  level_max  = bits_log2( size_ext );
[1]353
[637]354    // all CP0s register the DQDT root in local cluster manager
[582]355    cluster->dqdt_root_xp = XPTR( 0 , &cluster->dqdt_tbl[level_max] );
356
[637]357    // only CP0 in cluster 0 build the DQDT
358    if( local_cxy == 0 )
359    {
360
[582]361#if DEBUG_DQDT_INIT
[637]362thread_t * this = CURRENT_THREAD;
363printk("\n[%s] thread[%x,%x] enters : x_size = %d / y_size = %d / level_max = %d\n",
364__FUNCTION__, this->process->pid, this->trdid, x_size, y_size, level_max );
[582]365#endif
366   
367    // only CP0 in cluster 0 call the recursive function to build the quad-tree
368    if (local_cxy == 0) dqdt_recursive_build( local_cxy , level_max , XPTR_NULL );
369
370#if DEBUG_DQDT_INIT
[637]371dqdt_display();
[582]372#endif
373
[637]374    }
[582]375}  // end dqdt_init()
376
[583]377
[1]378///////////////////////////////////////////////////////////////////////////
[583]379// This recursive function is called by both the dqdt_increment_pages()
380// and by the dqdt_decrement_pages() functions.
[1]381// It traverses the quad tree from clusters to root.
382///////////////////////////////////////////////////////////////////////////
[632]383// @ node_xp    : extended pointer on current node
[583]384// @ increment  : number of pages variation
[438]385///////////////////////////////////////////////////////////////////////////
[632]386static void dqdt_propagate_pages( xptr_t  node_xp,
[583]387                                  int32_t increment )
[1]388{
389    // get current node cluster identifier and local pointer
[632]390    cxy_t         node_cxy = GET_CXY( node_xp );
391    dqdt_node_t * node_ptr = GET_PTR( node_xp );
[1]392
[583]393    // update current node pages number
[632]394    hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->pages ) , increment );
[1]395
396    // get extended pointer on parent node
[632]397    xptr_t parent_xp = (xptr_t)hal_remote_l64( XPTR( node_cxy , &node_ptr->parent ) );
[1]398
399    // propagate if required
[632]400    if ( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp, increment );
[1]401}
402
[632]403////////////////////////////////////////
404void dqdt_increment_pages( cxy_t    cxy,
405                           uint32_t order )
[583]406{
[632]407    // get local pointer on node[0] (same in all clusters)
408    dqdt_node_t * node_ptr = &LOCAL_CLUSTER->dqdt_tbl[0];
[583]409
[632]410    // update DQDT node[0] in remote cluster cxy
411    hal_remote_atomic_add( XPTR( cxy , &node_ptr->pages ) , (1 << order) );
[583]412
[632]413    // get extended pointer on parent node in remote cluster cxy
414    xptr_t parent_xp = hal_remote_l64( XPTR( cxy , &node_ptr->parent ) );
[583]415
[632]416     // propagate to DQDT upper levels
417    if( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp , (1 << order) );
418
[583]419#if DEBUG_DQDT_UPDATE_PAGES
420uint32_t cycle = hal_get_cycles();
421if( cycle > DEBUG_DQDT_UPDATE_PAGES )
422printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n",
[632]423__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid,
424hal_remote_l32( XPTR( cxy , &node_ptr->pages ), cxy, cycle );
[583]425#endif
426
427}
428
[632]429////////////////////////////////////////
430void dqdt_decrement_pages( cxy_t    cxy,
431                           uint32_t order )
[583]432{
[632]433    // get local pointer on node[0] (same in all clusters)
434    dqdt_node_t * node_ptr = &LOCAL_CLUSTER->dqdt_tbl[0];
[583]435
[632]436    // update DQDT node[0] in remote cluster cxy
437    hal_remote_atomic_add( XPTR( cxy , &node_ptr->pages ) , -(1 << order) );
[583]438
[632]439    // get extended pointer on parent node in remote cluster cxy
440    xptr_t parent_xp = hal_remote_l64( XPTR( cxy , &node_ptr->parent ) );
[583]441
[632]442     // propagate to DQDT upper levels
443    if( parent_xp != XPTR_NULL ) dqdt_propagate_pages( parent_xp , -(1 << order) );
444
[583]445#if DEBUG_DQDT_UPDATE_PAGES
446uint32_t cycle = hal_get_cycles();
447if( cycle > DEBUG_DQDT_UPDATE_PAGES )
448printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n",
[632]449__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid,
450hal_remote_l32( XPTR( cxy , &node_ptr->pages ), cxy, cycle );
[583]451#endif
452
453}
454
455
456
[438]457///////////////////////////////////////////////////////////////////////////
[583]458// This recursive function is called by both the dqdt_increment_threads()
459// and by the dqdt_decrement_threads functions.
[438]460// It traverses the quad tree from clusters to root.
461///////////////////////////////////////////////////////////////////////////
462// @ node       : extended pointer on current node
463// @ increment  : number of pages variation
464///////////////////////////////////////////////////////////////////////////
[583]465static void dqdt_propagate_threads( xptr_t  node,
466                                    int32_t increment )
[1]467{
[438]468    // get current node cluster identifier and local pointer
469    cxy_t         cxy = GET_CXY( node );
470    dqdt_node_t * ptr = GET_PTR( node );
[1]471
[438]472    // update current node threads number
[583]473    hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , increment );
[1]474
[438]475    // get extended pointer on parent node
[564]476    xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) );
[1]477
[438]478    // propagate if required
[583]479    if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment );
[1]480}
481
[583]482///////////////////////////////////
483void dqdt_increment_threads( void )
[1]484{
[438]485        cluster_t   * cluster = LOCAL_CLUSTER;
486    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
[19]487
[438]488    // update DQDT node level 0
[583]489    hal_atomic_add( &node->threads , 1 );
[1]490
[438]491    // propagate to DQDT upper levels
[583]492    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , 1 );
493
494#if DEBUG_DQDT_UPDATE_THREADS
495uint32_t cycle = hal_get_cycles();
496if( cycle > DEBUG_DQDT_UPDATE_THREADS )
497printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n",
[632]498__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, 
499node->threads, local_cxy, cycle );
[583]500#endif
501
[1]502}
503
[583]504///////////////////////////////////
505void dqdt_decrement_threads( void )
[1]506{
[438]507        cluster_t   * cluster = LOCAL_CLUSTER;
508    dqdt_node_t * node    = &cluster->dqdt_tbl[0];
[19]509
[438]510    // update DQDT node level 0
[583]511    hal_atomic_add( &node->threads , -1 );
[1]512
[438]513    // propagate to DQDT upper levels
[583]514    if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , -1 );
515
516#if DEBUG_DQDT_UPDATE_THREADS
517uint32_t cycle = hal_get_cycles();
518if( cycle > DEBUG_DQDT_UPDATE_THREADS )
519printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n",
[632]520__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, 
521node->threads, local_cxy, cycle );
[583]522#endif
523
[1]524}
525
[637]526///////////////////////////////////
527xptr_t dqdt_get_root( cxy_t    cxy,
528                      uint32_t level )
529{
530    xptr_t        node_xp;
531    cxy_t         node_cxy;
532    dqdt_node_t * node_ptr;
533    uint32_t      current_level;
[583]534
[637]535assert( (level <= 5) , __FUNCTION__, "illegal DQDT level %d\n", level );
536
537#if DEBUG_DQDT_GET_ROOT
538thread_t * this = CURRENT_THREAD;
539printk("\n[%s] thread[%x,%x] enters / cxy %x / level %d\n",
540__FUNCTION__, this->process->pid, this->trdid, cxy, level );
541#endif
542
543    // check macro-cluster
544    if( cluster_is_active( cxy ) )
545    {   
546        // initialise node_xp and current_level
547        node_xp       = XPTR( cxy , &LOCAL_CLUSTER->dqdt_tbl[0] );
548        current_level = 0;
549
550        // traverse the quad-tree from bottom to root
551        while( current_level < level )
552        {
553            node_cxy = GET_CXY( node_xp );
554            node_ptr = GET_PTR( node_xp );
555
556            node_xp = hal_remote_l64( XPTR( node_cxy , &node_ptr->parent ) );
557            current_level++;
558        }
559    }
560    else
561    {
562        node_xp =  XPTR_NULL;
563    }
564
565#if DEBUG_DQDT_GET_ROOT
566printk("\n[%s] thread[%x,%x] exit / root_xp[%x,%x]\n",
567__FUNCTION__, this->process->pid, this->trdid, GET_CXY( node_xp ), GET_PTR( node_xp ) );
568#endif
569
570    return node_xp;
571   
572}
573
[583]574/////////////////////////////////////////////////////////////////////////////////////
[1]575// This recursive function is called by both the dqdt_get_cluster_for_process()
[583]576// and by the dqdt_get_cluster_for_memory() functions to select the cluster with the
577// smallest number of threads per core, or the smallest number of pages per cluster.
[1]578// It traverses the quad tree from root to clusters.
[583]579/////////////////////////////////////////////////////////////////////////////////////
[1]580static cxy_t dqdt_select_cluster( xptr_t node,
581                                  bool_t for_memory )
582{
583    dqdt_node_t   node_copy;     // local copy of the current DQDT node
[582]584    xptr_t        child_xp;      // extended pointer on a DQDT child node
585    uint32_t      x;             // child node X coordinate
586    uint32_t      y;             // child node Y coordinate
587    uint32_t      select_x;      // selected child X coordinate
588    uint32_t      select_y;      // selected child Y coordinate
[1]589    uint32_t      load;          // load of the child (threads or pages)
590    uint32_t      load_min;      // current value of the minimal load
591
592    // get DQDT node local copy
593    hal_remote_memcpy( XPTR( local_cxy , &node_copy ), node , sizeof(dqdt_node_t) );
594
595    // return cluster identifier for a terminal mode
596    if( node_copy.level == 0 ) return GET_CXY(node);
597
598    // analyse load for all children in non terminal node
599    load_min = 0xFFFFFFFF;
[582]600    select_x = 0;
601    select_y = 0;
602    for( x = 0 ; x < 2 ; x++ )
[1]603    {
[582]604        for( y = 0 ; y < 2 ; y++ )
[1]605        {
[582]606            child_xp = node_copy.children[x][y];
607            if( child_xp != XPTR_NULL )
[1]608            {
[582]609                cxy_t         cxy  = GET_CXY( child_xp );
610                dqdt_node_t * ptr  = GET_PTR( child_xp );
[583]611
612                // compute average load  for each child
613                if( for_memory )
[582]614                {
[583]615                    load = hal_remote_l32( XPTR( cxy , &ptr->pages ) ) /
616                           hal_remote_l32( XPTR( cxy , &ptr->clusters ) );
617                }
618                else
619                {
620                    load = hal_remote_l32( XPTR( cxy , &ptr->threads ) ) /
621                           hal_remote_l32( XPTR( cxy , &ptr->cores ) );
622                }
623
624                // select children with smallest load
625                if( load <= load_min )
626                {
[582]627                    load_min = load;
628                    select_x = x;
629                    select_y = y;
630                }
[19]631            }
[1]632        }
633    }
634
635    // select the child with the lowest load
[582]636    return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory );
[1]637
[583]638}  // end dqdt_select_cluster()
639
640
[637]641///////////////////////////////////////////////////
642cxy_t dqdt_get_cluster_for_thread( xptr_t root_xp )
[1]643{
644    // call recursive function
[637]645    cxy_t cxy = dqdt_select_cluster( root_xp , false );
[583]646
[637]647#if DEBUG_DQDT_SELECT_FOR_THREAD
[583]648uint32_t cycle = hal_get_cycles();
649if( cycle > DEBUG_DQDT_SELECT_FOR_PROCESS )
650printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n",
651__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle );
652#endif
653
654    return cxy;
[1]655}
656
[637]657///////////////////////////////////////////////////
658cxy_t dqdt_get_cluster_for_memory( xptr_t root_xp )
[1]659{
660    // call recursive function
[637]661    cxy_t cxy = dqdt_select_cluster( root_xp , true );
[583]662
663#if DEBUG_DQDT_SELECT_FOR_MEMORY
664uint32_t cycle = hal_get_cycles();
665if( cycle > DEBUG_DQDT_SELECT_FOR_MEMORY )
666printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n",
667__FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle );
668#endif
669
670    return cxy;
[1]671}
672
Note: See TracBrowser for help on using the repository browser.