bsp模型适用于图计算_计算机并行计算考试重点总结「推荐收藏」

**计算机体系结构由程序设计者看到的计算机系统的属性，抽象的概念性的结构和功能属性。

计算机组成:是计算机体系结构的逻辑实现。

计算机实现:是计算机组成的物理实现。

重点内容

计算机系统的层次结构 现代并行计算机的组成

ü硬件核心:处理机、存储器和外围设备组成了计算机系统。

ü互连:外围设备可以直接或通过局域网和广域网与主机相连。

ü映射是一种算法结构与硬件结构相匹配的双向过程。包括处理机调度、存储器映象、处理器间的通信等..存在的问题：不能以通用和可移植方式进行并行程序设计。将着眼点放在语言执行的效率、对不同机器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性

改进编译器：预处理程序、预编译器、并行化编译器

ü预处理程序：采用顺序编译器和目标计算机的低层程序库实现高级并行结构。

ü预编译器：需要程序流分析、相关性检查和有限的优化来检测并行性。

ü联接过程的效果取决于预处理程序、预编译器、并行化编译器、加载程序

和操作系统支持的功效。由于程序行为的不可预测，现有的编译器在检测

所有类型的并行性时都不是完全自动或完全智能进行的。有效的办法：p将编译器命令插入源代码，帮助编译器做出较好的结果。这样，用户可与编译器进行交互重构，这已被证明对提高并行计算机性能是十分有用的。

物理结构

üMISD(多指令流单数据流)机在执行不同的指令流时，同一数据流通过处理机线性阵列就是所谓 流水线执行特定算法的脉动阵列(Systolic arrays)。

并行计算机有两大类：共享存储型多处理机、消息传递型多计算机

早期的超级计算机可分为：

流水线向量机：用带有少量带有向量硬件，但性能很高的处理机来装备.

SIMD计算机：强调开发大规模数据并行性

pSIMD计算机开发的是PE之间的空间并行性;p存储器分布的SIMD计算机由同一阵列控制部件控制的PE阵列组成;p程序和数据通过主机装入控制存储器;

p指令是送到控制部件进行译码;ü标量操作或控制操作，则将直接由与控制部件相连的标量处理机执行;ü向量操作，则将它广播到所有PE并行地执行;p划分后的数据集合通过向量数据总线广播到所有PE的本地存储器;pPE通过数据寻径网络互连。数据寻径网络执行PE间的通信，如移数、置换和其它寻径操作。控制部件通过执行程序来控制数据寻径网络。PE的同步由控制部件的硬件实现;p所有PE在同一个周期执行同一条指令;p可以用屏蔽逻辑来决定任何一个PE在给定的指令周期执行或不执行指令

共享存储器模型:是一种PE使用共享存储器的SIMD计算机。PE和存储器之间的通信网络是一个对准网络，它也受控制部件控制。

抽象机模型的概念与意义

ü并行计算机的理论模型是从物理模型抽象的；

ü为开发并行算法提供了一种方便的框架；

ü用这些模型可求得并行计算机的理论性能界限；

ü可在芯片制作前估算芯片区的VLSI复杂性和执行时间。

计算机求解一个规模为s的问题的算法复杂性取决于:Ø执行时间Ø存储空间

一个抽象机模型用语义属性和性能属性进行描述

语义属性:同构性、同步性、交互机制、地址空间、存储器模型、原子操作(不可分，有限)

性能属性：包括机器规模、时钟频率、工作负载、执行时间(顺序/并行)、速度、加速比、效率以及利用率等

语义属性具有较长的延续性，并行计算机换代时仍保持不变。

性能属性高度依赖系统结构平台，随着计算机换代而改变。

并行程序的操作类型：计算操作、并行性操作、交互操作

并行程序的开销源：并行性开销、通信开销、同步开销、不平衡开销

并行随机存取机模型 PRAM：用途:可用来开发并行算法和分析可扩展性及复杂性。MIMD、细粒度、严格同步、零开销、共享变量。特点：在PRAM上的一个并行程序由n个进程组成，其中第i个进程留驻在第i个处理器上，且由一串指令所组成。在每个基本时间步(称为周期)，每个处理器执行一条指令。指令包括数据传送、算/逻、控制流以及I/O指令，在典型的顺序计算机中均有这些指令。①规模为1的PRAM退化为传统的RAM机。这种机器为SISD机。②当处理器多于1个时，一个PRAM将访问多个数据流，且通常可执行多个指令流。因此PRAM是一个MIMD机。 MIMD的特例:

