Fuzzer: bad data with virtual instance reductions

[elliottslaughter]

Fuzzer version StanfordLegion/fuzzer@cf5e10d turns on inner tasks (with virtual mappings) for read-only and reduction privileges only. With this fuzzer version I am seeing a failure rate of about 17 per 1,000 with failures being reported as bad data.

$ build/src/fuzzer -fuzz:seed 150 -fuzz:ops 91 -fuzz:skip 89 -level 4
[0 - 7ff849d357c0]    0.000045 {4}{threads}: reservation ('dedicated worker (generic) #1') cannot be satisfied
[0 - 70000e2e9000]    0.060855 {6}{fuzz}: Bad region value: 6819924796, expected: 8019285617

Normally the fuzzer aborts at this point, but I have commented this out so I can complete the run:

https://github.com/StanfordLegion/fuzzer/blob/cf5e10dff468096bfa9642658279f4d70bf9b0a5/src/fuzzer.cc#L532

Legion Spy validates the resulting logs:

$ pypy3 legion/tools/legion_spy.py -lpa spy_0.log 
Reading log file spy_0.log...
...
Pass
Legion Spy analysis complete.  Exiting...

Spy logs here: spy_0.log

The trace shows we are running a set of single, leaf tasks over a partition followed by an inner task running on the same partition with the same reduction op.

$ build/src/fuzzer -fuzz:seed 150 -fuzz:ops 91 -fuzz:skip 89 -level 4,fuzz=2
[0 - 7ff849d357c0]    0.000046 {4}{threads}: reservation ('dedicated worker (generic) #1') cannot be satisfied
[0 - 70000b2cb000]    0.034604 {3}{fuzz}: Fuzzer Configuration:
[0 - 70000b2cb000]    0.034627 {3}{fuzz}:   config.initial_seed = 150
[0 - 70000b2cb000]    0.034629 {3}{fuzz}:   config.region_tree_depth = 1
[0 - 70000b2cb000]    0.034642 {3}{fuzz}:   config.region_tree_width = 4
[0 - 70000b2cb000]    0.034644 {3}{fuzz}:   config.region_tree_branch_factor = 4
[0 - 70000b2cb000]    0.034646 {3}{fuzz}:   config.region_tree_size_factor = 4
[0 - 70000b2cb000]    0.034648 {3}{fuzz}:   config.region_tree_num_fields = 4
[0 - 70000b2cb000]    0.034650 {3}{fuzz}:   config.num_ops = 91
[0 - 70000b2cb000]    0.034652 {3}{fuzz}:   config.skip_ops = 89
[0 - 70000b2cb000]    0.060233 {2}{fuzz}: Operation: 89
[0 - 70000b2cb000]    0.060247 {2}{fuzz}:   Launch type: single task
[0 - 70000b2cb000]    0.060249 {2}{fuzz}:   Task ID: VOID_LEAF_TASK_ID
[0 - 70000b2cb000]    0.060255 {2}{fuzz}:   Launch domain: <0>..<3>
[0 - 70000b2cb000]    0.060259 {2}{fuzz}:   Elide future return: 0
[0 - 70000b2cb000]    0.060264 {2}{fuzz}:   Fields: 0
[0 - 70000b2cb000]    0.060266 {2}{fuzz}:   Privilege: LEGION_REDUCE
[0 - 70000b2cb000]    0.060268 {2}{fuzz}:   Region redop: SumReduction<uint64_t>
[0 - 70000b2cb000]    0.060290 {2}{fuzz}:   Projection: 1048576
[0 - 70000b2cb000]    0.060302 {2}{fuzz}:   Partition: LogicalPartition(1,IndexPartition(9,1),FieldSpace(1))
[0 - 70000b2cb000]    0.060306 {2}{fuzz}:   Shifting shard points by: 0
[0 - 70000b2cb000]    0.060309 {2}{fuzz}:   Task: 0
[0 - 70000b2cb000]    0.060312 {2}{fuzz}:     Shard point: (0)
[0 - 70000b2cb000]    0.060357 {2}{fuzz}:   Task: 1
[0 - 70000b2cb000]    0.060360 {2}{fuzz}:     Shard point: (1)
[0 - 70000b2cb000]    0.060369 {2}{fuzz}:   Task: 2
[0 - 70000b2cb000]    0.060371 {2}{fuzz}:     Shard point: (2)
[0 - 70000b2cb000]    0.060377 {2}{fuzz}:   Task: 3
[0 - 70000b2cb000]    0.060379 {2}{fuzz}:     Shard point: (3)
[0 - 70000b2cb000]    0.060389 {2}{fuzz}: Operation: 90
[0 - 70000b2cb000]    0.060392 {2}{fuzz}:   Launch type: index space
[0 - 70000b2cb000]    0.060393 {2}{fuzz}:   Task ID: VOID_INNER_TASK_ID
[0 - 70000b2cb000]    0.060396 {2}{fuzz}:   Launch domain: <0>..<1>
[0 - 70000b2cb000]    0.060398 {2}{fuzz}:   Elide future return: 0
[0 - 70000b2cb000]    0.060400 {2}{fuzz}:   Fields: 0
[0 - 70000b2cb000]    0.060402 {2}{fuzz}:   Privilege: LEGION_REDUCE
[0 - 70000b2cb000]    0.060404 {2}{fuzz}:   Region redop: SumReduction<uint64_t>
[0 - 70000b2cb000]    0.060407 {2}{fuzz}:   Partition: LogicalPartition(1,IndexPartition(9,1),FieldSpace(1))

