2
\$\begingroup\$

I would like to calculate an effect of an external force on a binary tree (wind on a tree).

It's a recursive function - take a (parent) node and calculate the angle to rotate all of the nodes "younger" than the parent around the parent for the same angle according to the force applied. Then do it for the child nodes and repeat until you reach the leaves. If I'm calculating it right this is a problem of O(k * 2^n) complexity, where n is the depth of the tree and k number of nodes.

Since we rotate a lot of stuff (which is a nice matrix multiplication), it would be really nice to do it on the GPU. The problem is that this code needs to run as many times as the depth of the tree, and not all of it can run in parallel.

For each node (vertex) I have to modify all the nodes (vertices) downstream that vertex. This, however, ruins the parallelism of the GPU, since child nodes cannot be calculated before their parents, but the effect should lessen further up the tree I traverse. How do I make the GPU do this efficiently, if you consider the fact that I'll be having multiple trees in the scene?

Basically, on one hand, I have the same code that needs to execute for every vertex in the same way, but on the other, it needs to be executed in order, only vertices on the same level can run concurrently.

Any idea on how to solve this problem and what to do?

If I were to use Vulkan instead, would that broaden my options?

\$\endgroup\$
  • \$\begingroup\$ I think that the slowdown you'll receive from trying to force a square into a circular hole will outweigh the speedup you gain from being able to do fast matrix math \$\endgroup\$ – Bálint Jul 22 '18 at 0:30
  • \$\begingroup\$ But anyways, here developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch06.html \$\endgroup\$ – Bálint Jul 22 '18 at 0:31
3
\$\begingroup\$

The problem is that this code needs to run as many times as the depth of the tree, and not all of it can run in parallel.

...which is the prime indicator NOT to process this as such on the GPU. GPU architecture suits problems where the individually-processed elements are independent of one another.

If I were to use Vulkan instead, would that broaden my options?

No. Using a different API doesn't change the underlying GPU architecture, which doesn't suit this kind of problem as such. In any case, you may be better off using compute (OpenCL, CUDA) here.

Any idea on how to solve this problem and what to do?

Break down the problem to enable the sort of massively parallel processing where the GPU excels. At any given pass (phase), there can be no data dependencies, which is your current problem.

Run through multiple kernel passes, where each pass represents a depth in the tree; this would take in parent transforms from currentDepth-1 and output the child transforms for currentDepth.

Queueing work on the GPU

In OpenCL we submit commands via the command queue; in CUDA we submit streams. These will then run on the GPU in the same order as you have specified them in your CPU-side code.

These terms should help you to find the resources you need to code up a solution.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ So this should be doable on Vulkan, but also one layer at the time? \$\endgroup\$ – Karlovsky120 Jul 22 '18 at 7:42
  • \$\begingroup\$ @Karlovsky120 If you really want to try Vulkan, go ahead, but I would favour compute for this. Don't see why it wouldn't be possible under Vulkan, though. \$\endgroup\$ – Engineer Jul 22 '18 at 7:46
  • \$\begingroup\$ Doesn't Vulkan have compute shaders and command queues for this very reson? To unify openGL and openCL capabilities under one framework (among many other things)? \$\endgroup\$ – Karlovsky120 Jul 22 '18 at 15:15
  • \$\begingroup\$ @Karlovsky120 You're right. Thanks for pointing this out. Seems your road is clear then - good luck! \$\endgroup\$ – Engineer Jul 22 '18 at 15:16
  • \$\begingroup\$ Vulkan is heavily inspired from OpenCL in terms of command queues and synchronization (only better), and the compute shaders in vulkan are pretty much the same as OpenGL (later versions). Additionally you CAN do recursion on the gpu with cuda, though it won't prove usefull for OP's use case stackoverflow.com/questions/3644809/does-cuda-support-recursion \$\endgroup\$ – whn Aug 28 '18 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.