2014并行计算的复习思考题2

并行计算的复习思考题：1总结串行计算和并行计算在算法设计中的特点，并给出奇、偶排序的串行和并行算法2、掌握各种并行设计，并应用流水线设计技术给出冒泡排序的并行算法3、通过查资料掌握Amdahl定律的主要内容、应用范围及主要结论。4、总结并行计算中的计算模式，分析各自的特点。并列举1-2个你的研究领域里应用了哪些并行计算模式。5、掌握MPI中消息传递的模式，并分析各自的特点6、复习各种排序算法的并行化2、并行算法设计技术：①平衡树方法、②倍增技术、③分治策略、④划分、⑤流水线技术。①应用1——求最大值输入：n=2m个数存在数组A（n:2n-1)中输出：最大数置于A(1)中beginfork=m-1to0doforj=2kto2k+1-1par-doA(j)--max{A(2j),A(2j+1)}endforendforEnd应用2——求N个数之和输入：数组A（1:n)，N=2K输出：数组值的总和存储于A(1)中begin1.p=n/22.whilep0do3.fori=1topdoinparallel4.A(i)=A(2i-1)+A(2i)5.endparallel6.p=p/27.endwhileEnd应用3：SIMD-TC模型上非递归求前缀和参看笔记②应用2——列表排序：输入：数组A(1:n)，LINK(1:n),HEAD输出：RANK(1:n)begin1.fori=1tondoinparallelRANK(i)=1NEXT(i)=LINK(i)endparallel2.fork=1tologndo(2)fori=1toninparallelifNEXT(i)isnotzeroRANK(i)=RANK(i)+RANK(NEXT(i))NEXT(i)=NEXT(NEXT(i))endifendparallelendforend③SIMD模型上的分治算法输入：问题的输入集合I输出：问题的解输出OprocedureD&C(I,O)BEGINIFsmall(I,O)Thenreturn(ANSWER(I,O))ELSE(1)SPLITINPUT(I:S1,S2,S3,....,SK)(2)FORi=1tokpar-doD&C(Si,Ti)endfor(3)COMBINE(T1,T2....,TK,I,O)ENDIFEND④应用——归并算法均匀划分技术，应用——PSRS排序过程A.均匀划分b.局部排序c.正则采样d.采样排序e.选择主元f.主元划分g.全局交换h.归并排序3、描述：系统中某部件由于采用某种方式使系统性能改进后，整个系统性能的提高与该方式的使用频率或占总的执行时间的比例有关。主要应用：改善“系统瓶颈”性能。Amdahl定律定义了加速比：加速比=采用改进措施后性能/未采用改进措施前的性能=未采用改进措施前执行某任务时间/采用改进措施后执行某任务的时间n个处理器加速因子S=n/[1+(n-1)f]:f为非平行百分比，n越大，S不能超过1/f阿姆达尔定律不可并行计算的存在是很重要的，因为它将限制并行化的潜在好处。阿姆达尔定律指明如果一个计算的1/S本质上是顺序的，那么最大的性能改进将受限于因数S。其论证如下，一个并行计算的执行时间TP将是顺序部分计算时间和可并行化部分计算时间两者的和。如果该计算顺序地执行需要花费的时间是TS，则当有P个处理器时，TP可表示为S=n/[1+(n-1)f]假想P值非常大，使得可并行化部分的执行时间可以忽略不计，则最大可改进的性能将是因数S。也就是说，顺序执行代码在计算中所占的比例决定了使用并行手段所能改进性能的潜力。4.什么是计算模型？——抽象的，是硬件和软件之间的桥梁。很明显，如果算法的性能在抽象系统中都不能满足要求，那么在实际系统中实现就毫无意义。计算模型只关注算法复杂性方面。冯·诺依曼结构是一种理想的串行计算模型，在并行计算中，没有一个真正通用的并行计算模型。目前常见的并行计算模型：PRAM模型、BSP模型、logP模型、C3模型。①ParallelRandomAccessMachine（并行随机存取机器），有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。优点：使用简单，处理器间通信，存储管理，进程同步等隐含于模型中。缺点：共享单一存储器的假定，不适合于分布存储的异步的MIMD机器PRAM-CRCW并发读并发写CPRAM-CRCW(CommonPRAM-CRCW)：仅允许写入相同数据PPRAM-CRCW(PriorityPRAM-CRCW)：仅允许优先级最高的处理器写入APRAM-CRCW(ArbitraryPRAM-CRCW)：允许任意处理器自由写入PRAM-CREW并发读互斥写PRAM-EREW互斥读互斥写②异步APRAM模型，又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。优缺点：易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。③BSP模型是个分布存储的MIMD计算模型，特点是：它将处理器和路由器分开，这样做既掩盖具体的互连网络拓扑，又简化了通信协议；采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级；为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。④LogP模型是一种分布存储的、点到点通信的多处理机模型，特点是：抓住了网络与处理机之间的性能瓶颈；处理机之间异步工作，并通过处理机间的消息传送来完成同步；对多线程技术有一定反映；消息延迟不确定；可以预估算法的实际运行时间。⑤C3模型假定处理机不能同时发送和接收消息，它对超步的性能分析分为两部分：计算单元CU，依赖于本地计算量；通信单元COU，依赖与处理机发送和接收数据的多少、消息的延迟及通信引起的拥挤量。该模型考虑了两种路由（存储转发路由和虫蚀寻径路由）和两种发送/接收原语（阻塞和无阻塞）对COU的影响。5.MPI最基本的通信模式是在一对进程之间进行的消息收发操作，一个进程发送消息（MPI_Send(void*buf,intcount,MPI_Datatypedatatype,intdest,inttag,MPI_Commcomm)），另一个接收消息（MPI_Recv(void*buf,intcount,MPI_Datatypedatatype,intsource,inttag,MPI_Commcomm,MPI_Status*status)）。这种通信方式成为点对点通信：①标准模式：由MPI系统来决定是先将消息复制至一个缓冲区，然后立即返回，还是等待将数据发送出去后再返回。②缓冲模式：假设有一定量的缓冲区空间可供使用，发送者把消息拷贝到一个缓存，然后以非阻塞方式发送它。③同步模式：发送者发一个“请求发送”的消息，接收者存储这个请求。当一个匹配接收登入时，接收者发回一个“允许发送”的消息，这时发送者才真正发送消息。④就绪模式：在肯定相应接收已开始后，消息才被发送。6.①枚举排序：对该算法的并行化是很简单的，假设对一个长为n的输入序列使用n个处理器进行排序，只需每个处理器负责完成对其中一个元素的定位，然后将所有的定位信息集中到主进程中，由主进程负责完成所有元素的最终排位。输入：无序数组a[1]…a[n]输出：有序数组b[1]…b[n]Begin(1)P0播送a[1]…a[n]给所有Pi(2)forallPiwhere1≤i≤npara-do(2.1)k=1(2.2)forj=1tondoif(a[i]a[j])or(a[i]=a[j]andij)thenk=k+1endifendfor(3)P0收集k并按序定位End②快速排序：基本思想：在当前无序区R[1,n]中取一个记录作为比较的“基准”，用此基准将当前的无序区R[1,n]划分成左右两个无序的子区R[1,i-1]和R[i,n](1≤i≤n)，且左边的无序子区中记录的所有关键字均小于等于基准的关键字，右边的无序子区中记录的所有关键字均大于等于基准的关键字。快速排序算法并行化的一个简单思想是，对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。例如对一个长为n的序列，首先划分得到两个长为n/2的序列，将其交给两个处理器分别处理；而后进一步划分得到四个长为n/4的序列，再分别交给四个处理器处理；如此递归下去最终得到排序好的序列。当然这里举的是理想的划分情况，如果划分步骤不能达到平均分配的目的，那么排序的效率会相对较差。输入：无序数组data[1,n]，使用的处理器个数2m输出：有序数组data[1,n]Beginpara_quicksort(data,1,n,m,0)End假设quicksort(data,i,j)表示快速排序串行算法procedurepara_quicksort(data,i,j,m,id)Begin(1)ifm=0then(1.1)Pidcallquicksort(data,i,j)else(1.2)Pid:r=patrition(data,i,j)(1.3)Pidsenddata[r+1,j]toPid+2m-1(1.4)para_quicksort(data,i,r-1,m-1,id)(1.5)para_quicksort(data,r+1,j,m-1,id+2m-1)(1.6)Pid+2m-1senddata[r+1,j]backtoPidendifEnd