一、 可扩展性基本概念

1.可扩展性与可编程性

（只能说理想很美满，现实只能在增加可扩展性和增加可编程性，选其中一个）

2.可扩展性指标（相关参数）

机器规模（n）     

时钟频率（f）     

问题规模（s）     

CPU时间（T）     

I/O需求（d）   

存储容量（m）     

通信开销（h）     

计算机价格（c）     

程序设计开销（p）

3.可扩展性的直观定义

直观定义：对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率 E = 1， 则系统是可扩展的。

定义1：在给定的一台并行系统上运行一个给定的应用问题（并行算法）时，如果随并行系统规模增大而适当增加问题的规模，使并行系统的性能与其规模成线性比例增长，则称并行系统是可扩展的。

定义2：运行于一台给定的并行系统上的并行算法（并行应用程序），当系统的规模与算法的规模按比例增加时，其性能也按一定的比例提高，则该并行算法（并行应用程序）是可扩展的。

4.可扩展性的研究目的

1)确定某类问题的何种并行算法与何种并行系统的组合，可有效的利用系统大量处理机;

2)有算法在小规模并行机上的运行性能来预测起移植到大规模并行机上后的运行性能;

3)对一固定规模的问题，能确定起运行在某类并行系统上时，所需的最有处理机台数和获得的最大加速比。

4)指导并行算法和并行机体系结构的改进

二、可扩展性度量方法

1、等效率可扩展性度量方法：揭示问题规模与系统规模的关系（1987）；

效率是指系统规模p增加时，测量增加多少运算量（问题的规模w）会保持并行算法效率不变。

：并行机上的每个基本操作的平均时间；

（p，w）：并行计算时系统的总开销；

:算法的串行执行时间。

2、等速度可扩展性度量方法：揭示并行算法-机器组合的关系（1996）

3、等时间/通信开销比的可扩展性度量方法：等计算时间/通信开销比（1999）

可扩展性度量方法的基本要求：

1）能提供并行系统规模的变化如何影响起性能的信息；

2）能描述并行算法与并行机组合的函数；

3）可评估、可比较的定性性能度量方法。

三、可扩展性

1.恒等效率概念（Isoefficiency）

恒等效率定义为一个并行算法在并行计算机上实现时，为保持效率E固定所需的工作负载与机器规模n的相对关系。

假设:W = W（s）为工作负载，h  =  h （s，n）为通信开销，它随s、n增加而增大。其中，s为问题规模，n为机器规模。

则效率可以表示为：

问题的关键在于W（s）与h（s，n）之间的相对增长速度。机器规模一定，开销h的增长比工作负载W要慢。因而，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假若工作负载W随机器规模适当增加，那么就有希望保持效率不变。

对于已知的算法来说，为了保持恒定的效率，工作负载W可能需要对n以多项式或指数规律增长。不同的算法可能需要不同的工作负载增长速率以便在n增加时保持效率不致下降。

一般并行算法的恒定效率函数是n的多项式函数，即它们为0（nk），k >=1。n的幂越小，并行系统的可扩展性越大（系统包括算法和结构的组合）。

2.恒等效率函数

并行程序执行时间 Tp = (T1+T0)/p，其中，T1为总工作负载串行执行时间，T0为多节点总通信延时，p为节点数。

那么，加速比为：

而T1 = W ，W为以操作次数计算的总工作负载，为每个操作的平均执行时间。

如前面所述，工作负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下：

为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以下条件：

如果工作负载W(s)与(n)一样快的增长，那么已知算法结构组合就能使效率保持恒定。这个结论和前面的结论是一致的。

此时， W(s)与(n)是相同的，只要求出了W(s)的数量级，就可知道(n)了。为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。