ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 关于并行化编程的一些感悟

关于并行化编程的一些感悟

原创 Linux操作系统 作者:yu_single 时间:2010-05-20 13:31:54 0 删除 编辑

比赛是公司搞的,要求在20天时间内完成一程序,求三维空间内所有射线同所有三角平面的交点。射线和三角平面都通过文件方式输入,结果以文件输出,程序最后测试的平台有8核,8G的内存。算法,语言,线程库都不做限制,任意发挥,最后以结果正确,速度最快者获胜。我大概搞了七八天(由于放了长假还要上班,实际没有20天,不过这个大家都一样,公平),从对图形学零知识,学习向量、点乘、叉乘等等这些基础知识开始,到运用空间划分、光线行进算法,加上多线程,最后也能跑出相对满意的结果,虽然最后由于程序局部设计上的一点缺陷,导致公测的时候未跑出正确结果,但依然感触良多,故在博客中开个处女贴,一是作为纪念,二是希望能跟更多的技术爱好者共同交流,共同进步。

一:先说一下自己的整个比赛过程:

   当刚拿到题目的时候,除了需要先学习基本点图形学基础外,还在网上找了射线跟三角面求交的算法(也就几十行代码),然后很简单的认为只要每条射线跟每个三角面求一下交,所有的交点就能获得了,在算法上还能做啥优化不成?这种想当然使我很快实现了整个程序,包括读文件,写文件以及求交。拿比赛委员会给的最大的测试数据一测,跑了十几秒(由于本机是双核,于是用了两个线程来求交),然后想再做些优化,发现小小的程序已无太多优化的余地,遂心中起疑虑,这种算法是个选手都能想到,线程的效用也都能发挥到最大,那最后比成绩岂不是在拼运气,于是觉得应该没那么简单,但对于此前从未涉足过图形学的我来说,也实在不知该从何处下手优化。此状态持续了有三天左右,一直在一些小地方做优化,提高成绩也很有限。

  之后跟一个同事聊起此比赛,由于他研究生读的就是图形学,大概跟我提了一下空间划分、八叉数这些概念,突然感觉这里面有戏,于是开始在网上搜索这些概念,找相关的资料、论文,果然,发现了一片大天地,于是花了一两天时间好好研究了一把这些知识,并结合自身的需求,设计了出了一套算法。再马不停蹄的用代码实现,经过漫长的调试后一跑,时间降到了两三秒,我的天呀,这种成就感太让人兴奋了,不过兴奋之后并没有忘乎所以,开始分功能模块单独测试运行时间,哪一块所占时间大就先优化哪一块,时间在一点点缩短,令人感叹的地方也越来越多,最后优化到600多毫秒的时候,离最后提交时间就差一小时了,于是匆忙提交。哎,说到这里,有个教训需要提一下,那就是疏忽了测试数据,误以为最后公测的数据也应该跟委员会提供的最大数据量差不多,可实际根本就不是一个数量级的,导致了程序在初始化的时候发生错误,从而前功尽弃。虽然说比赛以参与为主,但既然参加了比赛,自然就希望能打败对手,所以最后失败也略感不爽。当然,这也算是个不大不小的经验教训,对自己今后还是会有帮助的。

二:下面主要从算法,数据结构,语言,多线程三个方面来总结优化的过程:

(1)      算法、数据结构永远是计算机的核心,语言只是表达它们的一种工具,而多线程多核只能算是一道诱人的小菜。

从我参与的整个过程看,算法在这里起到了决定性的作用,提高的性能绝不是多几个核能解决的,而数据结构设计的好坏,不仅对算法的性能提高有很大帮助,而且对多线程发挥效用也起到了决定性作用,因为好的数据结构能减少线程访问公共数据的冲突,从而让线程跑的更加畅通无阻。至于语言,我用的是C++,当然,是面向对象还是面向过程对这个比赛影响不大,主要是在使用C++库上面需要好好考察一番,尤其是STL,当整个运行时间降到1s以下时,你会发现无论它的 map类还是hash类都是那么的慢,能占个几百毫秒,这时如果你消耗点内存,开个全散列的读写缓存,几百毫秒一下就没了,当然,这里是以空间换时间。还有碰到的一个情况是,如果你要初始化几百万个对象,而这个对象里包含了一个vector,此vector的功能仅仅是插入一些数据,那你还是老老实实自己写个列表吧,因为它的初始化也是几百毫秒,当然,这里的情况比较特殊,一是有几百万个对象,二是程序性能优化是在毫秒级别的。你要是碰不到这种情况,用了也无所谓。这里就引出第二个结论。

