[GTV]公开源代码，恳请大家优化
本帖最后由 fwjmath 于 2010-6-8 01:17 编辑**** Hidden Message *****
上面是为CAS@home而写的新的版本的代码，比起之前的版本有比较大的加速，当然在算法上也有改动。
但是最重要的是在任务的分配上，不再需要生成全部的树，只需要生成需要计算的树，节省了一定的时间。而且有一个变量专门记录计算量，存盘点改为根据计算量存盘，所以也更为规律。记录计算量的变量的另一个用途就是BOINC积分的计算。
关于整个算法的描述，请参看如下链接：
http://arxiv.org/pdf/1003.3045
http://www.eleves.ens.fr/home/wfang/gtv/index.html（由于作者太懒，页面已完全停止更新…………………………）
现在公开源代码让大家监督，同时也让大家提一些优化的意见。源代码在GPLv2协议下发布。
data.txt是一个测试文件，用以测试正确性。 只看了代码，没运行。随便说点儿，希望管用
想要特别优化好，还是需要先profiling来分析
另外其实现在也不用太优化，功能性第一，能在BOINC跑了再慢慢优化也不迟
(1)
Line 335:
myrand()/(RAND_MAX+1.0) > SAaccept
这个是模拟退火吧
如果这行是hotspot的话（被频繁的执行），避免浮点、除法操作，最简单的变成myrand()×10>(RAND_MAX+1)
不过这样还是不够好。反正用的伪随机数，可以预先生成一个足够长的0/1序列，让1/长度=0.1。以后每次去看是0还是1就行了
(2)
换用Intel Compiler (ICC)来编译，打开合适的编译优化，估计能快不少
(3)
一开始就执行N次myrand()，预先生成随机序列存好，以后读就行了。或者直接用Intel MKL的库，效率非常高
(4)
没有递归的函数，把局部变量加static
(5)
提高cache性能，这个比较复杂。看样子程序不用太多内存，cache不会miss，但是可能会跨行增加操作时间
简单的办法是数据对齐，编译器有语句可以做到
另外测试把一些数据结构char->int，可能性能会更高
(6)
现在有太多的分支语句(if, while)，可能的话转化为数学表达式消除分支
这个比较技巧，而且破坏可读性，可以以后慢慢来
(7)
如果考虑移植，别用long long，不同平台大小不一。最保险的，跟计算有关的都用__int32，__int64之类的 水平有限，难以看懂（主要是懒得看啦）。
提个无聊的建议：
代码缩进比较乱，多空些行会比较美观。
TO 楼上：
(2)换用Intel Compiler (ICC)来编译，打开合适的编译优化，估计能快不少
这样的话对AMD的处理器很不利。最关键的一点是...Windows下的ICC收费。 本帖最后由 fwjmath 于 2010-4-13 01:09 编辑
回复 2# JUST
(1) 其实只是借用模拟退火里边跳出局部的想法，它不是热点，我用AMD Analyst做过分析。热点其实在DFSLabelRev这个函数里边，程序80%的时间都在它里边，有大量的递归，栈操作很多，而且没啥好的办法来消除。
(2) Linux版的确是用ICC编译的，随便开了几个编译开关，基本上差不多吧应该……Windows下的就随便用VC++ 2008编译了，开了比较多的优化的开关。其实我之前做过测试，旧版本的程序ICC编译出来的在linux下的运行速度和用VC++ 2005编译出来的在win下的运行速度差不多。主要还是DFSLabelRev实在没什么很好的优化方法……
(3) 其实myrand()的结果的另一个用途是checksum，而且这个函数至少调用上百万次，所以……还是算了吧……
(4) 这个为啥对性能会有帮助？
(5) 程序用非常少的内存，cache问题应该不大。有些数据结构写成char是故意的，为了输出的时候比较方便。
(6) 这个还要向你请教啊~~~
(7) 这个我看看，不过暂时问题不算很大。
谢谢JUST的意见~~~ 回复 3# cuihao
er...我干的很多东西都没啥美感，所以这一次也容忍了吧……
ICC在Win下要收费的确是个很麻烦的问题……之前有一次给3x+1（没有@home，是Eric Roosendaal的那个，翻译了他们网站的那个）做优化，为了编译64位汇编去蹭了三四次evaluation version…… fwjmath公开代码啦，那是不是要把GTV做成开源项目啊？
用VC++写的啊，那就没啥意见提了，我不是专业学软件，更郁闷的是我们学校在我们这届把他它从课程计划中给删了啊！！！我就没学过那个。。。。。。。。 回复 4# fwjmath
(1)
如果有时间的话，消除所有函数递归，改为堆栈来模拟，特别是用MSVC编译的时候
没用过AMD的profiling产品，你的CPU是AMD的？
我Vtune过期了，你可以考虑统计一下这几个，不然现在只能是猜
cache split line access
cache miss
CPI
branch miss及相应位置，这个很关键
其他各种stall及相应位置（比如RS full, ROB full）
(2)编译开关还是需要调校的，如果性能跟MSVC差不多那八成还能调得更好
(3)至少把myrand加上inline，如果编译器没有自动加的话
(4)全局变量放在data段，地址是硬编码，比如mov eax,
局部变量在stack，地址要计算的，比如mov eax,
有的架构对此很敏感
(5)cache性能不光是miss rate，access time也很关键。如果你的load/store的数据分割在两个cache line，就要用多余的时间
另一方面，非32bit操作可能会有partial reg stall
优化本身就是平台相关的，每个平台独立优化一个比较好 回复 3# cuihao
版权不会是个大问题，总有办法绕过 代码缩进看着已经比较顺眼了。当年很多同学都是些小说的格式写代码。
仍了很长时间，重新捡起来看着很吃力。如果能加上一些注释来表达你的思路就更容易理解了。
包括各个函数的设计和用途，我还没太理解呢。
所以是否可以有合并或者改成宏的函数，或者功能拆分或重新组合，现在还不太清楚。我慢慢看，如果我最终能看明白的话。
我一直希望你的最终输出结果能更多。然后反馈给你用来分析。
比如每一个种树形的计算结果。
用统计的方法可以得出树形的种类是如何分布的，数字的分布是否类似。可以获得证明更多的树的种类是可以推导的，而不用试错。
你可以让我们算所有的结果，我们做的不单单是证明n=37。而是可以有更多的发现。
我希望GTV的第2阶段是将数据分析也纳入任务当中。每个任务里有n=37的10M结果数据，用100M内存来将分析结果。才能更加充分的利用我们的计算成果，有更多有价值的结论出来。让更多的人可以获得这些信息并进一步进行研究。
这才是open & free
不要担心计算结果过多没有地方存储。和我们计算得出的价值相比，那点花费不算什么，我能帮你找到解决办法。 回复 7# JUST
(1) 以前好像试过，效果不太明显，可能是改得不够好……可能可以再试一下~~~
其实我的CPU也不是AMD的……所以也就只能看看热点而已……过段时间我再去弄个VTune看看这几个参数吧……
(2) 这个也要有空再做……
(3) 这个基本上VC开了/Ob2问题就不大的吧……以防万一还是加上……
(4) 局部变量这个我迟一点挖一下汇编代码看咋样~~~
(5) 还真的是要弄个VTune……char的问题我试试改一下看会不会好一些~~~ 准备看看效果，用院里实验室的机子运行的MSVC++6.0简体中文企业版，结果一个库文件它没有，我悲剧啦 回复 11# swh@home
unistd.h是linux下的，在windows下换成io.h和stdlib.h应该就可以了~~~ 原来如此啊，我一直没有机会接触linux的，谢谢了 wujie博士 你好，本人也很关注CAS@home项目。想询问下cas要公开给志愿者测试了吗？ 说实话。。。我对我的积分和我的权限表示鸭梨很大
页:
[1]
2
