CUDA与一个千年数学问题

欢迎您:游客帮助

我参与的帖子

CUDA与一个千年数学问题 [已结贴,结贴人:darkstorm2111203]

darkstorm2111203
樟树
等级:

发表于：2008-04-01 20:33:02 楼主

根据书上说和我的经验,要将CUDA计算发挥到最大，就必须尽量多的使用sharedmemory
有这么一个问题，比如你要将一个矩阵中的各行（共n行）两两间进行处理（科学计算中经常遇到的问题）
如果一个sharedmemory里面只存两行，那么就需要n/2个block，进行n-1次计算
但可能一个sharedmemory里面可以放更多的，比如7行，那么就只需要n/7个block，进行(n-1)/6次计算

这是什么概念呢？两个划分block的方式计算量相同，但是第二种方式的存储器访问可以节省84%,在我的应用中，两种方式性能差距达到了一倍！
这就涉及到一个排列组合问题，千年数学难题：女生散步问题。
15个女生，每天晚上3个一组出去散步，如何分组，使得经过一定次数后，恰好使得每个女生与其他女生散步且只散布一次？
在CUDA的官方例程特征值分解中，在最后的性能提高改进方法中也提到了分组问题，但是没有给出解决方法。
这个问题的计算量是非常大的，事实上，要得出512行的7个一组分组方式如果使用递归回溯方法可能需要几个月。如果可以得到这样一张组合表，无疑对解决CUDA架构下的shared memory利用率问题产生巨大帮助。我的思路是使用神经网络方法或者放宽约束条件，允许数据在一轮组合内被使用数次。

不知诸位在使用shared memory时还有什么好的想法。

问题点数：20 回复次数：38 修改删除举报引用回复

jack_luck
jack_luck
等级:

发表于：2008-04-02 10:37:391楼得分:0

问题很深奥，看来楼主的功底很深哦

修改删除举报引用回复

creazywind
冰*雪（爱过方知情重，醉过方知酒浓）
等级:

发表于：2008-04-02 19:42:582楼得分:0

呵呵不懂帮顶！

修改删除举报引用回复

clw_zxq
寒芦飘絮
等级:

发表于：2008-04-02 19:52:273楼得分:0

好难啊，我不是太清楚，应该有排列组合的公式吧，要不写一个算法，让超级计算机去算吧，呵呵。

修改删除举报引用回复

jeff_nie
多C多漂亮!
等级:

发表于：2008-04-02 20:31:244楼得分:0

不懂,还是顶了!

修改删除举报引用回复

striker_un
徐兴
等级:

发表于：2008-04-02 21:37:375楼得分:0

很深很奥妙。

修改删除举报引用回复

suggyi
suggyi
等级:

发表于：2008-04-02 21:50:436楼得分:0

有一点点明白，因为是中文的……

修改删除举报引用回复

ko0lo0
世界变了
等级:

发表于：2008-04-02 22:09:467楼得分:0

看不懂！！！

修改删除举报引用回复

mesedavy008
mesedavy
等级:

发表于：2008-04-03 04:57:258楼得分:0

该回复于2008-04-26 14:48:41被版主删除

修改删除举报引用回复

exy337
exy337
等级:

发表于：2008-04-03 05:42:019楼得分:0

UP

修改删除举报引用回复

zhuyx808
花心小和尚( 施主！赏个漂亮妞吧 )
等级:

发表于：2008-04-03 08:49:2110楼得分:0

很头痛

修改删除举报引用回复

shuizhilang
shuizhilang
等级:

发表于：2008-04-03 09:59:4111楼得分:0

up

修改删除举报引用回复

gxj760998
小猴子
等级:

发表于：2008-04-03 10:04:1712楼得分:0

LZ的两个问题是同意类型么？？
我怎么觉得第一个是基础性研究，就象1+1 = 2样，
第二个问题明显是算法优化，这种问题的个性非常明显，属于算法优化一类。
我不过一个门外汗，在学校时接触过一点数学方面的知识，出来几年了，用到的不多。
见笑了！

修改删除举报引用回复

Coder211
BlueGene
等级:

发表于：2008-04-03 10:26:5513楼得分:0

顶

修改删除举报引用回复

fisher811
大智若鱼
等级:

发表于：2008-04-03 11:28:5914楼得分:0

UP

修改删除举报引用回复

wgw335363240
rey
等级:

发表于：2008-04-03 14:42:1415楼得分:0

UP

修改删除举报引用回复

coy_zhangce
Coy
等级:

发表于：2008-04-03 15:07:4016楼得分:10

个人认为楼主的观点有点牵强。
对于GPU运算，首先应该考虑的是超轻量的线程，线程越小，单次运算量越少，就越可能发挥并行计算能力。对于采用复杂分组来加快运算，分支检测可能会很多，不一定可取。
其次，512并不是一个很大的数字。512行的数据，显然不会很大。512行分组方式同样不一定很大。但如果我们要算的不是512，而是4096呢？分组方式就会大的很多，而且不一定是线性增长，所以复杂分组应该有点欠考虑。

修改删除举报引用回复

guobingz
等级:

发表于：2008-04-03 16:35:4217楼得分:0

功底很深呀！顶一个

修改删除举报引用回复

HKCID
坏得不够彻底！
等级:

发表于：2008-04-03 16:55:1118楼得分:5

女生散步问题在70年代还是80年代被意大利的数学家解决了，不过不是通解；通解是我们一个数学家解决的。