(2)     不要轻易对性能瓶颈做出结论,一切都要在精确测量之后再确定。

直观判断的结论往往是不准确的,很多时候也很难做直观的判断,所以尽可能的插入一些统计数据,包括时间,循环执行次数等等有利于你做判断的数据。

(3)     性能瓶颈是在不断转化的,当不起眼的部分在你优化了其它部分后,它就是你下一步要攻克的对象了。

当我把求交的模块优化好之后,发现从得到交点到写出文件耗费了很长时间,一开始以为是从缓存把数据写到文件时慢了,但一测其实速度是很快的,于是就往上找,最后定位在sprintf_s这个函数上面(需要把double转换成char),一统计时间,乖乖,又是个几百毫秒的家伙,于是考虑自己写 double转换成char的函数,哈,很多人可能会直观觉得这会比较复杂,自己写出错风险较大,我一开始也这么觉得,可没办法,此处不优化,我夜不能寐啊,于是开始分析所有double可能的值,如何设计特殊情况,大概60行左右代码就完成功能,而sprintf_s据说有一千多行代码,故性能提升也很明显。而且从这里亦可看出无论是C还是C++,其提供的库函数往往为了普适性而会降低特殊性,这无疑会对一些特殊应用牺牲性能,所以在开发过程中一定要针对你的特殊情况量体裁衣,不要拿来就用。当然,当需要你自己动手写这些底层功能的时候,考验的又是算法和数据结构的基本功了。

(4)     扩展你的知识面,最好对它们都有一定的了解,这能让你在最短时间内做出最合适的选择。

由于我对图形学知识的匮乏,使得在前面浪费了很多宝贵时间;另外不了解OpenMP, TBB等这些线程库,不仅缩小了我的选择范围,也增加了自己学习的时间。在这样的比赛中,谁能更好的利用时间,谁就赢得了一半比赛。引申一下,很多开发人员往往认为我只要精通一门技术就走遍天下都不怕了,我觉得这是不够的。在做商业项目的时候,为了降低风险,满足客户需求,往往在一开始需要设计几套方案,此时考验的就是知识的广博,而当方案选定,需要实现的时候,考验的就是知识的精深了。从项目的生命周期来看,广博更处于上游,因此其影响力也更大。

(5)     先从大处着手优化,然后再优化小处,否则顺序颠倒,就算你在小处优化的再好,也只能是个甜头。所谓大处小处,请通过第2条来确定。

在时间有限的前提下,用最宝贵的时间来做最有利的事,往往这件事难度也会比较大,但不要任性去做自己喜欢或觉得简单的事,否则只能是在浪费时间,对结果却帮助不大。

(6)     模块化设计程序,让你有更方便的优化空间。

这点跟平时的编码功底很有关系,混乱的设计虽然最后功能也实现了,但会让你在优化的时候痛苦不堪,令结果也错误百出,最后不得不为了保证正确性而不做优化。而清晰的程序设计,尤其是数据和执行逻辑的耦合性低,会让你优化起来事半功倍。

(7)     记住,你程序的瓶颈也会因输入数据的差异而转变,所以不要忽略测试,并自己准备好最合理的测试数据。

关于这一点,也有不少感触,用一开始提供的样本数据,同最后公测的数据测试一比,发现瓶颈完全转变了,所以记得多用不同的数据测测,并按重要程度做优化。

(8) 当你需要频繁申请、释放内存的时候,可以考虑开辟一个内存池统一申请和释放内存,因为频繁的new,delete也会花你很多时间,当然,前提还是你的程序是在ms级别上的优化。


三:其它感悟

(1)    公司能多举办这类比赛,确实能激发员工的活力,像我以前对图形学,空间划分,OpenMP这些知识一无所知,在短短数十天时间就接触了大量相关知识并做优化,可以说能很大激发一个人的潜力,这让我感觉特别刺激:)。

(2)    从应用OpenMP这个线程库来看,其优点很明显,结构化特性很强,但缺点也明显,不适合开发大型程序,只能做局部优化,后面我会再去研究一下TBB怎么用,待研究过几套已有的线程库之后,我想用ACE和Loki两个C++库来实现一个类似于OpenMP功能的线程库,需要让它能适应大规模程序开发。

补充:我想实现的仅仅是OpenMP中我认为最有价值的那一部分(每个人的看法可能不同),即OpenMP在编译期可以十分方便的指定不同程序段是采用并行还是串行的方式执行。其它繁杂的功能并非我能力所及。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7364811/viewspace-663188/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2010-05-20

  • 博文量
    7
  • 访问量
    17964