Definition of synchronization scopes as sets

[williamih]

I've been trying to understand from the Vulkan spec the precise definition of a synchronization scope. It's not clear to me whether a synchronization scope is:

1. A set of pipeline stages. For example, a synchronization scope could be {TRANSFER, VERTEX_SHADER}.
2. Or, a set of operations. For example, { Copy region R from buffer B to C, Run vertex shader V }. That is, a synchronization scope would be the set of actual operations across the relevant pipeline stages.

The consensus seems to be that the first definition is correct. For example, my reading of the answer to this StackOverflow question (https://stackoverflow.com/questions/63587925/what-happens-when-srcstagemask-specifies-a-stage-which-is-not-in-the-pipeline-of) seems to indicate definition 1.

Another example is the blog post at https://themaister.net/blog/2019/08/14/yet-another-blog-explaining-vulkan-synchronization/ in which the discussion of execution dependency chains also seems to imply definition 1.

However, assuming definition 1 is the intention, this seems to potentially present an issue with the definition of execution dependency in S 7.1. Execution and Memory Dependencies of the Vulkan spec.

The spec states:

Let A and B be separate sets of operations.

Let S be a synchronization command.

Let A_S and B_S be the synchronization scopes of S.

Let A' be the intersection of sets A and A_S.

Let B' be the intersection of sets B and B_S.

If the synchronization scopes A_S and B_S are sets of pipeline stages according to definition 1, then the use of the term intersection seems like it doesn't match the standard mathematical meaning of set intersection. I.e. A_S would contain pipeline stages and A would contain operations, so we are taking the intersection of sets containing different types of objects. Is the spec using the term intersection in a more informal sense rather than the specific mathematical concept of set intersection?

I'd really appreciate any insight into whether definition 1 or 2 is correct, and if definition 1, then how should the term intersection be interpreted?

[krOoze]

You don't have to look all over the internet for explanatoring middle-men. Synchronization scope is what the specification says synchronization scope is:

Synchronization commands introduce explicit execution dependencies, and memory dependencies between two sets of operations defined by the command’s two synchronization scopes.

The synchronization scopes define which other operations a synchronization command is able to create execution dependencies with. Any type of operation that is not in a synchronization command’s synchronization scopes will not be included in the resulting dependency.

Simply put, synchronization scope is whatever scopes the extent of what the synchronization applies to.

There are two synchronization scopes to a synchronization operation. A synchronization command introduces a dependency such that it is guaranteed that stuff referred to by the first\source synchronization scope happens-before stuff referred to by the second\destination synchronization scope.

Each synchronization primitive then specifies concretely what its synchronization scopes are, and it can use whichever scoping\filtering rules it wants (including pipeline stages). For example semaphore signaling:

The second synchronization scope includes only the semaphore signal operation.

You can see the second synchronozation scope does not mention pipeline stages at all, nor is there even something like PIPELINE_STAGE_SEMAPHORE_SIGNAL, so 1. cannot be true generally.

It wouldn't even make sense. Synchronization can only synchronize things that are executed at some specific time. But there's nothing to synchronize against in a pipeline per se. Pipeline is not a finite state machine. In FSM, nodes could be said to be activated at the time the token walks through the FSM's nodes. Pipeline is not executed. It does not happen at some specific time. Pipeline always exists (and so do its stages). Operations flow through the pipeline instead. Hence the name "pipeline". It is a common misconception, because a diagram representing FSM and pipeline can look identically. But the substance of these concepts is different.

The execution dependency specification is somewhat important to understand, though the generic letters used do not help comprehension, and you need to read it 42 times to get it. Let's see if I can walk you through it:

• Let A and B be separate sets of operations.
• Let S be a synchronization command.
• Submitting A, S and B for execution, in that order, will result in execution dependency E between A' and B'.
• Execution dependency E guarantees that A' happens-before B'.

That's basically what was introduced in the intitial paragraph of the chapter. A synchronization operation (S resp. resulting dependency E) is something that guarantees some stuff (A') is executed before some other stuff (B'). Otherwise there would be no restraints ( A' and B' could execute in any order, interleaved\pre-empted, or in parallel, or whatever you can imagine).

For example:

A: vkCmdDraw();
A: vkCmdDispatch();
S: vkCmdPipelineBarrier();
B: vkCmdDrawButCooler();
B: vkCmdCopyImage();
vkQueueSubmit( the_above_stuff );

A and B are those commands, resp. a set of whatever queue operations they spawn.

A, S, and B was "submitted for execution, in that order". So we get an Execution Dependency E between A' and B', that ensures A' executes before B'. Whatever A' and B' is.

Now we know what A and B is. A' is what results by scoping A. B' is what results by scoping B.

• Let Aₛ and Bₛ be the synchronization scopes of S.

As introduced above, this formally says every Synchronization operation type has its synchronization scopes (first\source synchronization scope Aₛ, and destination synchronization scope Bₛ). Those scopes are concretely specified for each synchronization primitive, and can be further parametrized when the synchronization primitive is invoked (such as by the pipeline stages per specific vkCmdPipelineBarrier). Above I quoted "second synchronization scope" from Semaphore Signaling operation. You will find similar paragraphs for Semaphore Waiting operation, as well as for other synchronization primitives like Barriers, Subpass Dependencies, Events, and Fences.

• Let A' be the intersection of sets A and Aₛ.
• Let B' be the intersection of sets B and Bₛ.

We scope A (resp. B) to only A' (resp. B').

