Computational verification of Collatz conjecture using OpenCL
The lookup table lut should be hard-coded in the source code and defined outside the kernel function as a __constant space global variable. As it is now, every thread would have to recalculate the entire table. Also they take too much space for thread's private memory space. Alternately, maybe pre-calculate it on the host and pass it to the kernel in a __constant space argument.
The outer for loop should be reformulated so that every thread has the same values for the counter variables, and the number of iterations is a compile-time constant. Then applying #pragma unroll may accelerate it.
When code diverges (on NVIDIA), it can become as slow as if the diverging section (i.e. the inner do loop) on threads within each warp (= 32 adjacent threads) were executed sequentially. Maybe somehow change it so that there is no divergence inside warps.


Edit:


Maybe hardcoding the LUT and putting it into __global memory instead. The GPU would put it into global memory anyways because it is too large for the per-thread private memory. And like that the values don't have to be calculated inside the kernel.
It that does not accelerate it, maybe make a copy of it in __local memory (per work group). And copy it from global to local inside the kernel. Then use the shared lut.
Do this copy in a coalesced manner, using multiple work items. For example on NVIDIA, each n'th work item of 32 must access the n'th item of 32 from the global memory table.
Take the first (always-executed) iteration of the inner do loop outside the loop, and make it execute the next iterations (in a loop), only if it is needed for at least one work item the subgroup, using the subgroup functions.
Use an OpenCL profiler (one exists for AMD) to see where the performance losses are. Or port it to CUDA, and use the NVidia Visual Profiler (from the CUDA SDK).
Pre-calculate if 128 bit integers are needed for each work item, or if 64 bit (or 32 bit) are sufficient. Then only use 128 bit integers when any work item in the subgroup needs it.