Running Legion fixinvalidation at 86912ba

[elliottslaughter]

Edited to add Spy logs to the original issue.

[lightsighter]

This is pretty bizarre. The Legion Spy graph from a failing run looks well formed to me.
event_graph_top_level_2.pdf

[lightsighter]

Actually I might see the issue.

[lightsighter]

I don't think this is an issue in Legion. I think there is a bug in the fuzzer in terms of how it inlines the shadow inner tasks. It's mutating the regions directly in that inner task instead of launching a further sub-task and as a result the right values aren't being used to mutate (reduce into) the regions.

I hand checked Legion Spy's verification and it is correctly. Also, when you turn on detailed Legion Spy logging that current disables the inner task optimization in Legion, so these programs are really just failing with normal virtual mappings and reductions. The Legion Spy graph is definitely correct though and the failures are deterministic, so I really doubt that Legion is doing something wrong here.

[elliottslaughter]

It's always possible there's a fuzzer bug, but I'm not seeing it based on your description.

The inner task implementation just turns around and calls the leaf task body with the same region requirements:

https://github.com/StanfordLegion/fuzzer/blob/cf5e10dff468096bfa9642658279f4d70bf9b0a5/src/fuzzer.cc#L266-L283

Note that currently there will always be 0 or 1 region requirement, so the loop is degenerate. (We set 0 region requirements when the field set is empty, to avoid runtime warnings. Otherwise we always create exactly 1 region requirement.)

Meanwhile, on the shadow copy we actually do not launch a task at all, whether the task is inner or otherwise. Instead we manually run the projection functor (if required), grab the subregion, and directly invoke the mutation function inline.

For index space launches: https://github.com/StanfordLegion/fuzzer/blob/cf5e10dff468096bfa9642658279f4d70bf9b0a5/src/fuzzer.cc#L1032-L1043

For single task launches: https://github.com/StanfordLegion/fuzzer/blob/cf5e10dff468096bfa9642658279f4d70bf9b0a5/src/fuzzer.cc#L1071-L1080

Since the inner task launches exactly one subtask (because there is exactly one region requirement), these should be equivalent.

There can be issues with calling REDOP::fold vs REDOP::apply, because in the shadow copy we do not have a reduction instance at all, but are using a normal instance inline-mapped as READ_WRITE. However, you will note at the top of this issue that the reduction issue in question is SumReduction<uint64_t>, for which fold and apply are equivalent.

Notably, this is exactly the same logic we use validate runs with concrete instances, for which I am currently 50% of the way through validating 100,000 runs with 1,000 operations each, with no failures so far.

