Я пытаюсь реализовать бинарный поиск в вычислительном шейдере с HLSL. Это не классический бинарный поиск, так как ключ поиска, а также значения массива float
, Если для ключа поиска нет соответствующего значения массива, поиск должен вернуть последний индекс (minIdx
а также maxIdx
совпадать на этом этапе). Это наихудший случай для классического бинарного поиска, так как он занимает максимальное количество операций, я знаю об этом.
Итак, вот моя проблема:
Моя реализация выглядит так:
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;
}
Это приводит к сбою моего видео драйвера при выполнении программы. Я не получаю ошибку компиляции.
Однако, если я использую if
вместо while
Я могу выполнить его, и первая итерация работает, как и ожидалось.
Я уже сделал пару поисков, и я подозреваю, что это может быть связано с динамическим циклом в вычислительном шейдере. Но у меня нет предыдущего опыта работы с вычислительными шейдерами, а также немного опыта работы с HLSL, поэтому я чувствую себя потерянным.
Я собираю это с cs_5_0
,
Может ли кто-нибудь объяснить, что я делаю неправильно, или хотя бы намекнуть мне на какую-нибудь документацию / объяснение? Все, что может заставить меня начать решать и понимать это, будет очень цениться!
Шейдеры DirectCompute все еще подлежат обнаружению тайм-аута & Восстановление (TDR) поведения в драйверах. По сути, это означает, что если ваш шейдер занимает более 2 секунд, драйвер предполагает, что графический процессор завис, и сбрасывает его. Это может быть сложно с DirectCompute, когда вы намеренно хотите, чтобы шейдер работал долго (намного дольше, чем обычно делает рендеринг). В этом случае это может быть ошибка, но об этом нужно знать.
В Windows 8.0 или более поздней версии вы можете разрешить длительные шейдеры, используя D3D11_CREATE_DEVICE_DISABLE_GPU_TIMEOUT
когда вы создаете устройство. Это, однако, применимо ко всем шейдерам, а не только к DirectCompute, поэтому вы должны быть осторожны при использовании этого в целом.
Для систем специального назначения вы также можете использовать ключи реестра отключить TDR.