blocks|key|453128|text|不幸的是，组织图几乎不可能矢量化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|453129|不过，您可能会在一定程度上优化标量代码--一个常见的技巧是使用两个直方图，然后在最后将它们组合在一起。这允许您重叠加载/增量/存储，从而隐藏一些串行依赖关系和相关的延迟。伪代码：|453130|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|code-block|syntax|javascript|453131|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Histogramming is almost impossible to vectorize, unfortunately.

You can probably optimise the scalar code somewhat however - a common trick is to use two histograms and then combine them at the end. This allows you to overlap loads/increments/stores and thereby bury some of the serial dependencies and associated latencies. Pseudo code:

<pre><code>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
</code></pre>

blocks|key|453185|text|@Paul-R，在这个链接上有一些文章讨论了如何向量化直方图函数：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|453186|SIMD+Vectorization+of+Histogram+Functions|offset|length|453187|entityMap|0|LINK|mutability|MUTABLE|url|http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.9041&rep=rep1&type=pdf^0|0|0|15|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

@Paul-R, there exists some paper at this link which discusses how to vectorize histogram functions:

<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80.9041&amp;rep=rep1&amp;type=pdf" rel="nofollow">SIMD Vectorization of Histogram Functions</a>

blocks|key|453217|text|保罗有一个Simd项目，展示了他如何使用@+ermig1979+-R提到的类似方法以及SSE2和AVX2变体来做直方图：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|453218|项目：https://github.com/ermig1979/Simd|offset|length|453219|基本文件：https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp|453220|在这里可以看到一个AVX2实现：https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.cpp|453221|可以在下面看到标量解决方案，以说明创建多个直方图的基本原理，这些直方图在最后求和：|453222|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;+%2B%2Brow)
++++{
++++++++size_t+col+=+0;
++++++++for(;+col+<+alignedWidth;+col+%2B=+4)
++++++++{
++++++++++++%2B%2Bhistograms[0][src[col+%2B+0]];
++++++++++++%2B%2Bhistograms[1][src[col+%2B+1]];
++++++++++++%2B%2Bhistograms[2][src[col+%2B+2]];
++++++++++++%2B%2Bhistograms[3][src[col+%2B+3]];
++++++++}
++++++++for(;+col+<+width;+%2B%2Bcol)
++++++++++++%2B%2Bhistograms[0][src[col+%2B+0]];

++++++++src+%2B=+stride;
++++}

++++for(size_t+i+=+0;+i+<+HISTOGRAM_SIZE;+%2B%2Bi)
++++++++histogram[i]+=+histograms[0][i]+%2B+histograms[1][i]+%2B+
++++++++++++histograms[2][i]+%2B+histograms[3][i];
}|code-block|syntax|javascript|453223|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/ermig1979/Simd|1|https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp|2|https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.cpp^0|0|3|X|0|0|5|24|1|0|G|24|2|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|13|8|@]|9|@$D|14|E|15|1|16]]|A|$]]|$1|F|3|G|5|6|7|17|8|@]|9|@$D|18|E|19|1|1A]]|A|$]]|$1|H|3|I|5|6|7|1B|8|@]|9|@$D|1C|E|1D|1|1E]]|A|$]]|$1|J|3|K|5|6|7|1F|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|1G|8|@]|9|@]|A|$O|P]]|$1|Q|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|R|$S|$5|T|U|V|A|$W|X]]|Y|$5|T|U|V|A|$W|Z]]|10|$5|T|U|V|A|$W|11]]]]

ermig1979 has a Simd project which shows how he has done histograms using a similar approach to what @Paul-R has mentioned but also with SSE2 and AVX2 variants:

Project: <a href="https://github.com/ermig1979/Simd" rel="nofollow noreferrer">https://github.com/ermig1979/Simd</a>

Base file: <a href="https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp" rel="nofollow noreferrer">https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdBaseHistogram.cpp</a>

An AVX2 implementation can be seen here:
<a href="https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.cpp" rel="nofollow noreferrer">https://github.com/ermig1979/Simd/blob/master/src/Simd/SimdAvx2Histogram.cpp</a>

A scalar solution can be seen below to illustrate the basic principle of creating multiple histograms that are summed at the end:

<pre><code>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 &lt; height; ++row)
 {
 size_t col = 0;
 for(; col &lt; 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 &lt; width; ++col)
 ++histograms[0][src[col + 0]];

 src += stride;
 }

 for(size_t i = 0; i &lt; HISTOGRAM_SIZE; ++i)
 histogram[i] = histograms[0][i] + histograms[1][i] + 
 histograms[2][i] + histograms[3][i];
}
</code></pre>

blocks|key|453253|text|一些在直方图上工作的图像处理算法(例如均衡化、直方图匹配)可以与已知的百分位数一起工作-对于一个近似值，可以有效地将搜索并行到消耗4个累加器的初始范围(0,25,50,75,100%25)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|453254|输入流中的每个项目必须与所有时隙并行比较，从而增加频率。经过一定数量的轮次(例如，n*255次轮次保证uint8_t数据类型上没有溢出，然后将这些轮次累加到uint16_t)，基于线性插值重新计算每个时隙中的最小/最大限制。当然，也可以根据新数据改变了百分位数的估计值，重新运行序列。|453255|该算法不同于评估顺序，可以通过随机采样和多次遍历来缓解。|453256|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Some image processing algorithm working on histograms (e.g. equalization, histogram matching) can be made work with known percentiles -- and for an approximation one can effectively parallelize the search to initial ranges (0,25,50,75,100%) consuming 4 accumulators.

Each item in the input stream must be compared in parallel to all slots, incrementing the frequency. After a certain number of rounds (e.g. n*255 rounds guaranteeing no overflows on uint8_t data type, then accumulating those to uint16_t) the min/max limits in each slot are recalculated based on linear interpolation. And it's of course possible to re-run the sequence based on an estimation how much the new data has changed the estimates of the percentiles.

The algorithm would be variant to evaluation order, which could be mitigated by random sampling and multiple passes.

I am trying to implement histogram in Neon. Is it possible to vectorise ?

Methods to vectorise histogram in SIMD?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我正在尝试在霓虹灯中实现直方图。有没有可能进行矢量化？

问方法对SIMD直方图进行矢量化。
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问方法对SIMD直方图进行矢量化。EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问方法对SIMD直方图进行矢量化。
EN