数字系统设计及VHDL实践 专题五 专用集成电路 设计中的并行算法 主 讲 人：徐向民 单 位：电子信息学院

本章主要内容 并行算法理论 并行计算理论 并行算法的应用

并行算法简介 什么是并行算法 为什么需要并行 本质是把多任务映射到多处理机中执行，或将实现的多维问题映射到具有特定的拓扑结构的多处理机上求解。 为什么需要并行 同步加快计算速度、提高计算精度、快速时效要求、数值模拟计算； 以空间代价换取时间。

并行算法简介 当今并行算法研究的主要内容 并行算法研究的新机遇与新挑战 当今并行算法主要研究内容包括并行计算模型、并行算法设计技术和并行复杂性理论等。 并行算法研究的新机遇与新挑战 以空间代硬件的不断发展，为研究并行算法带来新的机遇 ； 如何充分利用，又带来了挑战。

并行算法的分类 数值计算并行算法 同步并行算法和异步并行算法 数值计算是指基于代数关系运算的计算问题。 非数值计算是指基于比较关系运算。 同步算法是指某些进程必须等待别的进程的并行算法,要求所有进程必须在一个给定时刻同步； 异步算法是指进程的执行相互独立，一般不必相互等待，根据当前的最新信息决定进程的继续或终止；

并行算法模型 数据并行模型(data-parallel model) 任务图模型(task graph model) 工作池模型(task pool) 主-从模型(maste-slave) 流水线模型(pipeline model) 混合模型

数据并行模型（data-parallel model） 数据并行模型是最简单的算法模型之一,在这种模型中任务被静态或半静态地映射到进程，并且每个任务都对不同数据进行相似的操作 ； 数据并行问题的一个重要特点，就是数据并发度随着问题规模的增加而增加，这样就可以使用更多的进程来有效地解决更大的问题。

任务图模型(task graph model) 在任务图模型中，使用任务之间的相互关系来提高本地性或减少交互开销； 以任务图模型为基础的算法的例子包括快速并行排序、稀疏矩阵分解以及从分治分解中导出的许多并行算法； 这种在任务依赖图中通过独立任务自然表示的并行形式称为任务并行。

工作池模型（task pool） 动态映射任务到进程以保持负载平衡 ； 工作既可以在开始时静态地获得，也可以动态地产生；也就是说，进程可以产生工作并把它添加到全局（也就可能是分布式）工作池中。 在消息传递模式中，当与任务相关的数据量远小于与任务相关的计算量时，通常就使用工作池模型；

主-从模型（master-slave） 在这种模型中，一个或者多个主进程产生任务并分派给工作者进程； 这种模型同样适用于共享地址空间模式或消息传递模式，因为交互是双向的，即管理者知道它要分发任务，而工作者知道它们要从管理者那儿接收任务； 在使用主-从模型时，一定要确保主进程不成为瓶颈，但当任务太小（或工作者相对太快）时会发生这种情况；

流水线模型（ pipeline model ） 在流水线模型中，数据流通过一串进程传递，每一进程执行一个任务 ； 流水线是生产者和消费者链，流水线中的每一进程都可看成它前面进程数据序列的消费者和它后面进程数据的生产者； 负载平衡是任务粒度的函数。粒度越大，填满流水线花费时间就越长，就是说，如果链中第一个进程产生的触发者要传播到最后一个进程，则有些进程必须等待。但是，粒度太小也会增加交互开销，因为进程在小块计算后，必须交互才能接收新的数据。适合于这种模型的最常用技术是重叠交互与计算。

假如完成某一任务需要五步H1，H2，H3，H4，H5；每一步需要一个单位的时间。 现在需要完成五个同样的任务，提供五个处理器来完成。 任务一完成 任务二完成 任务三完成 任务四完成 任务五完成 任务五 H1 H2 H3 H4 H5 任务四 任务三 任务二 任务一 1 2 3 4 5