To put it humanely, we "select" only those operation in A that match the scope of the synchronization (Aₛ).

There cannot be a dependency with something in Aₛ that we have not even submitted to queue. And we do not want to (and sometimes cannot) synchronize with everything that was submitted before, so we only select some subset of A. I.e. we want only dependency between stuff that is in the scope and actually exist in the queue. We are making a set intersection!

[williamih]

Thanks @krOoze! Really appreciate the detailed response. That's very helpful. Your notes on pipelines vs FSMs are interesting.

I'm still wondering about the use of set intersection in the execution dependency definition. Let's consider the following from the spec:

Let A' be the intersection of sets A and A_s

Using the normal definition of set intersection, this gives us A' = { x : x ∈ A and x ∈ A_S }

This raises the question of the meaning of the set membership symbol ∈ in this context. The Vulkan spec clearly states that the set A is a set of operations, so evidently x must be an operation in order to satisfy x ∈ A. In that case, how should we interpret the predicate x ∈ A_S? If x is an operation, then that would seem to imply A_S must contain operations in order for the set-membership to potentially be true.

So if the synchronization scope A_S was a set of operations, that would seem to fit with the set intersection definition above. However, if A_S is a set of operations, this seems to contradict the interpretation of execution dependency chains.

Consider this example:

vkCmdDispatch(...)
vkCmdPipelineBarrier(VK_PIPELINE_STAGE_COMPUTE_SHADER_BIT, VK_PIPELINE_STAGE_TRANSFER_BIT, ...)
vkCmdPipelineBarrier(VK_PIPELINE_STAGE_TRANSFER_BIT, VK_PIPELINE_STAGE_COMPUTE_SHADER_BIT, ...)
vkCmdDispatch(...)

Does this form an execution dependency chain so that there is a dependency between the second dispatch and the first dispatch (in submission order)? Notably, there is no actual transfer operation occurring in this example. The two links I gave in my original post suggest that this does, in fact, create a dependency chain even though there is no transfer operation.

Now supposing A_S and B_S are sets of operations, then clearly neither set contains a transfer operation, because no transfer operation was submitted to the queue in the above code. For an execution dependency chain, the spec requires the following:

For each consecutive pair of execution dependencies, a chain exists if the intersection of B_S in the first dependency and A_S in the second dependency is not an empty set.

Given that the second synchronization scope of the first dependency, and the first synchronization scope of the second dependency, both specify VK_PIPELINE_STAGE_TRANSFER_BIT, but there is no actual transfer operation, then A_S and B_S would have to be empty sets if they are sets of operations. Thus, if A_S and B_S are sets of operations, then this implies the above example would not create an execution dependency chain.

Do you think the above example does create a dependency chain? If so, how does that fit with the question of the interpretation of set intersection discussed above? Many thanks!

[krOoze]

Your notes on pipelines vs FSMs are interesting.

Many ambiguities and confusion can be tracked to this. It's hard to unlearn to think automatically of everything as being a FSM (we like it too much), but if one does, then at minimum Vulkan sync start to feel obvious and natural.

E.g. "how can this barrier synchronize with STAGE_COOL if stage cool is never even executed?". The question itself is not valid, because stages are not executable and so are not a thing that can ever "be executed" or "not executed". The ambiguity ceases to exist. Sometimes answers do not make sense, because the question were the problem all along. Analytic philosophy.

Using the normal definition of set intersection, this gives us A' = { x : x ∈ A and x ∈ A_S}

Well yea. I didn't know there were non-normal definitions of set intersections. I suspect massive level of overthinking will follow. I like where this is going already. 🤤

If x is an operation, then that would seem to imply A_S must contain operations in order for the set-membership to potentially be true.

Not concrete operations. Scope of operations.

