Методы для векторизации гистограммы в SIMD?

Ответ 1

Гистограммирование практически невозможно для векторизации, к сожалению.

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

init histogram 1 to all 0s
init histogram 2 to all 0s
loop
  get input value 1
  get input value 2
  load count for value 1 from histogram 1
  load count for value 2 from histogram 2
  increment count for histogram 1
  increment count for histogram 2
  store count for value 1 to histogram 1
  store count for value 2 to histogram 2
until done
combine histogram 1 and histogram 2

Ответ 2

ermig1979 имеет проект Simd, который показывает, как он сделал гистограммы с использованием аналогичного подхода к тому, что упомянул @Paul-R, но также и с вариантами SSE2 и AVX2:

Проект: https://github.com/ermig1979/Simd

Конкретный файл: https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp

Решение можно увидеть ниже:

        void Histogram(const uint8_t * src, size_t width, size_t height, size_t stride, uint32_t * histogram)
        {
            uint32_t histograms[4][HISTOGRAM_SIZE];
            memset(histograms, 0, sizeof(uint32_t)*HISTOGRAM_SIZE*4);
            size_t alignedWidth = Simd::AlignLo(width, 4);
            for(size_t row = 0; row < height; ++row)
            {
                size_t col = 0;
                for(; col < alignedWidth; col += 4)
                {
                    ++histograms[0][src[col + 0]];
                    ++histograms[1][src[col + 1]];
                    ++histograms[2][src[col + 2]];
                    ++histograms[3][src[col + 3]];
                }
                for(; col < width; ++col)
                    ++histograms[0][src[col + 0]];

                src += stride;
            }

            for(size_t i = 0; i < HISTOGRAM_SIZE; ++i)
                histogram[i] = histograms[0][i] + histograms[1][i] + histograms[2][i] + histograms[3][i];
        }

Ответ 3

@Paul-R, на этой ссылке есть статья, в которой обсуждается, как векторизовать функции гистограммы:

SIMD векторизация функций гистограммы

Ответ 4

Некоторый алгоритм обработки изображений, работающий с гистограммами (например, выравнивание, сопоставление гистограмм), может быть выполнен с известными процентилями - и для приближения можно эффективно распараллелить поиск до начальных интервалов (0,25,50,75,100%), потребляющих 4 аккумулятора.

Каждый элемент входного потока должен сравниваться параллельно всем слотам, увеличивая частоту. После некоторого количества раундов (например, n * 255 раундов, гарантирующих отсутствие переполнения по типу данных uint8_t, а затем накапливание их до uint16_t) минимальные/максимальные пределы в каждом слоте пересчитываются на основе линейной интерполяции. И, конечно же, можно повторно запустить последовательность на основе оценки того, насколько новые данные изменили оценки процентилей.

Алгоритм будет вариантом для порядка оценки, который может быть смягчен случайной выборкой и несколькими проходами.