《华工综合的高性能复习题集（考试复习用）》由会员分享，可在线阅读，更多相关《华工综合的高性能复习题集（考试复习用）（19页珍藏版）》请在金锄头文库上搜索。
1、 华工综合的高性能复习题2008 年11 月1. 解释以下基本概念 HPC, HPCC, Distributed computing, Meta computing, Grid computing MIMD, SIMD, SISD PVP, SMP,MPP, DSM, Cluster, Constellation UMA, NUMA, CC_NUMA, CORMA, NORMAHPC:高性能计算是计算机科学的一个分支，研究并行算法和开发相关软件，致力于开发高性能计算机（High Performance Comput
2、er）。计算密集型（Compute-Intensive）应用数据密集型（Data-Intensive）应用网络密集型（Network-Intensive）应用HPCC：高性能计算和通信（ High-Performance Computing andCommunications： HPCC） 分布式高性能计算、高速网络和Internet的使用分布式计算（Distributed Computing） 更着重于功能而不是性能的增加网格计算（Grid Computing） 分布式高性能计算（Distributed, High Performa
3、nce Computing：DHPC），或称元计算（Metacomputing）单指令单数据流：SISD 普及程度：MIMD SIMD MISD单指令多数据流：SIMD 多指令单数据流： MISD 多指令多数据流： MIMDn 对称多处理共享存储并行机（SMP：Symmetric MultiProcessing）；n 分布共享存储并行机（DSM：Distributed Shared Memory）；n 大规模并行机（MPP：Massively Parallel Processors）；n 工作站（微机）机群（COW：Cluster Of Workstation、Beowulf PC-Clust
4、er）；n 并行向量多处理机（PVP：Parallel Vector Processors）均匀访存模型（UMA：Uniform Memory Access）非均匀访存模型（NUMA：Nonuniform Memory Access）Cache一致性非均匀访存模型（CC-NUMA：Coherent-Cache Nonuniform Memory Access）分布式访存模型（DMA：Distributed Memory Access）2. 试比较PVP、SMP、MPP、DSM 和Cluster 并行机结构的不同点，以典型系统举例说明。SMP：对称多处理器，共享存储，高速缓存一致性，低通信延迟，
5、不可扩放性SSMP：可扩放共享存储多处理机，共享存储，扩放性好CC-NUMA：非均匀存储访问，高速缓存一致性，扩放性好MPP：大规模处理器数，分布存储，使用物理分布的存储器和I/O，扩放性好DSM：存储器物理分布，通过目录实现共享存储3. 列出常用静态和动态网络的主要参数（节点度、直径、对剖带宽和链路数）以及复杂度、网络性能、扩展性和容错性等。常用的标准互联网络有哪些？并行机规模：并行机包含的结点总数，或者包含的CPU总数；结点度：互联网络拓扑结构中联入或联出的一个结点的边的条数，称为该结点的度；结点距离：两个结点之间跨越的图的边的条数；网络直径：网络中任意两个结点之间的最长距离；点对点带宽：
6、图中边对应的物理联接的物理带宽；点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟；折半宽度：对分网络成两个部分（它们的结点个数至多相差1）所必须去掉的边的网络带宽的总和；总通信带宽：所有边的带宽之和快速以太网、FDDI、Switcher、ATM、Myrinet 、nfiniband、Qudrics、HiPPI4. 比较UMA、NUMA（CC-NUMA、COMA、NCC-NUMA）和NORMA 存储器体系结构的主要特征，并以典型系统来说明其优缺点。UMA（Uniform
7、 Memory Access）模型是均匀存储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；所有处理器访问任何存储字取相同的时间；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。 NUMA(Nonuniform Memory Access)模型是非均匀存储访问模型的简称。特点是：被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；处理器访问存储器的时间是不一样的；访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)；每台处理器照例可带私有高速缓存，外设也可以某种形式共
8、享COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；利用分布的高速缓存目录D进行远程高速缓存的访问;COMA中的高速缓存容量一般都大于2 级高速缓存容量；使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。 CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的简称。其特点是：大多数使用基于目录的高速缓存一致性协议；保留SMP结构易于编程的优点，也改善常规SMP的可扩
9、放性；CC-NUMA实际上是一个分布共享存储的DSM多处理机系统；它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。 NORMA（No-Remote Memory Access）模型是非远程存储访问模型的简称。NORMA的特点是：所有存储器是私有的；绝大数NUMA都不支持远程存储器的访问；在DSM中，NORMA就消失了。 5. 比较并行计算模型PRAM、BSP 和logP。评述它们的差别、相对优点以及在模型化真实并行计算机和应用时的局限性。PRAM模型 由Fortune和Wyllie1
10、978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素BSP模型由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。 p：处理器数(带有存储器) l：同步障时间(Barrier synchronization time) g：带宽因子(time steps/packet)=1/bandwidth 计算过程由若干超级步组成，
11、 每个超级步计算模式为左图优缺点强调了计算和通讯的分离， 提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递等。logP模型由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。模型参数L：network latencyo：communication overheadg：gap=1/bandwidthP：#processors注：L和g反映了通讯网络的容量 优缺点 捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述
12、、设计和分析。 BSP vs. LogP BSPLogP：BSP块同步BSP子集同步BSP进程对同步LogP BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSPBSPLogP+BarriersOverheadBSP提供了更方便的程设环境，LogP更好地利用了机器资源BSP似乎更简单、方便和符合结构化编程 6. 比较在PRAM 模型和BSP 模型上，计算两个N 阶向量内积的算法及其复杂度。设两个向量分别为A 和BPRAM：Step1 :每个处理器处理A的N/P个数值和B的N/P个数值，共N/P次乘法和N/P次加法Setp2：按照树递归方法计算局部和，共logPBSP:2n/P+log
13、P*g+logP*l+logP7. 什么是加速比（speed up）、并行效率（efficiency）和可扩展性（scalability）? 如何描述在不同约束下的加速比？约束条件：8. 如何进行并行计算机性能评测？什么是基准测试程序？P95基准测试程序(Benchmark)用于测试和预测计算机系统的性能,揭示不同结构机器的长处和短处,为用户决定购买或使用那种机器最合适他们的应用要求提供决策。/9. 什么是可扩放性测量标准？等效率函数的涵义是什么？什么是可扩放性测量标准：等效率测度（ ffi i i ） Efficiency Metrics） 效率：加速比/处理器数
14、48766; 简单情况下能得分析结果 等速度测度（Speed Metrics） 速度：每秒处理的数据量 便于通过实验数据得到结果 平均时延测度（Latency Metrics） 时延：理想并行时间与实际并行时间的差距 便于通过实验数据得到结果等效率函数的涵义：如果问题规模W 保持不变，处理器数p增加，开销To增大，效率E下降。为了维持一定的效率（介于0与1之间），当处理数p增大时，需要相应地增大问题规模W的值由此定义函数f E( P)为问题规模W随处理器数变化。fE(p)p的函数，为等效率函数。 10. 什么是分治
15、策略的基本思想？举例说明如何应用平衡树方法、倍增技术、和流水线技术。并行算法的基本设计技术 平衡树方法 倍增技术 分治策略 划分原理 流水线技术什么是分治策略的基本思想：将原问题划分成若干个相同的子问题分而治之，若子问题仍然较大，则可以反复递归应用分治策略处理这些子问题，直至子问题易求解。举例说明如何应用平衡树方法：设计思想 树叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层并行处理。 示例 P149求最大值计算前缀和举例说明如何应用倍增技术：设计思想又称指针跳跃(pointer jumping)技术，特别适合于处理链表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为2k的所有数据的计算。示例 表序问题P152 运行时间：t(n) =O(logn) p(n)=n（算法6 10）p(n)是处理器数目求森林的根P