For example: let scope B_S be "all operations in STAGE_VERTEX". And let scope A_S be ""all operations in STAGE_FRAGMENT". Then intersection of scopes B_S and A_S is "all operations in STAGE_VERTEX, STAGE_TCS, STAGE_TES, STAGE_GEOMETRY, or STAGE FRAGMENT". It is not an empty scope. Operation can hypothetically satisfy this filter. Empty scope would be intersection of B_S = STAGE_BOTOM and A_S = STAGE_TOP. That results in scope "no operations".

However, if AS is a set of operations, this seems to contradict the interpretation of execution dependency chains.

Sure. But not if you accept the clarification above. Feel free to improve the spec language for clarity and better accessibility.

Does this form an execution dependency chain so that there is a dependency between the second dispatch and the first dispatch (in submission order)? Notably, there is no actual transfer operation occurring in this example.

Well let me give you this quote from old version of the specification:

A pair of consecutive execution dependencies in an execution dependency
chain accomplishes a dependency between the stages A and B via
intermediate stages C, even if no work is executed between them that
uses the pipeline stages included in C.

Do you think the above example does create a dependency chain? If so, how does that fit with the question of the interpretation of set intersection discussed above? Many thanks!

So, I do. It fits per above weasling around the Issue.

The uberold specification did try to specify stuff in terms of pipeline stages, but it didn't work out. Nevertheless it strongly implies it means to work this way I say. This issue might be a vestige of the switch to more conceptual and formalistic explanation of things.

[Tobski]

Thanks for jumping on this one @krOoze! @williamih are there any other questions you have outstanding or are you satisfied with the response? If so can this issue be closed?

[williamih]

Thanks for following up on this @Tobski! I have a better understanding of the intent of the spec now thanks to @krOoze - really appreciate the help.

However, I do think there is the potential to make this mathematically a bit more precise, so could this please stay open? In particular, I think the notion of set intersection is being used in two different ways that are not mathematically the same: in the definition of the sets A' and B' based on operations and synchronization scopes; and in the definition of execution dependency chains.

I will try to think of some more specifics on this to clarify this further, so I can follow up after that.

[Tobski]

@williamih certainly - we'll wait for you to update then, and I'll at least take a look at the use of intersection in the interim.

[williamih]

@Tobski Thanks for waiting for me on this. Here's some more details on this.

In order to understand what is meant by "set intersection" in the context of synchronization scopes, I think we need to be able to specify exactly which individual objects are in the sets. That is, without a mathematical definition of a synchronization scope, we can interpret the concept of set intersection in an informal / intuitive sense, but not really in a strict mathematical sense. This is something I found confusing when reading the spec - the language around synchronization is phrased in quite a mathematical way (which is good!) but then a synchronization scope is defined informally rather than more mathematically. So, I think it would be good to formulate a more mathematical definition.

In my original post, I considered two alternative ways of defining synchronization scopes:

1. A set of pipeline stages. For example, a synchronization scope could be {TRANSFER, VERTEX_SHADER}.
2. Or, a set of operations. For example, { Copy region R from buffer B to C, Run vertex shader V }. That is, a synchronization scope would be the set of actual operations across the relevant pipeline stages.

Discussion with @krOoze helped me to understand that neither of these definitions appear to adequately capture the intent of the Vulkan spec given the set intersection operations stated in the spec.

In particular, @krOoze pointed out that definition (1) isn't sufficient because it isn't relevant for semaphore signaling, which doesn't directly correspond to a particular pipeline stage:

The second synchronization scope includes only the semaphore signal operation.

Definition (2) is also not sufficient because of the potential for execution dependency chains even when no work is executed between the pipeline stages. @krOoze pointed out that an earlier spec version included this wording:

A pair of consecutive execution dependencies in an execution dependency
chain accomplishes a dependency between the stages A and B via
intermediate stages C, even if no work is executed between them that
uses the pipeline stages included in C.

While the current version of the spec doesn't use this wording, my understanding is the intent is the same. This potential for dependency chains with intermediate stages C causes an issue with definition (2): if a synchronization scope is defined to contain operations, and if no work is executed using the stages in C, the synchronization scopes relating to C would be empty sets. Hence, there would be no dependency chain in this case, which appears to contradict the intent of the spec. (My earlier comment on this issue has more details on this).

In particular, I find this wording a bit confusing in S 7.1 Execution and Memory Dependencies:

Let A' be the intersection of sets A and A_S.
Let B' be the intersection of sets B and B_S.

