第二章性能评测

1第二章 性能评测2.1引言2.1.1 什么是并行机的基本性能2.1.2 为什么要研究并行机的性能评测2.1.3 如何评测并行机的性能2.2机器级性能评测2.2.1CPU 和存储器的某些基本性能指标2.2.2 并行和通信开销2.2.3 并行机的可用性与好用性2.2.4 机器的成本、价格与性 / 价比2.3算法级性能评测2.3.1 加速比性能定律2.3.2 可扩放性评测标准2.4程序级性能评测2.4.1 基准测试程序的分类2.4.2 基本基准测试程序2.4.3 并行基准测试程序2.4.4 商用基准测试程序2.4.5 SPEC 基准测试程序*2.5如何提高性能2.5.1 任务划分2.5.2 通信分析2.5.3 任务组合2.5.4 处理器映射2.5.5 任务调度2.6小结习题参考文献第二章 性能评测本章首先简单介绍一下什么是并行计算机的基本性能?为什么要研究机器的性能评测以及如何评测计算机的性能？然后，分别讨论机器级的性能评测，包括 CPU 和存储器的某些基 本性能指标，并行和通信开销以及机器的成本、价格与性/ 价比；算法级的性能评测，包括加速、效率和可扩放性等； 程序级的性能评测， 包括基本基准测试程序， 并行基准测试程序， 商用基准测试程序以及 SPEC 基准测试程序等；最后，从任务划分、通信分析、任务组合和 处理器映射等算法和程序设计的四个步骤，简要地讨论了如何提高并行系统的性能。2.1 引言了解和使用并行机， 自然要知道并行机的性能， 就普通意义上讲， 它就是并行机的好与 不好。所以本节首先就从这些简单内容讲起,包括什么是并行机的基本性能 ,为什么需要评测2机器的性能以及如何评测并行机性能。32.1.1 什么是并行机的基本性能所谓机器的性能(Performanee)通常是指机器的速度，它是程序执行时间的倒数。而程序执 行时间是指用户向计算机送入一个任务后，直到获得他需要的结果这一段等待时间，包括访问磁盘和访问存储器的时间，CPU 运算时间,I/O 动作时间以及操作系统的开销时间等。但在多 任务系统中,CPU 在等待 I/O 操作的同时可以转去处理另一个任务，这样分析起来就比较麻烦。所以在讨论性能时，有时也使用 CPUCPU 时间，它表示 CPU 的工作时间，不包括 I/O 等待时 间和运行其它任务的时间。很显然，用户所看到的执行时间是程序结束时所花费的全部时间 而不单是 CPU时间。1.单 CPL 性能TC，程序中指令总条数为 IN,执行每条指令所需的 平均时钟周期TCPU=INXCPIXTC其中,上式中 n 为程序中所有指令种类数。令 Ii/In表示第i种指令在程序中所占的比例，则上式可改写为:2. MIPS 禾口 MFLOPS已如上述，执行时间的倒数就是速度。速度通常可用MIPS(Million Instructions Per Second )表示，即每秒百万条指令，它很适合于评测标量机。对于一个给定的程序,MIPS 可表示为：6 6 6MIPS = IN/ (TEX10 )= RC/ (CPIX10 )=IN/( INXCPIXTCX10 )(2.4)其中，TE表示程序执行时间,Rc表示时钟速率，它是 TC的倒数。有时还用相对MIPSRel这一标准，此时需要事先选择一个参照的计算机性能，然后与其比较：MIPSRel=(TRef/ TV) XMIPSRef(2.5)其中,TRef表示在参照机上程序的执行时间,Tv表示相同程序在要评价机器上的执行时间,MIPSRef表示所约定的参照机的MIPS。在 80 年代，常以 DEC 公司的 VAX-11/780 作为参照机，称为 1 MIPS 机器。MFLOPS ( Millio n Floati ng Poi nt Operatio ns Per Seco nd )常用来评价向量计算机的性能， 表示假定机器的时钟周期为数为 CPI,则一个程序在CPU 上运行的时间 TCPU为:(2.1)CPI执行整个程序所需的时 钟周期数程序中指令总数 CPIiIiid(2.2)CPIi(2.3)4每秒百万次浮点运算：6MFLOPS =IFN/( TEX10 )(2.6)其中,IFN表示程序中的浮点运算次数。通常 MFLOPS 与 MIPS 之间无统一标准的量值关系。一般认为在标量计算机中执行一次 浮点运算平均需要 3 条指令，故有 1MFLOPS 约为 3MIPS 之说。3.并行机的基本性能指标并行计算机的基本性能参数可概括于表2.1 中。表 2.1 并行机基本性能参数一览表名称符号含意单位机器规模n处理器的数目无量纲时钟速率f时钟周期长度的倒数MHZ工作负载W计算操作的数目Mflop顺序执行时间T1程序在单处理机上的运行时间s （秒）并行执行时间Tn程序在并行机上的运行时间s （秒）速度Rn= W/Tn每秒百万次浮点运算Mflop/s加速Sn=T1/Tnr衡量并行机有多快r 无量纲效率En= Sn/n衡量处理器的利用率无量纲峰值速度Rpeak= n Rpeak所有处理器峰值速度之积，Rpeak为一个处理器的峰值速度Mflop/s利用率U =Rn/Rpeak可达速度与峰值速度之比P 无量纲通信延迟to传送 0-字节或单字的时间Ms渐近带宽roo传送长消息通信速率MB/s2.1.2 为什么要研究并行机的性能评测当今，计算机的性能评价与测试是一个正在研究中的课题，它与计算机体系结构，计算机软件,计算机算法共同构成了新兴的 计算科学(Computational Sciences)的四大支柱。并行计算机 系统远比单处理机系统复杂得多，所以为了更好地用好并行机，充分发挥其长处，以适应不同 应用问题的需求，评价与测试并行计算机的多种性能是非常必要的。1.发挥并行机长处，提高并行机的使用效率通过对不同并行计算机的性能进行测试，可以评价其优、缺点。根据它们的特点，对口相应的应用领域，充分发挥其长处，以提高并行计算机的使用效率。例如，通过测试 CPU 性能可 以为计算密集(Compute -ntensive)型应用问题建议较合适的并行机；通过测试网络性能， 可以为网络密集(Network-Intensive)型应用问题建议较适宜的并行机；通过对存储器和I/O通道性能的评试，可以为数据密集(Data-Intensive)型应用问题建议较满意的并行机等。52.减少用户购机盲目性，降低投资风险对于某一特定用户而言，并非购买越贵的机器越好。应该根据自己的计算问题特点，通过使用基准测试程序(见本章 2.4 节)所得到的一些结果数据，来帮助你决策购买何种并行计算机。并行计算机一般都很贵 ,一旦所购买的计算机在具体的应用中不能发挥应有的作用,那将是莫大的浪费。一般而言 ,用户大都不是并行计算机方面的专家,为减少购买并行机的投资风险 ,通过各种性能评测手段来最大限度地减少引进和购买并行计算机的盲目性是非常 重要的。3.改进系统结构设计，提高机器的性能并行计算机是个庞大复杂的系统， 即使具有丰富设计经验的人员， 也很难保证所设计出的 计算机系统十全十美。任何成功的设计都不可能一次完成，总是通过测试试用，不断修改、补充以臻完善。其中 ,按照性能测试所产生的测试结果比较全面,能够暴露设计中的一些问题这些问题对计算机设计者具有比较大的指导意义,针对这些问题改进现有的设计 ,可进一步提高计算机的性能 ,以适应各方面的应用需求。4. 促进软/ 硬件结合，合理功能划分根据对计算机性能的实际测试和统计分析 ,可以明确计算机所应完成的软件与硬件职能， 合理的功能划分以及适当的软 /硬件折衷。对于那些使用频繁、功能较简单的操作,在硬件工艺许可的情况下 ,当以硬件实现之；而对于那些不常使用、功能又较复杂的操作,在软件复杂度允许的情况下 ,当以软件代替之。这些常识范围内的知识,必须建立在对计算机的性能进行全面地测试和客观地分析的基础上。特别是在技术工艺水平不断提高,器件成本不断下降的今天 ,计算机软件功能硬化的趋势似乎越来越明显。5. 优化 “结构-算法-应用”的最佳组合通过对计算机性能的评测 ,可以发现什么类型的体系结构比较适合于什么类型的问题求解 算法；哪一类体系结构对哪一类应用问题比较有效； 某类算法比较适合于求解某类应用问题。 例如，网孔连接 的并行机结构比较适合于 矩阵运算 之类的算法； 树连接 的并行结构比较适合 于与数据库有关的一类应用问题； 数字滤波 这一类的算法是数字信号处理应用中经常使用的 算法。 当通过性能评测得出上述结论后， 我们就可针对某类应用问题， 设计出可以高效运行 某种体系结构上的算法了。6.提供客观、公正的评价并行机的标准不同的用户（包括机器的系统操作员） ，会从不同的角度来评价并行机的性能优劣。研 究并行机的性能评测的根本目的之一， 就是要试图提供一个统一的、 客观的、 公正的和可相 互比较的评价并行计算机的标准。为此就要从并行机的硬件体系、 软件功能、解题能力、使 用目的和测试手段等各个方面来评测并行计算机的性能。62.1.3如何评测并行机的性能怎样评测一台计算机的性能， 与测试者的出发点有关。 例如，计算机用户说机器很快，往 往是因为程序运行时间短； 而计算机管理员说机器很快， 往往是因为在一段时间内它能够完 成更多的任务。用户所关心的是从提交任务开始到运行结束之间的时间，即执行时间；而管理员所关心的是在单位时间能完成的工作量， 即吞吐率 （Throughput） 。所以，如何客观、 公正地评价计算机的性能不是一件容易的事,要涉及到计算机系统的诸多因素,它不仅与机器硬件速度有关 ,而且还与机器体系结构、计算方法与算法、程序编译优化、编程工具与环境,甚至与测试方法手段等有关。本节试图根据机器性能评测的层次,分别从机器级、 算法级和程序级三个层次来研究它们。请注意这种分层也只是为了讨论的方便。1. 机器级的性能评测机器级的性能评测，包括 CPU 和存储器的某些基本性能指标；并行和通信开销分析；并 行机的可用性与好用性以及机器成本、价格与性/价比等。它们中的有些是由机器厂商在销售时直接提供给用户的 ,是广大用户对并行计算机的第一印象,是引进和购买并行计算机时最主要的选择依据 ,特别是机器的基本性能指标和机器的价格是诸多并行机之间最可比的数据,也是非计算机专业用户选购并行机时决策的主要依据。2. 算法级的性能评测算法级的性能评测方法 ,最初大都是为了评价并行算法的性能提出的,后来这些评测方法也被推广到并行程序上。众所周知,在并行机上进行计算的主要目的就是要加速整个计算过程,所以研究并行算法的 加速 （比）性能是最根本的。 它体现了对于一个给定的应用 ,并行算法相对 于串行算法的执行速度加快了多少倍。此外，随着计算负载的增加和机器规模的扩大,研究并行算法的性能是否能随着处理器数目的增加而按比例的增加也是很主要的 ,这就是所谓的 并行算法的可扩放性 （Scalability） 问题。由于可扩放性是个很主要的概念， 所以后来推而广之， 就出现了诸如程序的可扩放性、 体系结构的可扩放性、 工艺技术的可扩放性以及应用的可扩 放性等等。3. 程序级的性能评测程序级的性能评测主要是使用一组 基准测试程序（Benchmark）测试和评价计算机系统的 各种性能。不同的基准测试程序，侧重目的也有所不同，但任何一组测试程序均要提供一组 控制测试条件、步骤、规则说明，包括测试平台环境、输入数据、输出结果和性能指标等。我们在第2.4 节将要详细讨论综合测试程序（如 Whetstone, Dhrystone 等），数学库测试程 序（如 Linpack , Lapack 等），应用测试程序（如 SPEC ,Splash 等），并行测试程序（如 NPB, Park Bench 等）和商用测试程序 （如 TPC A , TPC-B 等）等。2.2 机器级性能评测本节将有选择地讨论机器级的某些性能评测,主要包括 CPU 和存储器的某些基本性能指7标；并行和通信开销分析；机器的 可用性 （Availability） 和 好用性 （Usability） 以及机器的成本、价格与性 /价比等。2.2.1 CPU 和存储器的某些基本性能指标参照表 2.1 中所列出的并行计算机的一些基本性能参数,下面将着重讨论 CPU 和存储器的某些基本性能指标 ,主要包括工作负载、 并行执行时间、 存储器层次结构及其典型性能参数、 存储器带宽估计等。1.CPU 性能（1）工作负载（W）:所谓工作负载（荷），就是计算操作的数目,通常可用执行时间，所执行的 指令数目和所完成的浮点运算数三个物理量来度量它。其中 , 执行时间 ：它可定义为在 特定的计算机系统上的一个给定的应用所占用的总时间，系指应用程序从开始到结束所掠 过的时间（Elapsed Time）,它不只是 CPU 时间,还包括了访问存储器、磁盘、I/O 通道的时间和 OS 开销等。 影响执行时间主要因素有求解应用问题所使用的算法； 输入数据集及 其数据结构；求解问题的硬件平台和操作系统以及所使用的语言、编译/编辑器和二进制代码的库函数等。 浮点运算数：对于大型科学与工程计算问题，使用所执行的浮点运算数目来表示工作负载是很自然的。对于程序中的其它类型的运算，可按如下经验规则折算 成浮点运算（FLOP 数：在运算表达式中的赋值操作、变址计算等均不单独考虑（即它们 被折算成 0 FLOP）;单独赋值操作、加法、减法、乘法、比较、数据类型转换等运算均各 折算成 1FLOP;除法和开平方运算各折算成4 FLOP;正（余）弦、指数类运算各折算成8FLOP 其它类运算，可按其复杂程度，参照上述经验数据进行折算之。注意，在理论分析 时，常常假定各条指令和每个浮点运算均取相同时间，这种均匀一致的速度假定在实际的 计算系统中总是难以成立的。 指令数目：它与机器的指令系统有关。对于任何给定的应 用，它所执行的指令条数就可视为工作负载，常以百万条指令为计算单位，与其相应的速 度单位就是 MIPS（每秒百万条指令）。不过用 MIPS 来表示工作负载时要注意机器实际执行 的指令数不一定就是汇编程序中的指令数；所需执行的指令数目可能是依赖于输入数据值；即使对于固定的输入使用相同的高级语言，执行在 RISC 机器上的指令数通常比在 CISC机器上指令数要多 50%- 150%即使在相同的机器上，使用固定的输入，程序执行的指令 数也会因不同的编译或优化方法而不同；最后，较多的指令数也不一定意味着程序地执行 时间就长。（2）并行执行时间：在无重叠操作的假定下，并行程序的执行时间Tn为：Tn= Tcomput+ Tparo+ Tcomm（2.7）其中，Tcomput为计算时间，Tparo为并行开销时间,Tcomm为相互通信时间。而Tparo包括进 程管理（如进程生成、结束和切换等 ）时间 ,组操作 （如进程组的生成与消亡等 ）时间和进程查寻 （如询问进程的标志、等级、组标志和组大小等）时间；Tcmm包括同步（如路障、锁、临界区、 事件等）时间，通信（如点到点通信、整体通信、读/写共享变量等）时间和聚合操作（如归约、前缀运算等）时间。了解这些额外开销对开发并行程序大有好处：例如，要是并行开8销 Tparo较小，则程序员可使用动态并行程序；否则使用静态并行程序较好，因为进程只在 开始时生成而结束时消灭。又如，如果机器支持路障同步，则可使用同步算法；如果路障操 作太费时，则可使用异步算法。下面让我们使用第一章第1.5中所有介绍的异步 PRAM 模型(即 APRAM )来估计一下并行执行时间 Tn。在 APRAM 模型中，计算系由一系列用同步路障分开的所谓相(Phase)所组成。在每个相内，各个处理器均异步地执行局部计算，每个相中最后一条指令是同步路障指令。假定在第 i 相内计算量(即工作负载)为Wi,计算时间为 Ti(i)。令 DOP ( Degree ofParallelism)表示能够同时执行的最大进程数，称之为并行度。对于 n 个处理器的并行系统，显然 K DOPi max(Tn,T-)(2.12)Brent1 已经证明，不考虑 Tparo和 Tcomm时，满足下式：卫乞Tn乞五(2.13)nn将(2.12)代入(2.13),则有:(2.8)maxn(2.14)92.存储器性能（1）存储器的层次结构：在近代计算机中，为了加快处理器与存储器之间的数据移动，存储器通常按图 1.29 所示的层次结构进行组织。如图2.1 所示，对于每一层均可用三个参数表征之：容量 C C:表示各层的物理存储器件能保存多少字节的数据；延迟 L:表示读取各层物理器件中一个字所需的时间；带宽 B B:表示在 1 秒钟内各层的物理器件中能传送多少个字节。各层存储器及其相应的典型的C、L、B 值示于图 2.1 中。存储器带宽的估算：假定字长为 64 位,即 8 字节。对于 RISC 类型机器中的加法操作,它从寄存器中取 2 个 64 位的字相加后再回送至寄存器。通常RISC 加法指令可在单拍内完成，如果使用 100MHZ 的时钟，那么存储带宽将是 3X8X100X106=2.4GB/S 可见，较快的时钟 和处理器中较高的并行操作，可获得较宽的带宽。图 2.1 各层存储器的典型性能参数2.2.2 并行和通信开销这一节主要讨论由于并行而招致的时间开销Tparo和多进程相互作用所引起的通信开销Tcomm。这两种时间开销均比普通的计算时间要长得多，而且随系统不同而变化很大。例如一个 POWER2 处理器每个时钟周期（15ns）能执行 4 个浮点运算，但生成一个 Unix 进程（1.4 卩 s）可长得足以执行 372000 个浮点运算！通常，这么大的开销主要是由 OS 核和系统软件所造成 的。有了这样的数字印象后，在使用并行和通信操作时就要慎重。1.开销的量化既然这些额外开销如此之大，那么就应该定量化它们。但是，现实情况是计算机厂商们既很 少提供数据，也很少提供开销的估计方法。Hockney23曾针对点到点通信给出了几个有关开销的参数心、m1/2、t0和n0。下面我们将介绍使用测量的方法来量化这些开销参数。开销的 测量与所使用的数据结构、程序语言、通信硬件与协议以及计时方法（挂钟时间或 CPU 时间）等有关。为了获得精确的测量值并非易事，因为绝大多数机器系统只提供粗的时间分辩率（微秒级，甚至毫秒级）;并行机中的各处理器常以异步方式操作，不合公共时钟节拍；测量结果离散性太大，所以比较普遍的方法是采用点到点乒一乓测量法。B=1-32GB/S1-16GB/S1-4GB/S0.4-2GB/S1-16MB/S102.开销的测量对于点到点的通信，测量开销使用使用 乒-乓方法(Ping-Pong Scheme):节点 0 发送 m 个 字节给节点 1;节点 1 从节点 0 接收 m 个字节后，立即将消息发回节点 0。总的时间除以 2, 即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。用乒一乓方式测量延迟的代码段如下：/ *乒一乓法测量延迟的代码段*/forfor i=0 toto Runs 1 dodo /* 发送者 */ ifif (my _noded =0) thenthen temp =second( )/*second()为时标函数 */start _time =sec ond()send an m-byte message to node 1 receive an m-byte message from node 1 en d_time= sec ond() timer_overhead = start_time timer_overhead total_time = end_time-start_time + timer_overhead com muni catio n_timei = total_time/2elseelse ifif (my_node_id = 1) thenthen /* 接收者 */ receive an m-byte message from node 0 send anm-byte message to node 0endifendifendifendifendforendfor乒乓方法可一般化为 热土豆法(Hot-PotatoHot-Potato),也称为救火队法(Fire-BrigadeFire-Brigade ):节点 0 发送 m 个字节点 1,节点 1 在将其发送给接点 2,依此类堆，最后节点 n-1 再将其返回给 节点 0,最后时间再除以 n即可。3.开销的表达式通过测试方法所获得的开销数据，通常有3 种方法进行解释：列表法，绘图法和解析法。其中解析表示法是最通用的。 点到点的通信：Hockney 同对于点到点的通信，给出了如下所示的通信开销t(m)的解析表达式，它是消息长度 m (字节)的线性函数：t (m) = t0+ m / r-(2.15)其中,t。是启动时间(卩 s) ; rg是渐近带宽(MB/S),表示传送无限长的消息时的通信速率。Hockney 也同时引入了两个附加参数：半峰值长度 m/2(字节)，表示达到一半渐近带宽(即no(MB/S),表示短消息带宽。4 个参数 to、r 小 m”2和n0中只有两个是独立的，其它两个可使用如下关系式推导出:t0= m1/2/ rg= 1/n0整体通信：几种典型的整体通信有：播送(Broadcasting):处理器 0 发送 m 个字节给所有的 n 个处理器；收集(Gather):处理 0 接收所有 n 个处理器发来在消息，所以处理 器 0 最终接收了 mn 个字节；散射(Scatter):处理器 0 发送了 m 个字节的不同消息给所有 n 个处理器，因此处理器 0 最终发送了 m n 个字节；全交换(Total Exchange):每个处理器 均彼此相互发送m 个字节的不同消息给对方，所以总通信量为m6 个字节；循环移位L.)所需要的消息长度；特定性能2 -(2.16)11(Circular-shift ):处理器 i 发送 m 个字节给处理器 i+1，处理器 n-1 发送 m 个字节给处理器 0, 所以通信量为 m n 个字节。文献5将公式(2.15)推广之，使得通信开销 T(m ,n)是 m 和 n 的 函数，但 t0与ra只是 n 的函数：T(m ,n) = t0(n)+ m / r-(n)(2.17)同时,他们对 SP2机器所测得的数据进行拟合，推导出如表 2.2 所示的整体通信和路障 同步开销表达式。注意，当超过 256 个处理器时，路障开销为 768 卩 S,等效于执行 768X266=204,288 个浮 点运算。可见只有当大的计算粒度时，才宜于使用路障操作。表 2.2 SP2机器的整体通信和路障同步开销表达式一览表整体通信操作表 达式播送52logn + (0.029log n)m收集/散射(17log n +15) + ( 0.025n-0.02)m全交换1 2980logn + (0.03n.)m循环移位(6logn +60) + (0.003logn + 0.04 )m路障同步94log n + 102.2.3 并行机的可用性与好用性一个优良的并行机系统，除了应具有高的基本性能指标以及低的并行与通信开销外，还应具有可用性(Availability)和好用性(Usability)o其中，可用性是指系统正常运行时间的百分比； 而好用性是指用户使用机器时的感受程度。1.机器的可用性人们常将机器的 可靠性(Reliability),可用性(Availability),与服务性(Serviceability)合在一起 简称为机器的 RAS 性能，但有时候易将它们的概念相混淆。事实上，可靠性是用平均无故障时间 MTTF(Mean Time To Fail)来度量,系指系统失效前平均正常运行的时间；服务性是用平均修复时间 MTTR(Mean Time To Repair)来度量，系指系统失效后修理恢复正常工作的时间； 而可用性被定义为：Availability = MTTF / (MTTF+ MTTR)(2.18)由此可见，增加可用性有两种方法：或增加 MTTF,或减少 MTTR。有很多技术可以改进系 统的可用性，这些内容可以参见本书第六章中6.2.1 节有关内容，在此不再详细讨论。下面将着重讨论好用性问题。2.并行机的好用性因为机器的好用性直接与用户有关，所以机器的好用性的讨论是与并行机系统所提供的 用户环境分12不开的。目前用户使用并行机的环境主要有：远程登录结合命令行： 这是早期并行机典型的用户环境 ,用户通过登录到并行机上 ,再调用系统命令来完成自己的工作。 其 优点是简单、通用 ,只要并行机提供 Telnet 服务既可；而缺点是用户必须熟悉机器的有关命 令,且没有图形用户界面 GUI(Graphic User In terface),所以不够直观。GUIGUI + X X 协议：用户 从客户端直接登录到并行机上 ,利用 X 协议将并行机上的用户 GUI 窗口输送到本地计算机， 从而达到远程使用并行机的目的。其优点是用户远程使用并行机尤如在本地使用并行机一 样，所以很方便；而缺点是由于用户的图形界面是在并行机上实现的，所以占用了宝贵的 并行计算资源。此外，本地机必须支持 X 协议，否则窗口无法传到本地计算机来。客户 GUIGUI 服务器： 这种方式是由客户端提供用户环境的 GUI,并行机作为服务器解释和执行客 户端发来的请求。其优点是 GUI 不占用并行计算资源；而缺点是当客户端的机器平台发生 变化时，用户环境的 GUI 需要专门定制，所以通用性较差。 WebWeb 服务器+浏览器：以 Web浏览器作为用户环境界面，用户通过 统一资源定位 URLURL (Unified Resources Location)指定 Web 服务器，提出服务请求； Web 服务器分析用户请求，再向并行机发送命令，执行用户请求，并将结果传回给用户界面。 其优点是由于 Web 的跨平台特性，用户可在任何机器平台上远程 使用并行机，所以通用性非常好；而缺点是由于浏览器界面(如 Applet、Form、Cookie)的表达能力有限，所以难以将并行机的用户环境全面地、动态地提供给用户，速度也比较慢。用户环境的好用性一般可分为用户环境系统的好用性和用户界面的好用性，下面将分别讨论它们。然后简要地介绍一下用户界面设计的理论模型。(1) 用户环境系统的好用性 ：由于并行机的硬件和软件很复杂且差异性较大，让用户直接使用这些资源显然会大大加重用户的负担，所以需要提供一种便于使用这些资源的用户环境 系统。我们将并行机用户环境定义为并行机系统内所有支持用户与并行计算机相关的硬件/软件资源的工具的有机结合以及它们呈现给用户的表现形式。其中，工具的有机结合对应着整个用户环境的系统设计； 而工具集的表现形式则对应着整个用户环境的界面设计。用户环境应提供统一的用户界面， 统一的系统视图 (即各种工具的有机结合) 和统一的用户本地使 用工具集。设计用户环境系统 时：要灵活、易于扩充和集成；要尽量使用户应用软件的 开发与平台无关；不要求用户了解低层系统的实现细节，要向用户提供各项服务的接口而且尽量使用统一的标准以减轻用户负担； 因为人们所熟悉的计算环境是以串行机为参照物 的，所以要为用户提供 单一系统映象 SSI(Single System I m age) ，包括单入口 (访问 )点、单控制 点(在单一控制台上监控系统 )、单一内存映象 (单地址空间 )、单一作业管理系统 (允许用户以 独占或共享方式运行并 /串行作业 )和单一文件结构 (用户无论在哪台机器上登录，他所看到的 文件结构应当和一台机器上一致 )等。(2) 用户界面的好用性：用户界面是用户与软件之间的连接者。用户界面的好用性是指，特定的用户在使用某一软件来实现某一特定目标时，他通过用户界面所获得服务的有效性、高效性和满意程度。一个良好的 用户界面 应具有： 实用性 (Utility) ：用户界面应能提供 用户所需的各种服务，帮助用户完成所有任务；高效性 (Efficiency)(Efficiency) ： 好的用户界面应能帮助用户方便地获得各种有用的信息，而无须进行多种复杂的操作； 易学习性(Learnability) ：由于工作环境的不断变化和软件产品的不时更新，用户就得不断地学习。因此一个好用的用户界面应尽量减轻用户在学习使用过程中的负担。易于学习的用户界面应该简单、易于用户理解、记忆，尽量采用其所在领域中大家比较熟悉的风格。为了减轻用户13的记忆负担，系统应允许用户在没有记忆大量信息的情况下也能进行操作，要提供提示信息，尽量从给定的选项中作出选择就能完成操作；交互性：好的用户界面应提供充分的交互手段,包括用户怎样使用键盘、鼠标和软件工具进行交互；美观性：一个好的用户界面应给用户带来视觉的享受和使用的愉悦感。用户界面设计的理论模型：从用户界面的特性可以看出：实用性、高效性和易学习性反映的是各个界面元素的作用及其相互之间的关系，占整个界面设计的 60%;交互性决定了用户使用软件的感觉(Feel),占界面设计的 30%;美观性是指软件产品的外观(Look),它在开始时最受用户的注意，但在整个界面设计中只占10%。Alan Cooper 曾提出了用户界面设计中的三模型原则：即实现模型(ImplementationModel)，显示模型(Manifest Model)和概念模型(Conceptual Model)。概念模型也叫 心理模型 (MentalModel),它反映了用户头脑中软件应作的事情；是人们对于问题的内容依靠先天的知觉和后天的经验，在思想中构建起来的模型；是人们在头脑中形成的对问题内容以及解决问 题的方式的概念化描述。 我们在设计用户界面时所关心的心理模型是指用户对于如何使用软 件系统完成具体任务的理解是他们在自己的头脑中构想的计算机解决问题的模型。实现模型是程序员或工具的设计者对完成这些具体任务过程的描述，它和心理模型往往有很大差异，人们并不一定要了解完成这些任务的细节，他们往往在头脑中建立更加简单容易的概念，这些概念足以让他们正确地执行所要进行的操作。显示模型是指程序将软件功能呈现给用户的方式,亦即软件的用户界面。它不需要完全真实地反映程序的真正实现方式，它应该能够独立地反映程序的功能。三个模型之间的关系可由图2.2 来说明。程序的显示模型是由软件开发者决定的。一个软件的显示模型越接近用户的思维模型，用户就越容易理解和使用它；而当一个软件的显示模型更接近于实现的模型时，用户学习和使用起来就越困难；符合心理模型的用户界面设计 能在用户界面中充分体现用户思考和解决问题的方式，使软件系统更加容易被用户理解和使用,从而有效地提高用户界面的易学习性和高效性。2.2.4 机器的成本、价格与性/价比从技术的角度计算机的价格并不能算是机器的性能，但对广大购置计算机的人员来说，却往往是首先要考虑的因素。而计算机的价格是怎样定的呢？显然与生产制造计算机的成本有关。 所以了解计算机的最后标价是怎样从原料的成本逐步加码而来是很必要的。此外，性能显然与价格也有关系，人们总是希望花费最少的钱而能购置性能最高的机器，这就是计算机的所谓性能/ /价格比问题。对于任何计算机设计与制造者而言，如何利用各种先进技术来达到高的性 /实现模型反映了技术心理模型反映了用户视角14价比总是基本的目标。1机器的成本与价格价格和成本是两个不同但又相关的概念：成本并不代表用户购机的价格，它在变成实际价格之前是会经过一系列的变化；价格的上扬会使机器销售市场不景气，导致了产量的下降，从而使成本就会增大，而最终致使价格进一步上涨。一般而言，成本每变化 1000 美元，价格将会变化 30004000 美元，且价格又是一个时间的函数。下面参照图2.3 来说明从原料成本到最终标价的演变过程（以工作站为例）:原料成本：它是指一件产品中所有零部件的采购成本 总和，是价格中最基本、明显的部分；直接成本：它是指与一件产品生产直接相关的成本，包括劳务成本、采购成本（运输、包装等）、剩余零头和产品质量成本（人员培训、生产过程管 理等）等，直接成本通常在原料成本上增加20%40%;毛利：它主要包括公司的研发费、市场建立费、销售费、生产设备维护费、房租、贷款利息、付税前利润和税务费等，原料成本、直接成本和毛利相加在一起就得到平均销售价格，而毛利一般占其 20%55% ;折扣：它是产品在零售商店销售时，商店所获取的利润，它加上平均销售价格就是机器价目单 的标价，而折扣通常占标价的 40%50%，平均销售只能达到标价的50%75%。在美国，大部分公司只将收入的4%（微机产业）12%（高端计算机产业）投入研发，它不会轻易随时间变化。并行机一般投入研发的资金会更大。由于并行机销售情况不如微机、 工作站等，所以它的毛利就比较高，因此价格也就更高。并行计算机这种销售量不大而又需要很高的研发费用，就使得并行机的价格/ /成本比总是比微机、工作站、小型机等要高。平均销售价格33.3%折扣50%毛利33.3%毛利25% r直接成本12.5%直接成本8.3%直接成本原料成本75%原料成本37.5%原料成本25.1%原料成本增加 33.3%*增加 100%增加 50%4标价100%图 2.3 工作站从成本到标价的演变过程152机器的性能/价格比高的性能/ /价格比（Performance/Cost Ratio）是计算机设计者和使用者一致的目标。性/价比可定义为速度/买价，系指用单位代价（通常以百万美元表示）所获取的性能（通常以 MIPS 或MFLOPS 表示）。例如说，每百万元能获取多少个MIPS （每秒百万条指令）或多少个 MFLOPS （每秒百万次浮点运算）。高的性/价比就意味着是成本有效的（Cost-Effectively）。而成本有效性（Cost-Effectiveness）可用利用率（Utilization）来指示。利用率可定义为可达到的速度与峰值速 度之比。较高的利用率对应着每美元较多的Gflops。（1）性能/价格比：近代计算机的设计者非常注意提高机器的性/价比。例如,由于工作站机群 COW 的设计采用了 COTS（Commodity Off The-shelf）技术，使得其性/价比要比 PVP 和 MPP 等高得多。一般一台超级计算机或大规模并行机都很昂贵（费用常以几百万元，几千万元计）,而一台高性能的工作站相对便宜（费用仅以几万元或十几万元计）。一个 COW 系统从浮点运 算能力来看，虽然每台工作只有几Mflops 至 U 几十 Mflops,但一群工作站的总体运算性能可高达 Gflops 的量级,能接近一些超级计算机的性能,但价格却低了很多。Berkeley 的 NOW（Network ofWorkstations） 研究小组，曾将两台并行机 （16 个处理器的 Cray C90 PVP 和 256 个节点的 In tel Paragon）与由 256 个 RS6000 工作站所组成 4 种 NOW 系统的性/价比进行 了比较（针对大气层化学 的应用问题，程序系由并行求解常微分方程ODEQrdinaryDifferential Equations）、通信传输（Transport）和 I/O 操作三大步组成），其结果列于表 2.3 中。 如果只使用以太网和 PVM 经 TCP/IP 进行通信,那么此系统比 C90 慢 1000 倍，而性/价比也低 138 倍。但是如果代之以用高带宽的ATM 开关，再使用主动消息（Active Message）来加速通信，则改进后的机群系统要快于C90,而性/价比却高了 7 倍。表 2.3 C90、Paragon 和 4 种 NOW 系统的性能比较一览表待比较系统ODE(秒)通信 传输（秒）I/O 操 作（秒）总时间（秒）成本($ M)性/价比(Mflops/$M)Cray C907416 1273044In tel Parago n122410461078NOW42334040302734740.32NOW+ATM41922015221153.3NOW+PIO+ATM419210205535NOW+ATM+PIO+AM4810215342（2）禾I用率和成本有效性：已如上述，利用率可定义为实际可达速度与理论峰值速度之 比。如果用成本来衡量，则利用率对应于 Gflops/美元。低的利用率总是指明程序或是编译器 很差。经验的数据是：执行在单处理器的 MPP 上的顺序应用，其利用率为 5%40%,典型地 为 8%25% ;而执行在多个处理器的MPP 上的并行应用，其应用率为 1%35%,典型地为4%20%。所以，一般人认为执行在单节点上的顺序的利用率总是高于并行程序，因为后者伴有通信、等待等额外开销。但也有例外，例如在超过4 节点的 Paragon 上的并行APT（Adaptive Processing Testbed ）程序可达到最高的利用率，而在单节点上则不然。尽管高的性/价比意味着是成本有效的，但成本有效性的度量不应与性/价比相混淆，性/价比是被定义为速度与实价之比。图2.4 示出了 1995 年不同的计算机运行 NAS 基准测试程序（见本字节 2.4 节）所获得的性/价比。尽管 峰值 Gflops/百万美元”的性/价比波动较大，但 持续Gflops /百万美元的性/价比却集中在 1Gflops /百万美元。162.3 算法级性能评测本节从并行算法的角度讨论并行系统的有关性能, 测标准。它们也可以评测并行程序的性能。2.3.1 加速比性能定律简单地讲，并行系统的 加速（比）是指对于一个给定的应用，并行算法（或并行程序）的执行速 度相对于串行算法（或串行程序）的执行速度加快了多少倍。本节将要讨论三种加速比性能定律：适用于固定计算负载的AmdahlAmdahl 定律；适用于可扩放问题的 GustafsonGustafson 定律和受限于存储器的 SunSun 和 NiNi 定律。为了以下讨论方便，兹定义如下参数：令 p 是并行系统中处理器数； W 是问题规模（下文中也常叫作计算负载、工作负载，它定义为给定问题的总计算量）,Ws是应用程序中的串行分量，W 中可并行化部分为 Wp（显然 Ws+Wp=W） ;f 是串行分量比例（f = Ws/W,Ws=W1）,1-f 为并行分量比例（显然 f+（1-f）=1） ; Ts=T1为串行执行时间,Tp为并行执行时间；S 为加速（比）,E 为效率。1.Amdahl 定律AmdahI 加速定律的基本出发点是：对于很多科学计算，实时性要求很高，即在此类应用中时间是个关键因素，而计算负载是固定不变的。为此在一定的计算负载下，为达到实时性可利用增加处理器数来提高计算速度；因为固定的计算负载是可分布在多个处理器上的，这样增加了处理器就加快了执行速度，从而达到了加速的目的。在此意义下，1967 年 Amdahl 推导出了如下固定负载的加速公式：Ws WpWs WP/ p（219）为了归一化,Ws+ Wp可相应地表示为 f+（1-f），所以：主要包括加速比性能定律和可扩放性评Convex Cray CrayCray CrayDECIBMIBMNECSGI图 2.4 10 台并行机的性/价比（1995 年）17S= 1 / f这就是著名的 AmdahlAmdahl 加速定律，它意味着处理器数目的无限增大，并行系统所能达到的加速之上限为 1/f ,此结论在历史上曾对并行系统的发展起到了悲观的作用。Amdahl 定律的几何意义可清楚地表示在图2.5(a),(b)和(c)中。图 2.5 Amdahl 加速定律实际上并行加速不仅受限于程序的串行分量，而且也受并行程序运行时的额外开销影响。令 Wo为额外开销，则(2.19)式应修改为：S_ WsWp一WpWSWPWOfWW(_f)WO1f(P-1)WoP/W(222)pp当 pis时，上式变为：1fWO/W可见，串行分量越大和并行额外开销越大，则加速越小。当 pis时，上式极限为:p1 f (p -1)(2.20)(2.21)W/W Wvy vyWWpW1WpWpW1Wp23456S1024=1024/(1 + 1023f)1x100%程序中顺序部分的百分比f(c)(2.23)1024XTT91xTT0%1% 2%3% 4%处理器数P(a)(b)、48x-31X24xT间时行执W载负作工处理器数P182.Gustafson 定律问Gustafson 加速定律的基本出发点是：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦19必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。按此意义，1987 年 Gustafson 给出如下放大问题规模的加速公式8:S _ WSpWp _ WspWp-WSp Wp/pWSWp(2.24)归一化后可得S = f p (1-f) = p f (1-p) = p-f (p-1)(2.25)当 p 充分大时，S与 p 几乎成线性关系，其斜率为 1-f。这就是著名 GustafsonGustafson 加速定律，它意 味着随着处理器数目的增多，加速几乎与处理器数成比例的线性增加，串行比例不再是程序的瓶颈，这对并行系统的发展是个非常乐观的结论。Gustafson 定律的几何意义可清楚地表示在图2.6(a),(b)和(c)中。同样，当考虑到并行程序运行时的额外开销Wo时，(2.24)式应修改为:S，_ WpWP_ f p1- f_WSWP他 一 1WO/W注意，Wo是 p 的函数，它可能随 p 增大、减小或不变。一般化的Gustafson 定律欲达到线性加速必须 使 Wo随 p 减小，但这常常是困难的。3.Sun 和 Ni 定律9Xian-He Sun 和 Lio nel Ni 于 1993 年将 Amdahl 定律和 Gustafs on 定律一般化，提出了存储 受限的加速定律9。其基本思想是只要存储空间许可，应尽量增大问题规模以产生更好和更 精确的解(此时可能使执行时间略有增加)。换句话说，假若有足够的存储容量，并且规模可扩放的问题满足 Gustafson 定律规定的时间要求，那么就有可能进一步增大问题规模求得 更好或更精确的解。(2.26)20图 2.6 Gustafs on 加速定律TTTTPTPTPTPTPTP1024xP11111014x10O4x 993x983xS1024=1024-1023f-给定一个存储受限问题，假定在单节点上使用了全部存储容M 并在相应于 W 的时间内求123456处理器数P(a)W载负作工123456处理器数P(b)T间时行执0%1%2%3%4%程序中顺序部分的百分比f,S比速力21解之,此时工作负载 W= fW + (1-f)W。在 p 个节点的并行系统上，能够求解较大规模的问题是 因为存储容量可增加到pM。令因子 G(p)反应存储容量增加到p 倍时工作负载的增加量，所以扩大后的工作负载 W = fW + (1-f)G(p)W。对照(2.24)式，存储受限的加速公式相应为：fW 1 _ f G p WfW 1 - f G p W/p归一化后可得Sun 和 Ni 定律的几何意义可清楚地表示在图2.7 (a)和(b)中。图 2.7 Sun 和 Ni 加速定律同样，当考虑到并行程序运行时的额外开销Wo时，(2.27)式和(2.28)式可修改为:G(p)=p 时,它变为 f + p(1-f),这就是 Gustafson 加速定律(2.25)式；当 G(p)p 时,它相应于计算 机负载比存储要求增加得快，此时 Sun 和 Ni加速均比 Amdahl 加速和 Gustafson 加速为高。(2.27)IISf 1-f G Pf 1- f G p /p(2.28)T间时行执1234处理器数(b)fW 1 f WG pfW 1 - f G p W/p WOf 1-f G pf 1-fGp/pWfo/W(2.29)由(2.28)可知，当 G(p)=1 时,它变为这就是 AmdahI 加速定律(2.20)式;123456处理器数P(a)w载负作工TPTPT1T1224.有关加速的讨论在实际应用中，可供参考的加速经验公式是：p/log pwSwP可达线性加速的应用问题有诸如矩阵相加,内积运算等 ,此类问题几乎没有通信开销；对于分治类的应用问题 ,它类似于二叉树 ,树的同级可并行执行 ,但向根逐级推进时 ,并行度将逐渐减 少,此类问题可望达到 p/log p 的加速；对于通信密集类的应用问题 ,其加速经验公式可参考下 式：S = 1 / C ( p )(2.31)其中 C(p)是 p 个处理器的某一通信函数，或为线性的或为对数的。严格的线性加速是难以达到的 ,更何况 超线性加速 ( Superlinear Speedup) 。但在某些算法或 程序中，可能会出现超线性加速现象： 例如，在某些并行搜索算法中，允许不同的处理器在不同 的分枝方向上同时搜索，当某一处理器一旦迅速地找到了解，它就向其余的处理器发出中止搜 索的信号，这就会提前取消那些在串行算法中所作的无谓的搜索分枝，从而出现超线性加速现 象；又如，在绝大多数并行机中，每个处理器均有少量的高速缓存，当某一问题执行在大量的处 理器上，而其大多的数据均放在高速缓存中时，总的计算时间趋于减少，如果由于这种高速缓存效应所造成的计算时间下降补偿了由于通信等所造成的额外开销时间，则有可能造成超线性加速现象。最后值得指出的是，加速的含意对科学研究者和工程实用者可能有所不同：前者乐于使用 绝对加速(Absolute Speedup)的定义，即对于给定的问题，最佳串行算法所用的时间除以同一问 题其并行算法所用的时间；后者乐于使用 相对加速(Relative Speedup)的定义，即对于给定的问题，同一算法在单处理器上运行的时间除以在多个处理器上运行的时间。显然相对加速的定 义是较宽松和实际的。2.3.2 可扩放性评测标准评价并行计算性能的指标，除了上节所介绍的加速比以外，并行计算的 可扩放性 (Scalability)也是主要性能指标之一。可扩放性最简朴的含意是在确定的应用背景下，计算机系统 (或算法或程序等 )性能随处理器数的增加而按比例提高的能力。现今它已成为并行处理中一个重要的研究问题，被越来越广泛地用来描述并行算法(并行程序 )能否有效利用可扩充的处理器数的能力。1. 并行计算的可扩放性从上节所介绍的三种加速定律可知，增加处理器和求解问题的规模都可能提高加速比，而影响加速的因素有：求解问题中的串行分量；并行处理所引起的额外开销(通信、等待、竞争、冗余操作和同步等 弱加大的处理器数超过了算法中的并发程度。增加问题的规模 有利于提高加速的因素是： 较大的问题规模可提供较高的并发度； 额外开销的增加可能 慢于有效计算的增加；算法中的串行分量比例不是固定不变的(串行部分所占的比例随着问题规模的增大而缩小 )。一般情况下，增加处理器数，是会增大额外开销和降低处理器利用率 的，所以对于一个特定的并行系统，并行算法或并行程序，它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。按照 Webster 字典所作的定义 (Scalability is the ability to scale，i. e，the ability to adjust according(2.30)23to a proportion)，可扩放性涉及到调整什么和按什么比例两方面的问题。对于并行计 算而言，要调整的是处理数 p 和问题规模 W,两者可按不同比例进行调整，此比例关系(可能是 线性的，多项式的或指数的等 )就反映了可扩放的程度。当研究可扩放性时，总是将并行算法和体系结构一并考虑，也就是说可扩放性应该是算法和24结构的组合。所以当谈论算法的可扩放性时，实际上是指该算法针对某一特定机