华工《高性能计算技术》重点及复习题.docx

华工《高性能计算技术》重点及复习题.docx

《华工《高性能计算技术》重点及复习题.docx》由会员分享，可在线阅读，更多相关《华工《高性能计算技术》重点及复习题.docx（22页珍藏版）》请在冰点文库上搜索。

华工《高性能计算技术》重点及复习题

华南理工大学高性能计算技术复习题

题型：

单项选择10题，每题3分，共30分

综合题（问答、写代码，分析计算等）共6题，共70分。

考试时间：

2小时

1.解释以下基本概念

●HPC,HPCC,Distributedcomputing,Metacomputing,Gridcomputing

●MIMD,SIMD,SISD

●PVP,SMP,MPP,DSM,Cluster,Constellation

●UMA,NUMA,CC_NUMA,CORMA,NORMA

HPC:

HighPerformanceComputing高性能计算，即并行计算。

在并行计算机或分布式计算机等高性能计算系统上所做的超级计算。

HPCC：

HighPerformanceComputingandCommunication高性能计算与通信。

指分布式高性能计算、高速网络和Internet的使用。

Distributedcomputing：

分布式计算。

在局域网环境下进行的计算。

比起性能来说，它更注重附加功能。

一个计算任务由多台计算机共同完成，由传统的人和软件之间的交互变成软件和软件之间的数据交互。

Metacomputing：

元计算技术是将一组通过广域网连接起来的性质不同的计算资源集合起来，作为一个单独的计算环境向用户提供计算服务。

一个良好的元计算系统主要由三个部分组成：

一是尽量简单而又可靠的使用界面；二是资源管理系统;三是良好的编程模型和高效可靠的运行时环境。

元计算是网格计算的初级形态。

Gridcomputing：

网格计算。

利用互联网把分散在不同地理位置的电脑组织撑一个“虚拟的超级计算机”，其中每一台参与计算的计算机就是一个“节点”，而整个计算是由成千上万个“节点”组成的“一张网格”。

MIMD：

多指令多数据流。

每台处理机执行自己的指令，操作数也是各取各的。

SIMD：

单指令多数据流。

所有“活动的”处理器在同一时刻执行同一条指令对多个数据流进行操作。

SISD：

单指令单数据流。

传统的串行处理机。

CPU执行单一的指令流对单一的数据流进行操作。

PVP：

并行向量处理机。

系统中包含为数不多的高性能特制的向量处理器，使用专门设计的高带宽交叉开关网络将向量处理器连向共享存储模块。

通常不使用高速缓存，而使用大量的向量寄存器和指令缓冲器。

交叉开关

SMP：

对称多处理机。

节点包含两个或两个以上完全相同的处理器，在处理上没有主/从之分。

每个处理器对节点计算资源享有同等访问权。

SMP系统使用商品微处理器（具有片上或外置高速缓存），它们经由高速总线或交叉开关连向共享存储器。

MPP：

大规模并行处理机。

节点传统上是由单一CPU、少量的内存、部分I/O、节点间的互联以及每个节点的操作系统的一个实例组成。

节点间的互联（以及驻留于各节点的操作系统实例）不需要硬件一致性，因为每个节点拥有其自己的操作系统以及自己唯一的物理内存地址空间。

因而，一致性是在软件中通过“消息传送”（messagepassing）实现的。

具有以下特性：

1.处理节点采用商品微处理器；2.系统中有物理上的分布存储器；3.采用高带宽低延迟的互连网络；4.能扩放到上千至上万个处理器；5.异步的MIMD机器，进程间采用传递消息相互作用。

DSM：

分布共享存储多处理机。

在物理上有分布在各节点的局部存储器，从而形成一个共享的存储器。

对用户而言，系统硬件和软件提供了一个单地址的编程空间。

Cluster：

集群。

系统中的每个节点拥有小于16个处理器。

Cluster是一种并行或分布式处理系统，由一系列通过网络互连的互相协同工作的单机组成，形成单一、整合的计算资源。

