Changeset 583 for trunk/kernel/kern/dqdt.c
- Timestamp:
- Nov 1, 2018, 12:10:42 PM (6 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/kern/dqdt.c
r582 r583 28 28 #include <hal_atomic.h> 29 29 #include <hal_remote.h> 30 #include <thread.h> 30 31 #include <printk.h> 31 32 #include <chdev.h> … … 54 55 55 56 // display node content 56 nolock_printk("- level %d in cluster %x (node %x) : threads = %x / pages = %x\n",57 node.level, GET_CXY( node_xp ), GET_PTR( node_xp ), node.threads, node.pages );57 nolock_printk("- level %d / cluster %x : threads = %x / pages = %x / clusters %d / cores %d\n", 58 node.level, GET_CXY( node_xp ), node.threads, node.pages, node.clusters, node.cores ); 58 59 59 60 // recursive call on children if node is not terminal … … 102 103 // This static function initializes recursively, from top to bottom, the quad-tree 103 104 // 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. 105 // cluster manager. At each level in the quad-tree, this function initializes the 106 // node identified by the <cxy> and <level> arguments, selects in each child 107 // macro-cluster the precise cluster where will be placed the subtree root node, 108 // and call recursively itself to initialize the child node in the selected cluster. 109 109 /////////////////////////////////////////////////////////////////////////////////////// 110 110 // @ node cxy : cluster containing the node to initialize … … 124 124 uint32_t node_base_y; // associated macro_cluster y coordinate 125 125 uint32_t half; // associated macro-cluster half size 126 127 // get remote node cluster coordinates 126 uint32_t cores; // number of cores in macro cluster 127 uint32_t clusters; // number of clusters in macro cluster 128 129 // get node cluster coordinates 128 130 node_x = HAL_X_FROM_CXY( node_cxy ); 129 131 node_y = HAL_Y_FROM_CXY( node_cxy ); … … 140 142 cluster_t * cluster = LOCAL_CLUSTER; 141 143 142 // get local pointer on remote node to be initialized 143 dqdt_node_t * node = &cluster->dqdt_tbl[level]; 144 // build local and extended pointer on node to be initialized 145 dqdt_node_t * node_ptr = &cluster->dqdt_tbl[level]; 146 xptr_t node_xp = XPTR( node_cxy , node_ptr ); 144 147 145 148 #if DEBUG_DQDT_INIT 146 149 printk("\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 );150 __FUNCTION__, node_x, node_y, level, mask, half, node_ptr ); 148 151 #endif 149 152 150 153 // make remote node default initialisation 151 hal_remote_memset( XPTR( node_cxy , node ) , 0 , sizeof( dqdt_node_t ) ); 154 hal_remote_memset( node_xp , 0 , sizeof( dqdt_node_t ) ); 155 156 // initialize <parent> field 157 hal_remote_s64( XPTR( node_cxy , &node_ptr->parent ) , parent_xp ); 158 159 // initialize <level> field 160 hal_remote_s32( XPTR( node_cxy , &node_ptr->level ) , level ); 152 161 153 162 // recursive initialisation 154 if( level == 0 ) // terminal case 163 if( level == 0 ) // terminal case : cluster 155 164 { 156 // update parent field 157 hal_remote_s64( XPTR( node_cxy , &node->parent ) , parent_xp ); 165 // initialize <clusters> field in node 166 hal_remote_s32( XPTR( node_cxy , &node_ptr->clusters ) , 1 ); 167 168 // initialize <cores> field in node 169 cores = hal_remote_l32( XPTR ( node_cxy , &cluster->cores_nr ) ); 170 hal_remote_s32( XPTR( node_cxy , &node_ptr->cores ) , cores ); 158 171 } 159 else // non terminal 172 else // non terminal : macro-cluster 160 173 { 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 174 bool_t found; 175 uint32_t x; 176 uint32_t y; 177 cxy_t child_cxy; 178 xptr_t child_xp; 179 dqdt_node_t * child_ptr = &cluster->dqdt_tbl[level-1]; 180 181 // search an active cluster in child[0][0] macro-cluster 170 182 found = false; 171 183 for( x = node_base_x ; … … 175 187 (y < (node_base_y + half)) && (found == false) ; y++ ) 176 188 { 177 cxy = HAL_CXY_FROM_XY( x , y ); 178 if( cluster_is_active( cxy ) ) 189 child_cxy = HAL_CXY_FROM_XY( x , y ); 190 191 if( cluster_is_active( child_cxy ) ) 179 192 { 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 ) ); 193 // initialize recursively selected child[0][0] node 194 dqdt_recursive_build( child_cxy , level-1 , node_xp ); 195 196 // build extended pointer on child[0][0] node 197 child_xp = XPTR( child_cxy , child_ptr ); 198 199 // update <cores> field in node 200 cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) ); 201 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores ); 202 203 // update <clusters> field in node 204 clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) ); 205 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters ); 206 207 // update <child[0][0]> field in node 208 hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][0] ), child_xp ); 209 210 // udate <arity> field in node 211 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 ); 189 212 190 213 // exit loops … … 194 217 } 195 218 196 // try to find a validcluster in child[0][1] macro-cluster219 // search an active cluster in child[0][1] macro-cluster 197 220 found = false; 198 221 for( x = node_base_x ; … … 200 223 { 201 224 for( y = (node_base_y + half) ; 202 (y < (node_base_y + (half<< 2))) && (found == false) ; y++ )225 (y < (node_base_y + (half<<1))) && (found == false) ; y++ ) 203 226 { 204 cxy = HAL_CXY_FROM_XY( x , y ); 205 if( cluster_is_active( cxy ) ) 227 child_cxy = HAL_CXY_FROM_XY( x , y ); 228 229 if( cluster_is_active( child_cxy ) ) 206 230 { 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 ) ); 231 // initialize recursively selected child[0][1] node 232 dqdt_recursive_build( child_cxy , level-1 , node_xp ); 233 234 // build extended pointer on child[0][1] node 235 child_xp = XPTR( child_cxy , child_ptr ); 236 237 // update <cores> field in node 238 cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) ); 239 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores ); 240 241 // update <clusters> field in node 242 clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) ); 243 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters ); 244 245 // update <child[0][1]> field in node 246 hal_remote_s64( XPTR( node_cxy , &node_ptr->children[0][1] ), child_xp ); 247 248 // udate <arity> field in node 249 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 ); 216 250 217 251 // exit loops … … 220 254 } 221 255 } 222 223 // try to find a validcluster in child[1][0] macro-cluster256 257 // search an active cluster in child[1][0] macro-cluster 224 258 found = false; 225 for( x = (node_base_x + 259 for( x = (node_base_x +half) ; 226 260 (x < (node_base_x + (half<<1))) && (found == false) ; x++ ) 227 261 { … … 229 263 (y < (node_base_y + half)) && (found == false) ; y++ ) 230 264 { 231 cxy = HAL_CXY_FROM_XY( x , y ); 232 if( cluster_is_active( cxy ) ) 265 child_cxy = HAL_CXY_FROM_XY( x , y ); 266 267 if( cluster_is_active( child_cxy ) ) 233 268 { 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 ) ); 269 // initialize recursively selected child[1][0] node 270 dqdt_recursive_build( child_cxy , level-1 , node_xp ); 271 272 // build extended pointer on child[1][0] node 273 child_xp = XPTR( child_cxy , child_ptr ); 274 275 // update <cores> field in node 276 cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) ); 277 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores ); 278 279 // update <clusters> field in node 280 clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) ); 281 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters ); 282 283 // update <child[1][0]> field in node 284 hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][0] ), child_xp ); 285 286 // udate <arity> field in node 287 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 ); 243 288 244 289 // exit loops … … 248 293 } 249 294 250 // try to find a validcluster in child[1][1] macro-cluster295 // search an active cluster in child[1][1] macro-cluster 251 296 found = false; 252 297 for( x = (node_base_x + half) ; … … 254 299 { 255 300 for( y = (node_base_y + half) ; 256 (y < (node_base_y + (half<< 2))) && (found == false) ; y++ )301 (y < (node_base_y + (half<<1))) && (found == false) ; y++ ) 257 302 { 258 cxy = HAL_CXY_FROM_XY( x , y ); 259 if( cluster_is_active( cxy ) ) 303 child_cxy = HAL_CXY_FROM_XY( x , y ); 304 305 if( cluster_is_active( child_cxy ) ) 260 306 { 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 ) ); 307 // initialize recursively selected child[1][1] node 308 dqdt_recursive_build( child_cxy , level-1 , node_xp ); 309 310 // build extended pointer on child[1][1] node 311 child_xp = XPTR( child_cxy , child_ptr ); 312 313 // update <cores> field in node 314 cores = hal_remote_l32( XPTR ( child_cxy , &child_ptr->cores ) ); 315 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->cores ) , cores ); 316 317 // update <clusters> field in node 318 clusters = hal_remote_l32( XPTR ( child_cxy , &child_ptr->clusters ) ); 319 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->clusters ) , clusters ); 320 321 // update <child[1][1]> field in node 322 hal_remote_s64( XPTR( node_cxy , &node_ptr->children[1][1] ), child_xp ); 323 324 // udate <arity> field in node 325 hal_remote_atomic_add( XPTR( node_cxy , &node_ptr->arity ) , 1 ); 270 326 271 327 // exit loops … … 311 367 } // end dqdt_init() 312 368 369 313 370 /////////////////////////////////////////////////////////////////////////// 314 // This recursive function is called by the dqdt_update_threads() function. 315 // It traverses the quad tree from clusters to root. 316 /////////////////////////////////////////////////////////////////////////// 317 // @ node : extended pointer on current node 318 // @ increment : number of threads variation 319 /////////////////////////////////////////////////////////////////////////// 320 static void dqdt_propagate_threads( xptr_t node, 321 int32_t increment ) 322 { 323 // get current node cluster identifier and local pointer 324 cxy_t cxy = GET_CXY( node ); 325 dqdt_node_t * ptr = GET_PTR( node ); 326 327 // update current node threads number 328 hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , increment ); 329 330 // get extended pointer on parent node 331 xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) ); 332 333 // propagate if required 334 if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment ); 335 } 336 337 /////////////////////////////////////////////////////////////////////////// 338 // This recursive function is called by the dqdt_update_pages() function. 371 // This recursive function is called by both the dqdt_increment_pages() 372 // and by the dqdt_decrement_pages() functions. 339 373 // It traverses the quad tree from clusters to root. 340 374 /////////////////////////////////////////////////////////////////////////// … … 349 383 dqdt_node_t * ptr = GET_PTR( node ); 350 384 351 // update current node threads number385 // update current node pages number 352 386 hal_remote_atomic_add( XPTR( cxy , &ptr->pages ) , increment ); 353 387 … … 359 393 } 360 394 361 /////////////////////////////////////////// //362 void dqdt_ update_threads( int32_t increment)395 /////////////////////////////////////////// 396 void dqdt_increment_pages( uint32_t order ) 363 397 { 364 398 cluster_t * cluster = LOCAL_CLUSTER; … … 366 400 367 401 // update DQDT node level 0 368 hal_atomic_add( &node-> threads , increment);402 hal_atomic_add( &node->pages , (1 << order) ); 369 403 370 404 // propagate to DQDT upper levels 371 if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , increment ); 405 if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , (1 << order) ); 406 407 #if DEBUG_DQDT_UPDATE_PAGES 408 uint32_t cycle = hal_get_cycles(); 409 if( cycle > DEBUG_DQDT_UPDATE_PAGES ) 410 printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n", 411 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, node->pages, local_cxy, cycle ); 412 #endif 413 372 414 } 373 415 374 416 /////////////////////////////////////////// 375 void dqdt_ update_pages( int32_t increment)417 void dqdt_decrement_pages( uint32_t order ) 376 418 { 377 419 cluster_t * cluster = LOCAL_CLUSTER; … … 379 421 380 422 // update DQDT node level 0 381 hal_atomic_add( &node->pages , increment);423 hal_atomic_add( &node->pages , -(1 << order) ); 382 424 383 425 // propagate to DQDT upper levels 384 if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , increment ); 385 } 386 387 //////////////////////////////////////////////////////////////////////////////// 426 if( node->parent != XPTR_NULL ) dqdt_propagate_pages( node->parent , -(1 << order) ); 427 428 #if DEBUG_DQDT_UPDATE_PAGES 429 uint32_t cycle = hal_get_cycles(); 430 if( cycle > DEBUG_DQDT_UPDATE_PAGES ) 431 printk("\n[DBG] %s : thread %x in process %x / %x pages in cluster %x / cycle %d\n", 432 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, node->pages, local_cxy, cycle ); 433 #endif 434 435 } 436 437 438 439 /////////////////////////////////////////////////////////////////////////// 440 // This recursive function is called by both the dqdt_increment_threads() 441 // and by the dqdt_decrement_threads functions. 442 // It traverses the quad tree from clusters to root. 443 /////////////////////////////////////////////////////////////////////////// 444 // @ node : extended pointer on current node 445 // @ increment : number of pages variation 446 /////////////////////////////////////////////////////////////////////////// 447 static void dqdt_propagate_threads( xptr_t node, 448 int32_t increment ) 449 { 450 // get current node cluster identifier and local pointer 451 cxy_t cxy = GET_CXY( node ); 452 dqdt_node_t * ptr = GET_PTR( node ); 453 454 // update current node threads number 455 hal_remote_atomic_add( XPTR( cxy , &ptr->threads ) , increment ); 456 457 // get extended pointer on parent node 458 xptr_t parent = (xptr_t)hal_remote_l64( XPTR( cxy , &ptr->parent ) ); 459 460 // propagate if required 461 if ( parent != XPTR_NULL ) dqdt_propagate_threads( parent, increment ); 462 } 463 464 /////////////////////////////////// 465 void dqdt_increment_threads( void ) 466 { 467 cluster_t * cluster = LOCAL_CLUSTER; 468 dqdt_node_t * node = &cluster->dqdt_tbl[0]; 469 470 // update DQDT node level 0 471 hal_atomic_add( &node->threads , 1 ); 472 473 // propagate to DQDT upper levels 474 if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , 1 ); 475 476 #if DEBUG_DQDT_UPDATE_THREADS 477 uint32_t cycle = hal_get_cycles(); 478 if( cycle > DEBUG_DQDT_UPDATE_THREADS ) 479 printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n", 480 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, node->threads, local_cxy, cycle ); 481 #endif 482 483 } 484 485 /////////////////////////////////// 486 void dqdt_decrement_threads( void ) 487 { 488 cluster_t * cluster = LOCAL_CLUSTER; 489 dqdt_node_t * node = &cluster->dqdt_tbl[0]; 490 491 // update DQDT node level 0 492 hal_atomic_add( &node->threads , -1 ); 493 494 // propagate to DQDT upper levels 495 if( node->parent != XPTR_NULL ) dqdt_propagate_threads( node->parent , -1 ); 496 497 #if DEBUG_DQDT_UPDATE_THREADS 498 uint32_t cycle = hal_get_cycles(); 499 if( cycle > DEBUG_DQDT_UPDATE_THREADS ) 500 printk("\n[DBG] %s : thread %x in process %x / %d threads in cluster %x / cycle %d\n", 501 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, node->threads, local_cxy, cycle ); 502 #endif 503 504 } 505 506 507 ///////////////////////////////////////////////////////////////////////////////////// 388 508 // This recursive function is called by both the dqdt_get_cluster_for_process() 389 // and by the dqdt_get_cluster_for_memory() functions to select the cluster 390 // with smallest number of thread, or smallest number of allocated pages.509 // and by the dqdt_get_cluster_for_memory() functions to select the cluster with the 510 // smallest number of threads per core, or the smallest number of pages per cluster. 391 511 // It traverses the quad tree from root to clusters. 392 /////////////////////////////////////////////////////////////////////////////// 512 ///////////////////////////////////////////////////////////////////////////////////// 393 513 static cxy_t dqdt_select_cluster( xptr_t node, 394 514 bool_t for_memory ) … … 422 542 cxy_t cxy = GET_CXY( child_xp ); 423 543 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 ) 544 545 // compute average load for each child 546 if( for_memory ) 547 { 548 load = hal_remote_l32( XPTR( cxy , &ptr->pages ) ) / 549 hal_remote_l32( XPTR( cxy , &ptr->clusters ) ); 550 } 551 else 552 { 553 load = hal_remote_l32( XPTR( cxy , &ptr->threads ) ) / 554 hal_remote_l32( XPTR( cxy , &ptr->cores ) ); 555 } 556 557 // select children with smallest load 558 if( load <= load_min ) 427 559 { 428 560 load_min = load; … … 436 568 // select the child with the lowest load 437 569 return dqdt_select_cluster( node_copy.children[select_x][select_y], for_memory ); 438 } 570 571 } // end dqdt_select_cluster() 572 439 573 440 574 ////////////////////////////////////////// … … 442 576 { 443 577 // call recursive function 444 return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false ); 578 cxy_t cxy = dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , false ); 579 580 #if DEBUG_DQDT_SELECT_FOR_PROCESS 581 uint32_t cycle = hal_get_cycles(); 582 if( cycle > DEBUG_DQDT_SELECT_FOR_PROCESS ) 583 printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n", 584 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle ); 585 #endif 586 587 return cxy; 445 588 } 446 589 … … 449 592 { 450 593 // call recursive function 451 return dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true ); 452 } 453 594 cxy_t cxy = dqdt_select_cluster( LOCAL_CLUSTER->dqdt_root_xp , true ); 595 596 #if DEBUG_DQDT_SELECT_FOR_MEMORY 597 uint32_t cycle = hal_get_cycles(); 598 if( cycle > DEBUG_DQDT_SELECT_FOR_MEMORY ) 599 printk("\n[DBG] %s : thread %x in process %x select cluster %x / cycle %d\n", 600 __FUNCTION__, CURRENT_THREAD->trdid, CURRENT_THREAD->process->pid, cxy, cycle ); 601 #endif 602 603 return cxy; 604 } 605
Note: See TracChangeset
for help on using the changeset viewer.