I am doing a small project at school. I have done my code implementations in CUDA and did some performance measurements with real values, i.e. running the program with different number of threads, changing the size of the problem, changing both, etc.

The results of (time, speedup) look really nice. But then I was asked to do some theoretical analysis of the algorithms, specifically do a prediction of the time it will take my implementation to run as the number of threads increases. The problem was that I received some documents where they use "Timing diagrams" to try to model this, but this approach was for problems solved using MPI and I'm being asked to use exactly the same stuff to create a prediction model for CUDA. Is it possible to do this?

How can I do a prediction of how a given CUDA program (kernel) will run as I increase the number of threads used for computation? Say that my GPU has 240 cuda cores, now for sake of simplicity I am taking that if I launch a kernel with one thread that kernel will use only 1 core, if I launch 4 threads it'll use 4 cores up to a limit of 240 in that case when I launch 500 threads there won't be no more than 240 cores in use. It is highly likely that this is somehow wrong but It's something to start with.

Could you please give me some ideas to sketch this prediction model? I am really cracking my head because of this, I cannot came to a simple prediction model.


The very first problem was how to simulate a sequential running on the GPU in CUDA. As mentioned before what I did was launch a kernel with only one block and one thread, the result was what I expected as it turned out that the kernel ran slower. Then increasing the number of threads launched reduced the running time so I was getting benefit from the parallel architecture of the GPU. Now, the key question is launching K threads in CUDA, can I be sure that the number of cores used in the GPU equals the number of K threads? Somehow this is true because of what I said before.

Now moving forward I have to make a prediction model, based on timing diagrams. So first the sketch of the timing diagram is

Timing diagram for computing Mandelbrot Set in GPU

What my diagram shows (or at least tries to show) is that the critical path for the application to run depends on

  1. Sending data from CPU to GPU
  2. CUDA initialization and kernel launch configuration
  3. The time it takes the last warp to execute
  4. Sending data from GPU to CPU

The time of (1) and (4) can be straight forward computed: I know the GPU is connected to the CPU via PCI-Express 2nd gen and knowing the size of the problem I can know the actual time of transfers. Good :)

The time of (2) is hardware dependent, but for what I've been reading it takes around 60 to 65 ms.

Finally (3) the hardest part to predict is the actual running time of the computation (kernel runtime for a given number of threads). The way I modeled this was Tprocessing = Tcomputation + Tmemory

Tcomputation : number of cycles one thread does to compute 1 pixel of the set. The key question here is How to count the number of cycles? I naively counted the number of sums and multiplications and then multiplied it by the cycles each of them takes according to the architecture of the GPU. I am completely uncertain about this.

Tmemory : number of cycles one thread takes to go to global memory to read/write. From various references (including Udacity course on GPU) is no average 500 cycles.

Then we know the frequency at which the GPU clock works and summing all I would have an upper bound of the time it will take my program to run.

So basically everything is based on the idea that if I run one thread only one CUDA core is used, if I run ten threads then ten CUDA cores are used. Then I can predict what will is likely to happen if we have a GPU with 2048 CUDA cores as the GTX Titan.

I test my model with the Mandelbrot Set and well my timing was much bigger than the actual one, so something is missing.

  • 1
    $\begingroup$ Hi Brabbit27. Inside of this question is a really elegant question struggling to get out :) You're going to have much better luck in your responses if you make the following edits: [1] Add the homework tag to your question. [2] Give us a little more information about how you think you should be solving this. That means provide a small timing table of the runs you are discussing, and then do your best to provide a model estimating how the timing would be affected. I also suggest that you double-check with your teacher to make sure it is okay to ask for help here. $\endgroup$ May 20 '13 at 13:12
  • $\begingroup$ Yes in fact it is because I've spent some time reading and searching about prediction models but two results I get either I don't find something meaningful or the prediction models are way too complex that I can't understand how to apply them. I'll update my question and hope you can help me. I talked with my prof and he gave me some sheets with info but they were not so useful. I'll go again to talk to him, meanwhile I would like to work on this (we're on holidays). $\endgroup$
    – BRabbit27
    May 20 '13 at 13:54
  • $\begingroup$ @AronAhmadia my question has been updated. I explain generally where I am and the actual problem. Any suggestion would be very appreciated. $\endgroup$
    – BRabbit27
    May 20 '13 at 14:31
  • 1
    $\begingroup$ Your line of thinking is good. In an ideal world, you would head to a resource that covers GPUs in the same level of detail that Agner Fog's does for Intel and AMD CPUs. We are not living in that ideal :) You will need to construct very small synthetic programs that help you measure individual parts of your computation. Some ideas: Launch a kernel that doesn't do anything. Launch a kernel that only does memory operations. Launch a kernel that does floating-point operations in registers. Much of the information you seek is experimentally obtained. $\endgroup$ May 20 '13 at 21:23
  • 2
    $\begingroup$ I recommend you pick up one of the textbooks on programming with CUDA. I'm familiar with Programming Massively Parallel Processors, which seems to be along the lines of what you're looking for. $\endgroup$ May 21 '13 at 11:03