[OpenMP] Optimized trivial multiple edges from task dependency graph

[rpereira-dev]

Summary

From "3.1 Reducing the number of edges" of this paper - Optimization (b)

Task (dependency) nodes have a successors list built upon passed dependency.
Given the following code, B will be added to A's successors list building the graph A -> B

// A
# pragma omp task depend(out: x)
{}

// B
# pragma omp task depend(in: x)
{}

In the following code, B is currently added twice to A's successor list

// A
# pragma omp task depend(out: x, y)
{}

// B
# pragma omp task depend(in: x, y)
{}

This patch removes such dupplicates by checking lastly inserted task in A successor list.
Here is another schematic example of multiple edges removed

graph-optim-b.pdf18 KBDownload

[jdoerfert]

openmp/runtime/src/kmp_taskdeps.cpp

336

why is the order here swapped?

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

336

Order remains the same for callers; the patch only swaps in this prototype as i believe it was mistakenly inverted
(used to be sink -> source, is now source -> sink )

[tianshilei1992]

openmp/runtime/src/kmp_taskdeps.cpp

336

This looks pretty confusing IMO.

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

336

Want me to revert this change and only keep the multiple edges removal ? (4 lines 310, 322, 352, 378)
I can make another one just for the variable names which are currently misleading

[tianshilei1992]

openmp/runtime/src/kmp_taskdeps.cpp

336

Why the current variable names are misleading? If A depends on B, there is an edge A->B so A is source and B is sink.

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

336

The relation « A depends on B » is usually represented it through the edge B -> A, not A -> B

[tianshilei1992]

openmp/runtime/src/kmp_taskdeps.cpp

336

I understand libomp stores successors instead of predecessors but to be that doesn't mean we have an edge from B->A.

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

336

I believe we will not agree on what is misleading or not today :p
We can probably agree on who the "predecessor" and "successor" refer to, and rename those variables accordingly ?
I can also just revert 'sink' and 'source' names swap from the patch and keep as per before

Let me know

[protze.joachim]

The semantically orthogonal patches should be submitted separately. Merged the changes are hard to review.
I really doubt that your changes have the suggested effect. Did you verify that there is any effect?

Are you sure that your "optimization" does not remove necessary information from the LLVM implementation?

openmp/runtime/src/kmp_taskdeps.cpp

354

Is this necessary?

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

354

no, removing this extra bracket

[rpereira-dev]

In D158544#4610857, @protze.joachim wrote:

The semantically orthogonal patches should be submitted separately. Merged the changes are hard to review.
I really doubt that your changes have the suggested effect. Did you verify that there is any effect?

Yes, I verified inspecting data structures at run-time with a debugger on the two minimal examples above.
What is making you doubting ?

Are you sure that your "optimization" does not remove necessary information from the LLVM implementation?