修改删除举报引用回复

darkstorm2111203
樟树
等级:

发表于：2008-04-04 09:21:0919楼得分:0

分组交换的顺序可以用固定的查找表记录在globalmemory里，每次只要通过threadid和blockid查找就行了，不存在分支预测
加快gpu运算，恰恰需要增加单次调用__global__ 函数,两次访问global存储器之间的运算量尽量大，也就是增加运算密集度。
在cuda的手册中提高运算性能的章节也有提及，global存储器仍然是gpu运算的瓶颈，nVidia的意见是尽量在block内使用shared memory来进行数据交换。

修改删除举报引用回复

xfdydyh
hello Software!
等级:

发表于：2008-04-04 22:58:5120楼得分:5

18 楼的:我是学数学的,那个问题同matlab能解,而且是所有解.

修改删除举报引用回复

Q_282898034
我为编程狂
等级:

发表于：2008-04-05 01:18:4821楼得分:0

为什么是女生散步，不是男生散步

修改删除举报引用回复

darkstorm2111203
樟树
等级:

发表于：2008-04-05 15:39:5122楼得分:0

引用 20 楼 xfdydyh 的回复:
18 楼的:我是学数学的,那个问题同matlab能解,而且是所有解.

20楼的兄弟请赐教！我要求一个（518，7，84）的解，条件放宽点也行
不要穷举算法的...用穷举算法做肯定吃不消，工具箱里有什么函数可以调么？

修改删除举报引用回复

ymle1228
东边的红隼
等级:

发表于：2008-04-07 09:06:1223楼得分:0

MACK

修改删除举报引用回复

liaozhiyang
cyclone
等级:

发表于：2008-04-07 10:59:3424楼得分:0

好深的问题,不懂

修改删除举报引用回复

kolkosky
癫狂
等级:

发表于：2008-04-07 11:43:5125楼得分:0

这么复杂

修改删除举报引用回复

kolkosky
癫狂
等级:

发表于：2008-04-07 11:47:0726楼得分:0

12+11+10+9+8+7+6+5+4+3+2+1

修改删除举报引用回复

liuhao1201
等级:

发表于：2008-04-07 15:09:1127楼得分:0

mark

修改删除举报引用回复

moses731
等级:

发表于：2008-04-07 17:29:2128楼得分:0

up only up

修改删除举报引用回复

maning_1986530
等级:

发表于：2008-04-07 20:10:3129楼得分:0

up!up!

修改删除举报引用回复

oliverlee1
等级:

发表于：2008-04-07 22:01:1130楼得分:0

比较深奥。。。
呵呵

修改删除举报引用回复

szcoder1101
深圳起点
等级:

发表于：2008-04-08 09:54:4331楼得分:0

***************************************************************************

程序员在深圳QQ群大集

专业分类:
程序员在深圳JAVA群4247660
程序员在深圳c++群15195967
程序员在深圳.NET群Ⅱ:12203296
程序员在深圳TCP/IP协议栈开发:16956462
程序员在深圳JS & AJAX群:12578377
程序员在深圳英语学习群:23864353
深序员在深圳VB:11055959
程序员在深圳c++Ⅱ17409451
程序员在深圳c++群15195967
程序员在深圳嵌入式开发群37489763
程序员在深圳移动开发群31501597
程序员在深圳创业群33653422

不限专业分类:
高级群:17538442
第三群:2650485
第二群:7120862
第五群:29537639
第四群:28702746
第六群:10590618
第七群:10543585
第八群:12006492
第九群:19063074
第十群:2883885
第十一群:25460595
第十二群:9663807

深圳程序员QQ群联盟成立两年多，拥有三十个以上的QQ群,人数达二千多人,有30%以上的成员的经验丰富的老手,包括国内外顶级大公司的成员（如微软、IBM,SUN，华为）、国内著名高校和研究院成员，和有丰富实践经验的高级程序(包括参加过上亿元的项目的架构师),有很热爱技术的成员(包括自己写过嵌入式操作系统),还有少数女程序员。现推介如下QQ群,如有兴趣速速加入:深程高级群:17538442c++:15195967 .NET:12203296 mobile:31501597嵌入式:37489763 JAVA:4247660
——————————————————————————————————————————
希望大家不要认为群能给你带来什么，这只是一个平台,让同等水平的程序员有个交流的机会或许能得到一点信息或许能带来一点启发。

*****************************************************************************

修改删除举报引用回复

Promi
等级:

发表于：2008-04-21 21:29:4432楼得分:0

up

修改删除举报引用回复

cg600
ccc+++
等级:

发表于：2008-04-23 21:39:1333楼得分:0

六神无主

修改删除举报引用回复

robertkun
UUKUN
等级:

发表于：2008-04-25 15:33:0034楼得分:0

无语！

修改删除举报引用回复

IO_X
IO_X
等级:

发表于：2008-04-29 21:11:4435楼得分:0

避免一些需要两两操作且有序的算法，因为这不适合gpu。
比如在求解线性方程组时，避免用高斯消去法，而是用多重网格法(MG/AMG)+某种迭代(Jacobi/Red-Black G-S...)

修改删除举报引用回复

meiZiNick
三太子
等级:

发表于：2008-04-30 19:28:2136楼得分:0

支持搂主，收藏

修改删除举报引用回复

knowledge_Is_Life
阿凡
等级: