Проблема сортировки неожиданных индексов на вычислительном ядре - PullRequest
Новая
       133

Проблема сортировки неожиданных индексов на вычислительном ядре

2 голосов
/ 25 апреля 2020

У меня странная проблема, когда я пытаюсь выполнить сортировку индексов в порядке убывания. Я почти уверен, что мне не хватает некоторой базовой c идеи о том, как работают графические процессоры, так как я ожидаю, что эта программа будет работать нормально: 

layout(binding = 0, std430) buffer _6_3
{
    uint _m0[];
} _3;

layout(binding = 1, std430) buffer _8_4
{
    uint _m0[];
} _4;

uint _51(uint _63, uint _64)
{
    uint _66 = 0u;
    uint _67 = 1u;
    for (;;)
    {
        uint _72 = _66;
        if (_72 < 150u)
        {
            memoryBarrierBuffer();
            barrier();
            uint _76 = atomicCounter(_3._m0[_72]);
            memoryBarrierBuffer();
            barrier();
            _67 += uint(((_76 == _63) && (_72 > _64)) || (_76 < _63));
            _66++;
            continue;
        }
        else
        {
            break;
        }
    }
    uint _87 = _67;
    uint _90 = _64 + 1u;
    memoryBarrierBuffer();
    barrier();
    _3._m0[150u - _87] = _90;
    memoryBarrierBuffer();
    barrier();
    return _90;
}

void main()
{
    uint _49 = _3._m0[gl_GlobalInvocationID.x];
    uint _50 = _51(_49, gl_GlobalInvocationID.x);
}

Эта программа работает для небольших входных данных - допустим, упорядоченный список натуральных чисел от 1 до 500. Если мы заменим 150u на 50 или 75, результат будет таким, как ожидалось: первые 75 чисел уменьшатся с 75 до 1, после чего они начинаются с 76 до 500.

Проблема в том, что при входах более 100 некоторые индексы перемешиваются. Результаты представляют собой полные гиббери sh структуры, но показатели, конечно, остаются в пределах. Странная вещь в том, что если инвариант while увеличивается, скажем, 5000 для всех oop из 500 элементов, сортировка снова начинает работать.

Есть идеи, в чем может быть проблема? Я совершенно уверен, что не могу понять некоторую базовую c синхронизацию. Насколько я понимаю, мне не нужны никакие другие барьеры в моем коде, кроме случаев, когда индексы меняются в конце функции.

Для чего это стоит, это перевод следующей функции SPIR-V: 

%rankDown = OpFunction %1 None %rankdown_uint_signature
%self = OpFunctionParameter %1
%sindex = OpFunctionParameter %1
%rd = OpLabel
%iter = OpVariable %u32ptr Function %uint_0
%rank = OpVariable %u32ptr Function %uint_1

    OpBranch %while_start
    %while_start = OpLabel
    OpLoopMerge %endloop %continueloop None
    OpBranch %rankloop
    %rankloop = OpLabel
    %rloopload = OpLoad %1 %iter
    %loopgate = OpULessThan %bool %rloopload %uint_500
    OpBranchConditional %loopgate %start %endloop
    %start = OpLabel

        %_thrdValue = OpAccessChain %_ptr_Uniform_uint %_ %uint_0 %rloopload
        OpControlBarrier %uint_1 %uint_1 %UniformMemory
        %thrdValue = OpAtomicLoad %1 %_thrdValue %uint_1 %UniformMemory
        OpControlBarrier %uint_1 %uint_1 %UniformMemory

        %smaller = OpULessThan %bool %thrdValue %self

        %same = OpIEqual %bool %thrdValue %self
        %_is_after = OpUGreaterThan %bool %rloopload %sindex
        %_if_gate = OpLogicalAnd %bool %same %_is_after

        %if_gate2 = OpLogicalOr %bool %_if_gate %smaller
        %sel = OpSelect %1 %if_gate2 %uint_1 %uint_0

        %rankLoad = OpLoad %1 %rank
        %rank_adder = OpIAdd %1 %rankLoad %sel
        OpStore %rank %rank_adder

    OpBranch %continueloop
    %continueloop = OpLabel

        %iterLoad = OpLoad %1 %iter
        %iterAdd = OpIAdd %1 %iterLoad %uint_1
        OpStore %iter %iterAdd

    OpBranch %while_start
    %endloop = OpLabel

    %rankll = OpLoad %1 %rank
    %ow_index = OpISub %1 %uint_500 %rankll
    %_overwrite = OpAccessChain %_ptr_Uniform_uint %_ %uint_0 %ow_index
    %ow_index2 = OpIAdd %1 %sindex %uint_1

    OpControlBarrier %uint_1 %uint_1 %UniformMemory
    OpStore %_overwrite %ow_index2
    OpControlBarrier %uint_1 %uint_1 %UniformMemory

    OpReturnValue %ow_index2
OpFunctionEnd

Например, если мы изменим 150u на 250u и визуализируем результаты, мы получим следующее:

example with 250u

Здесь мы можем видеть, что упорядочение показывает, что в некоторых случаях, хотя l oop, кажется, не выполняется достаточно раз - в результатах существуют повторяющиеся значения, а некоторые значения исчезают.

Любой ввод ценится!

...