并行计算总复习之秘笈

高性能计算（并行计算）复习提纲第一章并行计算机系统及其结构模型1．了解并行计算机系统互联网络及其分类不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN 1，静态互联网络：是指处理单元之间有着固定连接的一类网络，在程序执行期间，这种点到点的连接不变。

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

2，动态互联网络：是用开关单元构成的，可按应用程序的要求动态的改变连接组态。

典型的动态网络包括总线、交叉开关和多级互连网络等,3，标准互联网络2.并行计算机系统结构，参见图1.20（P23）五种结构，要求理解这几种结构的硬件组成及工作方式。

2，并行计算机系统结构：行向量处理机pvp ：硬件：向量处理机vp、共享存储器SM。

工作方式：高带宽的交叉开关网络将vp连向共享存储模块，存储器可以以兆字节每秒的速度想处理器提供数据。

通常使用向量寄存器和指令缓冲器。

对称多处理机SMP：硬件：商品微处理器（具有片上或外设高速缓存）、共享存储器、I/O设备。

工作方式：微处理器由总线或交叉开关连向共享存储器。

每个处理器可同等的访问共享存储器、I/O设备和操作系统服务。

ＭPP一般是指超大型计算机系统，它具有如下特性：①处理节点采用商品微处理器；②系统中有物理上的分布式存储器；③采用高通信带宽和低延迟的互连网络；④能扩放至成百上千乃至上万个处理器；⑤它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用DSM分布式共享存储多处理机高速缓存目录DIR用以支持分布高速缓存的一致性。

ＤＳＭ和ＳＭＰ的主要差别是，ＤＳＭ在物理上有分布在各节点中的局存从而形成了一个共享的存储器。

对用户而言，系统硬件和软件提供了一个单地址的编程空间.COW工作站机群机群往往是低成本的变形的MPP。

COW的重要界线和特征是：①每个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等），一个节点也可以是一台PC或SMP；②各节点通过一种低成本的商品（标准）网络互连（；③各节点内总是有本地磁盘④节点内的网络接口是松散耦合到I/O 总线上的，⑤一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW 的操作系统是工作站ＵＮＩＸ，加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等。

