This is an archive of the discontinued LLVM Phabricator instance.

[OpenMP] Optimized trivial multiple edges from task dependency graph
ClosedPublic

Authored by rpereira-dev on Aug 22 2023, 1:15 PM.

Details

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

Diff Detail

Event Timeline

rpereira-dev created this revision.Aug 22 2023, 1:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 22 2023, 1:15 PM
rpereira-dev requested review of this revision.Aug 22 2023, 1:15 PM
rpereira-dev edited the summary of this revision. (Show Details)Aug 22 2023, 1:18 PM
jdoerfert retitled this revision from Optimized trivial multiple edges from task dependency graph to [OpenMP] Optimized trivial multiple edges from task dependency graph.Aug 22 2023, 10:38 PM
jdoerfert added inline comments.Aug 22 2023, 10:39 PM
openmp/runtime/src/kmp_taskdeps.cpp
336

why is the order here swapped?

rpereira-dev added inline comments.Aug 23 2023, 1:31 AM
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 added inline comments.
openmp/runtime/src/kmp_taskdeps.cpp
336

This looks pretty confusing IMO.

rpereira-dev added inline comments.Aug 23 2023, 7:20 AM
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 added inline comments.Aug 23 2023, 7:34 AM
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 added inline comments.Aug 23 2023, 7:46 AM
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 added inline comments.Aug 23 2023, 8:00 AM
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 added inline comments.Aug 23 2023, 8:29 AM
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 requested changes to this revision.Aug 23 2023, 10:55 AM
protze.joachim added a subscriber: 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?

This revision now requires changes to proceed.Aug 23 2023, 10:55 AM
rpereira-dev added inline comments.Aug 23 2023, 11:34 AM
openmp/runtime/src/kmp_taskdeps.cpp
354

no, removing this extra bracket

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 edited the summary of this revision. (Show Details)

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

I think this should work. Please add a test.

Added tests corresponding to the minimal code example attached previously

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.

  • 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

Got trolled yet again by automatic format...

  • Fixed indentation of the 'list' version of the __kmp_depnode_link_successor routine
protze.joachim accepted this revision.Aug 24 2023, 2:08 PM

Lgtm now

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

This revision is now accepted and ready to land.Aug 24 2023, 2:08 PM