第4章并行程序设.ppt

第4章 并行程序设计起步 1.两种并行类型 数据并行 任务并行 2.描述并行算法的方法 3.构造并行计算的三种方法 无限并行性 固定并行性 可扩展并行性 4.1 数据和任务并行 1.数据并行定义 是指同时对不同数据项完成相同操作的 并行. 并行量随数据规模而增长. 2.任务并行是指同时完成不同计算或任务的 并行. 4.2 Peril-L记号 Peril-L混合程序设计语言 作用:用来描述与分析并行算法 1.并行语句之一: forall------并行线程 线程个数由索引集合S的元素个数决定. 2.排它块语句:exclusive{body}--- 作用:提供互斥 3.障栅同步:barrier------同步 作用:仅在forall内部起作用.强迫线程停止直 到所有线程到达barrier.全部到齐后一 起出发. 4.存储模型 1)Peril-L语言提供两个地址空间 全局地址空间 局部地址空间 2)全局变量为所有线程共享 局部变量只能为所属线程独占. 3)forall内声明的变量,每个线程得一份; 在其外声明的变量,为所有线程共享. 4) 全局变量用下划线,局部变量不用. Localize()—全局变量本地化函数 5)全局存储器本地化三个问题 第1项索引值为0； 用Localize()局部化全局数据； 不存在本地拷贝。 4.2.5 同步存储器 Peril-L语言中满变量与空变量的操作 4.2.6 归约和扫描 1.Peril-L语言中归约与扫描的符号表示 归约用“/”表示 扫描用”\”表示 2.示例 +/count min\items Least=min/dataArray Total=+/count; beforeMe=+\count; Largest=max/localtotal 4.2.7 归约的抽象 1. 编程建议：若从多个线程组合值，应使用归约操作，而不用显式编程。 Exclusive {total+=prov_count;} total=+/prov_count 4.4 并行性的表示 4.4.1 固定并行性 1.K路并行算法； 2.处理器个数是固定的； 3.编程尽量避免使用具有特定并发度的程序 4.4.2无限并行性 1.无限并行性含义：硬件能提供无限的并行性，可设计所有可能的并行程序。 2.最大的并行性设计 3.当Pn时，又回到了固定并行或顺序执行 4.4.3 可扩展并行性 1.局部性原理 并行求解过程： 1）确定求解问题的组成部分； 2）设计一个重要子问题集（数据划分） 3）独立求解每一个子问题。 4.5 按字母顺序排序实例 1.排序的方法很多 2.字母排序应用于文件名、数据表等排序 4.5.1 无限并行性 1.奇偶交换排序算法 冒泡算法的变形---奇偶互换排序算法 算法分奇阶段与偶阶段 偶阶段偶数编号进程与它们的右邻居交 换数据 偶数阶段代码如下: 奇数阶段代码如下: 进程Pi:I=1,3,5(奇数) send(A,Pi+1); recv(B,Pi+1); if(AB) A=B; 综合代码,把两者结合起来即可. 4.5.2 固定并行性 线程数固定（处理器个数固定） 采用的算法： 1）将有n元素的字符串数组平均分到每一个线程； 2）由每一个线程统计分给它的字符串个数中，26个字母各自的个数 3）用归约统计每个字母的词数； 4）由各线程对原字符串进行重新排序 5）对同一字母的字符串进行排序 6）用扫描统计（前缀求和）求出该字母之前的记录数 7）重新将暂时局部数组保存回全局数组。 4.5.3 可扩展并行性 1. 采用双调谐排序算法 1.双调谐序列 双调谐归并排序的基础是双调谐序列 1)双调谐序列包含两个序列:一个递增,一个递减. 数列中的数先单调递增到一个最大的数,然后单调递减. a0a1a2,…,ai-1aiai+1,…,an-2an-1 2)通过移数或合并两个有序序列也可得到双调谐序列. 3)双调谐序列的“特殊”性质: 如果对所有的I将ai和ai+n/2(序列中有n个数,0=In/2)进程比较和交换操作,就能得到两个双调谐序列,其中一个双调谐序列中的所有数都小于另一个双调谐序列中的数. 3 5 8 9 7 4 2 1 3 4 | 2 1 | 7 5 | 8 9 2 1 | 3 4 | 7 5 | 8 9 1