如果在每一周期，所有处理器必须执行相同指令，即只有一个指令流时，则PRAM就成为单指令流、多数据流(SIMD)机器。

SPMD计算：单程序、多数据，所有进程执行同一程序，而由进程指标加以参数化。

SIMD和SPMD间的差别是，在SPMD计算中，同一周期可以执行不同指令。

①进程同步是严格的，任何处理器的存储器写操作或转移操作之前，必须完成其他处理器的存储器读操作。②PRAM是在指令级同步的。③实际的MIMD并行机是异步的。每个进程有自己的速率，与其他处理器进程速率无关。 在PRAM模型中，进程间通过共享变量(或共享存储器)进行交互，进程间通过共享变量进行交互的异步MIMD机，常称为多处理机。

进程间通过消息传递进行交互的异步MIMD机，常称为多计算机

①理论PRAM模型中，所有进程对所有存储单元均有相等的访问时间。这种机器为均匀存储器访问(UMA)。②若采用非均匀存储器访问(NUMA)，将演变为异步PRAM模型(APRAM)。③ PRAM模型不合适多计算机。

多计算机中，每个处理机有它自己的分离地址空间。这些机器被称为具有多地址空间。正是由于此原因，多计算机的处理机间通信不是通过共享变量，而是借助消息传递。

存储器模型：主要目的是协调写冲突问题，有四种PRAM模型方案。 ①EREW-PRAM模型——互斥读、互斥写。禁止一台以上处理机同时读、写同一存储单元。 这是限制最大的PRAM模型。②CREW-PRAM模型——并发读、互斥写。用互斥使写冲突避免。可以并行读同一存储单元。③ERCW-PRAM模型——互斥读、并发写。允许互斥读或并行写同一存储单元。④CRCW-PRAM模型——并发读、并发写，允许在同一时刻并行读或者并行写。PRAM模型常用EREW和CRCW规则优点：PRAM模型略去很多细节，形式简单，便于开发并行程序，在此模型基础上开发的并行算法易于改进成实用的并行算法。缺点：与物理模型存在差异，实际上，这种并行计算机是不存在的。原因在于零通信开销和指令级同步的不现实假设。共享存储器的SIMD机是与PRAM模型最接近的结构

块同步并行模型 BSP特点：(1)一个BSP程序有n个进程，每个驻留在一个结点上。基本时间单位是周期(或时间步)。(2)程序按严格的超步序列执行。(3)同步路障迫使进程等待。(4)BSP计算机是MIMD系统。(5)BSP模型是超步级的松同步。(6)在一个超步中，不同进程以不同速率异步执行。(7)BSP模型交互机制是共享变量或是消息传递。

h关系的定义：(1)一个h关系是任何通信操作的抽象，在其中，每个结点最多发出h个字到各结点，并且每个结点最多接收h个字。(2)在一个BSP计算机中，实现任何h关系的时间不会超过gh个周期，g是由机器平台决定的一个常数。一个超步执行时间的确定计算时间w：处理器中完成计算操作所需的最大周期数；路障同步开销为L；通信开销为gh周期，g是实现h关系的比例系数，常数；执行一个超步的时间为:w+gh+L

优点：与PRAM模型相比，BSP模型更为实际，更接近物理模型，BSP模型除了用于进程管理的并行性开销外，它考虑了所有其他开销

阶段并行模型基本描述：一个并行程序以一系列阶段加以执行，当前阶段的所有操作未完成之前，不能开始下一阶段操作

三类阶段的定义：并行化阶段主要涉及进程管理的开销阶段；计算阶段一个或多个处理器执行若干局部计算操作；交互阶段完成交互操作所执行的任务。。特点：不同的计算阶段可以不同的工作速度执行不同的工作负载；不同的交互操作可取不同的时间

可扩展性范围包括资源可扩展性是指通过增加处理器数、更多的存储部件(高速缓存，主存，磁盘)以及增加软件等方法，使系统具有更高性能或功能。涉及三方面：Ø规模可伸缩性、Ø资源扩展、Ø软件可扩展性。

ü当前的并行计算机规模的扩展：Ø加入更多处理器、Ø增加互连网络、接口以及通信软件在内的子系统、有效地利用更大并行性，即如何为扩大的系统进行编程

