发布时间 : 星期一 文章并行算法讲义更新完毕开始阅读d6ac36768e9951e79b8927da
Vll 课程安排 · 高性能计算机简介：高性能计算机的体系结构特点及编程方式。 · 消息传递环境：MPI 编程:消息传递 MPI （Message Passing Interface）标准。 · 分布式并行算法设计技术：分布式并行算法设计的基本原理与方法。 · 目的：学习分布式并行算法设计，分布式并行程序编制，高性能并行计算机使用 参考材料 · 孙家昶等，《网络并行计算与分布式编程环境》，科学出版社，1996。 · 张宝琳等，《数值并行计算原理与方法》，国防1.4.业出版社，1999。 · 李晓梅等，《可扩展并行算法的设计与分析》，国防1.4.业出版社，2000。 · 莫则尧等，《 消息传递并行编程环境 MPI》，科学出版社，2001。 · http://www.mpi-forum.org · http://lssc.cc.ac.cn/Parallel-programming/莫则尧/ · http://lssc.cc.ac.cn/Parallel-programming/唐志敏/ · ftp://ftp.cc.ac.cn/pub/home/zlb/bxjs/bxjs.pdf 1
第一部分
MPI消息传递编程 第一章 预备知识
§1.1 高性能并行计算机系统简介 §1.1.1 微处理器的存储结构
§1.1.2 Cache 结构对程序性能的影响
例1.1矩阵乘法中不同循环顺序对程序性能的影响 Ci,j??nk?1ai,kbk,j
DO J=l,N
DO I=l,N C(I,J) = 0.D0 END DO END DO DO I=l,N
DO J=l,N
DO K=l,N
C(I,J) = C (I,J) + A (I,K) * B (K ,J)
ENDDO ENDDO ENDDO
矩阵乘法实例 1：【 matmul0.m4】 矩阵乘法实例 2：【 matmul f】 §1.1.3 共享内存SMP型并行计算机 · 对称多处理器 （Symmetric Multl-Processors），或共享内存处理器 （Shared Memory Processors）。 · 多个处理器通过系统总线或交叉开关共享一个或多个内存模块。 · 优点:使用简单，维护方便。 · 缺点:受系统总线带宽限制，只能支持少量处理器 （一般十几个）。 · 并行编程方式:通常采用 OpenMP，也可使用消息传递 （MPI/PVM） 及 HPF。 · 代表机型 SGI Power Challeng，Sun El0000等。
§1.1.4 分布式内存MPP型并行计算机 · Massively Parallel Processors 的简称。 · 指由大量具有局部内存的计算结点通过高速系统网络联接而构成的并行处理系统。 · MPP系统的系统网络通常具有某种拓扑结构 （如tree，mesh，torus，hypercube）。
§1.1.5 DSM型并行计算机
分布共享内存:Distributed Shared Memory。
· 多个物理上具有独立内存的处理单元，通过高速网络联接在一起。 · 逻辑上作为共享内存并行机使用。 · 也称为NUMA 结构(NonUniform Memory Access）。 · 不同处理单元间内存的共享通过特殊的硬件／软件实现。 · 具有比SMP型并行机更好的可扩展性 （超过100 个 CPU）。 · 代表机型：SGI Origin 2000/3000。 §1.1.6 SMP/DSM机群 · 将多台SMP或DSM并行机通过互联网络连接而成。 · 目前国内外最高性能的并行机大多是这种结构。 §1.1.7 微机/1.4.作站机群 · 微机机群（PC cluster，又称为Beowulf cluster），1.4.作站机群 （NOW，Network Of Workstations）。将联网的多台微机或工作站组织成一台并行计算机。目前常用的网络有以太网 （l00Mbps），ATM (155/622Mbps),Myrinet (1.2Gbps,http://www.myricom.com) · 适合于构造中等规模的并行系统 （多达数百个处理器）。 · 根据机群中所使用的机型可为同构型和异构型两种。 · 根据机群的使用方式又可分为专用型和兼用型，前者指该机群专门用于并行计算。 · 微机工作站机群的优点是价格便宜、配置灵活、但其规模及并行效率受网络设备的制。
配以适当的系统管理工具及作业调度、性能监控、并行程序调试开发环境、及外设等，微机工作站机群系统可以达到与商用MPP系统一样的使用效果。
§1.1.8 TOP500
TOP50O Super computer Sites:【http://www.top500.org】 §1.2 并行编程模式 §1.2.1 自动并行与手工并行 · 在SMP及DSM并行机上编译系统通常具有一定的对用户程序（C/Fortran）进行自动并行化的能力，但经常需要人工干预 （通过指导语句、命令行选项等）以达到理想的并行效率。并行主要针对循环进行 （细粒度并行）。
· 在分布式内存并行机上尚无通用高效的，自动并行1.4.具，主要依靠人1.4.编写并行程序。 · 并行算法的设计及并行程序的编制已成为目前制约大规模并行计算机应用的主要障碍。 5 §1.2.2 OpenMP
在串行程序的循环语句前插入特定的指导语句，告知编译系统一些有助于对该循环进行并行的信息以及/或是强制编译系统按指定的方式将该循环并行化 · 主要限于SMP及DSM型的并行系统，现在也已发展到一些MPP系统 · 通常结合编译系统的自动并行化功能使用 · 也有一些自动并行化1.4.具，它们对程序结构及数据流进行分析，然后自动插入适当的 OpenMP语句 · OpenMP的优点是学习及使用相对简单，很多情况下不需要对原有算法及程序做大的改动。缺点是只适合一类特定的机型，并且程序的可扩展性通常不如用消息传递方式编写的并行程序 · 对一些具有强数据相关性的计算过程需要通过改变计算顺序或修改算法甚至设计新的算法来实现并行计算 · OpenMP程序实例：矩阵乘：【matmul-omp.f】 §1.2.3 DSM编程模式 · 建立在某种内存一致性协议之上，通过软件或软硬件结合的方式实现处理器间内存的共享 · 通过要求DSM并行程序中对内存的读写遵循一定的规则来减小维护内存一致性的开销 · 参看 http://lssc.cc.ac.cn/Parallel- programming/唐志敏/jiajia.ppt · 软件DSM系统实例：Jiajia:【 http://www.ict.ac.cn/chpc/chinese/field1.htm】 §1.2.4 高性能 Fotran:HPF · 基于数据并行的编程语言，即用户通过指导语句指示编译系统将数据分布到各处理器上，编译系统根据数据分布的情况生成并行程序 · 主要面向 Fotran 90/95 · 优点：编程相对简单，串并行程序一致 · 适合于SMP/DSM/MPP/cluster系统 · 主要缺点是并行过程对用户的透明度不高，程序的性能很大程度上依赖于所用的编译系统及用户对编译系统的了解，需要针对不同的HPF编译器做不同的优化，影响了程序的可移植性 · HPF程序实例：矩阵乘：【 matmul-hpf.f】 §1.2.5 消息传递并行编程模式 · 并行程序由一组独立运行的进程构成，进程间通过相互发送消息来实现数据交换 · 可以说消息传递并行编程是并行应用程序开发的最底层编程方式之一 很多其它并行开发语言或1.4.具 （ 如一些HPF编译器）将程序转化成消息传递型并行程序来实现并行 · 常用的消息传递平台有PVM（Parallel Virtual Machine）和MPI（Message Passing Interface） · 程序通用性好，用PVM或MPI编写的程序可以在任何并行计算机上运行 · 能够达到很高的并行效率，具有很好的可扩展性 · 缺点：程序的编制与调试比较困难，许多情况下要对程序甚至算法做大的改动 6 §1.3 Unix 程序开发简介 §1.3.l Unix 中常用的编译系统 · 编译器由前端和后端组成。通常用户只需使用前端命令即可完成编译、链接