Mandelbrot集(5)：硬件升级，算法优化：一切为了速度！
（yanlb2000, 2007.05.14, yanlb2000.blogcn.com）
上文，我简要分析了一下绘制Mandelbrot集的算法。提到，这个算法，主要可以归结为两个特点：浮点数密集型算法；适合编制为高度的并行运算。
以上分析的目的也是很明确的，就是要优化算法，提高绘制M集的速度。
这几年来，电脑绘制M集的速度的确有了飞速的发展。总结下来，大致可归结为几种类型方面的进步：有的纯粹是硬件运算能力的提高，有的是硬件能力和软件优化的配合，还有就是纯算法方面的优化。
·当初我是在286上绘制M集图像的。80286是个16位的CPU，主频一般是12MHz到24MHz，只能进行整数运算，因为标配是没有数学协处理器的。而所有的浮点运算，都是通过软件来实现的。主频本来就低，又没有硬件级别的浮点数运算，所以，速度慢是必然的。记得当时画一个M集，640*480的分辨率，迭代限制为256次，居然需要约2个小时。所以，我们只能等待更快的CPU的出现。
·此后的若干年，CPU严格遵循着摩尔定律发展着，386，486，Pentium, Pentium II, III, IV等相继问世，主频也一路高升，超过了几百MHz，达到了3GHz甚至更高。
而从80386DX开始，及以后所有型号x86系列，CPU就内置数学协处理器了。数学协处理器对M集算法的重要性是不言而喻的。
因此，单是主频的提升，以及硬件级的浮点数运算能力，就让该算法的实现速度大大提升了。
这些完全是硬件方面的进步。
·1996年左右，Intel推出了带MMX扩展的Pentium处理器。MMX即是多媒体扩展，能够在同一个指令中，并行处理多个数据。这是Intel针对当时大量出现的图像、声音密集型应用而设计的。其实从技术上说，这应属于原来大型系统CPU中才有的并行运算技术SIMD(Single Instruction Multiple Data)，只是因为集成电路的迅猛发展，能够在民用CPU上实现了。
我当时就发觉，这对M集绘制算法是有很大的意义的。不过遗憾的是，MMX只对整形数提供了并行支持，不支持浮点数。但，这毕竟是一个方向，我相信对浮点数的SIMD的支持也会实现的。
果然，Intel随后在Pentium III等CPU中实现了SSE技术，能够提供对浮点数的并行运算。随着CPU的发展，更完善的SSE2， SSE3等指令集也相继出现。
M集算法中，每个点的运算过程都是完全相同而且互不干扰的，所以，这特别适宜于通过SSE指令来实现。当然，真正要发挥SSE的威力，还需要程序语言、编译器甚至操作系统等的支持和配合才行。
·当奔腾升级到Pentium IV，主频上升到3GHz多接近4GHz的时候，无论是Intel还是AMD，都遇到了频率的瓶颈。CPU的主频已经很难象以前那样容易提升了。此后，CPU主要向着多核的方向发展，一个CPU封装中，有多个物理CPU核心。这样，电脑就可同时执行多个线程或进程，达到真正的并行处理。这种硬件进步，对M集算法也是有直接好处的。算法可以将绘制区域分块，交给多个线程，在多个CPU核心上并行处理。
当然，实现多核运算，也必须要编程语言、编译器、操作系统的支持。
这里，需要说明一下多核运算和上面SSE指令运算的异同。它们都是通过并行执行多个运算，来达到提升总体运算速度的目的。但在实现上是有区别的。
多核CPU简单地说就是一个电脑中就安装了多个物理的CPU核心，多个核心并行工作。根据算法特点，这些核心可以不同步，甚至执行其他程序指令。
而以上SSE指令则是在同一个CPU核心中，通过调用一条运算指令，就对多个数据同时进行运算。执行的是相同的一条指令。这，也正是将SSE归结为SIMD(Single Instruction Multiple Data，单指令多重数据)的原因。
而且，以上两种并行优化方式互不影响，可以同时叠加进行！
上面说的是硬件方面的提升和优化。再来看看纯软件算法方面，是否有可改进的地方。
·观察M集全图，并仔细考察算法，可以发现，当对M集内部的那些区域（集图像中心黑色葫芦形部分）进行计算的时候，每个绘图点所需的运算时间是最长的。因为，无论进行多少次迭代，都不能达到绝对值超出限定值的这个“溢出”条件，所以，总会进行“满负荷”的运算。而显然，最后的结果总是相同的，因为都是M集，所以，它们都属于同一种颜色（一般都画为黑色）。
所以，我们完全有理由对该区域进行优化。我们可以设定一个保守的M集区域。为简化算法，这可以是一个由几个矩形组合成的区域。每次运算的时候，先判断该绘图点是否属于该区域，如果是，则不进入迭代运算，而直接给出属于M集的结果。这样，就避免了大量的浮点运算。我那时在286上的Turbo C程序，就进行了这种优化，的确是大大缩短了绘图时间。
不过，设定这个优化区，是需要非常小心的，不能因为贪图更多的优化而靠边缘太近，否则一些本该有图案的地方会“黑”掉。
·优化无止境，我们进一步讨论。
当画好一副M集图像之后，我们往往希望能够“深入”其中的一些局部，放大观察。而且，最好是类似“漫游”一样，实时动画显示，能够平滑地实现放大、移动等动画过程。这一定是个美妙的过程。显然，为了达到实时动画显示的效果，我们至少需要每秒十几或最好二十多个画面的刷新率(fps)。（作为参考，NTSC电视画面是每秒30帧，PAL电视画面是每秒25帧。）而即使是现在的CPU，要达到每秒算出几十个画面的M集，还是有困难的。所以，必须大幅度优化。
考察动画过程，相邻两个画面，其实大部分是相同的，只是区域增大或减少了一小部分。所以，可以考虑保留上个画面中的大部分计算结果，而只对放大或缩小的部分进行运算，将得到的结果，与上个画面的结果进行插值运算，修正之后，就可以得到一个新的画面了。
说详细一点，举个例子。比如，放大一个640*480的画面，假设其下一个画面，只保留了原画面中间的部分，上、下、左、右的各2行都将被“放大”到屏幕外。这样，原中间的636*476将被放大到640*480。所以，只需要计算新“扩展出”的大致4行4列的绘图区域的值，再将它们均匀插值到剩下的636*476中就可以了。
这其实不是一个“不失真”的优化算法，因为这与混沌的初始值敏感的特性是背道而驰的。一个绘图点的值，通过上述优化计算得到的结果，可能与真正计算的有出入，甚至较大的出入。但实际上，只要设计得好，这种误差是可以保持在一个很小级别内的。
但单单通过这种优化，我们就可以获得极大的速度提升，我们可以将运算量降低大致2个数量级，这是非常可观的！
最后，再谈谈绘图输出的问题。M集计算之后，还需要通过绘图设备画出来。最普通最方便的方法，当然就是在显示器上画出来（废话！）。但这里也是有讲究的。当绘制一个大画面或全屏幕画面的时候，像素点达到了几十万或几百万，这也不得不涉及到速度问题。如果使用传统的Windows GDI作图方式，那是非常低效的。画单个静态画面还勉强能胜任，但如果需要达到上面所说的实时动画绘图，GDI是达不到要求的。好在，自从Windows 9x之后，微软就一直在发展DirectX规范，包括能绕过低效的GDI，直接访问显示卡绘图能力的DirectDraw，DirectGraphic。这样，实时绘图输出也就不是问题了。
Tags: Mandelbrot, 分形, 混沌, 算法