Therefore, the only possible issue is in the execution or implementation of the inner_task_body. I don't see how it could be an implementation issue, but if you see a bug there, let me know.

[elliottslaughter]

Am I reading this right? In your rendered event graph I see two tasks, UID 41 and UID 58, both reducing into the same field of the same instance. I see two fills, fill 14 and fill 18, preceding those. And I don't see any synchronization or data movement path that would synchronize those.

Aren't those tasks racing?

[lightsighter]

Yeah this is why I originally didn't allow reduction re-use. There are all sorts of bad cases like this that can occur in different contexts which are really hard to scope.

[lightsighter]

I think the only way to make this safe is actually to say that if you pick a non-leaf variant for a task with reduction-only privileges on some region requirements then you have to virtual map those reduction-only requirements. That should mean that all reduction instances are being reused in the same parent task context and the right analysis will happen.

[lightsighter]

Obviously we'll need to get approval for that in a Legion meeting.

[elliottslaughter]

Do you mean the non-leaf task's instance must be concrete?

Or do you mean, reuse will only be allowed within the same parent task? (So the leaf grandchild of the inner child will be forced to use a fresh instance?)

[lightsighter]

Do you mean the non-leaf task's instance must be concrete?

I'm saying non-leaf task must virtually map reduction-only region requirements.

Or do you mean, reuse will only be allowed within the same parent task?

That is an alternative implementation, but I think I prefer the requirement that all non-leaf tasks with reduction-only requirement virtually map them.

So the leaf grandchild of the inner child will be forced to use a fresh instance?

Or another reduction instance already in that context. But again you would only need to do that if we don't go the route of virtual mapping reduction-only requirements for inner tasks. I think I prefer the virtual mapping approach because it means that reduction instances aren't just scoped to the context of their immediate parent task.

[lightsighter]

So switching to virtual mapping of the inner tasks makes this work and the test is much happier. The event graph is correct too.
event_graph_top_level_2.pdf

[elliottslaughter]

Isn't EXCLUSIVE coherence supposed to guarantee that you get exclusive access to your reduction instance? This is x86 so the symptoms are probably not observable, but I wrote the task assuming exclusive access. In the event graph above it still appears that the tasks themselves are racing on the instance, though the fill and subsequent copy are properly synchronized.

[lightsighter]

Isn't EXCLUSIVE coherence supposed to guarantee that you get exclusive access to your reduction instance?

No, right now for reduction privileges EXCLUSIVE coherence is the same as ATOMIC coherence. See #788.

In the event graph above it still appears that the tasks themselves are racing on the instance, though the fill and subsequent copy are properly synchronized.

You can't see the reservations that Legion put around the use of the reduction instance in the Legion Spy graph, but Legion Spy is checking for their presence. They guarantee that one of the reduction tasks will go first and the other will go second.

[lightsighter]

Note the reservations were there even in the prior graph as well so there was no race there. The problem in the previous graph was the superfluous fill that was racing.

[lightsighter]

Legion Spy now correctly recognizes that there is an issue with this test case.

[lightsighter]

After the discussion in the Legion meeting this week, I went off and had a bit of a think about this issue and I actually think I have an even better solution than what I presented in the meeting. The good news is that it will fix this issue and clean-up a bunch of messy semantics that we used to have. The new approach will however depend on us doing #1528 and removing must-epoch launches as they are incompatible with the proposed changes.

Here is the core idea: all non-leaf tasks in the task tree effectively will share the same scope for physical analysis for a region as the task that created the root logical region for that region tree. This differs from today where non-leaf tasks can map instances (instead of virtually mapping their regions) and this creates a new "scope" for those logical regions separate from the enclosing parent task. Instead in this new semantics, even if the task creates a concrete mapping for a region, any sub-tasks that it launches will be mapped in the same context as the task itself. There are several important situations to consider here:

