并行计算考试复习

并行计算期末试题及答案1. 基础概念部分并行计算是一种计算模式，它使用多个处理单元同时执行计算操作，以加快计算速度。

在现代计算机系统中，我们常常使用多核处理器、图形处理器（GPU）或者分布式系统来实现并行计算。

1.1 并行计算的优势并行计算具有以下几个优势：加速计算速度：通过同时执行多个计算任务，可以极大地提高计算效率。

解决大规模问题：并行计算可以处理大规模和复杂的问题，提供更精确的结果。

降低能耗：通过合理利用处理器资源，可以降低计算任务的能耗。

应用广泛：并行计算可以应用于各个领域，如科学计算、大数据分析、机器学习等。

1.2 并行计算的分类并行计算按照任务之间的关系可以分为两类：数据并行：将数据划分为多个子集，同时在不同的处理器上进行计算，然后将计算结果汇总。

常见的应用包括矩阵运算、图像处理等。

任务并行：将任务划分为多个子任务，每个子任务由一个独立的处理器执行，最后将各个子任务的结果合并。

常见的应用包括并行搜索算法、并行排序等。

2. 并行计算的算法设计2.1 并行算法设计要点在设计并行算法时，需要考虑以下几个要点：任务划分：将计算任务划分为多个子任务，确保各个子任务之间的计算工作均衡，并保持任务之间的独立性。

任务调度：合理安排各个处理器上的任务执行顺序和时间，最大程度地减少通信开销和等待时间。

数据通信：处理器之间需要进行数据交换和通信，应选择合适的通信方式，并考虑通信延迟和带宽等因素。

数据同步：在多个处理器之间，可能需要进行数据同步操作，确保各个处理器之间的数据一致性。

2.2 并行算法实例：并行矩阵乘法并行矩阵乘法是一个常见的数据并行算法，可以有效地利用多核处理器加速大规模矩阵运算。

具体算法如下：步骤1：将输入矩阵划分为若干个小矩阵，每个小矩阵分配给一个处理器。

步骤2：每个处理器计算相应小矩阵的部分结果。

步骤3：将各个处理器计算得到的部分结果进行求和，得到最终的矩阵乘积结果。

3. 并行计算的应用举例3.1 科学计算在科学计算领域，有大量的计算任务需要处理大规模的数据和复杂的数学模型。

中国海洋⼤学研究⽣并⾏计算参考答案-复习⼀、名词术语翻译1）SIMD ：Single Instruction Multiple Data, 单指令多数据流。

2）MIMD ：Multiple Instruction Multiple Data, 多指令多数据流。

3）SIMT ：Single Instruction Multiple Threads, 单指令多线程。

4）SPMD ：Single Program Multiple Data, 单程序多数据流。

5）MPMD ：Multiple Program Multiple Data, 多程序多数据流。

6）PVP ：Parallel Vector Processor, 并⾏向量处理机。

7）SMP ：Symmetric Multiprocessor, 对称多处理机。

8）MPP ：Massively Parallel Processor, ⼤规模并⾏处理机。

9）DSM ：Distributed Shared Memory, 分布式共享存储。

10）COW ：Cluster of Workstation, ⼯作站机群。

11）UMA ：Uniform Memory Access, 均匀存储访问模型。

12）NUMA ：Nonuniform Memory Access, ⾮均匀存储访问模型。

13）COMA ：Cache-Only Memory Access, 全⾼速缓存访问模型。

14）NORMA ：No-Remote Memory Access, ⾮远程存储访问模型。

15）CC-NUMA ：Coherent-Cache Nonuniform Memory Access, ⾼速缓存⼀致性⾮均匀存储访问模型。

16）CUDA ：Compute Unified Device Architecture, 统⼀计算架构。

17）GPU ：Graphics Process Unit, 图形处理器。

