There is something like the BigO notation for the GPU world and the programmable pipeline?

Question

I find difficult to study the performance of a shader or a series of statement probably because the OpenGL is a state machine and also the execution is in parallel and not serialized like a standard X86 CPU I/O.

There is something that i can use for this? The BigO notation is based on the concept of growth, but with a state machine there is nothing growing, how i can approach the study of this kind of code/algorithm?

Answer 1

I think there's a bit of confusion going on here. Let me just quote the Wikipedia article:

In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.

In other words, it just measures how "good" an algorithm is, independently from the platform, library, API, or weather forecast.

I'll give you an example: let's say you want to use an algorithm to do some motion blur: it could be O(n), n being the number of pixels to process. If you write a program for the CPU, or a parallelized version running on the GPU thanks to OpenGL (whatever you think OpenGL is), it doesn't change the fact that your algorithm is still O(n).

Now some algorithms are parallel by nature, and and a parallel program will of course run faster than the sequential equivqlent, but this has nothing to do with the Big O notation. So to summarize, the lowest order (Big O) your algorithm is the better, and if it's a parallel algorithm, then it's even better.

Check this question on Stack Overflow if my prose isn't convincing enough: Are algorithms rated on the big-o notation affected by parallelism?. Or this blog post, for more details.

Answer 2

Usually you just look at differentials. Yes, OpenGL has a lot of state, but that doesn't matter here.

Usually you are doing something per pixel or per vertex. Usually that operation can happen in parallel among the available GPU cores.

So if you are doing Phong shading, it will get slower as the window resolution increases, or faster as the core count increases.

Usually only things O(N^2) benefit from GPGPU computing as it brings N cores. Thus on a GPU you aim for N^2 / N = N and the like.

I am not articulating things clearly, but GPGPU computing tries to bring N cores. Where as in classical Big O notation you had a single core. Let the number of cores be K

N^2 / K so with CPU thinking that would still be N^2. The aim of GPGPUs is to treat that like N things to do per core.

So then you have to consider what N is. Is it pixels? Vertexes? Faces? Tip: What shader is it in? is usually the answer.

Then for each Pixel you have too look at what is happening. Say you have L lights for each N Pixels. Then you have L*N complexity

Given all that, not everything can be done in parallel, in which case you can't use all N cores.

Answer 3

The BigO notation is just a way to display results - what you are really looking for is a different machine-model. Every processor is slightly different. For example, some have different L1/L2 caches, some can't do branching well, while others blaze through small branches with conditional instructions. This is why you do your performance analysis on a simplified model, which is oblivious to the details and makes your results applicable to a wider rage of machines.

Usually, for single threaded CPU algorithms, the RAM model, or some variation of it, is used. Most theoretical proofs (e.g. those about NP-completeness) are usually using a turing machine.

For massively-parallel architectures, such as GPUs, a PRAM can be used reasonably well. But there are also more specialized models such as this model.