并行算法的设计与分析5.pptx

Parallel Algorithms1/Ch5Y.Xu Copyright USTC2024/9/6 周五Parallel Algorithms Chapter 5 Sorting and Selecting in AsynchronousParallel Algorithms2/Ch52024/9/6 周五Y.Xu Copyright USTC主要内容主要内容n5.1 MIMD-CREW模型上的异步枚举排序算法模型上的异步枚举排序算法n5.2 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法n5.3 分布式分布式k-选择算法选择算法Parallel Algorithms3/Ch52024/9/6 周五Y.Xu Copyright USTC5.1 MIMD-CREW模型上的异步枚举排序算法模型上的异步枚举排序算法n5.1.1 MIMD异步异步算法的基本框架算法的基本框架n5.1.2 异步枚举排序算法异步枚举排序算法n5.1.3 示例示例n5.1.4 时间分析时间分析Parallel Algorithms4/Ch52024/9/6 周五Y.Xu Copyright USTC5.1.1 MIMD异步异步算法的基本框架算法的基本框架开始时所有处理器空闲，用某个开始算法，开始时所有处理器空闲，用某个开始算法，产生一些过程或进程产生一些过程或进程(算法的一段算法的一段)，进入进程，进入进程 等待队列；等待队列；若有空闲的机器，分配进程；进程执行完之后，若有空闲的机器，分配进程；进程执行完之后，机器进入等待；机器进入等待；若无等待进程，机器空闲，排队进入等待状态。若无等待进程，机器空闲，排队进入等待状态。注：注：SIMD每个时刻各处理器执行的操作相同每个时刻各处理器执行的操作相同Parallel Algorithms5/Ch52024/9/6 周五Y.Xu Copyright USTC5.1.2 异步枚举排序算法异步枚举排序算法1.输入待排序数组输入待排序数组X1.n，输出已排序数组，输出已排序数组T1.n。2.算法：算法：MIMD-CREW枚举排序枚举排序 begin (2.2)for j=1 to n do (1)for i=1 to n do if XiXj then k=k+1 create process i else if(Xi=Xj and ij)then k=k+1 end for end if (2)process i:(2.3)TK+1=Xi (2.1)k=0 end注：算法生成注：算法生成n个进程，第个进程，第i个进程计算个进程计算X中比中比xi小的元素数小的元素数k，将，将xi置于置于SM 数组数组Tk+1，各进程间无通讯要求，可互相独立完成。，各进程间无通讯要求，可互相独立完成。Parallel Algorithms6/Ch52024/9/6 周五Y.Xu Copyright USTC5.1.3 异步枚举排序算法示例异步枚举排序算法示例输入输入X=8,6,6,7,9，p(n)=2，P1生成生成5个进程，设进程调度按个进程，设进程调度按FIFO，P1与与P2首先执行进程首先执行进程1和进程和进程2 (1)进程内的运算进程内的运算(假定各操作时间相同，假定各操作时间相同，X数组已在本地数组已在本地)k=0,X(i)Xj,X(i)=Xj,ij,k=k+1,Tk+1=Xi (2)进程进程1：(3)进程进程2：1+3+3+3+3+3+1=17 类似地，进程类似地，进程3(18)，进程，进程4(13)，进程，进程5(15)Parallel Algorithms7/Ch52024/9/6 周五Y.Xu Copyright USTC5.1.4 异步枚举排序算法的时间分析异步枚举排序算法的时间分析1.假定：第假定：第(1)步之前无任何进程启动；步之前无任何进程启动；可在常数时间内解决读冲突；可在常数时间内解决读冲突；不考虑进程间的调度时间不考虑进程间的调度时间2.MIMD-异步枚举排序算法时间异步枚举排序算法时间 n个进程：每个进程时间个进程：每个进程时间O(n)Parallel Algorithms8/Ch52024/9/6 周五Y.Xu Copyright USTC主要内容主要内容n5.1 MIMD-CREW模型上的异步枚举排序算法模型上的异步枚举排序算法n5.2 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法n5.3 分布式分布式k-选择算法选择算法Parallel Algorithms9/Ch52024/9/6 周五Y.Xu Copyright USTC5.2 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法n5.2.1 SISD上的上的快排序快排序算法算法n5.2.2 SIMD-CRCW上的快排序算法上的快排序算法n5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法Parallel Algorithms10/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.1 SISD上的上的快排序快排序算法算法Procedure QUICKSORT(A,q,r)/输入无序序列输入无序序列(Aq,Ar);输出有序序列输出有序序列(Aq,Ar)begin if qr then (1)x=Aq (2)s=q (3)for i=q+1 to r do if Aix then (i)s=s+1 (ii)swap(As,Ai)end if (4)swap(Aq,As)(5)QUICKSORT(A,q,s)(6)QUICKSORT(A,s+1,r)endParallel Algorithms11/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.2 SIMD-CRCW上的快排序算法上的快排序算法1.算法说明算法说明(1)SIMD-CRCW上的快排序算法的核心是构造二叉排序树。上的快排序算法的核心是构造二叉排序树。(2)排序树的树根为排序树的树根为root，左孩子为，左孩子为Lcroot，右孩子为，右孩子为Rcroot(3)SM变量变量root,Lc1.n,Rc1.n,及待排序数组及待排序数组A1.n(4)n个处理器个处理器Pi存有存有Ai(5)得到二叉排序树后，只要中序遍历即可得到排序序列得到二叉排序树后，只要中序遍历即可得到排序序列(6)二叉排序树如下：二叉排序树如下：Parallel Algorithms12/Ch52024/9/6 周五Y.Xu Copyright USTC2.SIMD-CRCW上的快排序二叉树构造算法上的快排序二叉树构造算法 输入：输入：A1.n到到SM，n个处理器，并且个处理器，并且Ai保存在保存在Pi的的LM中中 输出：二叉排序树输出：二叉排序树root,Lc1.n,Rc1.n在在SM中中 begin (1)for each Pi par-do (1.1)root=i (1.2)fi=root (1.3)Lci=Rci=n+1 end for (2)repeat for each Pi,ifi par-do if(Ai Afi)or(Ai=Afi and ifi)then (2.1)Lcfi=i (2.2)if i=Lcfi then exit else fi=Lcfi end if else (2.3)Rcfi=i (2.4)if i=Rcfi then exit else fi=Rcfi end if end if end repeat end5.2.2 SIMD-CRCW上的快排序算法上的快排序算法/Pi将处理器号将处理器号i并发写入并发写入SM变量变量root，root的值是不确定的的值是不确定的/Pi并发读入并发读入root到到LM变量变量fi中中/Lci和和Rci初始化，使得不指向任何处理器初始化，使得不指向任何处理器/Ai是是LM变量变量,Afi是是SM变量变量;(Ai=Afi and ifi)为了排序稳定为了排序稳定/Pi将将i并发写入并发写入SM变量变量LCfi,竞争为竞争为fi的左孩子的左孩子/Pi将将i并发写入并发写入SM变量变量RCfi,竞争为竞争为fi的右孩子的右孩子 T(n)=O(logn),p(n)=n,c(n)=O(nlogn)Parallel Algorithms13/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法1.异步快排序异步快排序算法的思想算法的思想2.算法说明算法说明3.MIMD-TC上的异步快排序算法上的异步快排序算法4.示例示例5.时间分析时间分析Parallel Algorithms14/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法1.异步快排序异步快排序算法的思想算法的思想 并行做：找中值；并行做：找中值；并行做：依据中值，将序列划分为并行做：依据中值，将序列划分为子序列；子序列；对子序列并行递归地执行对子序列并行递归地执行和和，直至子序列长度，直至子序列长度 小于某个临界值时，进行直接排序；小于某个临界值时，进行直接排序；2.算法说明算法说明 SM的待排数组的待排数组X1.n,Qi为为X的子数组，的子数组，qi为为Qi中第中第1个个 元素的首地址，元素的首地址，|Qi|=si,R是存放是存放(qi,si)的的SM数组数组 算法输入数组算法输入数组X1.n，输出为排好序的数组，输出为排好序的数组X1.nParallel Algorithms15/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法3.MIMD-TC上的异步快排序算法上的异步快排序算法 begin (1)Q1=X (2)R1=(q1,n)(3)生成进程生成进程1 (4)进程进程i:/对对Qi进行快排序进行快排序 (4.1)(qi,si)=Ri /取出取出Qi的首地址和子序列的大小的首地址和子序列的大小 (4.2)if si2 then 直接排序直接排序Qi else (i)求求Qi的中值的中值m /调用串行调用串行k-选择算法选择算法 (ii)将将m定位在定位在X的最终排序位置上的最终排序位置上 (iii)将将Qi划分成小于和大于划分成小于和大于m的的Q2i和和Q2i+1两子序列两子序列 (iv)R2i=(q2i,s2i),(v)R2i+1=(q2i+1,s2i+1)(vi)生成进程生成进程2i和进程和进程2i+1 end if end Parallel Algorithms16/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法4.示例：示例：X=10,3,7,15,2,4,11,1,12,6,8,13,9,16,14,5,n=16,p(n)=4的执行过程的执行过程 Remark:第第0层第层第2层可以由层可以由4个处理器并行求解，而第个处理器并行求解，而第3层以上层以上 需要一个处理器顺序处理多个进程。需要一个处理器顺序处理多个进程。Parallel Algorithms17/Ch52024/9/6 周五Y.Xu Copyright USTC5.2.3 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法5.时间分析时间分析 假设假设n=2k(k=logn),p=2l;算法在执行过程中动态生成的进程数为算法在执行过程中动态生成的进程数为2i(i=0,1,k-1)所以，在第所以，在第0层第层第l层上的进程可以由层上的进程可以由p个处理器并行做，而第个处理器并行做，而第l+1层第层第k-1层层上的进程需要一个处理器顺序处理多个进程。上的进程需要一个处理器顺序处理多个进程。分情况如下：分情况如下：(1)对于第对于第0l层上各进程可以并行处理，每个进程执行时间为层上各进程可以并行处理，每个进程执行时间为 O(si)=O(n/2i)i=0l=logp (2)对于第对于第(l+1)(k-1)层上各进程层上各进程,顺序执行的进程数为顺序执行的进程数为2i-logp,执行的时间为执行的时间为 2i-logpO(n/2i)i=logp+1logn-1 综上，算法的时间综上，算法的时间 当当plogn时，算法是成本最优的时，算法是成本最优的 Parallel Algorithms18/Ch52024/9/6 周五Y.Xu Copyright USTC主要内容主要内容n5.1 MIMD-CREW模型上的异步枚举排序算法模型上的异步枚举排序算法n5.2 MIMD-TC模型上的异步快排序算法模型上的异步快排序算法n5.3 分布式分布式k-选择算法选择算法Parallel Algorithms19/Ch52024/9/6 周五Y.Xu Copyright USTC5.3 分布式分布式k-选择算法选择算法n5.3.1 分布式计算的概念分布式计算的概念n5.3.2 随机随机k-选择算法选择算法n5.3.3 确定确定k-选择算法选择算法Parallel Algorithms20/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念1.Distributed Computing:-not everything centralized -many processorsParallel Algorithms21/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念2.Distributed Systems:-Internet -The machines of our department -ATM machines,bank accounts3.What is then parallel computing?-Many processors in the same machine -All processors solve the same task A restricted form of distributed computing4.Basic Distributed Systems:-Message passing -Shared MemoryParallel Algorithms22/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 Message Passing Systems message Easy to implement in hardwareParallel Algorithms23/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 Shared Memory Systems -Not easy to implement in hardware-Easy to programParallel Algorithms24/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念5.Distributed Algorithms 分布式算法是由通讯链连接的多个场点分布式算法是由通讯链连接的多个场点(结点结点)协同完成某协同完成某 任务的算法，假定数据分布在若干场点，各场点之间任意任务的算法，假定数据分布在若干场点，各场点之间任意 互连网相连，一组进程间的通讯通过一组通道完成各进程互连网相连，一组进程间的通讯通过一组通道完成各进程 之间约定的一个发送或一个接收。之间约定的一个发送或一个接收。Parallel Algorithms25/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 Several problems:-The counting problem:Sequential Bottleneck!Shared variable 0,1,2,Parallel Algorithms26/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 A better solution:Counting networkmany sharedvariablesParallel Algorithms27/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 -Routing ProblemsParallel Algorithms28/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 -Finding the spanning tree problemParallel Algorithms29/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.1 分布式计算的概念分布式计算的概念 -Leader election problemLeaderParallel Algorithms30/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.2 随机随机k-选择算法选择算法n1.SISD上的随机上的随机k-选择算法选择算法n2.分布式随机分布式随机k-选择算法选择算法Parallel Algorithms31/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.2 随机随机k-选择算法选择算法1.SISD上的随机上的随机k-选择算法选择算法 从从B=b1,b2,bn中选出第中选出第k个小的元素个小的元素 算法算法1：若若|B|=1,输出；否则，执行输出；否则，执行；随机选取划分元随机选取划分元m;将将B分成分成BL,BE,BG，分别包含，分别包含B中中m的元素的元素 3.1 若若|BL|k,令令B=BL,k=k 3.2 若若|BL|+|BE|k|BL|,则输出则输出m 3.3 若若|BL|+|BE|k,令令B=BG,k=k-|BL|-|BE|用用B,k递归调用算法；递归调用算法；Parallel Algorithms32/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.2 分布式随机分布式随机k-选择算法选择算法2.分布式随机分布式随机k-选择算法选择算法 输入输入B=b1,b2,bn,场点场点S=S1,S2,Sp,通讯链通讯链L=SS;假定网络中已有一个生成树，场点假定网络中已有一个生成树，场点Si含有含有B中的子集中的子集Bi 算法算法2：通过对生成树的扫描，根结点计算出树中结点所含的元素数通过对生成树的扫描，根结点计算出树中结点所含的元素数 若若|B|=1，根结点输出，否则执行，根结点输出，否则执行；各结点已知：其元素数和元素的编号，其第各结点已知：其元素数和元素的编号，其第j个子树所含的元素数个子树所含的元素数t(j);随机地选取一个划分元素随机地选取一个划分元素m:先随机产生整数先随机产生整数i，-如果如果 it，t为为根结点中的元素数，则在根中选第根结点中的元素数，则在根中选第i个元素个元素；-否则取使否则取使 j=i-t-t(1)-t(2)-t(f-1)0的最大整数的最大整数f，在根的第，在根的第f个子树中找第个子树中找第j个元素个元素,递归地找下去；递归地找下去；将划分元素将划分元素m 根结点根结点所有结点所有结点 每个进程每个进程i将将Bi分成分成BLi,BEi,BGi,计算计算 依据依据m,|BL|,|BE|,|BG|之间的关系之间的关系(同算法同算法1)，确定下一步的调用，确定下一步的调用 需加上：将信息播送到所有结点需加上：将信息播送到所有结点 根据根据B,k做递归调用做递归调用Parallel Algorithms33/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.3 确定确定k-选择算法选择算法n1.SISD上的确定上的确定k-选择算法选择算法n2.分布式确定分布式确定k-选择算法选择算法Parallel Algorithms34/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.3 确定确定k-选择算法选择算法1.SISD上的确定上的确定k-选择算法选择算法 算法算法3:|B|较小，用排序求；较小，用排序求；将将B分成每分成每5个一组；个一组；求每组的中值求每组的中值:中值集中值集M;求求M的中值的中值m划分元；划分元；同算法同算法1 1中中；同算法同算法1 1中中；Parallel Algorithms35/Ch52024/9/6 周五Y.Xu Copyright USTC5.3.3 确定确定k-选择算法选择算法2.分布式确定分布式确定k-选择算法选择算法 算法算法4：求求|B|,当当|B|足够小时，送入根结点，排序求足够小时，送入根结点，排序求k-元素元素;每个进程按每个进程按5个元素一组分组，每个结点从其子结点个元素一组分组，每个结点从其子结点 接收零头，每接收零头，每5个一组分组，再把零头送往父结点；个一组分组，再把零头送往父结点；局部求局部求5个元素的中值；个元素的中值；以以M为输入，递归调用求为输入，递归调用求M的中值的中值m;同算法同算法1 1中的中的；Parallel Algorithms36/Ch5Y.Xu Copyright USTC2024/9/6 周五End of Chapter 5