复习要点1、Parallel computing并行计算，sequential computing串行计算，instruction指令，multiple多数据，communication通信，exclusive互斥，concurrent 并发，recursive递归，data数据，exploratory探索，speculative投机，block cyclic循环块，randomized block随机块，distribution分配，graph partitioning 图划分，speedup加速比，efficiency效率，cost费用，Amdahl’s law，architecture构架，fundimental functions基本函数，synchronization同步，matrix mulitiplication矩阵乘，matrix transposition 矩阵转置，bitonci sorting双调排序，odd-even sorting奇偶排序，Shortest path，minimum spanning tree，connected components，maximal independent set，2、SMP（对称多处理机连接）MPP (Massive Parallel Processors 大规模并行）Cluster of Workstation（工作站机群）Parallelism（并行化）, pipelining（流水线技术）, Network topology（网络拓扑结构）, diameter of a network（网络直径）, bisection width（对分宽度）, data decomposition（数据分解）, task dependency graphs（任务依赖图）, granularity（粒度）, concurrency（并发）, process（进程）, processor（处理器）, linear array（线性阵列）, mesh（格网）, hypercube（超立方体）, reduction（规约）, prefix-sum（前缀和）, gather（收集）, scatter（散发）, threads（线程）, mutual exclusion（互斥）, shared address space（共享地址空间）, synchronization（同步）, the degree of concurrency（并发度）, Dual of a communication operation（通信操作的对偶操作）3、并行计算与串行计算在算法设计主要不同点：(1)具有强大的处理器互连关系(2)并行计算依赖并行计算模型上的，如共享内存，共享地址空间或消息传递。

并行计算总复习题型：1．问答题；2．算法描述；3．走例子说明对算法的理解第二章SIMD 和MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。

SPMD的含义是什么？若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？在理想并行计算模型中（parallel random access machine(PRAM), EREW, CREW, 和CRCW表示的意思是什么？能画出多处理机系统中处理单元的基本互连结构图，Mash, hypercube, 网络，对静态网络的测度：直径，连通性，二分宽度(bisection width), cost.能说出一种解决多处理器系统中cache和内存数据一致性问题的方法。

能给出store-and-forward routing 和cut-through routing的思想通讯费用是如何计算的？延迟时间，t s, t h, t w对Mesh 的X-Y_routing和对Hypercube的E-Cube routing的路由规则。

如何把linear array, mesh 和hypercube 相互嵌入？G(i,d)函数的计算。

把复杂网络嵌入的简单网络，能说明些什么问题？其意义是什么？一般对简单网络的带宽是怎么要求的？第三章dependency graph 的定义及画法。

对同一问题dependency graph 的画法是否唯一？并行算法的粒度定义是什么？把processes 影射到processors的基本原则是什么？减少通讯，…,在并行算法设计时，有几种把计算分解的技术？能举例说明。

能说明data parallel model, task graph model 和work pool model 的含义。

第四章Basic communication operations能画出下列操作的示意图one to all broadcast; all to one reductionall to all broadcast; all to all reductionscatter, gather, all reduce, prefix sum，all to all personalized communication. Circular shift,能写出在hypercube上的one to all broadcast/ all to one reductionall-to-all personal broadcast;all-to-all broadcast;算法以及时间复杂性的分析。

并行计算总复习第一章：1并行计算与串行计算在算法和编程上有哪些显著差异？答：·并行算法设计与并行计算机处理器的拓扑连接相关·并行算法设计和采用的并行计算模型有关。

·并行计算有独自的通讯函数·并行算法设计时，如何将问题分解成独立的子问题是科学研究问题，并非所有的问题都可以进行分解。

2多核与多处理机的异同点？多处理机：把多个处理器通过网络互连形成一个新机器。

可以是专用，也可以是通用。

拓扑连接是可以改变的。

多核：在过去单个处理器芯片上实现多个“执行核”。

但这些执行核都有独立的执行命令集合和体系结构。

这些独立的执行核+超线程SMT技术组成多核处理器3对单处理器速度提高的主要限制是什么？答：晶体管的集成密度，功耗和CPU表面温度等第二章1 SIMD 和MIMD 所代表的计算模型是什么？主要区别和各自的系统结构示意图。

SPMD的含义是什么？SIMD指单指令多数据流模型；MIMD指多指令多数据流模型；SPMD指单程序多数据流模型，在SIMD中把指令改为程序表示每个处理器并行的执行程序。

SIMD MIMD硬件较少处理器较多处理器内存一个寻址系统，存储量小多个寻址系统，存储量大耗费较高，难开发易于开发（多个商业组件可用）加速高取决于应用2 若按通讯方式对并行算法进行分类有几种分类方法，各自的特点是什么？基于共享地址空间：并行平台支持一个公共的数据空间，所有处理器都可以访问这些空间。

处理器通过修改存储在共享地址空间的数据来实现交互。

基于消息传递：消息传递平台有p个处理节点构成，每个节点有自己的独立地址空间。

运行在不同节点上的进程之间的交互必须用消息来完成，称为消息传递。

这种消息交换用来传递数据、操作以及使多个进程间的行为同步。

3 在理想并行计算模型中（并行随机访问计算机parallel random access machine(PRAM), EREW, ERCW CREW, 和CRCW表示的意思是什么？EREW：互斥读互斥写，这一类的PRAM独占访问内存单元，不允许并发的读写操作。

1.并行算法:一些可同时执行的诸进程的集合，这些进程相互作用和相互协调。

2.并行与并发的关系：并行<并发并发是指两个或者多个事件在同一时间间隔内发生。

在单处理机系统中，每一时刻仅能有一道程序执行，宏观上多道程序在同时运行，微观上这些程序是分时交替执行。

3.并行与分布式的关系：网络；并行更注重性能，而分布式更注重透明共享。

4.并行与网格计算（普适计算）的关系：网格通过网络连接地理上分布的各类计算资源、存储资源、通信资源、软件资源、信息资源、知识资源等，形成对用户相对透明的虚拟的高性能计算环境，让人们透明地使用这些资源和功能。

它们与并行计算存在规模上的差异。

5.并行与云计算的关系：云计算以开放的标准和服务为基础，以互联网为中心，提供安全、快速、便捷的数据存储和网络计算服务，让互联网这片“云”上的各种计算机共同组成数个庞大的数据中心及计算中心。

云计算把计算及存储以服务的形式提供给互联网用户，用户所使用的数据、服务器、应用软件、开发平台等资源都来自互联网上的虚拟化计算中心，该数据中心负责对分布在互联网上的各种资源进行分配、负载的均衡、软件的部署、安全的控制等。

6.为什么要研究并行算法？（1）CPU的发展速度：Moore Law。

（2）“深蓝”计算机以3.5:2.5战胜卡斯帕罗夫。

（3）需求：快速（天气预报），提高计算精度，与理论、实验并重的科学方法（代替核武器实验）7.并行计算机分类1. SISD,Single Instruction Stream & Single Data Stream:特征：串行的和确定的。

指令系统: CISC, RISC2. SIMD,Single Instruction Stream & Multiple Data Stream:特征：同步的；确定的；适合于指令/操作级并行。

1)阵列处理机（资源重复）;2)流水线处理机（时间重叠）.3. MISD,Multiple Instruction Stream & Single Data Stream :4. MIMD,Multiple Instruction Stream & Multiple Data Stream共享存储MIMD，也称对称多处理机（SMP，Symmetry MultiProcessors），属于紧密耦合的多处理机系统适合于小粒度并行分布式共享存储MIMD，也称为非一致内存访问（NUMA, Non-Uniform Memory Access），属于松耦合的多处理机系统（共享虚拟存储技术）,适合于中小粒度并行分布式存储MIMD1).大规模并行系统MPP (Massively Parallel Processing)CM-5、曙光1000、神州-Ⅱ巨型机可以最大限度地增加处理机的数量，但结点间需要依赖消息传递进行通信，适合于中小粒度并行2).群集系统Cluster特点：适合于粗粒度并行8.网络直径（network diameter）：网络中最远的两台处理机间的距离，即处理机间通信所需要跨越的网络边的条数的最大值。

