Hi Mikhail, 

Thread divergence may occur not only when "high-level" divergence pattern (such as if-else) is reached but also if coalesced memory accesses are not obtained. For example, when threads within a warp perform load operations from global memory in 32-byte displaced, throughput is divided by 8. Considering Idx as usually (contigous identifiers for those threads within the warp), the following load operation

float aux = v[idx];

will be performed using one memory transaction while in the case of 

float aux = v[idx+8]

coalescence is lost and then 8 128-byte coalesced memory transactions will be required.This is a very typical issue and it is not straightforward to be reduced. Maybe some reordering of the memory or to rethink data structures may help to obtain it more coalesced but it is very dependent of the algorithm.

In you case, you have configured them as (7,3,3) so very probably memory (even shared) accesses are not obtained coalesded, Could it be your case?

Cheers

Dear Asier,

Yes, it could be, unfortunately, the problem i'm solving deals with data that can't be really 128-byte aligned.

thks

Hi, your blocksize is 7,3,3 i.e., 7*3*3 threads in a block it is too low number and it is not multiple of 32 (warpsize) => warp divergency (some threads are permanently off) .

To minimize latencies => the largest amount of resident warps is needed (for CC 2.0 is 48), but it can be difficult to reach because in your code 6KB of SHM per block is needed (max. 8 resindent blocks).

I think that a shared memory serialization causes a very small latency. 

Dear Ivan,

Thank you very much, but nvprof says that kernel performance is limited by register, i.e. it uses 63 registers and GPU can't run more than 8 blocks per SM. Why do you think SHM serialisation is not an issue in this case?

The warp size is 32, but in this case i have blocks of 63 threads each which is nearly 2 warps, i.e only 1 thread per warp is idling.

>> For example this causes divergence: if (x

Dear Đorđe,

Than you very much. But what does the intra-warp term mean?

Sorry Mikhail, I forgot to mention that the answer was about intra-warp divergence. In CUDA, there are two kinds of control (execution) path divergence: inter-warp and intra-warp.

I'll try to give an illustrative example. Imagine there are two squads of (say) 32 soldiers each, executing orders of one officer. The officer can give only one order to only one of the squads at the given moment (limitation of SIMD machines). Their task is to to prepare dinner and dig trenches. The first squad is "armed" with knives and potatoes, while the second is "armed" with shovels. The officer gives the order to the first squad to lift their knives. While they are lifting their knives, they can not do anything else, so the officer gives the order to the second squad to lift their shovels. By then, the first squad finished lifting their knives, so the officer gives them the order to lift the first potato. By then, the second squad finished lifting shovels, so they are issued the order to thrust the shovels into ground. By then, the first squad finished lifting potatoes, so the officer gives them the order to put the blade of their knives on the potatoes they are holding. The officer turns his attention to the second squad. Unfortunately, one of the soldiers hit a solid rock with his shovel, so the officer tells the other soldiers of the squad to wait (with their shovels thrust into ground), and addresses specifically the soldier who hit the rock to bend down and reach for the rock. The officer turns his attention to the first squad and tells them to rotate their potatoes by 20 degrees (he'd probably have to specify the axis of rotation and direction, but that is irrelevant here :) Then the officer turns his attention to the second squad, tells the soldier who hit the rock to grab the rock, and the other soldiers of the second squad to wait. Back to the first squad, the officer tells them to rotate their potatoes by 20 degrees (with the same remark as before). Back to the second squad, the officer tells the solder who grabbed the rock to throw the rock away (he'd probably have to warn the soldier to avoid hitting the rest of the squad with the rock, but we'll ignore that :) and the other soldiers of the squad to wait. Back to the first squad, another 20 degrees. Back to the second squad, the officer tells the soldier who just threw the rock away to thrust his shovel into ground and the other soldiers to wait. Back to first squad, another 20 degrees. Back to the second squad, the officer issues the order to the whole squad to lift their shovels (hopefully, with some soil on them) - because the problematic solder is now in the same state as the others from his squad.

I guess you figured out from this illustration that each squad is actually a warp, and a soldier is actually a thread. Warps compete for the commander's attention (concurrent execution), but within each warp threads execute their work in parallel. That is, in parallel - until at least one of them has to execute a different instruction from the others. In that case, some threads will have to wait until the others finish their work. There is loss in parallelism until their execution paths converge into a single path once again. As you could see, there is no loss in efficiency among two different warps (squads) even though the work they did was completely different. Put it simply, the work of the first squad was not influenced by the second squad and vice-versa. That is called inter-warp divergence. On the other hand, there was some loss in efficiency withing the second squad because one of the soldiers was unable to catch up with the rest of the squad - so the rest of the squad was forced to wait for him. Soldiers in that squad had to execute, at least partially, different orders. That is called intra-warp divergence and it causes some penalty. In the example I gave, the penalty was not great. Imagine that there was another soldier who hit a gold bar, and another one who hit an electric cable. The officer would probably not give the first one the order to throw the gold bar away, so other soldiers (including the one who hit the rock and the one who hit the electric cable) would have to wait for commander's attention. The worst possible situation would be when every single soldier within the squad hits something different with the shovel - different in a sense that it requires different kind of action. The commander would have to tell each one of them how to solve the problem, while the others (within the same squad) would have to wait.

I hope I managed to explain (in essence) what is intra-warp divergence :)

Dear Đorđe,

You made the great explanation ever :) Fortunately it meets my initial understanding of the process.

I also did some studies of the presented kernel and other one, and i found that actually problem is not really (or not only) in memory. I've tried to use 8 and 4 threads in x and y dimensions, respectively and found that computation time increases.  Also my kernel uses double precision erf() and exp() functions, seems like their evaluation consumes a lot of time... On the other hand kernels has many other DP operations (sub, mul, add), thus evaluation of erf() and exp() shouldn't impact remarkably. Also i suspect that use of DP variables doesn't allow to get rid of SHM back conflicts on GPU with CC2.x.

Dear Mikhail,

On Tesla accelerators, double precision arithmetic operations probably do not have important impact on computation speed (I don't know that for sure, it is just a guess). My experience with "regular" GPUs, such as GTX 280 or GTX 580, is that there is significant difference in computation speed between float and double types (and quite little between int and float). There are other tricks to accelerate your kernel. For example, instead of using "regular" round function (to round a float to the nearest int), I got a significant speedup just by using the less accurate function rintf. Now, depending on how much accuracy you need, you might want to try some tricks just in order to reduce the amount of computation, and get rid - where possible - of double precision operations. Or - try to create a lookup table for erf() - that might be faster, although less precise. I can not give any advice on bank conflicts with double precision variables since I completely avoided using DP - that is a problem I did not encounter so far :)