Реализация SpinLock в шейдере HLSL DirectCompute

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

Вот как я реализую блокировку вращения:

void LockAcquire()
{
    uint Value = 1;

    [allow_uav_condition]
    while (Value) {
        InterlockedCompareExchange(DataOutBuffer[0].Lock, 0, 1, Value);
    };
}

void LockRelease()
{
    uint Value;
    InterlockedExchange(DataOutBuffer[0].Lock, 0, Value);
}

Предыстория: мне нужна блокировка спина, потому что мне нужно вычислить сумму данных в большом двухмерном массиве. Сумма двойная. Вычисление суммы с помощью одного потока и двойного цикла дает правильный результат. Вычисление суммы с помощью многопоточности дает неверный результат, даже если вводится спин-блокировка, чтобы избежать конфликта при вычислении суммы.

Я не могу использовать InterLockedAdd, потому что сумма не умещается в 32-битное целое число, а я использую шейдерную модель 5 (компилятор 47).

Вот однопоточная версия, дающая правильный результат:

[numthreads(1, 1, 1)]
void CSGrayAutoComputeSumSqr(
    uint3 Gid  : SV_GroupID,
    uint3 DTid : SV_DispatchThreadID, // Coordinates in RawImage window
    uint3 GTid : SV_GroupThreadID,
    uint  GI   : SV_GroupIndex)
{
    if ((DTid.x == 0) && (DTid.y == 0)) {
        uint2 XY;
        int   Mean = (int)round(DataOutBuffer[0].GrayAutoResultMean);
        for (XY.x = 0; XY.x < (uint)RawImageSize.x; XY.x++) {
            for (XY.y = 0; XY.y < (uint)RawImageSize.y; XY.y++) {
                int  Value  = GetPixel16BitGrayFromRawImage(RawImage, rawImageSize, XY);
                uint UValue = (Mean - Value) * (Mean - Value);
                DataOutBuffer[0].GrayAutoResultSumSqr += UValue;
            }
        }
    }
}

а ниже - многопоточная версия. Эта версия дает аналогичные, но разные результаты при каждом выполнении, которое IMO вызвано неработающей блокировкой.

[numthreads(1, 1, 1)]
void CSGrayAutoComputeSumSqr(
    uint3 Gid  : SV_GroupID,
    uint3 DTid : SV_DispatchThreadID, // Coordinates in RawImage window
    uint3 GTid : SV_GroupThreadID,
    uint  GI   : SV_GroupIndex)
{
    int  Value  = GetPixel16BitGrayFromRawImage(RawImage, RawImageSize, DTid.xy);
    int  Mean   = (int)round(DataOutBuffer[0].GrayAutoResultMean);
    uint UValue = (Mean - Value) * (Mean - Value);
    LockAcquire();
    DataOutBuffer[0].GrayAutoResultSumSqr += UValue;
    LockRelease();
}

Использованные данные:

cbuffer TImageParams : register(b0)
{
    int2   RawImageSize;       // Actual image size in RawImage
}

struct TDataOutBuffer
{
    uint   Lock;                             // Use for SpinLock
    double GrayAutoResultMean;
    double GrayAutoResultSumSqr;
};

ByteAddressBuffer                  RawImage       : register(t0);
RWStructuredBuffer<TDataOutBuffer> DataOutBuffer  : register(u4);

Код отправки:

FImmediateContext->CSSetShader(FComputeShaderGrayAutoComputeSumSqr, NULL, 0);
FImmediateContext->Dispatch(FImageParams.RawImageSize.X, FImageParams.RawImageSize.Y, 1);

Функция GetPixel16BitGrayFromRawImage обращается к буферу байтового адреса RawImage для извлечения 16-битного значения пикселя из изображения в градациях серого. Это дает ожидаемый результат.

Любая помощь приветствуется.


person fpiette    schedule 19.09.2019    source источник
comment
Вы пробовали заблокировать над этой строкой: int Mean = (int) round (DataOutBuffer [0] .GrayAutoResultMean); или даже выше int Value = GetPixel16BitGrayFromRawImage (RawImage, RawImageSize, DTid.xy);   -  person VuVirt    schedule 19.09.2019
comment
Нет, не пробовал, потому что это нонсенс. Во всяком случае, я просто попробовал прямо сейчас, и это не изменилось. Кстати: GetPixel16BitGrayFromRawImage является потокобезопасным, потому что он обращается только к данным только для чтения, и это доказано, потому что я активно использую его во многих других многопоточных местах.   -  person fpiette    schedule 19.09.2019


