首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 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  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • 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
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-02 20:31:244楼 得分:0
    不懂,还是顶了!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • striker_un
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-02 21:37:375楼 得分:0
    很深很奥妙。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • suggyi
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-02 21:50:436楼 得分:0
    有一点点明白，因为是中文的……
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ko0lo0
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-02 22:09:467楼 得分:0
    看不懂！！！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mesedavy008
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 04:57:258楼 得分:0
    该回复于2008-04-26 14:48:41被版主删除
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • exy337
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 05:42:019楼 得分:0
    UP
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhuyx808
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 08:49:2110楼 得分:0
    很头痛
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • shuizhilang
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 09:59:4111楼 得分:0
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gxj760998
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 10:04:1712楼 得分:0
    LZ的两个问题是同意类型么？？
    我怎么觉得第一个是基础性研究，就象1+1 = 2样，
    第二个问题明显是算法优化，这种问题的个性非常明显，属于算法优化一类。
    我不过一个门外汗，在学校时接触过一点数学方面的知识，出来几年了，用到的不多。
    见笑了！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Coder211
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 10:26:5513楼 得分:0
    顶
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • fisher811
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 11:28:5914楼 得分:0
    UP
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wgw335363240
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-03 14:42:1415楼 得分:0
    UP
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • coy_zhangce
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：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
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：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
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：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
    该回复于2008-05-14 08:25:01被管理员删除
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Promi
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-21 21:29:4432楼 得分:0
    up
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cg600
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-23 21:39:1333楼 得分:0
    六神无主
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • robertkun
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-25 15:33:0034楼 得分:0
    无 语！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • 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
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-01 00:57:5437楼 得分:0
    我也想了解，谢谢LZ.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • UltraBejing
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-05-01 06:29:2338楼 得分:0
    关注 接分
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • schlafenhamster
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-06-26 14:20:4739楼 得分:0
    晕，想不明白
    修改 删除 举报 引用 回复
    公司简介| 广告服务| 银行汇款帐号| 联系方式| 版权声明| 问题报告
    北京创新乐知广告有限公司 版权所有, 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    文明办网文明上网举报电话：13552009689
    Copyright © 1999-2009, CSDN.NET, All Rights Reserved
    GongshangLogo