§3多处理机的并行和性能

《§3多处理机的并行和性能》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3多处理机的并行和性能并行算法程序并行性分析并行语言与并行编译多处理性能并行算法并行算法的定义和分类多处理机并行算法的研究思路并行算法的定义算法规定了求解某一特定问题时的有穷的运算处理步骤并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作并行算法的分类按运算基本对象：数值型（基于代数运算），非数值型（基于关系运算）按并行进程间的操作顺序不同：同步型，异步型，独立型按计算任务的大小：细粒度，中粒度，粗粒度并行计算的模型PRAM（ParallelRandomAccessMachine）APRAM(AsychromousPRAM)BSP(BulkSyn

2、chronousParallel)logP(Latency,Overhead,Gap,Processor)并行计算的功能降低单个问题求解的时间增加问题求解规模、提高问题求解精度(多机同时执行多个串行程序)容错、更高的可用性、提高吞吐率如何实现并行计算?分而治之!分而治之并行化的主要方法:分而治之根据问题的求解过程，把任务分成若干子任务(任务级并行或功能并行)根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理(数据并行)并行计算基本设计技术划分法(Partitioning)首先，将原问题分成p个独立的近乎大小相等的子问题；其次，用p台处理器并行求解诸子问

3、题。划分的难点在于要留心分解子问题，使得子问题的解很容易被组合成原问题的解。例如(m,n)-selection网络。分治法(Divide-and-Conquer)将原问题规模从大到小逐渐分解成一些特性相同的子问题；直到子问题很容易求解为止。分治很自然地导致递归过程，其注意力集中在子问题地合并上。例如FFT的计算。并行计算基本设计技术（续）平衡树法(BalancedTree)将输入元素作为叶节点构筑一棵平衡二叉树；然后自叶向根往返遍历。此法的优点是在树中能快速存取所需的信息。例如数据播送、求最大/最小值以及求和/前缀计算等。倍增法(Doubling)/指针跳跃法(Poin

4、terJumping)使用递归计算，将需要处理的数据间的距离逐步加倍，经k步后就可以完成距离为2k的所有数据的计算。此法特别适合于处理以链表或有根树之类为数据结构的问题。例如表序问题的计算和求森林根等。并行计算基本设计技术（续）流水线法(Piplining)将原任务t分成一系列子任务t1，t2，…，tm，使得一旦ti完成，后继的子任务就立即开始，并以同样的速率计算之。例如systolic计算。破对称法(SymmetryBreaking)打破某些问题的对称性，使原问题可并行计算。例如有向环图的顶点着色。并行算法常用的设计策略串行算法的直接并行化检测串行算法中固有并行性而直

5、接将其并行化。直接并行化的关键是分析数据执行时的相关性，为此有时需要调整原程序的执行顺序和复制共享变量等。直接并行化并非对所有问题均可行，但对很多应用问题仍不失为一种有效的方法。并非任何优秀的串行算法都可以产生最好的并行算法；相反一个不太好的串行算法则有可能产生很优秀的并行算法。并行算法常用的设计策略（续）设计全新的并行算法从问题本身的描述出发，根据问题的固有属性，从头开始设计一个全新的并行算法，而不管其相关的串行算法。此方法有难度，但通常可产生高效的并行算法。借用已有的算法求解新的一类问题仔细研究两类不同问题求解方法的内在的、直接或间接的相似性，借用已有的求解某问题的

6、并行算法来求解新的一类问题。此方法对初学者有一定难度，但一个好的借用法所设计的算法，往往给人带来深刻的影响，广为传颂。并行算法的一般设计过程划分（Partitioning）：将整个计算分解成一些小的任务，目的是尽量开拓并行性。通信（Communication）：确定诸任务并行执行中通信情况，以检测上述划分粒度的合理性。组合（Agglomeration）：根据性能和代价来考察上两步的结果，必要时组合一些小任务以减小通信开销。映射（Mapping）：将每个任务指派给个处理器，目的是最小化执行时间和最大化处理器利用率。并行算法一般设计过程并行算法的性能分析并行算法的基本性能指

7、标执行时间t(n)和所使用的处理器数p(n)计算成本c(n)=t(n)*p(n)加速比效率Amdahl定律计算负载固定，随着处理器数的增加计算时间将减少。令W是计算负载，Ws是W中的串行分量，Wp是W中的并行分量，f=Ws/W是串行分量比率，则Amdahl加速定律所以即使使用无穷多的处理器，加速也只能是1/fGustafson定律计算时间不变，增加处理器的同时亦要增加计算负载以提高计算精度，则Gustafson加速定律所以加速几乎是线性的。性能损失的原因顺序计算不需要的付出的开销不可并行化的计算部分空闲的处理器对资源的竞争多处理机并行算法