Ответы (2)


Вы стали жертвой проблемы XY здесь.

Начнем с проблемы Y. Ваша блокировка вращения не блокируется. Чтобы понять, почему ваша блокировка вращения не работает, вам необходимо изучить, как графический процессор обрабатывает создаваемую вами ситуацию. Вы создаете основу, состоящую из одной или нескольких групп потоков, каждая из которых состоит из множества потоков. Выполнение деформации происходит быстро, пока выполнение является параллельным, это означает, что все потоки, которые создают деформацию (волновой фронт, если вы предпочитаете), должны выполнять одну и ту же инструкцию с одним и тем же время. Каждый раз, когда вы вставляете условие (например, цикл while в вашем алгоритме), некоторые из ваших потоков должны идти по маршруту, а некоторые - другим. Это называется расхождением потоков. Проблема в том, что вы не можете выполнять разные инструкции параллельно.

В этом случае графический процессор может выбрать один из двух маршрутов:

  1. Динамическое ветвление, что означает, что волновой фронт (деформация) выбирает один из двух маршрутов и деактивирует потоки, которые должны принимать другой. Затем он откатывается, чтобы подобрать спящие нити с того места, где они были.
  2. Плоское ветвление, что означает, что все потоки выполняют обе ветви, затем каждый поток отбрасывает нежелательный результат и сохраняет правильный.

А теперь самое интересное:

Нет правила приведения, определяющего, как графический процессор должен обрабатывать ветвление.

У вас нет возможности предсказать, будет ли графический процессор использовать тот или иной подход, а в случае динамического ветвления невозможно заранее узнать, переведет ли графический процессор в режим сна прямой маршрут, другой - ветвь с меньшим количеством потоков. или тот, у кого больше. Невозможно узнать заранее, и разные графические процессоры могут выполнять код по-разному (и будут). Один и тот же графический процессор может даже изменить свою работу с разными версиями драйверов.

В случае вашей спин-блокировки ваш графический процессор (и его драйвер, а также версия компилятора, которую вы используете в настоящее время), скорее всего, пойдут на стратегию плоского ветвления. Это означает, что обе ветви выполняются всеми потоками основы, поэтому блокировки вообще нет.

Если вы измените код (или добавите атрибут [branch] перед циклом), вы можете принудительно выполнить динамическое ветвление потока. Но это не решит ваших проблем. В конкретном случае спин-блокировки вы просите GPU отключить все потоки, кроме одного. И это не совсем то, что GPU захочет делать. Графический процессор попытается сделать обратное и закроет единственный поток, который оценивает состояние по-другому. Это действительно приведет к меньшему расхождению и увеличению производительности ... но в вашем случае это отключит единственный поток, который не находится в бесконечном цикле. Таким образом, вы можете получить полный волновой фронт потоков, заблокированных в бесконечном цикле, потому что единственный, кто может разблокировать цикл ... спит. Ваша спин-блокировка фактически превратилась в тупик.

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

Лучшее предложение относительно спин-блокировок в графических процессорах -… не используйте их. Всегда.

А теперь вернемся к проблеме Y.

Что вам действительно нужно, так это способ вычисления суммы данных в большом двухмерном массиве. Итак, что вы действительно ищете, так это хороший алгоритм сокращения. Некоторые из них есть в Интернете, или вы можете написать собственный код, в зависимости от ваших потребностей.

Я просто добавлю несколько ссылок для начала, если они вам понадобятся.

Отступление о расхождениях

NVIDIA - Конференция по технологиям графических процессоров 2010, слайды < / а>

Goddeke - вводное руководство

Донован - параллельное сканирование на графическом процессоре

Barlas - многоядерное программирование и программирование на GPU