Constellation：

系统中的每个节点拥有大于或等于16个处理器。

UMA：

UniformMemoryAccess.均匀存储访问模型。

特点：

1.物理存储器被所有处理器均匀共享，所有处理器访问任何存储单元花费相同的时间；2.每台处理器可带私有高速缓存；3.外围设备也可以一定形式共享。

NUMA：

NonuniformMemoryAccess.非均匀存储访问模型。

特点：

1.被共享的存储器在物理上是分布在所有的处理器中的，组成全局地址空间；2.处理器访问存储器的时间是不同的，访问本地存储器或群内共享存储器较快，访问外地存储器或全局存储器较慢；3.每台处理器可带私有高速缓存，外设可以某种形式共享。

COMA：

Cache-OnlyMemoryAccess.全高速缓存存储访问。

是NUMA的一种特例。

特点：

1.各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；2.利用分布的高速缓存目录进行远程高速缓存的访问；3.高速缓存容量一般大于2级高速缓存容量；4.使用COMA时，数据开始可以任意分配，因为在运行时它最终会被迁移到要用到的它的地方。

CC_NUMA：

Coherent-CacheNonuniformMemoryAccess.高速缓存一致性非均匀存储访问模型。

实际上是将一些SMP机器作为一个单节点而彼此连接起来所形成的一个较大的系统。

特点：

1.使用基于目录的高速缓存一致性协议；2.保留SMP结构易于编程的优点，改善了常规SMP的可扩放性问题；3.实际上是一个分布共享存储的DSM多处理机系统；4.最显著的优点是程序员无需明确地在节点上分配数据，在运行时高速缓存一致性硬件会自动地将数据迁移到要用到的它的地方。

NORMA：

No-RemoteMemoryAccess.非远程存储访问模型。

分布存储的多计算机系统，所有的存储器都是私有的，仅能由其处理器访问。

绝大多数NORMA不支持远程存储器访问。

2.试比较PVP、SMP、MPP、DSM和Cluster并行机结构的不同点，以典型系统举例说明。

3.列出常用静态和动态网络的主要参数（节点度、直径、对剖带宽和链路数）以及复杂度、网络性能、扩展性和容错性等。

常用的标准互联网络有哪些？

答：

静态网络（StaticNetworks）是指处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；动态网络（DynamicNetworks）是用交换开关构成的，可按应用程序的要求动态地改变连接组态。

典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换

网、蝶形网络等；典型的动态网络包括总线、交叉开关和多级互连网络等。

下面我们比较在可扩展计算机平台或计算机机群系统中为了实现系统动态互连，系统总

线、多级网络和交叉开关的硬件需求和潜在的性能。

代别

类型

以太网

10BaseT

快速以太网

100BaseT

千兆位以太网

1GB

引入年代

1982

1994

1997

速度（带宽）

10Mb/s

100Mb/s

1Gb/s

最

大

距

离

UTR（非屏蔽双扭对）

100m

100m

25－100m

STP（屏蔽双扭对）

同轴电缆

500m

100m

25－100m

多模光纤

2Km

412m（半双工）

2Km（全双工）

500m

单模光纤

25Km

20Km

3Km

主要应用领域

文件共享，

打印机共享

COW计算，

C/S结构，

大型数据库存取等

大型图像文件，

多媒体，

因特网，

内部网，

数据仓库等

常用的标准互联网络有：

FDDI：

光纤分布式数据结构采用双向光纤令牌环可提供100~200Mb/s数据传输。

双向环可提供冗余通路，以提高可靠性。

缺点是不能支持多媒体信息流。

其他还有快速以太网，Myrinet，HiPPI（高性能并行接口），ATM（异步传输模式），ScalableCoherentInterface（SCI），QuadricsInterconnect（QsNet），InfiniBand

4比较并行计算模型PRAM、BSP和logP。

评述它们的差别、相对优点以及在模型化真实并行计算机和应用时的局限性。

1）PRAM模型：

并行随机存取机器，也可称为共享存储的SIMD模型。