并行算法的性能评估 运行时间（TS，TP） 总并行开销（T0=p* TP - TS ） 并行度 加速比（SP = TS / TP ） 效率（EP = SP / p） 成本（p* TP）

并行程序开发环境 特征 消息传递 共享存储 数据并行 典型代表 MPI, PVM OpenMP HPF 可移植性 主流并行计算机 SMP, DSM SMP, DSM, MPP 并行粒度 进程级大粒度 线程级细粒度 进程级细粒度 并行操作方式 异步 松散同步 数据存储模式 分布式存储 数据分配方式 显式 隐式 半隐式 学习入门难度 较难 容易 偏易 可扩展性 好 较差 一般

并行程序性能优化 减少通信量、提高通信粒度 全局通信尽量利用高效集合通信算法 挖掘算法的并行度，减少CPU空闲等待 负载平衡 通信、计算的重叠 通过重复计算来减少通信，即以计算换通信

并行程序举例 假定一个有100个元素的数组A，要计算A的每个元素（除A(1)和A(100)外）的左右相邻两个元素值之和的平均值，并将平均值保存在数组ANEW中，该算法的串行伪代码如下： real A(100), ANEW(100) ...... do i = 2, 99 ANEW(i) = (A(i-1)+A(i+1)*0.5 enddo 下面分别使用共享存储模型、并行循环模型、分布存储SPMD（单程序多数据）模型来实现该算法。

假设有一台由4个处理机组成的共享存储并行机，使用FORTRAN的并行循环实现上述程序的并行代码如下： 并行程序举例 假设有一台由4个处理机组成的共享存储并行机，使用FORTRAN的并行循环实现上述程序的并行代码如下： real A(100), ANEW(100) ...... PARALLEL do i = 2, 99 ANEW(i) = (A(i-1)+A(i+1)*0.5 enddo 该段程序尽管实现了并行计算，并获得所需要结果，但由于计算粒度太小，不能弥补因派生并行线程带来的开销。

并行程序举例 为了获得更好的结果，可以加大任务粒度，通过使用外层循环分块，使每个处理机执行一个迭代块为24次，伪代码如下： real A(100), ANEW(100) ...... PARALLEL do ib = 1, 100, 25 PRIVATE i, myfirst, mylast myfirst = MAX(ib, 2) mylast = MIN(ib+24, 99) do i = myfirst, mylast ANEW(i) = (A(i-1)+A(i+1)*0.5 enddo

ANEWlocal(i) = (Alocal(i-1) +Alocal(i+1))*0.5 并行程序举例 下面在分布存储并行机上，使用消息传递SPMD模型来实现上述程序： ！This code is executed by all processors; ！myP is a private local variable containing the processor number；myP runs from 0 to 3; ！Alocal and ANEWlocal are local versions of arrays A and ANEW If (myP. NE. 0) send Alocal(1) to myP – 1 If (myP. NE. 3) send Alocal(25) to myP + 1 If (myP. NE. 0) receive Alocal(0) from myP – 1 If (myP. NE. 3) receive Alocal(26) from myP + 1 myFirst = 1 myLast = 25 If(myP == 0) myFirst = 2 If(myP == 3) myLast = 99 do i = myFirst, myLast ANEWlocal(i) = (Alocal(i-1) +Alocal(i+1))*0.5 enddo

并行程序举例 在发送和接收操作之间插入本地计算，实现计算与通信的重叠，以获得更好的并行性能，伪代码如下： If (myP. NE. 0) send Alocal(1) to myP – 1 If (myP. NE. 3) send Alocal(25) to myP + 1 do i = 2, 24 ANEWlocal(i) = (Alocal(i-1)+Alocal(i+1))*0.5 enddo If (myP. NE. 0) then receive Alocal(0) from myP – 1 ANEWlocal(1) = (Alocal(0)+Alocal(2))*0.5 endif If (myP. NE. 3) then receive Alocal(26) from myP + 1 ANEWlocal(25) = (Alocal(24)+Alocal(26))*0.5

并行程序举例 并行算法设计 映射 并行计算模型 并行计算机

并行计算 基本概念 同时对多个任务或多条指令、或对多个数据项进行处理。 主要目的 提供比传统计算机快的计算速度 解决传统计算机无法解决的问题

并行计算 时间 流水线技术 并行计算 SIMD 空间 多处理器 MIMD 串行计算 SISD

并行计算模型 从不同并行计算机体系结构中抽象出来的、供并行算法设计者使用的一种抽象的并行机。 连接软件和硬件的桥梁。

并行计算模型 PRAM 给算法设计者 提供设计基础 通用性较强 可移植性好 BSP 并行计算模型 LogP C3 串行计算模型 冯诺依曼

PRAM模型 PRAM （Parallel Random Access Machine）是一种理想的并行计算模型，属于SIMD共享存储模型。 一台PRAM并行计算机由若干处理机和一个全局的共享存储器构成。通过SM的R/W交换数据，隐式同步计算。

PRAM模型 P1 共享存储器 P2 …… Pn

适于算法设计、分析 底层细节隐藏在模型中 优点 算法易修改，可移植性强 扩展性强 PRAM 共享存储器容量无限大 理想化 无限多功能相同处理器 处理器任何时刻可交换数据

BSP(Bulk Synchronous Parallel)模型 把并行计算机抽象为三个独立的模块： 处理器-内存单元 全局的通信网络 各处理器之间的路障同步机制

BSP模型 存储器 存储器 …… 处理机 处理机 全局互联网络 路障同步机构 模型参数 p：处理器数(带有存储器) g：全局通信网络的路由器吞吐率(带宽因子) L：路障同步的开销

一个BSP计算过程由若干超级步组成，每个超级步具体分为三个部分： 首先各处理机进行本地计算。 各处理机向其它处理机提出远程内存读写请求。 所有处理机进行路障同步，本次超级步的数据通信仅当同步以后有效。

BSP模型中的计算过程

BSP模型成本分析 在BSP计算中，如果用了s个超级步，则总的运行时间为：

BSP模型特点 将处理器和路由器分开，强调了计算任务和通信任务的分开。 路由器仅仅完成点到点的消息传递，简化了通信协议 。 采用障碍同步的方式以硬件实现全局同步 ，减轻了程序员负担。

LogP模型 基本概念 模型参数 一种分布存储的、点到点通信的多处理机模型。其中通信由一组参数描述，实行隐式同步。 L(Latency)：源处理机与目标处理机之间进行消息通信所需要的等待延迟时间的上限。 o(overhead)：处理机准备发送或准备接受每个消息的时间开销，在这段时间内处理机不能执行其它操作。 g(gap)：一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。 P(Processor)：处理机个数。

LogP模型特点 描述分布式存储互联网络特征 抓住网络与处理机的性能瓶颈 LogP 处理机间异步工作，通过消息传送同步 根据参数分析算法通信复杂度 预估算法的实际运行时间

C3模型 计算单元CU 本地计算量 超级步性能分析 处理机发送接收数据量 通信单元COU 消息的延迟 通信的拥挤量

C3模型 模型参数 p 处理器个数 h 网络延迟 b 网络的对分宽度 S 启动时间，及建立一个消息时的开销 L 消息包的长度，即消息包所含字节数

C3模型开销 C3模型用2个量C和La来描述网络的拥挤，其中，C表示参与通信的处理机对的数目， La表示处理机间路由消息包的平均数目，则有 　　(1) 连接上的拥挤量Cl=La*C/b 　　(2) 处理机上的拥挤量Cp=La*C/b*h 在一个超步中，若Si与Ri分别表示第i个处理机总的发送和接收时间，则有 　　　COU=max(Si+Ri)+Cl+Cp, 0<i<p-1

小结 LogP模型最复杂，PRAM模型最简单。 BSP模型可以看成是LogP模型的改进和演化，而PRAM模型又可以看成是BSP模型的简化。 BSP模型较好的综合了其他两个模型的优点，在面向物理机器实现方面优于PRAM模型，而和LogP模型相比，又更加便于进行算法设计和性能预测。

并行算法在遥感图像融合的应用 遥感图像融合简介 主成分分析（PCA） 串行PCA 并行PCA

遥感图像融合简介 图1（a） MS图像 图1（b） Pan图像

遥感图像融合简介 图2 融合后的图像

遥感图像融合简介 遥感图像融合常用技术： 比值融合方法 滤波融合方法 多分辨率分析方法 成分替换方法（如PCA）

主要成分分析简介 主成分分析方法 把原来多个变量划为少数几个综合指标的一种统计分析 方法。从数学角度来看，这是一种降维处理技术。

主要成分分析简介 例：评价学生的综合能力 基础知识（x1） 动手能力（x2） 学习能力（x3） 学生1 8 2 5 学生2 6 学生3 9 学生4 4 7 学生5 学生6 学生7 学生8

原始数据: 第一步:进行标准化处理 则：

第二步:计算相关系数矩阵R 则： 其中：

第三步：计算R的特征值和特征向量 根据特征方程 计算特征值，并使其按大小顺序排列为： 的特征向量 ，由 计算得到： 本例计算得到： 特征值： 对应的特征向量：

第四步：计算各主成分 其中：

第五步：计算第k个主成分贡献率及累计贡献率 贡献率: 累计贡献率: 取选取主成分个数原则： 一般取累计贡献率达85—95%的特征值所对应的第一、第二、…、第m（m≤p）个主成分。 本例计算得到： 特征值： 贡献率： 0.46 0.37 0.17 累计贡献率： 0.46 0.83 1.00 故只需取第一和第二主成分。

串行PCA 基本说明： 图像表示为向量形式； Pan图像和MS图像配准 ，使尺寸一样，为m×n； MS图像的R、G、B三个波段数据以一个矩阵输入，则输入矩阵为s×3的大小，其中s=m×n。 图（a） MS图像 图（b） Pan图像

串行PCA 图3 串行PCA融合过程

串行PCA 第一步：输入矩阵的协方差矩阵： R＝ 其中σij表示第i和第j个波段的数据做协方差计算，计算公式为：

串行PCA 第二步：计算协方差矩阵的特征向量v及特征值d； 第三步：将特征向量矩阵v乘以输入数据矩阵得到主成分矩阵P，记P中对应于最大特征值的一行P1为第一主成分； 第四步：将P1用经过拉伸后的全色图像pan的数据替换,得到新的P矩阵； 第五步：v矩阵的转置v’乘以P矩阵，反变换回RGB坐标系统。

并行PCA 图4 数据并行划分

并行PCA 并行计算模型： BSP模型 并行算法模型： 数据并行模型 图5 PCA并行机

图6 并行PCA算法的并行流程 59

并行PCA 第一步：输入矩阵的协方差矩阵： 其中： R＝

并行PCA 各个结点Pi进程将 传给主结点P； 再由主结点P算出整幅图像的R、G、B平均值后，广播给其它结点。

并行PCA 第二步：计算协方差矩阵的特征向量v及特征值d；由主进程完成，并将计算结果广播到其他非主进程结点； 第三步：在每个结点上，完成由R、G、B向P1、P2、P3的转换，记P中对应于最大特征值的一行P1为第一主成分。 62

并行PCA 第四步：在每个结点上，将P矩阵的第一主成分用经过拉伸后的全色图像pan的数据替换； 第五步：在各个结点进程上，v矩阵的转置v’乘以P矩阵，反变换回RGB坐标系统。此步骤不涉及到各个结点进程间的通信，可以完全并发的执行。

并行PCA 实验结果： 图7（a） MS图像 图7（b） Pan图像

并行PCA 实验结果： 图8（a） MS图像 图8（b） 融合后图像

并行PCA 性能分析： 表2各种图像的执行时间（单位s）