高性能计算课件.ppt

高性能计算 第2讲 引论 课程安排 并行算法设计过程举例 并行程序设计 MPI (Message Passing Interface) 并行计算性能分析 并行算法研究方法学 并行算法的研究 学科体系：理论－设计－实现－应用 并行算法理论 并行算法设计分析 并行算法实现 并行算法应用 研究方法：结构－算法－编程 并行计算机体系结构 并行算法的设计 并行程序设计 高性能计算课程目标 高性能计算研究现状 学习如何面向高性能计算机设计和运行并行程序 研究分析影响并行效率的相关问题 并行算法研究与实现 课程特点 并行化技术 理论与实践相结合 自主学习 加强实践 授课方式 通过课程讲授、课程论文、课堂报告和课堂讨论的方式 课程论文： 针对所选择的应用问题，基于并行思想和技术进行求解和实现，对计算结果进行总结分析完成论文； 在阅读必威体育精装版文献的基础上，分析、总结和完成某个研究领域的综述; 课程论文严格按照论文版面格式，上大学报中文版。 课堂报告与课堂讨论要求： 每人至少精读论文6篇以上，参考文献不少于20篇； 要有自己的评论和见解，不要简单翻译或引用原文的摘要和运行结果； 报告内容积极参加讨论 要求： 结合自己的研究领域，深入查阅必威体育精装版资料，确定选题； 认真阅读论文；组织课堂报告，参与课堂讨论； 培养严谨的科研作风，严禁抄袭。 参考文献 并行算法研究方法学 陈国良等 计算机学报 Vol31No.9 2008 陈国良《并行计算：结构，算法，编程》高等教育出版社，2001.5 高性能计算并行编程技术——MPI并行程序设计 都志辉等，清华大学出版社 并行程序设计（Designing and Building Parallel Programs) Ian Foster 人民邮电出版社 2002 并行程序设计 陆鑫达等译 机械工业出版社 Parallel Programming:Techniques and Applications Using Networked Workstation and Parallel Computers Web References Levels of Abstraction 并行算法的一般概念: 定义和分类 并行算法 一组可同时执行且可互相协作的诸进程的集合。 分类 并行算法的一般设计过程 划分 域分解和功能分解 通讯 任务间的数据交换 组合 任务的合并使得算法更有效 映射 将任务分配到处理器，并保持负载平衡 并行算法的一般概念: 并行算法的复杂度 并行算法复杂性的度量 运行时间t(n)：计算时间tc和选路(路由)时间tr 处理器数目p(n) 成本c(n)：c(n)=t(n)×p(n) 成本最优性：若c(n)等于在最坏情形下串行算法所需要的时间，则并行算法是成本最优的。 加速比Sp(n)：Sp(n)=ts(n)/tp(n)，其中ts(n)为求解问题的最快的串行算法在最坏情形下所需的运行时间，tp(n)为求解同一问题的并行算法在最坏情形下的运行时间。 注：(1)加速比Sp(n)反映算法的并行性对运行时间的改进程度。 (2)若Sp(n)=p(n)，则达到线性加速；若Sp(n)p(n)，则为超线性加速(一般出现在某些特殊的应用中，如并行有哪些信誉好的足球投注网站等)。 并行效率Ep(n)：Ep(n)=Sp(n)/p(n)， 0Ep(n)=1 注：反映了并行系统中处理器的利用程度。 工作量(或运算量) W(n)：并行算法所执行的总操作步数。(与处理器的数目无关) 均匀划分技术 划分方法 n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理 A[(i-1)n/p+1..in/p] (2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序 (3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素 (4)样本排序：用一台处理器对p2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段 (7)全局交换：各