I assume it shouldn't, this is simply removing redundant entries in the 'successors' list
I tested on the task-based LULESH in the mentionned paper (https://github.com/rpereira-dev/LULESH), original report correctness checking passes (https://asc.llnl.gov/sites/asc/files/2021-01/lulesh2.0_changes1.pdf).

[rpereira-dev]

Reverted (source, sink) names swap of the __kmp_depnode_link_successor function; added a comment instead

[tianshilei1992]

I think this should work. Please add a test.

[rpereira-dev]

Added tests corresponding to the minimal code example attached previously

[protze.joachim]

The new tests are missing a RUN line (see first line in below diff).
I think, you should also add REQUIRES: linux to avoid failures on Windows from missing dll-exports for your newly added kmpc functions

I furthermore suggest to add a task with depend(out:y) to the inoutset test just to verify that dropping the edges does not introduce inconsistencies:

0a1,2
> // RUN: %libomp-compile-and-run
> // REQUIRES: linux
17,19c19,21
<       kmp_task_t *A, *B, *C, *D, *E, *F;
<       kmp_depnode_list_t *A_succ, *B_succ, *C_succ;
<       kmp_base_depnode_t *D_node, *E_node, *F_node;
---
>       kmp_task_t *A, *B, *C, *D, *E, *F, *G;
>       kmp_depnode_list_t *A_succ, *B_succ, *C_succ, *E_succ, *F_succ;
>       kmp_base_depnode_t *D_node, *E_node, *F_node, *G_node;
60a63,67
>       deps[1].flags = 2; // OUT
>       G = __kmpc_omp_task_alloc(&loc, gtid, TIED, sizeof(kmp_task_t), 0, NULL);
>       __kmpc_omp_task_with_deps(&loc, gtid, G, 1, deps + 1, 0, 0);
>       
64a71,72
>       E_succ = __kmpc_task_get_successors(E);
>       F_succ = __kmpc_task_get_successors(F);
68a77
>       G_node = __kmpc_task_get_depnode(G);
101a111,114
> 
>       // E -> G and F -> G
>       assert(E_succ && !E_succ->next && F_succ && !F_succ->next);
>       assert(E_succ->node == G_node && F_succ->node == G_node);

Indention doesn't look right for the newly added if blocks in kmp_taskdeps.cpp. git clang-format doesnt't help, so please add indention for these blocks.

[rpereira-dev]

• Added missing RUN lines in the test files
• Added REQUIRES: linux in the test files
• Added an additional out: y node in the inoutset test
• Manually fixed indentation failing on git clang-format

[rpereira-dev]

Got trolled yet again by automatic format...

• Fixed indentation of the 'list' version of the __kmp_depnode_link_successor routine

[protze.joachim]

Lgtm now

Explicitly setting OMP_NUM_THREADS doesn't have any effect with the explicit num_threads clause

openmp/runtime/src/kmp_taskdeps.cpp

if (task) {
         tdg_status = KMP_TASK_TO_TASKDATA(task)->tdg->tdg_status;
       if (__kmp_tdg_is_recording(tdg_status))
         __kmp_track_dependence(gtid, dep, node, task);
     }
 #endif
     if (dep->dn.task) {
       KMP_ACQUIRE_DEPNODE(gtid, dep);
       if (dep->dn.task) {
+        if (!dep->dn.successors || dep->dn.successors->node != node) {
 #if OMPX_TASKGRAPH
         if (!(__kmp_tdg_is_recording(tdg_status)) && task)
 #endif
           __kmp_track_dependence(gtid, dep, node, task);
         dep->dn.successors = __kmp_add_node(thread, dep->dn.successors, node);
         KA_TRACE(40, ("__kmp_process_deps: T#%d adding dependence from %p to "
                       "%p\n",
                       gtid, KMP_TASK_TO_TASKDATA(dep->dn.task),
                       KMP_TASK_TO_TASKDATA(task)));
         npredecessors++;
         }
+      }
       KMP_RELEASE_DEPNODE(gtid, dep);
     }
   }
   return npredecessors;
 }
 
+// Add the edge 'sink' -> 'source' in the task dependency graph
 static inline kmp_int32 __kmp_depnode_link_successor(kmp_int32 gtid,
                                                      kmp_info_t *thread,
                                                      kmp_task_t *task,
                                                      kmp_depnode_t *source,
                                                      kmp_depnode_t *sink) {
   if (!sink)
     return 0;
   kmp_int32 npredecessors = 0;
 #if OMPX_TASKGRAPH
   kmp_tdg_status tdg_status = KMP_TDG_NONE;
   kmp_taskdata_t *td = KMP_TASK_TO_TASKDATA(task);
   if (task) {
     if (td->is_taskgraph)
       tdg_status = KMP_TASK_TO_TASKDATA(task)->tdg->tdg_status;
     if (__kmp_tdg_is_recording(tdg_status) && sink->dn.task)
       __kmp_track_dependence(gtid, sink, source, task);
   }
 #endif
   if (sink->dn.task) {
     // synchronously add source to sink' list of successors
     KMP_ACQUIRE_DEPNODE(gtid, sink);
     if (sink->dn.task) {
+      if (!sink->dn.successors || sink->dn.successors->node != source) {
 #if OMPX_TASKGRAPH
       if (!(__kmp_tdg_is_recording(tdg_status)) && task)
 #endif
         __kmp_track_dependence(gtid, sink, source, task);
       sink->dn.successors = __kmp_add_node(thread, sink->dn.successors, source);
       KA_TRACE(40, ("__kmp_process_deps: T#%d adding dependence from %p to "
                     "%p\n",
                     gtid, KMP_TASK_TO_TASKDATA(sink->dn.task),
                     KMP_TASK_TO_TASKDATA(task)));
 #if OMPX_TASKGRAPH
       if (__kmp_tdg_is_recording(tdg_status)) {
         kmp_taskdata_t *tdd = KMP_TASK_TO_TASKDATA(sink->dn.task);
         if (tdd->is_taskgraph) {
           if (tdd->td_flags.onced)
             // decrement npredecessors if sink->dn.task belongs to a taskgraph
             // and
             //  1) the task is reset to its initial state (by kmp_free_task) or
             //  2) the task is complete but not yet reset
             npredecessors--;
         }
       }
 #endif
       npredecessors++;
       }
+    }
     KMP_RELEASE_DEPNODE(gtid, sink);
   }
   return npredecessors;
 }
 
 static inline kmp_int32
 __kmp_process_dep_all(kmp_int32 gtid, kmp_depnode_t *node, kmp_dephash_t *h,
                       bool dep_barrier, kmp_task_t *task) {