第二章 性能语言

性能分析

编写并行程序的原因只有两个: 用较少的时间解决一个固定大小的问题,或者 用合理的时间解决一个较大的问题. 无论上述哪种情况都是为了提高性能.OpenMP是一种用于编写并行程序设计的编程语言.在某种层面上,它总是要回到性能上.

性能的原始评判标准是以时间为基础的.但即使是时间这个词也有多种定义.

CPU时间: CPU频率*CPU在执行程序时消耗的周期数.

墙钟时间: 由计算机外部时钟测量的时间.

每秒执行浮点运算数(FLOPS): 高性能计算(HPC)在很大程度上是以浮点数的运算为中心的.因此我们常常使用墙钟时间一秒钟内可以完成的浮点运算来考虑性能.
FLOPS上可以加上相应的前缀,如:Mega($10^6$),Giga($109$),Tera($10^{{12}$),Peta($10}$).
与FLOPS的定义类似的,还有 每秒执行的操作(OPS) 或 每秒执行的指令(IPS) 等.

加速比S(P): 加速比是一个程序运行时间的比率.理想情况下,在一个处理器上用可获得的最好串行算法运行一个程序,然后用并行软件在P个处理器上再次运行它.
如果定义$T_S$为串行程序的运行时间,定义$T_P$为在P个处理器上的并行程序的运行时间,那么加速比的定义为:
$$S(P)=\dfrac{T_S}{T_P}$$

在理想的情况下,加速比等于处理器的数量.

并行效率eff: 用于衡量可缩放的加速比与完美线性加速比接近程度的量.
$$eff=\dfrac{S(P)}{P}$$

阿姆达尔定律

阿姆达尔定律: 假设一个程序有一个占比为$\alpha$的工作,这部分是串行了.我们称$\alpha$为串行比例.如果$\alpha$是一个问题的串行比例,那么$1-\alpha$就是并行比例.令串行代码运行时间为$T_S$,则使用P个处理器的并行代码的运行时间为$T_P$.有:
$$T_P=\alpha\times T_S+(1-\alpha)\times\dfrac{T_S}{P}$$
则加速比为:
$$Speedup=\dfrac{T_S}{T_P}=\dfrac{1}{\alpha+\dfrac{1-\alpha}{P}}$$
当P趋近于无穷大时,该加速比揭示了并行优化的最好性能:
$$\lim\limits_{P\to\infty}Speedup=\dfrac{1}{\alpha}$$

例:已知算法可以为程序提速95%,求最佳加速比?
由程序提速95%,有串行比例$\alpha$=0.05.
代入$\lim\limits_{P\to\infty}Speedup=\dfrac{1}{\alpha}$,则最佳加速比为20.

由于算法的限制,阿姆达尔定律限制了并行的收益.而 并行开销 是指管理并行应用程序中的线程所花费的时间.并行开销的来源是管理数据.

为了体现这一开销的威力,给出 考虑并行开销的阿姆达尔定律 为:
$$T_P=(\alpha+\gamma\times P)\times T_S+(1-\alpha)\times\dfrac{T_S}{P}$$

其中,我们将开销建模为一个按P缩放的小常数$\gamma$,随着处理器的增加,并行开销会增长,最终以比阿姆达尔定律限制所建议的更极端的速度将这个数字向下拉.

强扩展: 一个固定规模的问题,性能随着处理器数量增加而变化.

弱扩展: 每个处理器的工作两个是固定的,随着处理器的增加,整个问题的大小也在增加.

阿姆达尔定律从另一个角度说明了这样一个问题: 强扩展难以持续.

如果串行比例$\alpha$是有关问题大小N的递减函数,则加速比将成为P与N的函数:

$$Speedup(P,N)=\dfrac{T_S}{T_P}=\dfrac{T_S}{\alpha(N)+\dfrac{P}{1-\alpha(N)}T_S}$$

负载均衡

我们可以把程序定义的工作看做是程序所执行的全部操作.当我们创建一个并行版本的程序时,我们将工作分成若干块,并将这些块分配给线程去执行.如果有多个处理器使得线程可以同时执行,我们就会以并行的方式进行工作以减少程序的整体执行时间. 当并行程序的最后一个线程完成时,它才算完成.

因此,我们设计一个并行程序的目标是让所有线程在同一时间完成,这意味着我们期望它们都有相同的工作量.如果把工作看成是给线程施加负载,我们说作为算法设计者的工作就是"均衡线程之间的负载".

为了分析程序的负载均衡,我们将它们分为两对对立项:

• 显式与自动: 是由程序员计算出一个固定的公式来生成负载均衡,还是在计算过程中自动出现负载均衡?

• 静态与动态: 工作的分解和安排执行的方式在编译时是固定的吗?还是在程序运行时动态发生的?

针对这两对对立项,可以组合出四种不同的组合:

• 显式,静态: 程序根据程序中的逻辑来定义分块,这些表达式在编译时是固定的.

• 显式,动态: 程序代码中写下了决定工作分配方式的逻辑,但程序运行时它时常重新动态审视该逻辑以重新分配负载.

• 自动,动态: 程序创建了一系列快,并把他们放在一个队列中.线程抓住一个工作快,完成它后回到队列.

• 自动,静态: 静态负载均衡策略的本质是在工作开始前,工作分布就固定了.

roofline模型

屋顶线性能模型(Roofline Performance Model) :用于分析模型在特定计算平台上所能达到的理论计算性能上限的模型.

计算量: 针对单个输入,模型完成一次完整的向前传播所发生的浮点运算个数.

访存量: 针对单个输入,模型完成一次完整的向前传播所发生的内存交换总量,也即模型的空间复杂度.

计算强度(Computational intensity): 表示每Byte内存交换到底用于多少次浮点运算,计算强度越大,内存使用效率越高.指程序执行的浮点运算次数与支持这些运算所需的数据移动的比率.

算力(Execution unit,max performance): 计算平台每秒能完成的浮点运算数上限.

带宽(Data path,bandwidth): 计算平台每秒能完成的内存交换量上限.