person kefren    schedule 23.09.2019
comment
Уау! Я думаю, мне нужно многому научиться, прежде чем продолжить. Спасибо за вашу помощь. Спасибо за ссылки. - person fpiette; 23.09.2019
comment
Могу я дать вам предложение, о котором вы не просили;) Я вижу, вы всегда отправляете группы потоков с помощью одного потока [numthreads (1, 1, 1)]. Это очень неэффективно. Хорошей стартовой базой могут быть группы потоков с 64, 128 или 256 потоками. Тогда вы сможете продолжить оптимизацию. - person kefren; 23.09.2019
comment
Спасибо за совет. Я введу новый вопрос, чтобы мы могли как следует обсудить эту тему. - person fpiette; 24.09.2019
comment
Я последовал твоему предложению: теперь я использую большое количество потоков на группу и производительность на порядок выше. Спасибо за совет. - person fpiette; 24.09.2019
comment
Я отвечу на него как можно скорее, но это непростой вопрос, поэтому у меня должно быть время, чтобы дать хороший ответ. Кстати, если эти ответы вам помогли, подумайте о том, чтобы принять их, если вы найдете их удовлетворительными. - person kefren; 24.09.2019

Как упоминал Кефрен, ваша спин-блокировка не работает из-за расхождения деформации. Однако есть способ спроектировать спин-блокировку графического процессора, которая не приводит к тупиковой ситуации. Я использовал эту спин-блокировку для пиксельного шейдера, но она также должна работать в вычислительном шейдере.

RWTexture2D<uint> mutex; // all values are 0 in the beginning

void doCriticalPart(int2 coord) {
   bool keepWaiting = true;
   while(keepWaiting) {
      uint originalValue;
      // try to set the mutex to 1
      InterlockedCompareExchange(mutex[coord], 0, 1, originalValue);
      if(originalValue == 0) { // nothing was locked (previous entry was 0)
         // do your stuff
         // unlock mutex again
         InterlockedExchange(mutex[coord], 0, originalValue);
         // exit loop
         keepWaiting = false;
      }
   }
}

Подробное объяснение того, почему это работает, можно найти в моей дипломной работе бакалавра на странице 30. Там же. также является примером для GLSL.

Примечание. Если вы хотите использовать эту спин-блокировку в пиксельном шейдере, вы должны проверить SV_SampleIndex == 0 перед вызовом этой функции. Пиксельный шейдер может порождать некоторые вспомогательные вызовы для определения уровней mipmap выборки текстуры, которые вызывают неопределенное поведение для атомарных операций. Это может привести к бесконечному выполнению цикла для вызова этого помощника, что приведет к тупиковой ситуации.

person Felix Brüll    schedule 25.10.2019
comment
Ваша реализация на самом деле не отличается от моей, за исключением того, что вы написали встроенный код, а я использовал функцию. Поскольку компилятор HLSL встроил все функции, это стало почти таким же. - person fpiette; 25.10.2019
comment
Разница в том, что в моей реализации цикл while находится вокруг LockAcquire AND LockRelease. Ваш цикл while находится только вокруг LockAcquire, что может вызвать взаимоблокировку, потому что все потоки в группе продвигаются только как группа (lockstep) = ›Если даже один поток не получает блокировку в вашей реализации, все другие потоки не будут продвигаться и поэтому не снимет блокировку - person Felix Brüll; 26.10.2019
comment
Реализация fpiette не привела к тупиковой ситуации в его оборудовании. Это может на некотором оборудовании. На его оборудовании проблема заключалась в том, что обе ветви выполнялись для всех потоков, и это приводило к отсутствию блокировки. То же самое может произойти с вашей реализацией, и тот факт, что она работает с вашей конкретной парой оборудования / драйвера, не дает никаких гарантий для другого оборудования или других версий драйверов. Вы можете получить спин-блокировку, которая работает на вашем ПК. Но вы не можете сделать в графических процессорах спин-блокировку, которая надежно работала бы на каждой версии оборудования или на всех версиях драйверов. - person kefren; 10.11.2019
comment
Что произойдет, если я добавлю тег [ветвь] перед оператором if. Тогда внутренняя часть будет выполнена только в том случае, если блокировка действительно была получена. Или я что-то упускаю? - person Felix Brüll; 10.11.2019
comment
Ваш мьютекс сломан, потому что нет гарантии, что следующее не произойдет: 1. Поток A получает блокировку 2. Warp всегда выполняет ветвь «не удалось получить блокировку» на неопределенный срок, планируя выполнить A после этого (но это будет никогда не происходит) 3. Поток A никогда не возобновляет выполнение, поэтому никогда не освобождает мьютекс. - person Matias N Goldberg; 03.09.2020