特点：

假定存在着一个容量无限大的共享存储器，有有限或无限个功能相同的处理器，且均有简单的算术运算和逻辑判断功能。

在任何时刻各处理器均可通过共享存储单元相互交换数据。

优点：

特别适合于并行算法的表达、分析和比较；使用简单，很多诸如进程间通信、存储管理和进程同步等并行机的低级细节均隐含于模型中；易于设计和稍加修改便可运行在不同的并行机上；且有可能在PRAM模型中加入一些诸如同步和通信等需要考虑的问题。

缺点：

PRAM是一个同步模型，这意味着所有指令均按锁步方式操作；用户虽感觉不到同步的存在，但它的确是很费时的；共享单一存储器的假定，显然不适合分布存储的异步的MIMD机器；假定每个处理器均可在单位时间内访问任何存储单元而略去存取竞争和有限带宽等是不现实的。

2）BSP模型：

“大”同步模型，是个分布存储的MIMD计算模型。

特点：

BSP将处理器和选路器分开，强调了计算任务和通信任务的分开，而选路器仅施行点到点的消息传递，不提供组合、复制或广播等功能，这样做既掩盖了具体的互联网拓扑，又简化了通信协议；采用路障方式的以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员无过分的负担；为PRAM模型所设计的算法均可采用在每个BSP处理器上模拟一些PRAM处理器的方法实现之。

●优点

Ø在软件和硬件之间架起一座类似于冯.偌依曼的桥梁；

Ø如果计算和通信可合适的平衡，则可克服分布MIMI模型编程能力较差的特点；

Ø实现了一些重要的算法，且均避免了自动存储管理的额外开销；

Ø可有效地在超立方网络和光交叉开关互利技术上实现，与特定的工艺技术无关，只要选路器有一定的通信吞吐率。

●缺点

Ø在BSP模型中，要求超级步的长度必须能充分地适应任意的h-relation；

Ø超级步发送的消息最快也要在下一个超级步才可以使用；

ØBSP模型中的全局路障同步假定是用特殊的硬件支持，在很多并行机中可能没有相应的现成的硬件机构。

3）logP模型：

是一种分布存储的，点到点通信的多处理机模型。

●特点

logP模型是一种分布存储的、点到点通信的多处理机模型，其中通信网络由一组参数来描述，但它不涉及具体网络结构，也不假定算法一定要用显式的消息传递操作进行描述（实现隐式同步）。

●优点

ØlogP模型将现代和将来的并行机的特性进行了精确的综合，以少量的参数L、o、g和p刻画了并行机的主要瓶颈；

Ø无须说明编程风格或通信协议，可以等同地用于共享存储、消息传递和数据并行等各种风范；

ØlogP模型的可用性已得到多个算法的证实；

ØlogP模型是BSP模型的细化，也可以转换为PRAM模型；

Ø打开了研究模型的新途径，为设计并行机体系结构提供了指导性意见。

●缺点

Ø（难以进行算法描述、设计和分析）

BSP和logP相互比较：

1.现今最流行的并行计算模型是BSP和logP，已经证明两者本质上是等效的，且可以互相模拟；2.BSP为算法和程序提供了更多的方便，而logP却提供了较好的机器资源的控制；3.BSP所引起的精确度方面的损失比起其所提供的更结构化的编程风格的优点来是小的；4.BSP模型在简明性、性能的可预测性、可移植性和结构化可编程性等方面更受人欢迎和喜爱。

三者关系：

LogP和PRAM模型是并行计算模型的两个极端.BSP模型可以看成是上述两个模型的折衷.相比之下,LogP模型过于复杂,缺乏有效的分析和性能预测的模型,而PRAM则过于简单,无法真实地描述物理机器。

BSP模型较好地综合了其它两个模型优点,在面向物理机器实现方面优于PRAM模型,而和LogP模型相比,又更加便于进行算法设计和性能预测。

4.比较在PRAM模型和BSP模型上，计算两个N阶向量内积的算法及其复杂度。