ü计算机系统中发展最快的部件是处理器进展最慢的部分是程序设计语言

SMP和MMP只具有有限的空间可扩展性；ü因特网则具有最好的空间可扩展性

可扩展设计原理：ü独立原理ü平衡设计原理ü可扩展性设计原理、时延隐藏原理

独立原理：应努力使系统中的各个组成部分(硬、软件)相互独立如果无法达到完全独立，则应尽力使相关程度减至最小并使相关性尽量清晰。优点：ü使独立扩展成为可能，ü使异构可扩展性成为可能、要求部件不受制于一个特别的体系结构或系统

ü消息传递接口(MPl)是使用少量独立(正交)语言特征的成功范例。üMPI基于4个相互正交的主要概念：数据类型、通信操作、通信子集、虚拟拓扑

实现独立原理的两种通用技术：ü将体系结构和实现分开、ü使用标准组件

平衡设计原理：ü应努力最小化任何性能瓶颈ü应避免不平衡系统的设计ü应避免单点失效，即一个部件失效将使整个系统崩溃

Amdahl法则：处理速度应与存储器容量和I／O速度相平衡 实现：ü粗略地估计每秒一百万指令(MIPS)的计算速度，应与1MB存储器容量和1Mb/s的I/O速率相平衡

并行系统50％法则ü并行程序性能取决于：Ø负载不平衡;Ø并行化开销;Ø通信启动开销(t0);Ø以及每字节通信开销(tc)；ü50％法则：4个开销因素的每一个使性能衰减都不大于50％，那么就认为此并行系统是平衡的

单结点速度P1”表示的是“计算速度”；“渐进带宽r∞=1/tc”表示的是“通信速度”。

设计“平衡的”由两个慢速部件(处理器速度、网络速度)构成的系统。优于设计“不平衡的‘一个快速(处理器速度)一个慢速(网络速度)构成的系统。平衡设计可以改善系统的性能

ü计算机系统设计理念：Ø在设计一个可扩展的系统时，应该从一开始就将可扩展性作为主要目标，而不是设计完成后再来考虑这一问题。Ø为系统将来可能扩展以提供更高性能或缩小以使价格降低或是有更大的成本有效性作好准备。

可扩展性设计的两种流行方法：过度设计、向后兼容性

过度设计：是指系统在设计时不单纯地只是为了满足目前系统的最低需要，设计必须包括一些附加特性，以期在未来的扩展系统中性能得到改进

ü地址空间大小：即处理器能直接访问的字节单元数。

向后兼容性：在设计硬件或软件部分时，必须兼顾缩减系统的需求。向后兼容性并不表示一个旧系统的所有特性都应保留。应该剔除陈旧的特性，在应用过度设计技术时，应考虑成本问题且不应对未来期待过多，虽然有时过度设计确实能减少总的开发和生产成本。

缺少合适的并行软件是阻碍主流用户接纳并行计算的主要原因。并行系统软件和应用软件不仅数量很少,而且功能性也相当原始。困难：p并行编程中有许多不同的模型是一个更复杂的智力活动。并行程序的环境要比串行程序落后得多

编程模型(虚)即是程序员在开发一个并行程序时所见到和使用的模型。自然模型(实)是由一个特定并行计算机平台所提供的、用户可见的最低层的编程模型，其他的编程模型可在此自然模型上加以实现

环境工具是指任何硬件和软件的实用程序，以帮助用户程序的开发和执行，ü是那些通常与操作系统或程序设计语言无关的工具集

ü大多数程序基于命令式机器模型，中心概念是状态更新ü一个命令式程序可看成是一个状态机(或一个自动机)

程序变量集：数据变量、控制变量

ü开始时，进程为不存在状态。当它的创建者，父进程执行进程创建操作后，它才出现。一个新创建的子进程准备执行，但仅在被调度后，它方可开始运行(执行其代码)。

ü重量级的并行进程不适用于可扩展并行计算机，除非并行进程具有粗计算粒度。要开发较细粒度并行性，必须使用轻量级进程

OS进程和线程间的主要差别：在重量级的OS进程中，多个线程能共存于进程(包括进程描述符)的同一地址空间，并且共享；当创建一个(重量级)进程时，通常它有一个单线程，称为基本线程；通过执行一个线程创建操作，任何进程能创建另外的线程

