并行算法第三章并行算法的设计基础

1、 第三章第三章并行算法的设计基础并行算法的设计基础3.1 3.1 并行算法的基础知识并行算法的基础知识3.2 3.2 并行算法的复杂性度量并行算法的复杂性度量3.3 3.3 并行算法中的同步与通信并行算法中的同步与通信3.4 3.4 并行计算模型并行计算模型3 3.1 并行算法的基础知识4 并行算法的分类数值计算数值计算：基于代数关系运算的一类：基于代数关系运算的一类非数值计算非数值计算：基于比较关系运算的一类：基于比较关系运算的一类同步算法同步算法：算法的多个进程的执行必须相互等待：算法的多个进程的执行必须相互等待异步算法异步算法：算法的多个进程的执行不需要相互等待：算法的多个进程的执行不需

2、要相互等待 分布算法分布算法：由通信链路连接的多个节点，协同完成问题由通信链路连接的多个节点，协同完成问题 求解的一类并行算法求解的一类并行算法确定算法确定算法：算法的每一步都能明确地指明下一步应该如：算法的每一步都能明确地指明下一步应该如 何行进的一类算法何行进的一类算法随机算法随机算法：算法的每一步随机地从指定范围内选取若：算法的每一步随机地从指定范围内选取若 干参数，由其来确定算法下一步的走向干参数，由其来确定算法下一步的走向5 并行算法的特点6 并行算法的表达7 3.2并行算法的复杂性度量时间复杂度时间复杂度问题的规模问题的规模空间复杂度空间复杂度8 时间复杂度9 时间复杂度10 时间

3、复杂度11 时间复杂度12 计算复杂度对计算时间的影响13 并行计算性能评估中的几个参数14并行计算性能评估中的几个参数15 3.3 并行算法中的同步与通信161.如何将问题划分成子问题？如何将问题划分成子问题？2.各处理器完成什么任务？各处理器完成什么任务？3.如何实现各处理器对共享变量的访问？如何实现各处理器对共享变量的访问？ 思考？思考？17共享共享变量变量S18并行算法中的同步 Begin (1)S=0;(2)for all Pi where 0ip-1 do (2.1) L=0; (2.2) for (j=i;jn;j+=p) L=L+aj; (2.3) lock(S); S=S+L

4、; (2.4) unlock(S); End19 并行算法的通讯20 并行算法的通讯1.如何将问题划分成子问题？如何将问题划分成子问题？2.各处理器完成什么任务？各处理器完成什么任务？3. 处理器之间是否存在通信？处理器之间是否存在通信？思考？思考？A划分为划分为B=A1.n,(i-1)r+1.irX划分为划分为w=X(i-1)r+1;ir 计算计算Z=BW21矩阵向量相乘矩阵向量相乘Y=AX22 并行算法的通讯233.4 并行计算模型24并行计算模型25串行计算模型总线总线CPU内存储器内存储器I/O接口接口1输入输入/输出输出设备设备I/O接口接口n输入输入/输出输出设备设备I/O接口接口外存储器外存储器26 PRAM模型27 PRAM模型Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory28 PRA