• If we have two non-leaf tasks with read-only privileges on the region running in parallel: this is fine, their sub-tasks can make as many read-only copies of the region as they want. If they race to update the equivalence set(s) for the region it doesn't matter because whichever ones get there first will win the benign race to issue copies and later tasks arriving at the equivalence set will see the updated instances and hook up dependences correctly.
• If we have two non-leaf tasks with reduction-only privileges on the region running in parallel: this is similar to the failure mode here and it will also work correctly since whichever sub-tasks map first will win the benign race and initialize new reduction instances and the later arriving sub-tasks from either non-leaf task will see those changes and do the right thing.
• If we have a read-write exclusive non-leaf task: we know nothing else can be mapping in parallel with it, so it can launch all of it's sub-task and map them in order updating the relevant equivalence sets, and then when it is done mapping later things can map also using the same equivalence sets. Note that this even works if there are two non-leaf tasks using relaxed coherence modes (e.g. simultaneous) because we still require those non-leaf tasks to map in order and each of them are not considered map until all their child sub-tasks are mapped (cummulativity). So the right thing happens even with relaxed coherence modes.

The only place where this doesn't work is with must-epoch operations because there we actually do have potentially two or more non-leaf tasks with read-write simultaneous on the same logical region executing and launching sub-tasks in parallel (e.g. the "shards" of static control replication) which would then be racing to update the equivalence sets, and that just does not work at all.

Let me know if anyone has any thoughts about this approach. I'll bring it up in the Legion meeting next week since it would mean expediting the removal of static control replication features which I was going to request to do anyway next week, but this is another reason to start doing it.

[elliottslaughter]

I'm going to remove SCR anyway so that is not an issue.

But what about concurrent index space launches? Are we saying that all such tasks must be leaf tasks?

[lightsighter]

But what about concurrent index space launches? Are we saying that all such tasks must be leaf tasks?

Concurrent index space task launches must still have non-interfering region requirements in order to guarantee that they can run concurrently (like a normal index space task launch). That ensures the necessary invariant for the above to work for all the cases except for read-write-simultaneous. What we need to decide is whether read-write simultaneous meets the definition of non-interfering region requirements. Today, read-write simultaneous does not count as non-interfering except for in the case of must-epoch launches: two tasks with read-write simultaneous (or one with read-write simultaneous and one with some other privilege simultaneous) always incur a mapping dependence between them until they resolve whether or not they map to the same physical instance. If the first task is a non-leaf, then it won't be mapped until it runs, launches all its children, and all it's children are mapped. That clearly doesn't work with concurrent index task launches and you'll get an error if you tried to do that today. The only way this works today is if you do this with must-epoch launches where we have special cases littered all over the runtime to allow such a relaxation of the mapping dependences. Getting rid of must-epoch launches eliminates the one case where this breaks down. Nobody has had a need to have read-write simultaneous be non-interfering outside of must-epoch launches yet (including Legate and FlexFlow with concurrent index space task launches), so I'm inclined to keep things that way unless someone makes a compelling case for read-write simultaneous to be considered non-interfering.

[lightsighter]

As an aside: I think the reason concurrent index space task launches today don't need read-write simultaneous to be non-interfering is that they don't actually rely on communication through the simultaneously mapped region the way that static control replication does. Instead, they are doing MPI or NCCL collective calls inside the concurrent index space task launches to do communication, but the actual sub-regions of the point tasks are non-interfering with each other.

There is one place where I can think that we might get into trouble and that is with read-write replicated where all the point tasks are producing the same output region. That's a very special case and I'm inclined to enforce that you can only do that with a leaf task variant.

[elliottslaughter]

There's one major class of computations that I'm concerned we're disallowing with this change: genuinely concurrent computations.

Admittedly, Legion already isn't great for this and the situation has been hacky at best. However, there are certain computations I have worked on where genuine concurrency would have fit the application domain better than what I ended up writing.

An example is Psana and Spinifel. One of our goals in Spinifel was to process data as it was coming in. Because you don't know how fast the data transfer is going, you don't know how much application work to do vs I/O. You can model it as a sequential computation by just fixing the ratio at some constant K, but this is a hack. As a result you end up with a tunable you need to tune separately on every machine (and possibly at every node count / application configuration), and even then what you have is not dynamically responsive to the running application.

