[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

333

why is the order here swapped?

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

333

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

333

This looks pretty confusing IMO.

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

333

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

333

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

333

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

333

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

333

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

350

Is this necessary?

[rpereira-dev]

openmp/runtime/src/kmp_taskdeps.cpp

350

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;
 }
 
 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)
+                                                     kmp_depnode_t *sink,
+                                                     kmp_depnode_t *source) {
+  if (!source)
     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);
+    if (__kmp_tdg_is_recording(tdg_status) && source->dn.task)
+      __kmp_track_dependence(gtid, source, sink, task);
   }
 #endif
-  if (sink->dn.task) {
-    // synchronously add source to sink' list of successors
-    KMP_ACQUIRE_DEPNODE(gtid, sink);
-    if (sink->dn.task) {
+  if (source->dn.task) {
+    // synchronously add sink to source' list of successors
+    KMP_ACQUIRE_DEPNODE(gtid, source);
+    {
+      if (source->dn.task) {
+        if (!source->dn.successors || source->dn.successors->node != sink)
 #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);
+        __kmp_track_dependence(gtid, source, sink, task);
+        source->dn.successors =
+            __kmp_add_node(thread, source->dn.successors, sink);
         KA_TRACE(40, ("__kmp_process_deps: T#%d adding dependence from %p to "
                       "%p\n",
-                    gtid, KMP_TASK_TO_TASKDATA(sink->dn.task),
+                      gtid, KMP_TASK_TO_TASKDATA(source->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);
+        kmp_taskdata_t *tdd = KMP_TASK_TO_TASKDATA(source->dn.task);
         if (tdd->is_taskgraph) {
           if (tdd->td_flags.onced)
-            // decrement npredecessors if sink->dn.task belongs to a taskgraph
+            // decrement npredecessors if source->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);
+    }
+    KMP_RELEASE_DEPNODE(gtid, source);
   }
   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) {
   KA_TRACE(30, ("__kmp_process_dep_all: T#%d processing dep_all, "