How to decide how to parallelize nested loops on GPU

Suppose I have an algorithms which I want to implement ona GPU. The algorithm consists of a main loop, and all iterations of the loop can be run in parallel. Also, each iteration of the loop has an inner loop whose iterations can be run in parallel. Lets say that I need N iterations of the main loop, and M iterations of the inner loop (per main loop iteration), and that my GPU has L cores.

If N+N*M <= L, I can run everything in parallel. But if this is not the case, I need to decide what to run sequentially. How should I make this decision? For example, if N=10, M=5, L = 20, when should I choose each of these options (or any other options)?:

1. Run all main iterations in parallel, and all inner loop sequentially.
2. Run all main iterations sequentially, and all inner loop in parallel.
3. Run all main iterations in parallel, two of the inner loops in parallel and the rest sequentially.
4. Run three of the main iterations in parallel, run each of their inner loops in parallel, run the rest of the main iterations and their inner loops sequentially.
• Are you using CUDA? – James Apr 8 '16 at 17:19
• @James I wasn't explicitly thinking about CUDA, but if it simplifies the answer then we can assume that. – Lior Apr 8 '16 at 21:35

To make the answer more general, I don't think it makes sense to deal with problems where the number or parallelizable tasks is close to the number of computational units: if it is, you haven't revealed enough parallelism yet or the problem is too small. If there is enough parallelism, the "tail effect" is negligible assuming that all tasks take about the same time to process. For CPUs, where the number of cores is much lower compared to GPUs, the general strategy is to split the problem into small blocks of fixed size (say, n*m) and then process the blocks in parallel -- this preserves data locality and avoids the need to decide along which axis the problem should be parallelized. For distributed systems, first split the tasks into big blocks equal to the number of nodes and then split each block into smaller blocks as before. For other GPU frameworks you will probably need to adapt to their execution model, but I think there will always be some block structure.