16

我正在尝试在 Neon 中实现直方图。是否可以矢量化？

4

4 回答 4

11

不幸的是，直方图几乎不可能矢量化。

但是，您可能可以稍微优化标量代码 - 一个常见的技巧是使用两个直方图，然后在最后将它们组合起来。这允许您重叠加载/增量/存储，从而隐藏一些串行依赖项和相关的延迟。伪代码：

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
于 2012-10-20T07:29:03.977 回答
8

ermig1979 有一个 Simd 项目，该项目展示了他如何使用与@Paul-R 提到的类似方法以及 SSE2 和 AVX2 变体来完成直方图：

项目：https ://github.com/ermig1979/Simd

基础文件：https ://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp

在这里可以看到一个 AVX2 实现： https ://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.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];
}
于 2015-07-15T10:39:25.777 回答
2

@Paul-R，此链接上有一些论文讨论了如何向量化直方图函数：

直方图函数的 SIMD 矢量化

于 2014-04-11T18:00:27.917 回答
1

一些处理直方图的图像处理算法（例如均衡、直方图匹配）可以使用已知的百分位数进行工作——对于近似值，可以有效地将搜索并行化到初始范围（0、25、50、75、100%），消耗 4 个累加器。

输入流中的每一项都必须与所有插槽并行进行比较，从而增加频率。经过一定数量的轮次后（例如，n*255 轮次保证 uint8_t 数据类型没有溢出，然后将这些累加到 uint16_t），每个槽的最小/最大限制基于线性插值重新计算。当然，可以根据新数据对百分位数估计值的改变程度的估计来重新运行序列。

该算法将是评估顺序的变体，可以通过随机采样和多次传递来缓解。

于 2017-08-03T17:58:12.450 回答