Excluded untied tasks from task stealing constraint

[jlpeyton]

Summary

If either current_task or new_task is untied then skip task scheduling constraint checks, because untied tasks are not affected by the task scheduling constraints.

[AndreyChurbanov]

LGTM

[pawosm01]

Regression found. See comment in line 1754.

openmp/trunk/runtime/src/kmp_tasking.c

1754

This line causes race condition which leads to occasional livelock in strassen_taskdep benchmark from Kastors suite (a benchmark that heavily uses task dependencies). Could be replicated on AArch64 and x86_64, typically working on odd number of cores (5, 7, etc.).

[AndreyChurbanov]

openmp/trunk/runtime/src/kmp_tasking.c

1754

I agree the change in this line is a bug. But once it has beed committed, could you please advise how to better fix the issue?

Is it OK to create new review request that reverts the change in this line and close current one?

Or should I revert both changes and re-submit the diff with only the first change that looks OK?

Or can I just revert the change in this line and close the review without changing the diff?

Thanks, Andrey

[pawosm01]

I don't really know what to do with this, I guess the original author knows best what's next...

[jlpeyton]

openmp/trunk/runtime/src/kmp_tasking.c

1754

Can you give the exact libomp revision you're using, how you are calling strassen_taskdep, operating system, compiler?

[pawosm01]

Runtime:

I'm using libomp from latest git master built using clang and gcc (tried both builds with the same result)

Benchmark:

strassen_taskdep from kastors-1.1 built using clang from git master (it never catched livelock when built with gcc and having libomp as a GOMP drop-in replacement!)

Machine:

processor : 31
vendor_id : GenuineIntel
cpu family : 6
model : 45
model name : Intel(R) Xeon(R) CPU E5-2690 0 @ 2.90GHz
stepping : 7
microcode : 0x710
cpu MHz : 1200.000
cache size : 20480 KB
physical id : 1
siblings : 16
core id : 7
cpu cores : 8
apicid : 47
initial apicid : 47
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf eagerfpu pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm ida arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid
bogomips : 5787.09
clflush size : 64
cache_alignment : 64
address sizes : 46 bits physical, 48 bits virtual
power management:

System:

3.13.0-86-generic #131-Ubuntu SMP Thu May 12 23:33:13 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

Starting:

$ KMP_TOPOLOGY_METHOD=cpuinfo OMP_PROC_BIND=close OMP_DISPLAY_ENV=true OMP_STACKSIZE=64M OMP_NUM_THREADS=7 bin/strassen_taskdep -i 5 -n 4096 -d 5 -s 64

Successful run should print:

OPENMP DISPLAY ENVIRONMENT BEGIN

 _OPENMP='201511'
[host] OMP_CANCELLATION='FALSE'
[host] OMP_DEFAULT_DEVICE='0'
[host] OMP_DISPLAY_ENV='TRUE'
[host] OMP_DYNAMIC='FALSE'
[host] OMP_MAX_ACTIVE_LEVELS='2147483647'
[host] OMP_MAX_TASK_PRIORITY='0'
[host] OMP_NESTED='FALSE'
[host] OMP_NUM_THREADS='7'
[host] OMP_PLACES='cores'
[host] OMP_PROC_BIND='close'
[host] OMP_SCHEDULE='static'
[host] OMP_STACKSIZE='64M'
[host] OMP_THREAD_LIMIT='2147483647'
[host] OMP_WAIT_POLICY='PASSIVE'

OPENMP DISPLAY ENVIRONMENT END

Program : bin/strassen_taskdep
Size : 4096
Iterations : 5
Cutoff Size : 64
Cutoff depth : 5
Threads : 7
Time(sec):: avg : 5.616665 :: std : 0.431984 :: min : 5.050717 :: max : 6.352281 :: median : 5.648555

[AndreyChurbanov]

I've submitted https://reviews.llvm.org/D26182 that fixes the problem pointed to by Paul.

[jlpeyton]

Paul, can you accept the changes in here so we can close this revision?

[AndreyChurbanov]

Fixed by revision https://reviews.llvm.org/D26182.

openmp/trunk/runtime/src/kmp_tasking.c

if (TCR_4(thread_data -> td.td_deque_ntasks) == 0) {
                       gtid, thread_data->td.td_deque_ntasks, thread_data->td.td_deque_head,
                       thread_data->td.td_deque_tail) );
         return NULL;
     }
 
     tail = ( thread_data -> td.td_deque_tail - 1 ) & TASK_DEQUE_MASK(thread_data->td);  // Wrap index.
     taskdata = thread_data -> td.td_deque[ tail ];
 
-    if (is_constrained) {
+    if (is_constrained && (taskdata->td_flags.tiedness == TASK_TIED)) {
         // we need to check if the candidate obeys task scheduling constraint:
         // only child of current task can be scheduled
         kmp_taskdata_t * current = thread->th.th_current_task;
         kmp_int32        level = current->td_level;
         kmp_taskdata_t * parent = taskdata->td_parent;
         while ( parent != current && parent->td_level > level ) {
             parent = parent->td_parent;  // check generation up to the level of the current task
             KMP_DEBUG_ASSERT(parent != NULL);
if ( !is_constrained ) {
         // only child of current task can be scheduled
         kmp_taskdata_t * current = __kmp_threads[ gtid ]->th.th_current_task;
         kmp_int32        level = current->td_level;
         kmp_taskdata_t * parent = taskdata->td_parent;
         while ( parent != current && parent->td_level > level ) {
             parent = parent->td_parent;  // check generation up to the level of the current task
             KMP_DEBUG_ASSERT(parent != NULL);
         }
-        if ( parent != current ) {
+        if ( parent != current && (taskdata->td_flags.tiedness == TASK_TIED) ) { // untied is always allowed to be stolen
             // If the tail task is not a child, then no other childs can appear in the deque (?).
             __kmp_release_bootstrap_lock( & victim_td -> td.td_deque_lock );
             KA_TRACE(10, ("__kmp_steal_task(exit #2): T#%d could not steal from T#%d: task_team=%p "
                           "ntasks=%d head=%u tail=%u\n",
                           gtid, __kmp_gtid_from_thread( threads_data[victim_tid].td.td_thr ),
                           task_team, victim_td->td.td_deque_ntasks,
                           victim_td->td.td_deque_head, victim_td->td.td_deque_tail) );
             return NULL;