PRAM模型

求两个N维向量A,B的内积s（s=∑a*b）

串行:

N个乘法,N-1个加法

共需2N个周期

PRAM机（n个处理器）:

每个处理器p完成N/n个乘法,N/n-1个加法,共2N/n个周期，然后采用树归约方法将n个局部和相加---logn周期，共需要2N/n+logn个周期

加速度:

2N/（2N/n+logn）n（N>>n）

BSP模型

求两个N维向量A,B的内积s（s=∑a*b）假设8个处理器

超步1:

计算:

每个处理器在w=2N/8周期内计算局部和

通讯:

处理器0,2,4,6将局部和送给1,3,5,7

路障同步

超步2:

计算:

处理器1,3,5,7各自完成一次加法（w=1）

通讯:

1,5将中间结果送给3,7

路障同步

超步3:

计算:

处理器3,7各自完成一次加法（w=1）

通讯:

3将中间结果送给7

路障同步

超步4:

计算:

处理器7完成一次加法（w=1）,产生最后结果

总执行时间:

2N/8+3g+3l+3个周期.在n个处理器的BSP机上,需

2N/n+logn（g+l+1）个周期,比PRAM多了（g+l）*logn,其分别对应

于通讯和同步的开销

5.什么是加速比（speedup）、并行效率（efficiency）和可扩展性（scalability）?

如何描述在不同约束下的加速比？

答：

粒度：

是各个处理机可独立并行执行的任务大小的度量大粒度反映可并行执行的运算量大，亦称为粗粒度指令级并行等则是小粒度并行，亦称为细粒度

加速比：

串行执行时间为Ts，使用q个处理机并行执行的时间为Tp（q），则加速比为Sp（q）=Ts/Tp（q）。

简单的说，并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度快了多少倍。

效率：

设q个处理机的加速比为Sp（q），则并行算法的效率Ep（q）＝Sp（q）/q。

反映了并行系统中处理器的利用程度

可扩放性：

其最简朴的含义是在确定的应用背景下，计算机系统（或算法或编程等）性能随处理器数的增加而按比例提高的能力。

在不同的约束条件下的加速比产生了三个重要的加速比性能定律：

Amdahl定律：

约束条件：

1，对于很多科学计算，实时性要求很高，即在此类应用中时间是个关键因素，而计算负载是固定不变的。

为此在一定计算负载下，达到实时性可利用增加处理器数来提高计算速度。

2，因为固定的计算负载是可分布在多个处理器上的，这样增加了处理器就加快了执行速度，从而达到了加速的目的。

Gustafson定律：

1，对于很多大型计算，精度要求很高，即此类应用中精度是个关键因素，而计算时间是固定不变的。

此时为了提高精度，必须加大计算量，相应的亦必须增多处理器数目才能维持计算时间不变。

2，除非学术研究，在实际应用中没有必要固定工作负载而使计算程序运行在不同数目的处理器上，增多处理器必须相应增大问题的规模才有实际意义。

Sun－Ni定律：

只要存储空间许可，应尽量增大问题的规模以产生更好的或更精确的解（此时可能使执行时间略有增加）。

6.如何进行并行计算机性能评测？

什么是基准测试程序？

什么是可扩放性测量标准？

如何进行并行计算机性能评测：

（没有如何进行并行计算性能评测）。

基准测试程序用于测试和预测计算机系统的性能，揭示了不同结构机器的长处和短处，为用户决定购买和使用哪种机器最适合他们的应用要求提供决策。

可扩放性测量标准：

是在确定的应用背景下，计算机系统性能虽处理器数的增加而按比例提高的能力。

7.并行算法设计的一般过程PCAM是指什么？

各个步骤中的主要判据是什么？

PCAM是Partitioning（划分）、Communication（通信）、Agglomeration（组合）和Mappin（映射）首字母的拼写，它们代表了使用此法设计并行算法的四个阶段。

上述各阶段简述如下：

划分：

