Controling order of execution of a (compute) shader on an array of vertices (data) in Vulkan

Question

Is it possible to force Vulkan to execute a shader on vertices (data) in a semi-consecutive manner?

For example, if the data passed to the shaders as a binary tree, shader would process it one layer at the time, starting from the root, while allowing multiple nodes to be processed concurrently only if they're on the same layer. I know that synchronicity is a big thing in Vulkan, but I'm unsure if it could be used at this layer of the pipeline.

A use for it would be in a structure where the results of parents influence the results of their children, while the work on the each element is done with the same code.

An example would be to calculate the effect of the wind on a tree - if nodes are the branching points of a tree, the location of each point would depend on the force applied to the source branch, but also on the force applied to each and every of it's ancestors, since each branch would bend, but also move with the rest of the tree - the rotations would add up. Doing it the way I described above would greatly speed up the computation for a single tree, possible increasing performance enough to scale the simulation maybe even several orders of magnitude. The benefits are even greater if you do it for all the trees in the scene at once.

Is this possible with Vulkan? What topics should I look into specifically in order to accomplish this?

Answer 1

Vulkan is not really suited to at least some of the task you're trying to accomplish. It has no mechanism to declare from within a shader that some additional work should be invoked. Or at least, not directly.

The most effective way to execute this on the GPU would be to compute each level of all of the trees as a distinct dispatch operation. So you process all root nodes first, then the first level for each tree, then the second level, etc. Each compute shader invocation will need to do the processing for its node and store that computed data.

This also requires that you store your tree data in a fairly scrambled way. All of your trees need to live (on the GPU side) in the same general array, preferably with all nodes for a particular level stored contiguously with one another. This makes processing easier, but it makes adding new nodes harder.

The biggest performance problem will likely be the dependency issue. Each layer depends on the execution of the previous layer, which means you won't get much parallelism between layers. You're effectively inducing a stall between each set of layers. If you're executing thousands of nodes, you'll saturate your GPU's execution units just fine; it's the first few layers when you have few nodes that will have less performance than they could.

Now, you may be able to avoid this performance problem by using a different shader for the first couple of layers. Such a shader would have each invocation process, say, the first 3 levels of the tree. On the one hand, this mitigates synchronization costs. But on the other hand, each shader invocation has to read and process a lot more data. And reading/writing a bunch of data from multiple invocations can be expensive, compared to having a more pipelined operation.

So you should profile it and see what works best.

Oh, and FYI: OpenGL compute shaders are just as capable of this as Vulkans.