并行算法》课程总结与复习Ch1 并行算法基础1.1并行计算机体系结构并行计算机的分类SISD,SIMD,MISD,MIMD ； SIMD,PVP,SMP,MPP,COW,DSM 并行计算机的互连方式静态： LA（LC）,MC,TC,MT,HC,BC,SE动态： Bus, Crossbar Switcher, MIN（Multistage InterconnectionNetworks）1.2并行计算模型PRAM 模型： SIMD-SM ，又分 CRCW（CPRAM,PPRAM,APRAM）,CREW,EREWSIMD-IN 模型： SIMD-DM异步 APRAM 模型： MIMD-SMBSP模型：MIMD-DM，块内异步并行，块间显式同步LogP 模型： MIMD-DM ，点到点通讯1.3并行算法的一般概念并行算法的定义并行算法的表示并行算法的复杂度：运行时间、处理器数目、成本及成本最优、加速比、并行效率、工作量并行算法的 WT表示：Brent定理、WT最优加速比性能定律并行算法的同步和通讯Ch2 并行算法的基本设计技术基本设计技术平衡树方法：求最大值、计算前缀和倍增技术：表序问题、求森林的根分治策略： FFT 分治算法划分原理：均匀划分（PSRS排序）、对数划分（并行归并排序）、方根划分（Valiant归并排序）、功能划分（（m,n）-选择）流水线技术：五点的 DFT 计算Ch3 比较器网络上的排序和选择算法3.1Batcher归并和排序0-1 原理的证明奇偶归并网络：计算流程和复杂性（比较器个数和延迟级数）双调归并网络：计算流程和复杂性（比较器个数和延迟级数）Batcher排序网络：原理、种类和复杂性3.2（m, n）-选择网络分组选择网络平衡分组选择网络及其改进Ch4 排序和选择的同步算法4.1一维线性阵列上的并行排序算法4.2二维Mesh上的并行排序算法ShearSort排序算法Thompson&Kung 双调排序算法及其计算示例4.3Sto ne双调排序算法4.4Akl并行k-选择算法：计算模型、算法实现细节和时间分析4.5Valia nt并行归并算法：计算模型、算法实现细节和时间分析4.7 Preparata并行枚举排序算法：计算模型和算法的复杂度Ch5 排序和选择的异步和分布式算法5.1MIMD-CREW 模型上的异步枚举排序算法5.2MIMD-TC 模型上的异步快排序算法5.3分布式k-选择算法Ch6 并行搜索6.1单处理器上的搜索6.2SIMD 共享存储模型上有序表的搜索：算法6.3SIMD 共享存储模型上随机序列的搜索：算法6.4树连接的 SIMD 模型上随机序列的搜索：算法6.5网孔连接的 SIMD 模型上随机序列的搜索：算法和计算示例Ch8 数据传输与选路8.1引言信包传输性能参数维序选路（X-Y选路、E-立方选路）选路模式及其传输时间公式8.2单一信包一到一传输SF和CT传输模式的传输时间（一维环、带环绕的Mesh、超立方）8.3一到多播送SF和CT传输模式的传输时间（一维环、带环绕的Mesh、超立方）及传输方法8.4多到多播送SF和CT传输模式的传输时间（一维环、带环绕的Mesh、超立方）及传输方法8.5贪心算法（书 8.2）二维阵列上的贪心算法蝶形网上的贪心算法8.6随机和确定的选路算法（书 8.3）Ch12 矩阵运算12.1矩阵的划分：带状划分和棋盘划分，有循环的带状划分和棋盘划分12.2矩阵转置：网孔和超立方连接的算法及其时间分析12.3矩阵向量乘法带状划分的算法及其时间分析棋盘划分的算法及其时间分析12.4矩阵乘法简单并行分块算法Cannon算法及其计算示例Fox 算法及其计算示例 DNS 算法及其计算示例 Systolic 算法Ch13 数值计算13.1稠密线性方程组求解 SIMD-CREW 的上三角方程组回代算法SIMD-CREW 上的 Gauss-Jordan算法MIMD-CREW 上的 Gauss-Seidel算法13.2稀疏线性方程组的求解三对角方程组的奇偶规约求解法Gauss-Seide迭代法的红黑着色并行算法13.3非线性方程的求根Ch14 快速傅立叶变换FFT14.1快速傅里叶变换 (FFT) 离散傅里叶变换 (DFT) 串行 FFT 递归算法及其计算原理串行 FFT 蝶式计算及其蝶式计算流图14.2DFT 直接并行算法SIMD-MT 上的并行 DFT 算法14.3并行 FFT 算法 SIMD-MC 上的 FFT 算法 SIMD-BF 上的 FFT 算法及其时间分析Ch15 图论算法15.1图的并行搜索P-深度优先搜索及其计算示例 p-宽深优先搜索及其计算示例 p-宽度优先搜索及其计算示例15.2图的传递闭包基于布尔矩阵乘积的算法原理计算示例SIMD-CC 上的传递闭包算法15.3图的连通分量基于传递闭包的算法基于顶点合并的算法15.4图的最短路径基于矩阵乘积的算法原理计算示例15.5图的最小生成树 SIMD-EREW 模型上的 Prim 算法算法的时间分析Ch17 组合搜索17.1基于分治法的与树搜索与树并行搜索过程处理器数目与搜索效率关系17.2基于分枝限界法的或树搜索串行分枝限界法示例: 0-1 背包问题,8- 谜问题及其搜索算法的并行化 TSP问题的分枝限界算法及其并行化Ch18 随机算法18.1引言基本知识：随机算法的定义、分类时间复杂性度量设计方法18.2低度顶点部分独立集串行算法随机并行算法及其正确性证明18.5多项式恒等的验证基本原理和方法矩阵乘积的验证原理。

复习要点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.指令并行：指令并行是将一个计算任务分解为多个子任务，并且在多个处理器或计算机上同时执行。

每个处理器或计算机负责执行一部分指令，并将结果传递给下一个处理器或计算机继续执行。

指令并行可以提高计算效率，尤其适用于需要大量指令执行的任务，如矩阵运算和神经网络训练。

4.流水线并行：流水线并行是将一个计算任务分解为多个阶段，并且在多个处理器或计算机上同时执行不同的阶段。