将整个计算分解成小的任务，其目的是尽量开拓并发执行的机会；

通信：

确定诸任务执行中所需交换的数据和协调诸任务的执行，由此可检测上述划分的合理性。

组合：

按性能要求和实现的代价来考察前两阶段的结果，必要时可将一些小的任务组合成更大的任务以提高性能或减少通信开销。

映射：

将每个任务分配到一个处理器上，其目的是最小化全局执行时间和通信成本以及最大化处理器的利用率。

划分判据：

（1）你所划分的任务数，是否至少高于目标机上处理器数目的一个量级？

如果不是，则你在后继的设计步骤中将缺少灵活性。

（2）你的划分是否避免了冗余的计算和存储要求，如果不是，则所产生的算法对大型问题可能是不可扩放的。

（3）诸划分的任务是否尺寸大致相当，如果不是，则分配处理器时很难做到工作量均衡。

（4）划分的任务数是否与问题尺寸成比例？

理想情况下，问题尺寸的增加应引起任务数的增加而不是任务尺寸的增加。

如果不是这样，则你的算法可能不能求解更大的问题，尽管有更多的处理器。

（5）确认你是否采用了几种不同的划分法，多考虑几种选择可提高灵活性，同时要考虑域分解又要考虑功能分解。

通讯判据:

（1）所有任务是否均执行同样多的通信？

如果不是，则所设计的算法的可扩展性可能是不好的。

（2）每个任务是否只与少许的近邻相通信？

如果不是，则可能导致全局通信，在此情况下，应设法将全局通信结构化为局部通信结构。

（3）诸通信操作是否能并行执行？

如果不是，则所设计的算法很可能是低效的和不可扩放的，在此情况下，设法试用分治技术来开发并行性。

（4）不同任务的计算能否并性执行？

如果不是，则所设计的算法很可能是低效的和不可扩放的，在此情况下，可考虑重新安排通信/计算之次序等来改善之。

组合判定：

（1）用增加局部性方法施行组合是否减少了通信成本？

如果不是，检查能否由别的组合策略来达到

（2）如果组合已造成重复计算，是否已权衡了其权益。

（3）如果组合已重复了数据，是否已证实这不会因限制问题尺寸和处理器数的变化范围而牺牲了可扩放性？

（4）由组合所产生的任务是否有类似的计算和通信代价。

（5）任务数目是否仍然与问题尺寸成比例？

如果不是，算法则不是可扩放的。

（6）如果组合减少了并行执行的机会，是否已证实现在的并发性仍能适应目前和将来的并行机。

（7）在不导致负载不平衡，不增加软件工程代价和不减少可扩放性的前提下，任务数能否再进一步减少，在其他条件等同时，创建较少的大粒度的任务算法通常是简单有效的。

（8）如果并行化现有的串行程序，是否考虑了修改串行代码所增加的成本？

如果此成本是高的，应考虑别的组合策略，它能增加代码重用的机会。

映射判据：

（1）如果采用集中式负载平衡方案，你是否已验证中央管理者不会成为瓶颈？

（2）如果采用动态负载平衡方案，你是否衡量过不同策略的成本？

（3）如果采用概率或循环法，你是否有足够多的任务来保证合理的负载平衡？

典型地，任务数应10倍于处理数。

（4）如果要为一个复杂问题设计一个SPMD程序，你是否考虑过基于动态任务创建和消除的算法：

后者可能得到一个更加简单的算法，但是性能可能有问题。

8.什么是域分解和功能分解？

如何将全局通信转换为局部通信？

什么是表面－容积效应和重复计算？

映射的策略是什么？

域分解：

也叫数据划分。

所要划分的对象是些数据，这些数据可以是算法（或程序的输入数据，计算的输出数据，或者算法所产生的中间结果。

功能分解：

也叫计算划分，其基本出发点不同于域分解，它首先关注于被执行的计算上，而不是计算所需的数据上，然后，如果所作的计算划分是成功的，再继续研究计算所需的数据上，这些数据可能是不相交的，这就意味着划分很成功，或者这些数据有相当的重叠，这就产生大量的通信，此时就暗示应考虑数据分解。

