资源描述：
《随机算法》--并行计算与分布式计算 山东大学(张庆科》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、山东大学高性能计算学科组HighPerformanceComputingResearchGroupReporter：张庆科,牛佳瑞2021年8月3日并行算法+分布式算法1234“PRAM模型”随机快速排序(QuickSort)随机盒排序(BoxSort)图：随机求极大独立集(MIS)1报告提纲张庆科5选择协调问题牛佳瑞并行计算分布式计算前言并行计算分布式计算并行计算研究单系统内是相对于串行计算而言,可分为：时间上的并行(流水线技术）和空间上的并行（多个处理器并发的执行计算）研究分散系统如何进行计算。先将问题分解，
2、子问题由多个计算机进行处理，最后收集所有的计算结果。串行计算机模型：冯·诺伊曼模型（当前主流）并行计算机模型:PRAM模型，BSP模型，LogP等单处理器并行多处理器并行服务器服务器服务器服务器大任务取指译码执行写回取指译码执行写回取指译码执行写回任务任务CPUCPUCPUCPUCPUCPU取指译码执行写回PRAM模型11.1PRAM-模型共享全局存储器(超级)P1P2Pi...PRAM（SynchronousParallelRandomAccessMachine）即“同步并行随机存储器模型”Pn...RAM模型
3、PRAM模型寄存器寄存器寄存器寄存器读写读写读写读写P存储器寄存器读写每个处理器都支持RAM模型，型号完全相同所有处理器通过公用时钟同步运行每个处理器都能够访问（读/写）整个内存每个处理器都有常数个局部寄存器程序存储器r0r1r2…指令计数器内存储器累加器只读输入带只写输入带1.2PRAM-分析P1P2Pi...Pn...寄存器寄存器寄存器寄存器共享全局存储器122PRAM模型的访存冲突问题P1P2Pi...Pn...寄存器寄存器寄存器寄存器共享全局存储器ef“并行步”（parallelsteps）①各处理器P选
4、择一个全局存储单元,读存储内容(操作数1）②将操作数1与自己寄存器中的操作数2一起执行一条指令③处理器向它所选择的存储单元中写数据pqtsda读读读读问题2：多个处理器同时写一个单元的情况，该问题称为并发写（cWrite），硬件实现更困难；-★-★-★-若TM表示一并行算法在一并行计算模型M上的运行时间，则写读写写写写问题1：多个处理器同时读一个单元的情况，该问题称为并发读（cRead）,但是硬件实现困难；nn0f(n)c*g(n)nn0c1g(n)c2g(n)f(n)nn0c*g(n)f(n)渐近记号：用来表示
5、算法的渐近运行时间趋势的记号，用定义域为自然数集N={0,1,2,...}的函数来定义。渐进运行时间记号我们很熟悉的句子“…算法的时间复杂度为O(..)”复杂度分类1.多项式复杂度2.非多项式复杂度计算时间复杂度时间复杂度的误解：程序执行到结束所耗费时间的长短（静态片面理解）--你是否也这样认为？时间复杂度的正解：描述当问题的规模扩大后，程序耗费的时间增长的有多快！（动态全局理解）千僖难题之P=NP？NP的误解：NP就是非多项式问题，其实这是不对的~PNPNP-CompleteNP-Hard问题求解难度Polyn
6、omial:多项式问题★Non-DeterministicPolynomial：非确定多项式问题NP完全问题：多是指数级或者阶乘级问题NP难问题：最高求解难度的问题?并行快速排序算法22.1QuickSort（串行算法）314592687P1P2P3P4P5P6P7P8P931429687143341342689891689675算法灵魂：递归（Recursion）快排：元素划分越对称，排序速度就越快（原因：问题被分解的速度快）递归本质：大事化小，小事化了效率：O(nlogn)527382.2问题提出1.问题：如
7、何用n个不同的处理器，对n个互不相同的数进行排序？2.要求：①算法以高概率在O(logn)并行步内完成排序②所有处理器的操作次数总和为O(nlogn)初步考虑在CREWPRAM模型下设计随机快速排序方案(RandomQuickSort)QuickSortMergeSortHeapSortIntroSortBestAverageWorstnlognnlognnlognnlognnlognnlognnlognnlognnlognnlognnlognn2Sort2.3RandomQuickSort输入：n个不同的无序数
8、；注：Pi为第i个PRAM的处理器输出：n个数的递增排序序列（0,1,2,3,4,5,6,7,8,9,10,11）算法过程动画演示0：if(n=1)算法停止；/*算法终止条件*/1：从n个数中随机的选择一个作为分离元S;2：从由每个处理器判断其元素的值比轴元S的大小关系；4：每个小于分离元S的数移动到处理器Pi内()每个大于分离元S的数移动到处理器Pk内()5：递归地对处