If a synchronization scope is not a set of operations (as discussed earlier, defining a synchronization scope as a set of operations causes issues), then in my view, it does not make sense to intersect a set of operations (A or B) with something that is not a set of operations (a synchronization scope).

[williamih]

Here's one option to potentially make this clearer.

It seems to me that a key issue is that in some cases a synchronization scope refers to pipeline stages, and in at least one case (semaphore signaling) a scope refers to a specific operation.

One potential way to address this could be to make it explicit that a synchronization scope can include either of these concepts.

E.g. we could define a synchronization scope Z as an ordered pair Z = (P, Q) where P is a set of pipeline stages and Q is a set of operations.

We could then update the text in S 7.1 Execution and Memory Dependencies that currently reads as follows:

Let A and B be separate sets of operations.
Let S be a synchronization command.
Let A_S and B_S be the synchronization scopes of S.
Let A' be the intersection of sets A and A_S.
Let B' be the intersection of sets B and B_S.

This could be changed to something like:

Let A and B be separate sets of operations.
Let S be a synchronization command.
Let A_S = (P_A, Q_A) and B_S = (P_B, Q_B) be the synchronization scopes of S.
Let A' = {x in A | x is in Q_A or x uses a pipeline stage in P_A}
Let B' = {x in B | x is in Q_B or x uses a pipeline stage in P_B}

Then we could make similar updates in other places in the spec (e.g. the definition of execution dependency chains could consider the intersection of the sets of pipeline stages).

This is just one idea though - could be other ways to address this!

[Tobski]

Ok, I think I see the problem and I do understand the confusion. The way I think about this is that a pipeline stage is just a specifier for a set of operations - e.g. EARLY_FRAGMENT_TESTS is a specifier for "all fragment test operations performed before fragment shading". Perhaps we could call this out better?

Maybe we could even change it to "potential" operations, given that even if no operations are actually performed it still counts; both in the sense of chains as you've described, but also in things like draw commands where parts of the pipeline are not actually executed (e.g. raster discard).

Would something like that work?

[Tobski]

(Also thanks for the detailed explanation and feedback!)

[williamih]

Thanks @Tobski!

Could you maybe show some examples of text in the spec that you would potentially change? Doesn't have to be all the changes of course, just enough for me to get the idea.

To check that I'm understanding you:

• You're saying that a synchronization scope is a set of operations.
• However, the operations could be "hypothetical" operations; that is, a synchronization scope contains every potential operation that could run in those pipeline stages, even if the app never actually asks for any operations to be run using those pipeline stages.

Is that correct?

If so, I believe this would fix the issue! The notion of potential / hypothetical operations is a bit of an abstract formalism, but I think that is okay.

[Tobski]

Could you maybe show some examples of text in the spec that you would potentially change? Doesn't have to be all the changes of course, just enough for me to get the idea.

Sure. It might take me a bit to get to this as there's a lot going on in the next few weeks, but I'll see if I can figure something out and will let you know.

Is that correct?

Yep.

[williamih]

Sure. It might take me a bit to get to this as there's a lot going on in the next few weeks, but I'll see if I can figure something out and will let you know

Sounds good - really appreciate you taking the time to consider this, thanks!

[williamih]

(And of course if I can do anything to help, let me know!)

[krOoze]

Here's some more details on this.

@williamih good summary

I think it is basically a type safety problem. We are mixing "scopes" and "operations" in a set intersection function.

Probably the hyperformalism of using set theory might unnecesserily complicate things.

Scope is a scope. It is a filter. Perhaps clearer would be the semantics of "applying" scope\filter to a set of operations, which yield a subset of those operations. I don't think it is too "abstract" if communicated properly and without trying to put it neat mathematical\hyperformal box.

(As I remember someone tried to put the sequence of memory types in terms of order theory. Once that was deleted, and instead went on to directly say what comes first, and what comes next without the baggage of the whole body of mathematics, it became 1000x more clear. Mathematics is good for describing things that are hard to grasp for a human brain. But there is overhead to mathematics when trying to describe things that are supposed to be simple and obvious in the first place.)

Additionally needs to clarify what an overlap of scope\filters is for the purposes of the dependency chaining. Annoying wordsmithing, but shouldn't be awfully hard. It is basically a transitive property of the sync primitives.

[krOoze]

Here's my attempt at it: #1833

[williamih]

@krOoze That pull request looks great and I think your description of it being a type safety issue is a good explanation of this issue. Have just added a couple of questions to the PR.

I think either this PR or @Tobski's idea of considering "potential" operations would work to fix this issue.

Thanks!

[Tobski]

Thanks @krOoze this looks like a good direction - I was aiming for a small change but I think your cleanup makes sense.