将全局通信转换为局部通信：

局部通信时，每个任务只与较少的几个近邻通信；全局通信中，每个任务与很多别的任务通信。

并行算法可采用分治法进行优化一方面提高了算法的并行度；同时也可将全局通信转换为局部通信

表面－容积效应：

一个任务的通信需求比例于它所操作的子域的表面积，而计算需求却比例于子域的容积。

在一个二维问题中，“表面积“比例于问题的尺寸，而”容积“比例于问题尺寸的平方。

因此一个计算单元的通信/计算之比随问题（任务）尺寸的增加而减少。

重复计算：

它也称为冗于计算。

有时候可以采用不必要的多余的计算的方法来减少通信要求和/或执行时间。

映射的策略：

开发映射的主要目的是减少算法的总的执行时间，其策略有二：

一是把那些能够并发执行的任务放在不同的处理器上以增强并行度；二是把那些需频繁通信的任务置于同一个处理器上以提高局部性。

9.什么是OpenMP的编程模型、体系结构、控制结构和数据域子句？

OpenMP的编程模型

首先，OpenMP是基于线程的并行编程模型（ParallelProgrammingModel），一个共享存储的进程由多个线程组成，OpenMP就是基于已有线程的共享编程模型；其次，OpenMP是一个外部的编程模型，而不是自动编程模型，它能够使程序员完全控制并行化。

体系结构

控制结构

并行域结构：

一个并行域就是一个能够被多线程执行的程序块，它是最基本的OpenMP并行结构；共享任务结构：

共享任务结构把其内封闭的代码段划分给线程队列中的各线程执行；组合的并行共享任务结构；同步结构：

OpenMP提供了多种同步结构来控制与其他线程相关的线程的执行。

数据域子句

OpenMP的数据域子句用来定义变量的范围，它包括PRIVATE、FIRSTPRIVATE、LASTPRIVATE、SHARED、DEFAULT、REDUCTION和COPYIN等。

10.什么是MPI的消息、数据类型、通信域？

如何应用MPI的扩展数据类型？

一个消息（message）指在进程间进行的一次数据交换，在MPI中，一个消息由通信器、源地址、目的地址、消息标签和数据构成。

MPI系统中数据的发送与接收操作都必须指定数据类型。

数据类型可以是MPI系统预定义的，称为原始数据类型，也可以是用户在原始数据类型的基础上自己定义的数据类型。

MPI中的通信域（Communicator）提供了一种组织和管理进程间通信的方法。

MPI通信域包括两部分进程组和通信上下文进程组即所有参加通信的进程的集合如果一共有N个进程参加通信则进程的编号从0到N-1通信上下文提供一个相对独立的通信区域不同的消息在不同的上下文中进行传递不同上下文的消息互不干涉通信上下文可以将不同的通信区别开来。

MPI除了可以发送或接收连续的数据之外还可以处理不连续的数据其基本方法可采取允许用户自定义新的数据类型又称派生数据类型的方法，即可扩展的数据类型。

11.什么是MPI的阻塞通信和非阻塞通信？

点到点通信模式有哪些？

群集通信模式？

阻塞通信（BlockingCommunication）：

当一个通信过程的请求的完成依赖与某个“事件”时，我们说它是阻塞式的。

对于发送过程，数据必须被成功地发送或安全地拷贝到系统缓存

以便于保存它的应用缓存可以被重用。

对于接收操作，数据必须被安全地存储到接收缓存中以便它可以被利用。

非阻塞通信（NonblockingCommunication）：

当一个通信过程的完成不需要等待任何通信事件的完成就可以返回时，它就属于非阻塞通信，例如将数据从用户的内存拷贝到系统缓存

或消息的到达。

对于一个非阻塞发送，在它完成之后修改或重用应用缓存是很危险的，这就需要编程者保证此时应用缓存是空闲的可以被重用。

点到点通信有