By the way, the reason why Psana isn't easy to tune dynamically is because it has deep task hierarchy. What you want to have is a tree of tasks, where the root of the tree reads "small" data (i.e., a minimized record of what events are in the data files), and as you go down the tree you progressively inflate the data and do more and more expensive computations. At the leaves, you have "big" data which you then process—a structure that perfectly maps to Legion ONLY if the computation itself is trivially parallel.

If the computation is NOT trivially parallel (as it is in Spinifel), then what you end up needing is more akin to two task trees. You want one task tree for reading I/O, you want to have a handoff (somehow) in the middle, and you want your second task tree taking whatever is the most recent version of the data and running with it. Unsurprisingly, I did not actually get this structure to work because Legion makes assumptions that programs can be run in sequential order (which this cannot), and thus makes it difficult to correctly issue the appropriate amount of outstanding work. Very screwy things can happen here and it is easy to end up in a livelock type situation where you are starving one side of the computation or else get very jittery performance. Thus we ultimately settled for the fixed-ratio K approach even though it's not an ideal solution.

So, on the one hand I never got this to work anyway, but on the other hand I am somewhat concerned that this type of thing (if not Psana specifically) does come up from time to time, and we don't really have a solution to it, even by way of escape hatches to get out of Legion's standard semantics that make the concurrency the user's responsibility.

[mpokorny]

While I certainly don't understand a lot of the discussion on this issue, what @elliottslaughter said about concurrency in Legion applications sounded a few bells. My application has at least one computation (A) that should probably be done concurrently, in which the main data stream uses whatever result A provides whenever it is updated, but can proceed with an "old" result from A until that time. Currently I just ignore that concurrency aspect, and depend on the "new" result of A as soon as that computation begins, but real concurrency would likely be of some benefit. I'm only mentioning this to lend my support to avoiding changes that make true concurrency any more difficult to achieve (if I ever get around to implementing that).

[lightsighter]

This should probably be a topic of discussion in the Legion meeting next week (@mpokorny can you make it?).

Unsurprisingly, I did not actually get this structure to work because Legion makes assumptions that programs can be run in sequential order (which this cannot)

So to be very clear, what I'm proposing here is weaker than requiring that programs have to be able to run in sequential order. I am proposing that they have to be able to be capable of being mapped in sequential order. Actual execution order can be parallel/concurrent. I suspect that is probably still not weak enough for the PSANA use case that you describe because it would still require that all the sub-tasks in the I/O part of the task tree are mapped before any of the sub-tasks in the "running" part of the task tree are mapped.

To illustrate why this is necessary, consider a task tree that looks like this (labeled in sequential order):

     A
   /   \
  B     D
  |     |
  C     E

Let's say that A creates a logical region R, and that each of B, C, D, and E want read-write privileges on region R. To run in parallel, both B and D request read-write simultaneous on R and map to instance X. Let's consider the case where we allow both mapping and execution concurrency, meaning that B and D both map and start running at the same time. They launch their sub-tasks (C and E respectively) and then those sub-tasks go to map. Consider the case where C and E both happen to pick the same instance Y to map to. Now realize that because B and D are running in parallel, they each have their own "scope" for determining what the valid instances are. Let's say C wins the mapping race and it issues it's copy from X to Y and starts running. Then after C has started running and mutating instance Y, E comes along and maps which also triggers a copy from X to Y. This copy stomps on top Y at the same time C is still mutating it. I suspect that you guys would be very surprised if something like that was permitted to happen. 😉

Now you might ask: why not get rid of the separate scopes for B and D and have them map in the same enclosing scope of A, similar to how we proposed doing it above for read-only, reduce-only, and read-write exclusive/atomic cases. The problem there is that the analysis for copy-in/copy-out semantics for read-write simultaneous (restricted) cases are not designed to be atomic today. They require multiple steps and there's nothing at the moment other than mapping dependences that ensure that things happen in the right order. Mapping dependences only exist between tasks launched by the same parent task. So to support this would require adding some atomicity mechanism to the mapping of tasks these simultaneous cases. Maybe we could come up with something like that but it would almost certainly be something that is global in scope which might be expensive.

[elliottslaughter]

