1

I have a perfectly parallel function that would run great on a machine with 1024 cores and 4GB RAM. There's quite a lot of branching (doing set union and traversing structs). There is no communication between threads (except when the whole calculation is complete). Each thread needs less than 1MB of private memory, and no shared memory. The result of each computation can be merged like a CRDT; it is basically max over a set of structs.

I know this would fit distributed computing. GPU's are more efficient and powerful than CPU's, so I would like to use them instead. It seems like this would fit GPGPU, since it's massively parallel and uses so little memory, but how can I tell? OpenCL/AMD/CUDA doesn't matter.

Improve this question

1 Answer 1

Reset to default
2

GPUs are designed for executing code that has few or no branches. Specifically, they work on a principle of clustering data together that will cause the same branches to be taken through a routine and running them simultaneously across the same instructions where possible. If your code involves a large number of branches and these branches are difficult for the processor's dispatch mechanisms to cluster together, then it seems unlikely that they will benefit hugely from running on a GPU. See this description of branching in GPU architectures for more detail.

Improve this answer
5
  • Any estimate on how much parallelism is needed for it to break even, compared to a arm/x86 cpu?
    – Drathier
    Commented May 9, 2016 at 7:47
  • 1
    It'll depend very much on what GPU you're using, of course. A current high-end GPU might degrade from ~3000 parallel operations down to as low as 24 parallel operations if there is too much branching for it (although there'd have to be a lot of branching for that to happen...), reducing computation throughput from 6 TFLOPs down to about 40 GFLOPs, which is to say about a quarter what a high end CPU would be able to handle, or about the same as the fastest ARM chips currently available (assuming ideal circumstances, i.e. repeatedly running the fused add+multiply instruction).
    – Jules
    Commented May 9, 2016 at 18:22
  • 1
    But that would require a lot of branching. If you take a look at a GPU's specs, you'll see a description of how many stream processors it has per compute unit. The worst case is that it only manages to use one in each unit. But in order for that to happen, your code has to branch so much and so randomly that every attempted computation ends up executing different code. So if a GPU has 128 stream processors per unit, you'd have to have significantly more than 128 possible code paths to hit that minimum, which seems unlikely for most reasonable algorithms.
    – Jules
    Commented May 9, 2016 at 18:28
  • 1
    On low end gpus, of course, you lose less simply because they run less in parallel anyway. Typical mobile GPUs may only have 24-32 processors in either 4 or 8 units, so slowdown due to branching is only likely to be 1/4 to 1/8th in any case, so it may be the case that it is a significant proportion of the speed of a high-end GPU in a worst-case scenario, but that you'll get down to its lowest performance with a lot fewer branches.
    – Jules
    Commented May 9, 2016 at 18:46
  • Incredibly good comments, wish I could upvote twice!
    – Drathier
    Commented May 9, 2016 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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