每个处理器或计算机负责执行一个阶段，并将结果传递给下一个处理器或计算机继续执行下一个阶段。

流水线并行可以将计算任务分解为多个独立的部分，并在同时执行的情况下提高计算效率。

5.任务分解和调度：任务分解和调度是将一个大任务分解为多个小任务，并且将这些小任务分配给不同的处理器或计算机执行。

任务分解和调度可以根据任务的特性和处理器或计算机的性能自动选择最优的分解和调度策略，以提高计算效率和加快计算速度。

6.数据划分和通信：数据划分和通信是将大规模的数据划分为多个小块，并且在多个处理器或计算机之间进行数据交换和通信。

并行计算总复习题型：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.任务划分策略在进行任务划分时，需要考虑任务之间的依赖关系和数据的共享情况。

可以采用自顶向下或者自底向上的划分策略，将任务分解为更小的子任务，使得子任务之间的依赖关系更加简单和清晰。

同时，还可以根据任务之间的依赖关系和通信模式，采用分层划分或互换划分的方式，减少通信和同步的开销。

二、通信与同步优化在大规模并行计算中，通信和同步操作往往是影响计算性能的重要因素，因此需要通过一些优化技巧来减小通信和同步的开销。

1.减少通信量可以通过减少通信量来减小通信的开销。

可以采用聚集通信和分散通信的方式，将多个小消息合并成一个大消息进行发送，从而减少通信的次数和开销。

此外，还可以通过数据压缩、数据过滤等方法来减小通信数据的大小，提高通信效率。

2.异步通信在进行通信操作时，可以采用异步通信的方式进行。

异步通信可以使发送和接收操作重叠，从而提高计算和通信的效率。

异步通信可以通过非阻塞操作、回调函数等方式来实现。

并行计算：使用并行计算提高计算效率的技巧和方法并行计算是一种通过同时处理多个任务或部分任务来提高计算效率的方法。

在计算机科学领域中，随着数据量不断增大和计算需求不断增加，传统的串行计算方式已经无法满足要求。

因此，并行计算技术成为了一种重要的解决方案。

并行计算的主要优点包括：提高计算效率、减少计算时间、增加计算容量、降低成本等。

利用多核处理器、集群、云计算等技术，可以实现并行计算。

以下是一些提高并行计算效率的技巧和方法：1.任务分解：将大任务分解成多个子任务，然后同时执行这些子任务，提高整体计算效率。

在任务分解过程中，要考虑到任务之间的依赖关系和数据之间的传输延迟，避免出现资源竞争和数据不一致的情况。

2.负载均衡：合理分配任务给不同的处理单元，避免出现某一处理单元负载过重而导致整体性能下降的情况。

负载均衡可以通过动态调整任务分配策略来实现，根据任务的执行情况进行监控和调整。

3.数据传输优化：在并行计算过程中，数据传输往往是影响计算效率的关键因素之一。

通过减少数据传输量、优化数据传输路径、减少数据传输延迟等方法，可以提高计算效率。

4.并行编程模型：选择合适的并行编程模型对于提高计算效率至关重要。

常见的并行编程模型包括MPI、OpenMP、CUDA等，根据具体的应用场景和硬件平台选择合适的并行编程模型可以提高计算效率。

5.并行算法设计：设计并行算法时，需要考虑到并行计算的特点，合理利用并行计算资源，减少通信开销和数据冗余，提高算法并行度和并行效率。

6.硬件优化：在进行并行计算时，选择合适的硬件设备也非常重要。

优化硬件配置、选择性能强劲的处理器和内存、使用高速网络连接等方法可以提高并行计算效率。

7.并行计算框架：利用现有的并行计算框架如Hadoop、Spark等，可以简化并行计算的开发流程，提高开发效率，同时也能够提高计算效率。

8.任务调度策略：合理的任务调度策略能够有效地利用计算资源，避免资源浪费和资源竞争，提高整体计算效率。

并行计算总复习第一章：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.1、用向量语言VFORTRAN，把一维数组A（0：1000）的所有元素均置成PAI；A（0：1000）= PAI1.2、用向量语言VFORTRAN，把一维数组A（-1：1000）的第偶数号元素减少1；1.3、用向量语言VFORTRAN，把一维数组A（0：1000）的第奇数号元素置成其原值立方的正弦；A（1：1000:2）= sin( A（1：1000:2）**3)1.4、已知一维数组A（－1000：999）。

