1.2.2 Mandelbrot集

接下来，我们介绍一个非常经典的并行计算的例子，并且将在本书中多次用到这个例子—— 一个生成Mandelbrot集图形的算法。首先，让我们来定义Mandelbrot集。

对于给定的复数c，当时，我们可以定义这样一个递归序列，其中，而时，该序列可以表示为。如果n增加到无穷大，仍然以2为界，就说c是Mandelbrot集的元素。

回想一下，我们可以将复数表示在二维笛卡儿平面上，其中x轴表示实数分量，y轴表示虚数分量。因此，我们可以很容易地用一个令人印象深刻的（也是众所周知的）图形来可视化Mandelbrot集。这里，我们将在复笛卡儿平面上用较浅的阴影表示Mandelbrot集的元素，用较深的阴影表示不属于Mandelbrot集的元素，具体如图1-1所示。

图1-1

现在，让我们考虑一下如何用Python代码来生成Mandelbrot集。因为我们不可能检查每一个复数是否属于Mandelbrot集，所以必须选择检查的范围。同时，我们必须确定需要检查每个范围（由width、height确定）中的多少个点，还要在检查|z_n|时，确定n的最大值（max_iters）。接下来，我们将编写一个函数，用它来生成Mandelbrot集的图形——就本例来说，我们通过连续迭代图形中的每一个点来完成该任务。

首先，我们需要导入NumPy库，它是本书中经常用到的一个数值运算库。具体来说，这里的功能是通过simple_mandelbrot函数实现的。我们先用NumPy的linspace函数生成一个充当离散复平面的网格（下面的代码应该是相当简单的）：

import numpy as np

def simple_mandelbrot(width, height, real_low, real_high, imag_low,
imag_high, max_iters):
     real_vals = np.linspace(real_low, real_high, width)
     imag_vals = np.linspace(imag_low, imag_high, height)
     # we will represent members as 1, non-members as 0.
     mandelbrot_graph = np.ones((height,width), dtype=np.float32)
     for x in range(width):
         for y in range(height):
             c = np.complex64( real_vals[x] + imag_vals[y] * 1j )
             z = np.complex64(0)
             for i in range(max_iters):
                 z = z**2 + c
                 if(np.abs(z) > 2):
                     mandelbrot_graph[y,x] = 0
                     break
     return mandelbrot_graph

我们要添加一些代码，以便将Mandelbrot集的图形转储到一个PNG格式的文件中。为此，首先需要导入相应的库：

from time import time
import matplotlib
# the following will prevent the figure from popping up
matplotlib.use('Agg')
from matplotlib import pyplot as plt

现在，让我们添加一些代码来生成Mandelbrot集，将其图形转储到一个文件中，并使用time函数对两个操作进行计时：

if __name__ == '__main__':
     t1 = time()
     mandel = simple_mandelbrot(512,512,-2,2,-2,2,256, 2)
     t2 = time()
     mandel_time = t2 - t1
     t1 = time()
     fig = plt.figure(1)
     plt.imshow(mandel, extent=(-2, 2, -2, 2))
     plt.savefig('mandelbrot.jpg', dpi=fig.dpi)
     t2 = time()
     dump_time = t2 - t1
     print 'It took {} seconds to calculate the Mandelbrot
graph.'.format(mandel_time)
     print 'It took {} seconds to dump the image.'.format(dump_time)

现在，让我们运行这个程序（该程序也可以从本书配套资源的文件夹1下面的Mandelbrot0.py文件中找到），如图1-2所示。

图1-2

可以看到，生成Mandelbrot集耗时约14.62秒，转储图形耗时约0.11秒。我们是以逐点方式生成Mandelbrot集的。不同点的坐标值之间并不存在依赖关系，因此生成Mandelbrot集实际上就是一个可并行操作。相比之下，转储图形的代码则无法并行化。

现在，让我们用阿姆达尔定律来分析一下。就本例来说，如果将相应的代码并行化，我们可以得到多大的加速比？如上所述，该程序的两个部分总共用时约14.73秒。我们可以并行化生成Mandelbrot集的代码，也就是说，可并行化的那部分代码的执行时间占比为p=14.62/14.73≈0.99。因此，这个程序可并行化比例约为99%！

那么，我们可以获得多大的加速比呢？笔者目前用的是一台拥有640个内核的GTX 1050的笔记本电脑，使用阿姆达尔定律时，N将是640。所以，计算加速比的公式为

这个加速比的值无疑是非常好的，足以表明将算法并行化到GPU上的努力是非常值得的。记住，阿姆达尔定律只是给出了一个非常粗略的估计值！将计算任务转移到GPU上时，我们还要考虑其他因素，比如在CPU和GPU之间发送和接收数据所需的额外时间，或者转移到GPU上的算法只能部分并行，等等。