avatar

Derek Zeng

A programmer

小结优化

by coderek

貌似这学期所做的事情都是围绕优化这个问题来进行的。那我就来总结一些我接触的优化方式吧。这些优化方式都是从具体的事物上产生,但都可以抽象化到很多地方。

Hierarchical Structure

这个主要说的是事物组织的方式。如果是有等级划分,从大到小,从粗到细,从高到低的话,一个复杂的事物就可以运行的井井有条,这主要要归功于高效的检索。比如说,用Binary Partition Subdivision 做occlusion culling, 如果上面的node 不可见那么下面的node就不用再看了,这样一下子就可以省掉很多多余的运算,很快就能找到哪些是可见的多边形。其实这里的高效是利用了Binary Tree的高效,类似的有Quad Tree和Oct Tree.

Pre-Computation

把所有可以预先计算的东西全都在线下算好,然后在运行程序的时候就可以直接拿来用。这种思想使得很多复杂的东西都可以实时表现出来,比如说3D动画。那些灯光效果可能是用渲染农场渲染了好几天才完成的,放映出来却也就只有好几十秒的事情。但效果是相当的逼真。所以预先计算应该是提高性能所必需的。

Data Compression

现在的电脑磁盘大到不行了,但有一个问题是传输速度还是很慢,一般的就只有20多MB/秒。所以这是一个瓶颈问题。类似的问题还有网络带宽,特别是手机无线网络。解决这些问题的方法可以是将所需要的数据压缩。具体用什么样的方法,格式压缩,需不需要加密的问题就要因人而异了。Quake 的一个一般大的地图,几千个多边形,用run-length compression之后的Bit-Array PVS只有不到3MB。简单的加密可以是xor如果要安全点就要更麻烦了。

Perception-based/Interest Set

这些看起来可能只适合游戏,因为对于一些可信度高的应用来说,是不能对用户的perception也就是感知作出一些假设的。但这里所说的意思其实是,如果有太多的信息,我们是没有必要把所以信息都表现出来,因为用户不能一下子把所有东西都看到。这里其实包含这比较多的UI设计,如果是做应用软件。好的UI设计也是可以很好的减小计算量,而这些在手机上尤为重要。

Adaptive/Progressive

如果一下子不能把想要的东西计算出来,可以先大概的预计一下,勾勒出一个框架,然后再在之前框架的基础上重复计算。之所以要把这个框架先表现出来给用户看,一是可以让他很快的了解结果,二是如果他从框架很明显看出趋势不对得不到想要的结果,就可以直接取消计算,节省资源。比如在radiosity里面使用的Jacobian iteration 每一个轮回都比前一个要更靠近真实值。

Fast Memory

CUDA里面对于不同层次内存的使用是非常讲究的。但一般是速度快的内存都有这样那样的局限比如小或者是只读,所以如何有效的分配内存是一项很深的技术。需要对系统的深入了解,比如BUS 宽度,数据宽度,有几个计算核,每个核的分配是怎样的。如果内存分配恰当,是可以达到几十,几百倍的提速。

Approximation

有时有些问题很难甚至无法解决,我们需要用估算来求出一个大概的答案。估算不是准确的答案,但近似于准确。它不需要很多资源来创造,是很多学术上解决问题的一个方法。

(End of article)