对于每个元素，倘若其正切值不超过立方值，则令原值减半；否则，令原值加倍。

用向量语言VFORTRAN的语句，描述之。

1.5、在下面的PFORTRAN 主程序段里，标记出并行语句和并行进程名，并指出可能的最大并行数目。

1 program matmul2 external init_matrix, mul_matrix, prt_matrix3 shared_distributed c : block4 parameter(SIZE=32768)5 integer a(SIZE,SIZE), b(SIZE,SIZE), c(SIZE,SIZE)6 call init_matrix(a,b)7 call m_set_procs(SIZE÷32)8 call mg_fork(mul_matrix(a,b))9 call m_kill_procs()10 call prt_matrix(a,b,c)11 end1.6、在分辨率为SIZE*SIZE(SIZE为2的幂)的黑白带灰度的显示屏幕上：左上角为坐标原点，Ｘ轴向下，Ｙ轴向右；０为白，１为黑。

用NUMNODES(亦为2的幂，且<SIZE/4)个并行节点把现有的图象(位图表示)map[0:SIZE-1,0:SIZE-1]加以变换。

Map的初值：map[i][j]=(i+j)/(2*(SIZE-1))……0≦i,j<SIZE主进程：for (I=0,row=0;I<NUMNODES;I++,row+=SIZE/NUMNODES)send(row,Pi);for (I=0;I<SIZE**2;I++){ recv(oldrow,oldcol,newvalue,Pany);temp_map[oldrow][oldcol] = newvalue;}for (I=0;I<SIZE;I++)for (j=0;j<SIZE;j++)map[I][j]=temp_map[I][j];从进程：recv(row,Pmaster);for (oldrow=row;oldrow<(row+SIZE/NUMNODES);oldrow++)for (oldcol=0;oldcol<SIZE;oldcol++){newrow=oldrow÷4*4;newcol=oldcol÷4*4; /*÷是整除运算符*/newvalue=map[newrow][newcol];send (oldrow,oldcol,newvalue,Pmaster);}6.1、在卷面上标记出消息发送语句；6.2、在卷面上标记出消息接收语句，以及与之配对的消息发送语句。

计算机学院研究生《并行计算》课程考试试题（2010级研究生，2011.1）1．（12分）定义图中节点u和v之间的距离为从u到v最短路径的长度。

已知一个d维的超立方体，1）指定其中的一个源节点s，问有多少个节点与s 的距离为i，其中0≤i≤d。

证明你的结论。

2）证明如果在一个超立方体中节点u与节点v的距离为i，则存在i！条从u到v的长度为i的路径。

i C i。

个节点与s 1)有的距离为d证明：由超立方体的性质知：则与某个节d位二进制来表示，一个d维的超立方体的每个节点都可由点的距离为i的节点必定在这d位二进制中有i位与之不同，那么随机从d ii CC得节点就有位就有个。

种选择方式，即与s的距离为i位中选择i dd2)证明：由1）所述可知：iv节点的二进制位数中有iv的距离为则分别表示u、节点u与节点DD...D...D...D D表示为：v，设节点位是不同的。

u表示为：节点dj?ij1?2ij?1''D...DD...D D D...，则现在就是要求得从dj?2i?1j?ji1''D...DD...D...D D D D D...D...D...D的途径有多变换到d2?j1j?i?ij1d?j?i12?1jij i*(i?1)*(i?2)*...*2*1i!中途少种。

那么利用组合理论知识可知共有即径。

所以存在i！条从u到v的长度为i的路径。

2．（18分）6个并行程序的执行时间，用I-VI表示，在1-8个处理器上执行了测试。

下表表示了各程序达到的加速比。

对其中的每个程序，选出最适合描述其在16个处理器上性能的陈述。

a）在16个处理器上的加速比至少比8个处理器上的加速比高出40%。

b）由于程序中的串行程序比例很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。

c）由于处理器增加时开销也会很大，在16个处理器上的加速比不会比8个处理器上的加速比高出40%。