《高性能计算技术》练习题word精品文档13页.docx
- 文档编号:15992735
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:11
- 大小:22.23KB
《高性能计算技术》练习题word精品文档13页.docx
《《高性能计算技术》练习题word精品文档13页.docx》由会员分享,可在线阅读,更多相关《《高性能计算技术》练习题word精品文档13页.docx(11页珍藏版)》请在冰点文库上搜索。
《高性能计算技术》练习题word精品文档13页
高性能计算与云计算练习题
1.解释以下基本概念
●HPC,HPCC,Distributedcomputing,Cloudcomputing
●MIMD,SIMD,SISD
HPC:
HighPerformanceComputing高性能计算,即并行计算。
在并行计算机或分布式计算机等高性能计算系统上所做的超级计算。
HPCC:
HighPerformanceComputingandCommunication高性能计算与通信。
指分布式高性能计算、高速网络和Internet的使用。
Distributedcomputing:
分布式计算。
在局域网环境下进行的计算。
比起性能来说,它更注重附加功能。
一个计算任务由多台计算机共同完成,由传统的人和软件之间的交互变成软件和软件之间的数据交互。
Cloudcomputing:
云计算(CloudComputing)是一种新兴的商业计算模型。
它将计算任务分布在大量计算机构成的资源池上,使各种应用系统能够根据需要获取计算力、存储空间和各种软件服务。
MIMD:
多指令多数据流。
每台处理机执行自己的指令,操作数也是各取各的。
SIMD:
单指令多数据流。
所有“活动的”处理器在同一时刻执行同一条指令对多个数据流进行操作。
SISD:
单指令单数据流。
传统的串行处理机。
CPU执行单一的指令流对单一的数据流进行操作。
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模型相比,又更加便于进行算法设计和性能预测。
5.比较在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,其分别对应
于通讯和同步的开销
6.什么是加速比(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定律:
只要存储空间许可,应尽量增大问题的规模以产生更好的或更精确的解(此时可能使执行时间略有增加)。
7.如何进行并行计算机性能评测?
什么是基准测试程序?
什么是可扩放性测量标准?
如何进行并行计算机性能评测:
(没有如何进行并行计算性能评测)。
基准测试程序用于测试和预测计算机系统的性能,揭示了不同结构机器的长处和短处,为用户决定购买和使用哪种机器最适合他们的应用要求提供决策。
可扩放性测量标准:
是在确定的应用背景下,计算机系统性能虽处理器数的增加而按比例提高的能力。
8.并行算法设计的一般过程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程序,你是否考虑过基于动态任务创建和消除的算法:
后者可能得到一个更加简单的算法,但是性能可能有问题。
9.什么是域分解和功能分解?
如何将全局通信转换为局部通信?
什么是表面-容积效应和重复计算?
映射的策略是什么?
域分解:
也叫数据划分。
所要划分的对象是些数据,这些数据可以是算法(或程序的输入数据,计算的输出数据,或者算法所产生的中间结果。
功能分解:
也叫计算划分,其基本出发点不同于域分解,它首先关注于被执行的计算上,而不是计算所需的数据上,然后,如果所作的计算划分是成功的,再继续研究计算所需的数据上,这些数据可能是不相交的,这就意味着划分很成功,或者这些数据有相当的重叠,这就产生大量的通信,此时就暗示应考虑数据分解。
将全局通信转换为局部通信:
局部通信时,每个任务只与较少的几个近邻通信;全局通信中,每个任务与很多别的任务通信。
并行算法可采用分治法进行优化一方面提高了算法的并行度;同时也可将全局通信转换为局部通信
表面-容积效应:
一个任务的通信需求比例于它所操作的子域的表面积,而计算需求却比例于子域的容积。
在一个二维问题中,“表面积“比例于问题的尺寸,而”容积“比例于问题尺寸的平方。
因此一个计算单元的通信/计算之比随问题(任务)尺寸的增加而减少。
重复计算:
它也称为冗于计算。
有时候可以采用不必要的多余的计算的方法来减少通信要求和/或执行时间。
映射的策略:
开发映射的主要目的是减少算法的总的执行时间,其策略有二:
一是把那些能够并发执行的任务放在不同的处理器上以增强并行度;二是把那些需频繁通信的任务置于同一个处理器上以提高局部性。
希望以上资料对你有所帮助,附励志名言3条:
1、理想的路总是为有信心的人预备着。
2、最可怕的敌人,就是没有坚强的信念。
——罗曼·罗兰
3、人生就像爬坡,要一步一步来。
——丁玲
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高性能计算技术 性能 计算 技术 练习题 word 精品 文档 13