To clarify, the way Legion works now is NOT ideal for concurrency, nor the best way to handle the needs of those use cases (either from an implementation or a user perspective). Therefore, I am not defending the current feature set as much as raising this use case so that everyone is aware. I think it would be worth thinking about what first-class support for concurrency would actually look like, and that might mean ripping out the current must epoch launches and starting with a clean slate.

Sharing some more details about how Psana worked the last time I tried this:

As I recall, I ended up giving up on regions entirely. Instead I created a global variable in every process that held a buffer, which I protected with a lock. This buffer was not visible to Legion at all, it was just some random Python object. On the producer side of the computation, I would lock the buffer and push the data into it. On the consumer side, I would grab whatever data happened to be available but not wait around to see if more was produced. This worked ok-ish if I remember, except that it was difficult to control the relative rate of tasks on each side. Since both sides were spinning as fast as possible, it was easy to get into situations where I was wasting a lot of effort (and potentially starving out the other side) due to the spinning.

So, this never really worked that well and I don't think removing must epochs would make it substantially harder, unless we remove the ability to have non-leaf concurrent index launches. (For this use case, the launches would not need to have any region requirements at all; the concurrency is only required so that the computations run at the same time.)

As for the task tree in Mike's last comment: this is already a problem in today's semantics. The reason is that the current simultaneous coherence is already too restrictive. It really only works with one-level region tree hierarchies, and Psana's was deeper than that. Therefore, what I wanted to do was to pass a root region as read-write-simultaneous, but then not allocate it in a specific instance, and assign subregions (or subregions of subregions) to specific tasks that would then (somehow) use this for handing off data from one side of the computation to the other. This has never worked in Legion due to Legion's requirement that tasks can only run concurrently with simultaneous coherence if they use the same instance. Therefore, from the perspective of Psana specifically, the proposed changes do not break any capabilities that we used to have. On the other hand, this also means that there is a gap in Legion that we have never filled either.

[lightsighter]

So, this never really worked that well and I don't think removing must epochs would make it substantially harder, unless we remove the ability to have non-leaf concurrent index launches.

There's no plans to restrict concurrent index task launches beyond their existing restrictions. They can map whatever task variants they want. At the moment we do require that they have non-interfering region requirements.

The reason is that the current simultaneous coherence is already too restrictive. It really only works with one-level region tree hierarchies

I would actually argue that you can have deeper region trees, we just expect all the concurrent tasks using that region map to the same physical instance such that coherence can be maintained currently (e.g. restricted coherence).

Therefore, what I wanted to do was to pass a root region as read-write-simultaneous, but then not allocate it in a specific instance, and assign subregions (or subregions of subregions) to specific tasks that would then (somehow) use this for handing off data from one side of the computation to the other.

I think this is the second thing I proposed above which would allow read-write simultaneous to do a virtual mapping; that is more expensive but allows Legion to maintain coherence of the data even when there are multiple concurrent tasks. We'd have to think really carefully about how tasks from different contexts that are relying on this mechanism for coherence would work. Can coherence of data be established at mapping time or does it need to wait until runtime being the most obvious question here that would likely create quite a challenge. Presumably you have some way that you want to say that, but I bet we're lacking the primitives for you to say what you actually want at the moment. However, there's at least a viable path there.

except that it was difficult to control the relative rate of tasks on each side.

I don't think there's going to be anything that Legion can do to help you here in a concurrent world because there's no data dependences to guide the execution (most tasks are racing). Instead you'll need to have a sophisticated implementation of select_tasks_to_map in your mapper to guide which order and how many tasks are going to be mapping and running at a time.

In summary, when it comes to concurrency, I think there are two dimensions to the design that we consider:

1. Data coherence: I think it is possible to generalize Legion's data coherence mechanisms to work in the case of concurrent subtasks (e.g. C & E in my example above). There are some open questions to answer, but I see a path.
2. Scheduling: I don't think there's much of anything that Legion can do here. We expose this problem up through select_tasks_to_map and at that point the mapper has to do something intelligent to make sure the right tasks map in the right order to avoid running out of memory.