While loop in compute shader is crashing my video card driver

Question

I am trying to implement a Binary Search in a compute shader with HLSL. It's not a classic Binary Search as the search key as well as the array values are float. If there is no matching array value to the search key, the search is supposed to return the last index (minIdx and maxIdx match at this point). This is the worst case for classic Binary Search as it takes the maximum number of operations, I am aware of this.

So here's my problem:

My implementation looks like this:

uint BinarySearch (Texture2D<float> InputTexture, float key, uint minIdx, uint maxIdx)
{
    uint midIdx = 0;
    while (minIdx <= maxIdx)
    {
        midIdx = minIdx + ((maxIdx + 1 - minIdx) / 2);
        if (InputTexture[uint2(midIdx, 0)] == key)
        {
            // this might be a very rare case
            return midIdx;
        }

        // determine which subarray to search next
        else if (InputTexture[uint2(midIdx, 0)] < key)
        {
            // as we have a decreasingly sorted array, we need to change the
            // max index here instead of the min
            maxIdx = midIdx - 1;
        }

        else if (InputTexture[uint2(midIdx, 0)] > key)
        {
            minIdx = midIdx;
        }
    }

    return minIdx;
}

This leads to my video driver crashing on program execution. I don't get a compile error.

However, if I use an if instead of the while I can execute it and the first iteration works as expected.

I already did a couple of searches and I suspect this might have to do something with dynamic looping in a compute shader. But I have no prior experience with compute shaders and only little experience with HLSL as well, which is why I feel kind of lost.

I am compiling this with cs_5_0.

Could anyone please explain what I am doing wrong or at least hint me to some documentation/explanation? Anything that can get me started on solving and understanding this would be super-appreciated!

AFAIK there's a limit on the number of loops you can do, usually in the order of 256 or so.. — Kenney
your minIdx = midIdx in the final elseif should probably be minIdx = midIdx + 1. since you don't increase the lower bound, you can get into an infinite loop. — Marc B
This code can get stuck in a loop in C++, so I doubt that HLSL has anything to do with it. (Search for 2.1 in {3.0, 2.0, 1.0} and you'll get stuck.) — molbdnilo

Chuck Walbourn Chuck Walbourn · Accepted Answer · 2015-09-17T17:41:11

DirectCompute shaders are still subject to the Timeout Detection & Recovery (TDR) behavior in the drivers. This basically means if your shader takes more than 2 seconds, the driver assumes the GPU has hung and resets it. This can be challenging with DirectCompute where you intentionally want the shader to run a long while (much longer than rendering usually would). In this case it may be a bug, but it's something to be aware of.

With Windows 8.0 or later, you can allow long-running shaders by using D3D11_CREATE_DEVICE_DISABLE_GPU_TIMEOUT when you create the device. This will, however, apply to all shaders not just DirectCompute so you should be careful about using this generally.

For special-purpose systems, you can also use registry keys to disable TDRs.

While loop in compute shader is crashing my video card driver

1 Answers