颗粒度是指在两次并行性操作之间所执行的计算负载。

单线程：从程序员的观点，一个数据并行程序中由一个进程执行，具有单一控制线；使得一个数据并行程序就像一个顺序程序。并行操作子聚合数据结构上：数据并行程序的一个单步(语句)，可指定同时作用在不同数据组元素或其他聚合数据结构上的多个操作；松散同步(LooselySynchronous)：在数据并行程序的每条语句之后，均有一个隐含的同步，这种语句级的同步是松散的(相对于SIMD机器每条指令之后的紧同步而言)；全局命名空间：数据并行程序中的所有变量均驻留在单一地址空间内，所有语句可访问任何变量，只要满足通常的变量作用域规则；隐式相互作用：因为数据并行程序的每条语句之末存在着一个隐含的路障，所以不需要一个显式同步；通信可由变量指派而隐含地完成。隐式数据分配：程序员不必要明确地指定如何分配数据，可将改进数据局部性和减少通信的数据分配方法揭示给编译器

分别对应数据并行模型 消息传递模型 共享变量模型

并行程序的并行度(degree of parallelismDOP)通常定义为可同时执行的分进程数。

颗粒度;指在两次并行性操作或交互操作之间所执行的计算负载

通信操作类型：数据交换、同步操作、聚集操作

宏基准程序

NPB基准程序组由5个核心(EP、MG、CG、FT和IS)和3个模拟应用(LU、SP和BT)程序组成。

核心程序：EP 基准程序、MG基准程序、CG基准程序、FT基准程序、IS基准程序。模拟应用程序：BT、LU、SP

PARKBENCH基准程序组：低层基准程序、核心基准程序、压缩应用基准程序、HPF编译器基准程序

并行STAP程序组：APT、HO-PD、BM、EL等4个基准程序的结构

用户经常提到6种性能：执行时间；速度;吞吐率；利用率;成本有效性;性能／成本比

工作负载(W)：是程序中的计算操作数 Ppeak：是处理器的峰值速度

处理速度;是指单位时间的工作负载(W)的处理,W 表示“工作负载”，其单位是“Mflop(兆

浮点运算)”,处理速度：Pn=W/Tn,其单位是Mflop／s

提高系统吞吐率的两个方法:流水化、无相关的分配

利用率 Un=Pn/(nPpeak)指一个给定计算机实际可达到速度与峰值速度之比

成本有效性：单位成本实现的工作负载。衡量单位： Gflop／$

3个指标来测量程序C的计算工作负载：执行时间；执行的指令数；执行的浮点操作数；

存储器层次结构的主要指标：存储器容量、存储器时延、存储器带宽

并行性开销的来源：进程管理、分组操作、进程查询操作。交互开销的来源：同步、聚集、通信

并行程序中的开销可分为3类：负载不平衡开销、并行性开销、交互开销。执行一个并行程序所需的时间为： T= Tcomp+Tpar+Tinteract

并行性开销的来源：进程管理、分组操作、进程查询操作

交互开销来源：同步、聚集、通信

数据并行：在理想环境下于每个时钟内可并发地执行500到3500个算术操作。

指令级并行：并行度较低。指令级并行性的极限约在5左右，很少超过7。一个合理设计的超标量处理器上，可期待每周期并发执行2.0到5.8条指令。

加速比分析：

n是并行系统中处理器数。W是问题规模(给定问题的总计算量)Ws=W1为顺序工作负载，Wp为并行工作负载 。为顺序分量比例，=Ws/W；1-为并行分量比例Ts=T1为顺序执行时间，Tp为并行执行时间。S为加速比；E为效率。

考虑开销的加速比说明：

并行加速比不仅受限于程序的顺序分量，而且也受并行程序运行时的平均开销影响。

Amdahl定律结论：固定负载加速比随顺序瓶颈α和平均开销的增加而急剧下降。顺序瓶颈问题不能用单纯增加机器规模(处理器数目)的办法来解决。

存储受限的加速定律：基本思想：只要存储空间许可，应尽量增大问题规模，以产生更好和更精确的解(此时可能使执行时间略有增加)

受限存储器加速比定义：此时工作负载仍然表示为W=αW+(1-α)W。Ø令因子G(n)反应存储容量增加到P倍时工作负载的增加量，扩大后的工作负载为:W’=αW+(1-α)G(n)W**