首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
  • 归并排序的数据生成器 [已结贴,结贴人:haojn]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-10 11:20:39 楼主
    Intel多核比赛专用
    C/C++ code
    #include "tbb/cache_aligned_allocator.h" #include "mkl_vsl.h" using namespace tbb; int n; int *a; cache_aligned_allocator<int> alloc_a; VSLStreamStatePtr stream; void gen(int _n,int seed) { int status; n=_n; a=alloc_a.allocate(_n); status=vslNewStream(&stream,VSL_BRNG_MCG31,seed); status=viRngUniform(VSL_METHOD_DUNIFORM_STD,stream,_n,&(a[0]),0,(1<<28)-1); }

    gen(元素个数N,初始种子值Seed)
    可以用它来统一比较运行时间,省得从文件读入了

    我目前的时间:
    N=1^25,Seed=12345,单线程3.81秒
    0  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-10 14:09:531楼 得分:0
    N=1^25,Seed=12345,单线程3.81秒

    这个时间包括读入和输出数据的时间吗?
    我单线程不包括IO在XEON5110的时间是 10秒。

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-10 17:58:552楼 得分:0
    只是排序时间,不包括I/O,我是在Q6600上测的

    不过据说这次计时是包括I/O的。如果真是这样的话,优化I/O才是关键。真希望Intel能改变规则只计算排序时间
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-11 10:36:323楼 得分:0
    haojn, 不知道Q6600和XEON5110性能差别有多大。
    在你的机器上,对2^25的数据用TBB的parallel_sort()排序需要多长时间?
    我的双XEON5110使用TBB的parallel_sort()需要2.15秒。
    不管怎么样,你的单线程3.81感觉很快了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-11 11:13:064楼 得分:0
    parallel_sort()用了1.7秒,4个线程;5.89秒,单线程
    我的操作系统比较臃肿,TBB的版本(20_017)不是最新,可能有些影响

    Q6600是2.4G,两个封装,每个封装2核,L1D是32K*2,L2是4M
    XEON5110是1.6G,双核,L1D也是32K*2,L2也是4M
    两个FSB都是1066

    双XEON55110和Q6600主要差别是主频,另外Q6600两个封装之间的通信延迟可能会短一些,不过服务器主板的内存控制器性能会高于桌面

    2.15*(1.6/2.4)=1.43,看来你的系统更有效率
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-13 19:10:215楼 得分:0
    haojn 如果完美的线程化你的程序 你的成绩应该是3.8/4 = 0.95
    比parallel_sort() 快了将近1倍 强啊!!!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 20:38:316楼 得分:0
    我现在依然没有做并行化,打算最后再加上,现在优化重点转移到I/O了

    parallel_sort()其实就是用parallel_for()写的qsort,而qsort本身其实是不太适于并行的

    不过我感觉这次比赛基本上是看I/O时间了
    我现在N=2^25时的输出时间是11.8秒,输入还没有做
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-21 19:14:437楼 得分:0
    我单线程不包括IO
    在XEON5120的时间是 10秒。

    单线程 6.146269 seconds
    多线程 2.170675 seconds
    parallel_sort: 1.830920 seconds

    线程化做得不够好
    4个核 1:3
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-21 19:16:108楼 得分:0
    看来haojn的程序比我快很多.
    我实在想不出更好的优化策略了.已经展开了递归只能提交了.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-22 11:56:259楼 得分:0
    没时间做,·唉~过来学习~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-23 19:02:0010楼 得分:0
    为了加速I/O,我用了x64,结果单线程排序退化成4.7秒

    多线程的效率极低,4个线程只能到2.15秒,似乎有明显的资源争用


    这次基本上看测试的顺序了,如果排在前面的那个程序占了很大内存,那么文件缓存将被evict,I/O的时间就非常多了


    对了,大家有得到额外的100分么(有效提交3个问题后)?我的好像没有
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-23 20:26:2911楼 得分:0
    读写文件的时间也要计算在内?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-23 21:14:5712楼 得分:0
    我得到了额外的50分 在提交第4个问题的时候
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-23 23:27:5013楼 得分:0
    我还没交第4个

    现在是:

    总分 899
    提交作品( 3 份作品) 300
    加分 0
    评委评分 599
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-23 23:46:2614楼 得分:0
    读写文件的时间也要计算在内?
            是的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 17:10:4515楼 得分:0
    昏 原来haojn=just
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 18:06:3316楼 得分:0
    呵呵,是啊。我以为你早就知道了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 18:56:5217楼 得分:0
    denghui0815的照片很像崔永元啊
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 20:10:0218楼 得分:0
    我倒 我没那么有个性吧!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 21:53:1819楼 得分:0
    应该是像小崔一样有个性
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 21:59:2820楼 得分:0
    没有装mkl库,我用了
    C/C++ code
    size_t *constructData(size_t size){ size_t *src = alloc_a.allocate(size); for(int i=0; i<size; i++) src[i]=i; random_shuffle(src, src+size); return src; }

    parallel_sort()单线程 7.x,两线程4.x
    自己的归并      单线程 6.x,两线程3.x

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-24 22:51:2221楼 得分:0
    我现在才提交程序,是不是要扣分啊。
    我的测试是在VMWARE上做的——
    480MB,五千万随机整数,30秒。
    244MB,2千五百万随机整数,11秒。
    97MB,一千万随机整数,4秒。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-25 07:35:0122楼 得分:0
    vmware的效率很差劲的,你的执行时间可是大大地缩水了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-25 17:06:0523楼 得分:0
    等楼主上传代码
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-25 20:32:3024楼 得分:0
    呵呵 谢谢关注 我的源码
    http://download.csdn.net/user/huanyun/

    希望能看到更多的人共享源码, 互相学习. :)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-25 20:35:1725楼 得分:0
    昏倒 发错地方了 :(
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-25 22:54:2826楼 得分:0
    上传了,请在这里下载

    http://download.csdn.net/user/haojn

    里面有文档,这里就不贴算法了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-26 10:12:4127楼 得分:0
    我在64bit虚拟机上始终无法编译出你的程序,郁闷
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-26 10:21:5628楼 得分:0
    是不是TBB版本的问题?
    win32能编译么?


    有什么办法能删除上传的资源?没想到上传了3个...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-26 10:37:4629楼 得分:0
    不能删。我要说CSDN的坏话了,这个CSDN论坛,发帖、格式编辑、上传、下载、个人空间......很多地方都做得糟糕
    修改 删除 举报 引用 回复

    网站简介广告服务网站地图帮助联系方式诚聘英才English 问题报告
    世纪乐知(北京)网络技术有限公司 版权所有 京 ICP 证 020026 号
    Copyright © 2000-2007, CSDN.NET, All Rights Reserved