1 /* 2 * kmp_taskdeps.cpp 3 */ 4 5 6 //===----------------------------------------------------------------------===// 7 // 8 // The LLVM Compiler Infrastructure 9 // 10 // This file is dual licensed under the MIT and the University of Illinois Open 11 // Source Licenses. See LICENSE.txt for details. 12 // 13 //===----------------------------------------------------------------------===// 14 15 16 //#define KMP_SUPPORT_GRAPH_OUTPUT 1 17 18 #include "kmp.h" 19 #include "kmp_io.h" 20 #include "kmp_wait_release.h" 21 22 #if OMP_40_ENABLED 23 24 //TODO: Improve memory allocation? keep a list of pre-allocated structures? allocate in blocks? re-use list finished list entries? 25 //TODO: don't use atomic ref counters for stack-allocated nodes. 26 //TODO: find an alternate to atomic refs for heap-allocated nodes? 27 //TODO: Finish graph output support 28 //TODO: kmp_lock_t seems a tad to big (and heavy weight) for this. Check other runtime locks 29 //TODO: Any ITT support needed? 30 31 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 32 static kmp_int32 kmp_node_id_seed = 0; 33 #endif 34 35 static void 36 __kmp_init_node ( kmp_depnode_t *node ) 37 { 38 node->dn.task = NULL; // set to null initially, it will point to the right task once dependences have been processed 39 node->dn.successors = NULL; 40 __kmp_init_lock(&node->dn.lock); 41 node->dn.nrefs = 1; // init creates the first reference to the node 42 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 43 node->dn.id = KMP_TEST_THEN_INC32(&kmp_node_id_seed); 44 #endif 45 } 46 47 static inline kmp_depnode_t * 48 __kmp_node_ref ( kmp_depnode_t *node ) 49 { 50 KMP_TEST_THEN_INC32(&node->dn.nrefs); 51 return node; 52 } 53 54 static inline void 55 __kmp_node_deref ( kmp_info_t *thread, kmp_depnode_t *node ) 56 { 57 if (!node) return; 58 59 kmp_int32 n = KMP_TEST_THEN_DEC32(&node->dn.nrefs) - 1; 60 if ( n == 0 ) { 61 KMP_ASSERT(node->dn.nrefs == 0); 62 #if USE_FAST_MEMORY 63 __kmp_fast_free(thread,node); 64 #else 65 __kmp_thread_free(thread,node); 66 #endif 67 } 68 } 69 70 #define KMP_ACQUIRE_DEPNODE(gtid,n) __kmp_acquire_lock(&(n)->dn.lock,(gtid)) 71 #define KMP_RELEASE_DEPNODE(gtid,n) __kmp_release_lock(&(n)->dn.lock,(gtid)) 72 73 static void 74 __kmp_depnode_list_free ( kmp_info_t *thread, kmp_depnode_list *list ); 75 76 static const kmp_int32 kmp_dephash_log2 = 6; 77 static const kmp_int32 kmp_dephash_size = (1 << kmp_dephash_log2); 78 79 static inline kmp_int32 80 __kmp_dephash_hash ( kmp_intptr_t addr ) 81 { 82 //TODO alternate to try: set = (((Addr64)(addrUsefulBits * 9.618)) % m_num_sets ); 83 return ((addr >> kmp_dephash_log2) ^ addr) % kmp_dephash_size; 84 } 85 86 static kmp_dephash_t * 87 __kmp_dephash_create ( kmp_info_t *thread ) 88 { 89 kmp_dephash_t *h; 90 91 kmp_int32 size = kmp_dephash_size * sizeof(kmp_dephash_entry_t) + sizeof(kmp_dephash_t); 92 93 #if USE_FAST_MEMORY 94 h = (kmp_dephash_t *) __kmp_fast_allocate( thread, size ); 95 #else 96 h = (kmp_dephash_t *) __kmp_thread_malloc( thread, size ); 97 #endif 98 99 #ifdef KMP_DEBUG 100 h->nelements = 0; 101 #endif 102 h->buckets = (kmp_dephash_entry **)(h+1); 103 104 for ( kmp_int32 i = 0; i < kmp_dephash_size; i++ ) 105 h->buckets[i] = 0; 106 107 return h; 108 } 109 110 static void 111 __kmp_dephash_free ( kmp_info_t *thread, kmp_dephash_t *h ) 112 { 113 for ( kmp_int32 i=0; i < kmp_dephash_size; i++ ) { 114 if ( h->buckets[i] ) { 115 kmp_dephash_entry_t *next; 116 for ( kmp_dephash_entry_t *entry = h->buckets[i]; entry; entry = next ) { 117 next = entry->next_in_bucket; 118 __kmp_depnode_list_free(thread,entry->last_ins); 119 __kmp_node_deref(thread,entry->last_out); 120 #if USE_FAST_MEMORY 121 __kmp_fast_free(thread,entry); 122 #else 123 __kmp_thread_free(thread,entry); 124 #endif 125 } 126 } 127 } 128 #if USE_FAST_MEMORY 129 __kmp_fast_free(thread,h); 130 #else 131 __kmp_thread_free(thread,h); 132 #endif 133 } 134 135 static kmp_dephash_entry * 136 __kmp_dephash_find ( kmp_info_t *thread, kmp_dephash_t *h, kmp_intptr_t addr ) 137 { 138 kmp_int32 bucket = __kmp_dephash_hash(addr); 139 140 kmp_dephash_entry_t *entry; 141 for ( entry = h->buckets[bucket]; entry; entry = entry->next_in_bucket ) 142 if ( entry->addr == addr ) break; 143 144 if ( entry == NULL ) { 145 // create entry. This is only done by one thread so no locking required 146 #if USE_FAST_MEMORY 147 entry = (kmp_dephash_entry_t *) __kmp_fast_allocate( thread, sizeof(kmp_dephash_entry_t) ); 148 #else 149 entry = (kmp_dephash_entry_t *) __kmp_thread_malloc( thread, sizeof(kmp_dephash_entry_t) ); 150 #endif 151 entry->addr = addr; 152 entry->last_out = NULL; 153 entry->last_ins = NULL; 154 entry->next_in_bucket = h->buckets[bucket]; 155 h->buckets[bucket] = entry; 156 #ifdef KMP_DEBUG 157 h->nelements++; 158 if ( entry->next_in_bucket ) h->nconflicts++; 159 #endif 160 } 161 return entry; 162 } 163 164 static kmp_depnode_list_t * 165 __kmp_add_node ( kmp_info_t *thread, kmp_depnode_list_t *list, kmp_depnode_t *node ) 166 { 167 kmp_depnode_list_t *new_head; 168 169 #if USE_FAST_MEMORY 170 new_head = (kmp_depnode_list_t *) __kmp_fast_allocate(thread,sizeof(kmp_depnode_list_t)); 171 #else 172 new_head = (kmp_depnode_list_t *) __kmp_thread_malloc(thread,sizeof(kmp_depnode_list_t)); 173 #endif 174 175 new_head->node = __kmp_node_ref(node); 176 new_head->next = list; 177 178 return new_head; 179 } 180 181 static void 182 __kmp_depnode_list_free ( kmp_info_t *thread, kmp_depnode_list *list ) 183 { 184 kmp_depnode_list *next; 185 186 for ( ; list ; list = next ) { 187 next = list->next; 188 189 __kmp_node_deref(thread,list->node); 190 #if USE_FAST_MEMORY 191 __kmp_fast_free(thread,list); 192 #else 193 __kmp_thread_free(thread,list); 194 #endif 195 } 196 } 197 198 static inline void 199 __kmp_track_dependence ( kmp_depnode_t *source, kmp_depnode_t *sink ) 200 { 201 #ifdef KMP_SUPPORT_GRAPH_OUTPUT 202 kmp_taskdata_t * task_source = KMP_TASK_TO_TASKDATA(source->dn.task); 203 kmp_taskdata_t * task_sink = KMP_TASK_TO_TASKDATA(sink->dn.task); // this can be NULL when if(0) ... 204 205 __kmp_printf("%d(%s) -> %d(%s)\n", source->dn.id, task_source->td_ident->psource, sink->dn.id, task_sink->td_ident->psource); 206 #endif 207 } 208 209 template< bool filter > 210 static inline kmp_int32 211 __kmp_process_deps ( kmp_int32 gtid, kmp_depnode_t *node, kmp_dephash_t *hash, 212 bool dep_barrier,kmp_int32 ndeps, kmp_depend_info_t *dep_list) 213 { 214 KA_TRACE(30, ("__kmp_process_deps<%d>: T#%d processing %d depencies : dep_barrier = %d\n", filter, gtid, ndeps, dep_barrier ) ); 215 216 kmp_info_t *thread = __kmp_threads[ gtid ]; 217 kmp_int32 npredecessors=0; 218 for ( kmp_int32 i = 0; i < ndeps ; i++ ) { 219 const kmp_depend_info_t * dep = &dep_list[i]; 220 221 KMP_DEBUG_ASSERT(dep->flags.in); 222 223 if ( filter && dep->base_addr == 0 ) continue; // skip filtered entries 224 225 kmp_dephash_entry_t *info = __kmp_dephash_find(thread,hash,dep->base_addr); 226 kmp_depnode_t *last_out = info->last_out; 227 228 if ( dep->flags.out && info->last_ins ) { 229 for ( kmp_depnode_list_t * p = info->last_ins; p; p = p->next ) { 230 kmp_depnode_t * indep = p->node; 231 if ( indep->dn.task ) { 232 KMP_ACQUIRE_DEPNODE(gtid,indep); 233 if ( indep->dn.task ) { 234 __kmp_track_dependence(indep,node); 235 indep->dn.successors = __kmp_add_node(thread, indep->dn.successors, node); 236 KA_TRACE(40,("__kmp_process_deps<%d>: T#%d adding dependence from %p to %p", 237 filter,gtid, KMP_TASK_TO_TASKDATA(indep->dn.task), KMP_TASK_TO_TASKDATA(node->dn.task))); 238 npredecessors++; 239 } 240 KMP_RELEASE_DEPNODE(gtid,indep); 241 } 242 } 243 244 __kmp_depnode_list_free(thread,info->last_ins); 245 info->last_ins = NULL; 246 247 } else if ( last_out && last_out->dn.task ) { 248 KMP_ACQUIRE_DEPNODE(gtid,last_out); 249 if ( last_out->dn.task ) { 250 __kmp_track_dependence(last_out,node); 251 last_out->dn.successors = __kmp_add_node(thread, last_out->dn.successors, node); 252 KA_TRACE(40,("__kmp_process_deps<%d>: T#%d adding dependence from %p to %p", 253 filter,gtid, KMP_TASK_TO_TASKDATA(last_out->dn.task), KMP_TASK_TO_TASKDATA(node->dn.task))); 254 255 npredecessors++; 256 } 257 KMP_RELEASE_DEPNODE(gtid,last_out); 258 } 259 260 if ( dep_barrier ) { 261 // if this is a sync point in the serial sequence, then the previous outputs are guaranteed to be completed after 262 // the execution of this task so the previous output nodes can be cleared. 263 __kmp_node_deref(thread,last_out); 264 info->last_out = NULL; 265 } else { 266 if ( dep->flags.out ) { 267 __kmp_node_deref(thread,last_out); 268 info->last_out = __kmp_node_ref(node); 269 } else 270 info->last_ins = __kmp_add_node(thread, info->last_ins, node); 271 } 272 273 } 274 275 KA_TRACE(30, ("__kmp_process_deps<%d>: T#%d found %d predecessors\n", filter, gtid, npredecessors ) ); 276 277 return npredecessors; 278 } 279 280 #define NO_DEP_BARRIER (false) 281 #define DEP_BARRIER (true) 282 283 // returns true if the task has any outstanding dependence 284 static bool 285 __kmp_check_deps ( kmp_int32 gtid, kmp_depnode_t *node, kmp_task_t *task, kmp_dephash_t *hash, bool dep_barrier, 286 kmp_int32 ndeps, kmp_depend_info_t *dep_list, 287 kmp_int32 ndeps_noalias, kmp_depend_info_t *noalias_dep_list ) 288 { 289 int i; 290 291 #if KMP_DEBUG 292 kmp_taskdata_t * taskdata = KMP_TASK_TO_TASKDATA(task); 293 #endif 294 KA_TRACE(20, ("__kmp_check_deps: T#%d checking dependencies for task %p : %d possibly aliased dependencies, %d non-aliased depedencies : dep_barrier=%d .\n", gtid, taskdata, ndeps, ndeps_noalias, dep_barrier ) ); 295 296 // Filter deps in dep_list 297 // TODO: Different algorithm for large dep_list ( > 10 ? ) 298 for ( i = 0; i < ndeps; i ++ ) { 299 if ( dep_list[i].base_addr != 0 ) 300 for ( int j = i+1; j < ndeps; j++ ) 301 if ( dep_list[i].base_addr == dep_list[j].base_addr ) { 302 dep_list[i].flags.in |= dep_list[j].flags.in; 303 dep_list[i].flags.out |= dep_list[j].flags.out; 304 dep_list[j].base_addr = 0; // Mark j element as void 305 } 306 } 307 308 // doesn't need to be atomic as no other thread is going to be accessing this node just yet 309 // npredecessors is set -1 to ensure that none of the releasing tasks queues this task before we have finished processing all the dependencies 310 node->dn.npredecessors = -1; 311 312 // used to pack all npredecessors additions into a single atomic operation at the end 313 int npredecessors; 314 315 npredecessors = __kmp_process_deps<true>(gtid, node, hash, dep_barrier, ndeps, dep_list); 316 npredecessors += __kmp_process_deps<false>(gtid, node, hash, dep_barrier, ndeps_noalias, noalias_dep_list); 317 318 node->dn.task = task; 319 KMP_MB(); 320 321 // Account for our initial fake value 322 npredecessors++; 323 324 // Update predecessors and obtain current value to check if there are still any outstandig dependences (some tasks may have finished while we processed the dependences) 325 npredecessors = KMP_TEST_THEN_ADD32(&node->dn.npredecessors, npredecessors) + npredecessors; 326 327 KA_TRACE(20, ("__kmp_check_deps: T#%d found %d predecessors for task %p \n", gtid, npredecessors, taskdata ) ); 328 329 // beyond this point the task could be queued (and executed) by a releasing task... 330 return npredecessors > 0 ? true : false; 331 } 332 333 void 334 __kmp_release_deps ( kmp_int32 gtid, kmp_taskdata_t *task ) 335 { 336 kmp_info_t *thread = __kmp_threads[ gtid ]; 337 kmp_depnode_t *node = task->td_depnode; 338 339 if ( task->td_dephash ) { 340 KA_TRACE(40, ("__kmp_realease_deps: T#%d freeing dependencies hash of task %p.\n", gtid, task ) ); 341 __kmp_dephash_free(thread,task->td_dephash); 342 } 343 344 if ( !node ) return; 345 346 KA_TRACE(20, ("__kmp_realease_deps: T#%d notifying succesors of task %p.\n", gtid, task ) ); 347 348 KMP_ACQUIRE_DEPNODE(gtid,node); 349 node->dn.task = NULL; // mark this task as finished, so no new dependencies are generated 350 KMP_RELEASE_DEPNODE(gtid,node); 351 352 kmp_depnode_list_t *next; 353 for ( kmp_depnode_list_t *p = node->dn.successors; p; p = next ) { 354 kmp_depnode_t *successor = p->node; 355 kmp_int32 npredecessors = KMP_TEST_THEN_DEC32(&successor->dn.npredecessors) - 1; 356 357 // successor task can be NULL for wait_depends or because deps are still being processed 358 if ( npredecessors == 0 ) { 359 KMP_MB(); 360 if ( successor->dn.task ) { 361 KA_TRACE(20, ("__kmp_realease_deps: T#%d successor %p of %p scheduled for execution.\n", gtid, successor->dn.task, task ) ); 362 __kmp_omp_task(gtid,successor->dn.task,false); 363 } 364 } 365 366 next = p->next; 367 __kmp_node_deref(thread,p->node); 368 #if USE_FAST_MEMORY 369 __kmp_fast_free(thread,p); 370 #else 371 __kmp_thread_free(thread,p); 372 #endif 373 } 374 375 __kmp_node_deref(thread,node); 376 377 KA_TRACE(20, ("__kmp_realease_deps: T#%d all successors of %p notified of completation\n", gtid, task ) ); 378 } 379 380 /*! 381 @ingroup TASKING 382 @param loc_ref location of the original task directive 383 @param gtid Global Thread ID of encountering thread 384 @param new_task task thunk allocated by __kmp_omp_task_alloc() for the ''new task'' 385 @param ndeps Number of depend items with possible aliasing 386 @param dep_list List of depend items with possible aliasing 387 @param ndeps_noalias Number of depend items with no aliasing 388 @param noalias_dep_list List of depend items with no aliasing 389 390 @return Returns either TASK_CURRENT_NOT_QUEUED if the current task was not suspendend and queued, or TASK_CURRENT_QUEUED if it was suspended and queued 391 392 Schedule a non-thread-switchable task with dependences for execution 393 */ 394 kmp_int32 395 __kmpc_omp_task_with_deps( ident_t *loc_ref, kmp_int32 gtid, kmp_task_t * new_task, 396 kmp_int32 ndeps, kmp_depend_info_t *dep_list, 397 kmp_int32 ndeps_noalias, kmp_depend_info_t *noalias_dep_list ) 398 { 399 400 kmp_taskdata_t * new_taskdata = KMP_TASK_TO_TASKDATA(new_task); 401 KA_TRACE(10, ("__kmpc_omp_task_with_deps(enter): T#%d loc=%p task=%p\n", 402 gtid, loc_ref, new_taskdata ) ); 403 404 kmp_info_t *thread = __kmp_threads[ gtid ]; 405 kmp_taskdata_t * current_task = thread->th.th_current_task; 406 407 bool serial = current_task->td_flags.team_serial || current_task->td_flags.tasking_ser || current_task->td_flags.final; 408 #if OMP_41_ENABLED 409 serial = serial && !(new_taskdata->td_flags.proxy == TASK_PROXY); 410 #endif 411 412 if ( !serial && ( ndeps > 0 || ndeps_noalias > 0 )) { 413 /* if no dependencies have been tracked yet, create the dependence hash */ 414 if ( current_task->td_dephash == NULL ) 415 current_task->td_dephash = __kmp_dephash_create(thread); 416 417 #if USE_FAST_MEMORY 418 kmp_depnode_t *node = (kmp_depnode_t *) __kmp_fast_allocate(thread,sizeof(kmp_depnode_t)); 419 #else 420 kmp_depnode_t *node = (kmp_depnode_t *) __kmp_thread_malloc(thread,sizeof(kmp_depnode_t)); 421 #endif 422 423 __kmp_init_node(node); 424 new_taskdata->td_depnode = node; 425 426 if ( __kmp_check_deps( gtid, node, new_task, current_task->td_dephash, NO_DEP_BARRIER, 427 ndeps, dep_list, ndeps_noalias,noalias_dep_list ) ) { 428 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d task had blocking dependencies: " 429 "loc=%p task=%p, return: TASK_CURRENT_NOT_QUEUED\n", gtid, loc_ref, 430 new_taskdata ) ); 431 return TASK_CURRENT_NOT_QUEUED; 432 } 433 } else { 434 #if OMP_41_ENABLED 435 kmp_task_team_t * task_team = thread->th.th_task_team; 436 if ( task_team && task_team->tt.tt_found_proxy_tasks ) 437 __kmpc_omp_wait_deps ( loc_ref, gtid, ndeps, dep_list, ndeps_noalias, noalias_dep_list ); 438 else 439 #endif 440 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d ignored dependencies for task (serialized)" 441 "loc=%p task=%p\n", gtid, loc_ref, new_taskdata ) ); 442 } 443 444 KA_TRACE(10, ("__kmpc_omp_task_with_deps(exit): T#%d task had no blocking dependencies : " 445 "loc=%p task=%p, transferring to __kmpc_omp_task\n", gtid, loc_ref, 446 new_taskdata ) ); 447 448 return __kmpc_omp_task(loc_ref,gtid,new_task); 449 } 450 451 /*! 452 @ingroup TASKING 453 @param loc_ref location of the original task directive 454 @param gtid Global Thread ID of encountering thread 455 @param ndeps Number of depend items with possible aliasing 456 @param dep_list List of depend items with possible aliasing 457 @param ndeps_noalias Number of depend items with no aliasing 458 @param noalias_dep_list List of depend items with no aliasing 459 460 Blocks the current task until all specifies dependencies have been fulfilled. 461 */ 462 void 463 __kmpc_omp_wait_deps ( ident_t *loc_ref, kmp_int32 gtid, kmp_int32 ndeps, kmp_depend_info_t *dep_list, 464 kmp_int32 ndeps_noalias, kmp_depend_info_t *noalias_dep_list ) 465 { 466 KA_TRACE(10, ("__kmpc_omp_wait_deps(enter): T#%d loc=%p\n", gtid, loc_ref) ); 467 468 if ( ndeps == 0 && ndeps_noalias == 0 ) { 469 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no dependencies to wait upon : loc=%p\n", gtid, loc_ref) ); 470 return; 471 } 472 473 kmp_info_t *thread = __kmp_threads[ gtid ]; 474 kmp_taskdata_t * current_task = thread->th.th_current_task; 475 476 // We can return immediately as: 477 // - dependences are not computed in serial teams (except if we have proxy tasks) 478 // - if the dephash is not yet created it means we have nothing to wait for 479 bool ignore = current_task->td_flags.team_serial || current_task->td_flags.tasking_ser || current_task->td_flags.final; 480 #if OMP_41_ENABLED 481 ignore = ignore && thread->th.th_task_team->tt.tt_found_proxy_tasks == FALSE; 482 #endif 483 ignore = ignore || current_task->td_dephash == NULL; 484 485 if ( ignore ) { 486 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no blocking dependencies : loc=%p\n", gtid, loc_ref) ); 487 return; 488 } 489 490 kmp_depnode_t node; 491 __kmp_init_node(&node); 492 493 if (!__kmp_check_deps( gtid, &node, NULL, current_task->td_dephash, DEP_BARRIER, 494 ndeps, dep_list, ndeps_noalias, noalias_dep_list )) { 495 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d has no blocking dependencies : loc=%p\n", gtid, loc_ref) ); 496 return; 497 } 498 499 int thread_finished = FALSE; 500 kmp_flag_32 flag((volatile kmp_uint32 *)&(node.dn.npredecessors), 0U); 501 while ( node.dn.npredecessors > 0 ) { 502 flag.execute_tasks(thread, gtid, FALSE, &thread_finished, 503 #if USE_ITT_BUILD 504 NULL, 505 #endif 506 __kmp_task_stealing_constraint ); 507 } 508 509 KA_TRACE(10, ("__kmpc_omp_wait_deps(exit): T#%d finished waiting : loc=%p\n", gtid, loc_ref) ); 510 } 511 512 #endif /* OMP_40_ENABLED */ 513 514