并⾏计算考试复习1在并⾏机系统中，主流操作系统有UNIX/Linux，AIX(IBM)，HPUX(HP)，Solaris(SUN)，IRIX(SGI)等。

2 常⽤的并⾏算法设计的基本技术有划分，分治，倍增，流⽔域，破对称，平衡树等设计技术。

3 Matlab并⾏程序编写过程分为创建对象，创建⼯作，指定⼯作任务，提交⼯作，等待和返回计算任务结果六步。

1. 云计算是对（ D ）技术的发展与运⽤A. 并⾏计算 B⽹格计算 C分布式计算 D三个选项都是2. IBM在2007年11⽉退出了“改进游戏规则”的（ A ）计算平台，为客户带来即买即⽤的云计算平台。

A. 蓝云B. 蓝天C. ARUZED. EC23. 微软于2008年10⽉推出云计算操作系统是（ C ）A. Google App EngineB. 蓝云C. AzureD. EC24. 2008年，（ A ）先后在⽆锡和北京建⽴了两个云计算中⼼A. IBMB. GoogleC. AmazonD. 微软5. 将平台作为服务的云计算服务类型是（ B ）A. IaaSB.PaaSC.SaaSD.三个选项都不是6. 将基础设施作为服务的云计算服务类型是（ A ）A. IaaSB.PaaSC.SaaSD.三个选项都不是7. IaaS计算实现机制中，系统管理模块的核⼼功能是（ A ）A. 负载均衡 B 监视节点的运⾏状态 C应⽤API D. 节点环境配置8. 云计算体系结构的（ C ）负责资源管理、任务管理⽤户管理和安全管理等⼯作B. 资源池层C. 管理中间件层D. SOA构建层9. 下列不属于Google云计算平台技术架构的是（ D ）A. 并⾏数据处理MapReduceB.分布式锁ChubbyC. 结构化数据表BigTableD.弹性云计算EC210. 在⽬前GFS集群中，每个集群包含（ B ）个存储节点A.⼏百个B. ⼏千个C.⼏⼗个D.⼏⼗万个11. 下列选项中，哪条不是GFS选择在⽤户态下实现的原因（ D ）A.调试简单B.不影响数据块服务器的稳定性C. 降低实现难度，提⾼通⽤性D. 容易扩展12. GFS中主服务器节点存储的元数据包含这些信息（ BCD ）A.⽂件副本的位置信息B.命名空间C. Chunk与⽂件名的映射D. Chunk副本的位置信息13. 单⼀主服务器（Master）解决性能瓶颈的⽅法是（ ABCD ）A.减少其在数据存储中的参与程度B. 不适⽤Master读取数据C.客户端缓存元数据D. 采⽤⼤尺⼨的数据块14. （ B ）是Google提出的⽤于处理海量数据的并⾏编程模式和⼤规模数据集的并⾏运算的软件架构。

