直方图统计

我想问下类直方图统计有没有什么好的办法。我现在的情况是:1024*1024纹理,统计到4000个类中,但是只有300~500 个类是有内容的,用到了shared memory 的原子操作,但还是很慢,请问有什么高级的算法吗,对于直方图统计?

有点不太明白这是个什么问题,楼主可否稍微详细地说一下。
以及,如果能抽象为数学问题,可以让更多不同专业的人看明白。

抽象数学问题 额,没有那么搞的理论基础。

可以把他看城是:统计一个纹理上出现颜色为红色的像素的数目,统计的颜色种类有3000种,其中有值的只有300种。 统计中原子操作耗费时间。
我想问:有没有什么奇奇怪怪的并行算法可以避免原子操作的?

我说的是“抽象为数学问题”,而不是“抽象的数学问题”。类似于小学生应用题转化为算术题的概念。

比如说你这个问题里面颜色有3000种是如何表示的?什么叫做“有值的有300种”?你需要实现的问题是如何的?你之前是如何使用原子操作实现的?

总之你得让一个不做你这个具体问题的人看明白是怎么回事,才能开展讨论。而不是假定大家都是你课题组的,或者都是你的小同行。

我来猜测一下楼主的可能算法过程:
(1)为4000个颜色类别分配空间。例如分配4000个int。
(2)将4000个分类里面的初始值设置为0.
(3)上去一百万个线程。
(4)每个线程读取一个元素。判断(此处可能涉及运算), 属于何种种类。
(5)将归属种类的统计数量原子加1. 例如atomicAdd(&你的目标种类的地址, 1);
(6)完成统计后,绘制直方图。

这是对楼主您的问题的一个假设实现,我们假装您的算法是如上写的好了。(因为您没有提供算法)。

那么我们看一下肉眼能见的瓶颈在哪里:
原子操作上。

看来此假设基本满足您的实际实现。

那么对楼主您的建议:
(1)购买Kepler卡,kepler卡大幅度提升了原子操作的性能。
(2)如果您不方便立刻升级硬件,您可以继续使用您的fermi卡,您可以考虑这个改善:
立刻停止在shared memory上使用原子操作(如果有),请改为在global memory上. 后者快得多。(是不是不符合您的想象?但原子操作的确在global上比shared快好多)。
(3)您可以更改统计算法,有很多统计算法可以供您选择。

考虑到您的统计流程涉及读取/计算判断归类/写入归类。
我目测您的算法在最终优化后,可能只受限于访存速度。我这里给您粗略的估计下您的理论上最终可能优化到的极限:
假设您的元素是4B大小。您需要读取102410244B = 4MB, 写入到归类里,我们假设最多也是4MB好了(其实可能没有那么多写入,只是粗略估计), 计算判断时间不计,被访存完全掩盖。

那么最终您能达到的性能:4MB * 2 / 您的卡的global吞吐量每秒峰值,如果您用的是GTX460,
大约需要4MB * 2 / (100GB/s), 也就是需要大约0.1ms.这可能是您的问题的优化极限了。

建议最简单的:使用global memory做原子操作。
如果您想追求极限,建议您继续跟帖ICE版主,让ICE和您一起考虑算法上的优化。

祝您一切顺利。
横扫千军

目前原子操作的效率不高,因此加速不明显,当然在k20上有提高,或者考虑编写一个适合CUDA的直方图统计算法!

您好,您知道在KEPLER上面全局显存和共享存储器的原子操作吞吐率具体是多少吗?
感觉上全局显存达不到100GB/s这个吞吐率吧?这个数字好像是普通的访存吞吐率,而不是原子操作吞吐率。

另外原子操作的吞吐率是不是跟访问地址的分散程度有关?
假设各地址完全分散而没有冲突,这种情况下能达到最大是多少?完全集中为一个地址又会如何?
多谢!

是的。跟分散程度(冲突率)有关。

完全没有冲突,效果如何?这个我没有数据。官方也没有给出数据。但以前的老NV论坛(英文版)曾经有人用red指令(reduction, 相当于不返回旧值的原子操作)来做global memory上的完全无冲突的加法,然后他给出了直接读取,增加,写入常规操作的对比。这个作者的结论是,完全无冲突的时候,可能比手工读入,计算,写回要快。他给出的理由是,直接在某单元上完成,不需要SP的参与。节省了资源。

本人提供上述信息仅供songyong2参考,不代表本人或者论坛赞同或者不赞同其观点。
欢迎songyong2继续发帖。

您能大致解释一下为什么全局显存的原子操作比共享存储器的吞吐率要大吗?
我是想毕竟全局存储器的操作延迟很大,能在共享存储器做的尽量在共享存储器做才是啊。

是的。fermi, 在 global memory上的原子操作性能比在shared memory上的要好,但手册没有给出解释。

但根据未知的来源表明,fermi有native指令(据说叫atom和red), 支持在global memory上如此干。而对于shared memory, 却只有ldlk之类的,需要使用类似软件锁的机制实现原子操作。所以性能不好可能在这里。

注意,第二段落的内容来源未知,也不是NV保证的内容,只是为了楼主的CUDA开发便利,而给出的转载,我和本论坛不保证赞同但也不保证反对其观点。

那在Kepler上面如何?原子操作在共享存储器上应该比全局显存要好了吧?
总不能将原子操作都要放到全局去吧。这个延迟不好弥补啊。

kepler无资料,无数据。

延迟不算神马。本来就是为掩盖延迟而设计的卡。对吧。

其次,这延迟真心危害没你想想的那么大的,至少还有L2顶上。

延迟800个周期,需要上百条指令来隐藏啊,那么容易应付吗?
L2的延迟也不小啊,也需要数百周期吧,这个我没有见到过具体资料介绍。
另外我还想问一个问题就是PCIE的延迟您是否知道?
另外我看到有资料说是共享地址1个操作,分散地址64个操作,不知道是不是这样?
非常感谢您的答复!

话说,您平日不从global memory/L2里读取数据,写入数据吗?您直接无冲突的atomicAdd的总延迟都比您的读入寄存器,增加,回写的延迟要小呢。亲。没事的。800个周期是算的SP频率(fermi上)。其实也无所谓。大家从PCI-E拉过来数据不是一样用么。亲。既然设计了global memory, 就用吧。

PCI-E的延迟我不知道,建议咨询PengWang同学,
另外,关于您的:“另外我看到有资料说是共享地址1个操作,分散地址64个操作,不知道是不是这样?:”我不懂。依然建议此条咨询WangPeng.

pci-e应该比global慢得多了,无论是延迟还是带宽,而且和你系统的情况有关,比如说你的主板芯片组北桥芯片(或者被CPU集成了的北桥芯片)。

直方图的问题也在困扰我,我的情况可能更麻烦,sharememory里面都放不下直方图,只能装进global。加上原子操作和几百万个点,已经慢的不行了,不知道这个问题在CUDA里面有没有新的策略。

lianuosun您好:

一般尽量使用block内的通信机制尽量减少global的原子操作是一个可供考虑的优化途径。

其他您的问题的具体事宜,请您另外开贴详细介绍下情况,以便讨论。

祝您好运~