1、3 多处理机的并行和性能 n 并行算法 n 程序并行性分析 n 并行语言与并行编译n 多处理性能并行算法n 并行算法的定义和分类n 多处理机并行算法的研究思路并行算法的定义n 算法规定了求解某一特定问题时的有穷的运算处理步骤n 并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作并行算法的分类n 按运算基本对象：数值型（基于代数运算），非数值型（基于关系运算）n 按并行进程间的操作顺序不同：同步型，异步型，独立型n 按计算任务的大小：细粒度，中粒度，粗粒度并行计算的模型n PRAM（ Parallel Random Access Machine）n APRAM(Asychr
2、omous PRAM) n BSP(Bulk Synchronous Parallel)n logP(Latency, Overhead, Gap, Processor)并行计算的功能n 降低单个问题求解的时间n 增加问题求解规模、提高问题求解精度n (多机同时执行多个串行程序 )容错、更高的可用性、提高吞吐率如何实现并行计算 ? 分而治之 !分而治之n 并行化的主要方法 :分而治之n 根据问题的求解过程，把任务分成若干子任务 (任务级并行或功能并行 )n 根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理 (数据并行 )并行计算基本设计技术 n 划分法 (Partition
3、ing) n 首先，将原问题分成 p个独立的近乎大小相等的子问题；其次，用 p台处理器并行求解诸子问题。n 划分的难点在于要留心分解子问题，使得子问题的解很容易被组合成原问题的解。n 例如 (m, n)-selection网络 。n 分治法 (Divide-and-Conquer) n 将原问题规模从大到小逐渐分解成一些特性相同的子问题；直到子问题很容易求解为止。n 分治很自然地导致递归过程，其注意力集中在子问题地合并上。n 例如 FFT的计算 。并行计算基本设计技术（续）n 平衡树法 (Balanced Tree) n 将输入元素作为叶节点构筑一棵平衡二叉树；然后自叶向根往返遍历。n 此法的优点是在树中能快速存取所需的信息。n 例如数据播送、求最大 /最小值以及求和 /前缀计算等。 n 倍增法 (Doubling)/指针跳跃法 (Pointer Jumping)n 使用递归计算，将需要处理的数据间的距离逐步加倍，经 k步后就可以完成距离为 2k的所有数据的计算。n 此法特别适合于处理以链表或有根树之类为数据结构的问题。n 例如表序问题的计算和求森林根等。