ALU Arithmetic Logic Unit 算术逻辑单元Amdahl 定律通过使用某种更快速的执⾏⾏式⾏获得的性能改进受限于这种快速⾏式的使⾏时间在总执⾏时间APIC 高级可编程中断控制器ARM Advanced RISC Machine 进阶精简指令集机器ATR Adaptive Timekeeping Replacement 自适应守时替换算法availability 可用性服务完成状态相对于服务完成和服务中断间隔的一种度量MTTF/MTTF+MTTRAVX Advanced Vector Extensions：高级矢量扩展指令集BCD Binary Coded Decimal 二进制编码的十进制BHR 分支历史记录BPaaS Business Process as a Service 商业流程即服务BTB Branch Target Buffer 分支目标缓冲器CAM Content Addressed Memory 按内容寻址和访问的存储器关联存储器CCNUMA Cade coherent NUMA 带Cache一致性的NUMAcluster 机群由多个完整的计算机通过⾏速⾏络连接起来的特殊操作系统管理可并⾏行⾏作的CMP Chip Multiprocessor 芯片多处理器，多核处理器CMP Chip Multiprocessor 芯⾏片多处理理器在单个硅⾏片内联合两个或更更多个处理理器Computer Architecture 计算机体系结构计算机软硬件的功能分配及其界⾏确定Computer Implement 计算机实现计算机组成的物理实现包括具体的物理电路制造技术及工艺等Computer Organization计算机组成实现系统结构中所描述的功能部件及其功能部件间的互连CPI Cycles Per Instruction：平均时钟周期数Data Hazard 数据冲突：流水线中指令的交叠执⾏使得指令中操作数读写的顺序不同于串⾏执⾏时的顺序DMA Direct Memory Access 直接内存访问DRAM Dynamic Random Access Memory：动态随机存取存储器 SDRAM Synchronous 同步内存EBCDIC Extended Binay Coded Decimal Interchange Code 扩展的二进制编码的十进制EPROM Ereasable Programmable Read only Memory 可擦除可编程只读存储器FLOPS Floating-Point Operations Per Second：每秒浮点操作数GPU Graphics Processing Unit 图形处理单元GRC Governance Risk Management and Compliance 监管⻛险管理遵守Iaas Infrastructure as a Service 基础设施即服务Iaas Infrastructure as a Service 基础设施即服务IC Instruction Count：指令数ILP Instruction Level Parallelism 指令级并行LFU Least Frequently Used：最不经常使用的算法，将使用频率最低的行淘汰利用了块地址流调度的历史信息正确地反映了程序的局部性LRU Least Recently Used：最近最少使用的算法，把近一段时间内使用次数最少的行替换掉MCAPI Multi-core Communication API 多处理器通信应用程序接口MIND 每个处理器取⾏己的指令对⾏己的数据进⾏操作MIPS Million Instructions Per Second：每秒百万指令数MISD ⾏组相同的数据送给多个处理部件每个处理部件执⾏不同的指令序列MMX MultiMedia eXtention：多媒体扩展指令集MPI Message Passing Interface 信息传递接口MPMD Multiple Program Multiple Data 多程序多数据MPP (Massive parallel processing) 海量并行处理结构MTBF Mean Time between Failures：平均故障间隔时间MTTF Mean Time to Failure：平均无故障时间MTTR Mean Time to Repair：平均修复时间NAS Network Attached Storage 连接到⾏络上的带散件管理和通信功能的磁盘阵列拥有自己的cpu和存储管理系统，独⾏立于应⾏用服务器NBin Neuron Buffer in 输入神经元缓存NBout Neuron Buffer out 输入神经元缓存NFU Neural Functional Unit 神经元功能单元NoC Network on Chip 片内互联网络片内的数据转发通信网络是一种集成式的交换网络NSM Neuron Selector Module 神经元选择器模块NUMA Nonuniform Meng Access ⾏均匀内存访问系统OLTP Online Transaction Processing：联机事务处理OPT Optimal replacement algorithm 最优替换算法替换最远的将来才可能使用的行Paas Platform as a Service 平台即服务PaaS Platform as a Service 平台即服务PDP Provable Data Procession 数据的持有性证明PEFU Processing Element Function Unit PE功能单元PHT 预测历史表Pipeline Bubble 流⾏线⾏泡流水线或其部分因条件不允许连续执行而必须停滞pipeline Hazard 流⾏水线冲突阻碍流⾏线正常流水或潜在地导致不正确计算的所有因素Pipeline Interlock 流水线互锁为维持正确的执⾏模式采用停滞或⾏泡⾏法消解数据冲突的一种硬件技术PVM Parallel Virtual Machine 并⻛虚拟机RAID Redundant Array ofIndependent Disks 独⻛磁盘冗余阵列RAW (Read After Write)先写后读冲突-也叫真实依赖或真数据依赖-一条指令写，后续指令读，在写操作完成之前读 WAR ：先读后写冲突，也叫反依赖，一条指令读，后续指令写，在读操作完成之前写WAW：写写冲突，也叫输出依赖，两条写指令，写的顺序与期望顺序相反Reliability 可靠性连续服务完成的一种度量或是从初始运行时刻到发生故障时刻的时间度量RISC Reduced Instruction Set Computer 精简(复杂complex)指令集计算机SaaS Software as a Service 软件即服务SaaS Software as a service 软件即服务SAML Seong Assert on Markup Language 安全断⾏标记语言SAN Storage Area Network ⾏种通过专⾏用⾏速⾏络将一个或多个⾏络存储设备和服务器连接起来的专⾏用存储⾏SB Synapse Buffer 突触缓存SIB Synapse Index Buffer 突触索引缓存SIMD Single Instruction Multiple Data：单指令多数据流相同的一条指令由多个处理部件同时执行使用不SIMT Single Instruction Multiple Theads 单指令多线程SISD Single Instruction Stream Single Data Stream 单处理器执⾏⾏条指令对内存中的单个数据进⾏操作SLA Service Level Agreement 服务级别协议SMP Symmetrical Multiprocessors 对称多处理器集中式的共享内存和所有处理器具有对称关系每个处理器访问内存的时间是一样的SMT Simultaneous Multithreading 并发多线程使单个CPU同时运⾏多个线程SOAP Simple Object Access Protocol 简单对象访问协议SPMD Single Program Multiple Data 单程序多数据SRAM Static Random Access Memory：静态随机存取存储器SSE Streaming SIMD Extensions：流式 SIMD 扩展指令集SSM Synapse Selector Module 突触选择器模块Structural Hazards 资源冲突流水线中两条或两条以上的指令同时使⾏用相同的资源TIPC Transparent Inter-Process Communication 透明的进程间通信TLP Thread Level Parallelism 线程级并行TLS Thread Level Speculation 线程级推测Transparency：透明性，一种本来存在的事物或现象，从某种角度看好像不存在UMA uniform Memory Access 均匀内存访问VLIW Very Long Instruction Word 超长的指令字VLSI Very Large Scale Integration：超大规模集成电路WDM Weight Data Multiplexing 权值多路复用。