国家大学生创新性试验计划.doc

燕山大学国家大学生创新性试验计划进度报告课题名称：并行边界元方法及应用指导教师：陈一鸣项目负责人：杨永章 小组成员：杨永章 璩秋龙 董彩超 所在院系：理学院06级信息与计算科学2009年2月25日一）并行计算并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。 基本体系结构并行计算或称平行计算是相对于串行计算来说的；所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。MIMD类的机器又可分为以下常见的五类：并行向量处理机(PVP)，对称多处理机(SMP)，大规模并行处理机(MPP), 工作站机群(COW)，分布式共享存储处理机(DSM)。访存模型 并行计算机有以下四种访存模型：均匀访存模型（UMA），非均匀访存模型（NUMA），全高速缓存访存模型（COMA），一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）平行计算模型不像串行计算机那样，全世界基本上都在使用天才计算机科学家冯诺依曼的计算模型；并行计算机没有一个统一的计算模型。不过，人们已经提出了几种有价值的参考模型：PRAM模型，BSP模型，LogP模型，C3模型等。并行计算机网络并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式1）.静态连接：一维线性连接，网孔连接，超立方体连接，树连接，立方环连接，洗牌交换连接，蝶形连接，金字塔连接等。 2）.动态连接： 总线连接(Bus)，交叉开关(CS)，多级互联网络(MIN)。 网络的基本术语：1）.节点度 2）.网络直径 3）.对剖宽度 4）.嵌入并行计算机性能度量1.基本指标 1.执行时间 2.工作负载 3.存取性能 2.加速比评测 1.Amdahl定理 2.Gustafson定理 3.Sun-Ni定理 3.可扩放性标准 1.等效率标准 2.等速度标准 3.平均延迟标准并行算法并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。常见的非数值算法设计方法举例 并行播送与并行求和 并行排序算法； 并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。 关于图论中的一些并行算法： 图论作为一门到近代才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。 关于串处理的并行算法： KMP算法的并行化。常见的数值算法设计方法举例 并行快速傅里叶变换并行计算的发展从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。 并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 节点性能不断进步20世纪60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现。这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机。IBM 360是这一时期的典型代表。 到了20世纪60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs公司此时开始实施Illiac 计划，研制一台64颗CPU的SIMD主机系统，它涉及到硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小的原型系统（仅使用了16颗CPU）终于在1975年面世时，整个计算机界已经发生了巨大变化。 首先是存储系统概念的革新，提出虚拟存储和缓存的思想。以IBM 360/85和IBM 360/91为例，两者是属于同一系列的两个机型，IBM 360/91的主频高于IBM 360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线。但是，IBM 360/85的整体性能却高于IBM 360/91，惟一的原因就是前者采用了缓存技术，而后者则没有。 其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器中被用作缓存，而CDC7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到计算机中。元器件技术的这两大革命性突破，使得Illiac 的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。 处理器高速发展 1976年Cray-1问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15年。Cray-1对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列技术手段的使用，使Cray-1的主频达到了80MHz。 微处理器随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基梅隆大学开始在当时流行的DEC PDP-11小型计算机的基础上研制一台由16台PDP-11/40处理机通过交叉开关与16个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。 从20世纪80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议。而伯克利加州大学则对总线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，C.mmp开创出的共享存储多处理器之路越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。 通信机制稳步前进 同一时期，基于消息传递机制的并行计算机也开始不断涌现。20世纪80年代中期，加州理工学院成功地将64个i8086/i8087处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。 20世纪80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性。20世纪90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。 20世纪90年代至今，主要的几种体系结构开始走向融合。 属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息。 Cray T3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。 随着微处理器商品化、网络设备的发展以及MPI/PVM等并行编程标准的发布，集群架构的并行计算机出现开始。IBM SP2系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。 有限元并行计算的发展和现状 目前，在计算力学领域内，围绕着基于变分原理的有限元法和基于边界积分方程的边界元法，以及基于现在问世的各种并行计算机，逐渐形成了一个新的学科分支有限元并行计算。它是高效能的，使得许多现在应用串行计算机和串行算法不能解决或求解不好的大型的、复杂的力学问题能得到满意的解答，故其发展速度十分惊人。在国际上已经掀起了利用并行机进行工程分析和研究的高潮。从1975到1995年的二十年间，有关有限元方法 和相应的数值并行计算的文章已发表1000余篇。有限元并行计算正在向两个方向发展。一是对系统方程组实 施并行求解的各种算法。二是并行分析方法，包括有限元并行算法和边界元并行算法，前者趋向成熟，而后者的研究较少。对这一方面的研究，是为了挖掘有限元计算自身潜在的并行性，是有限元并行计算的根本问题。 国内 并行算法的设计和有效实现强烈地依赖于并行机的硬软件环境。国内仅极少数单位拥有并行机，且机型杂乱，因此研究人员少，起步晚，而且局限于特定的硬件环境。从有限元分析方法的内容来看，发表的几十篇研究论文（报告）还未显示出较强的系统性。 1）南京航空航天大学周树荃教授等在YH-1向量机上实现了刚度矩阵计算、对称带状矩的Cholesky分解和线性方程组的求解等并行处理。针对不规则结构工程分析问题，他们还采用了变带宽存贮方法，并实现了刚度矩阵的并行计算以及求解变带宽稀疏线性方程组的并行直接解法。 2）中国科学院计算中心王荩贤研究员等在基于Transputer芯片的分布式MIMD系统上，提出了有限元分析中变带宽线性方程组的并行直接解法，初步完成了一个静力分析程序。 3）重庆大学张汝清教授等借助于ELXSI-6400共享存贮器型MIMD系统，先后开展了范围比较广泛的并行算法研究，主要成果有： a)提出了静力分析中子结构解法的并行算法，以及动力分析中模态综合子结构法的并行算法； b)从波前法出发，发展了多波前并行算法以求解大型结构分析问题； c)从Jacobi块迭代法和加权残差法出发，导出了基于异步控制的有限元方程并行解法和有限元并行迭代的基本格式； d)利用图论中的着色理论，实现了刚度矩阵的并行计算； e)实现了基于有色线剖分的SOR并行迭代解法； f)实现了子空间迭代法、Lanczos法以及利用多项式割线迭代法和矢量迭代法求解结构固有频率和模态的并行算法； g)针对弹塑性分析，提出了一种多波前子结构并行算法； h)针对弹性接触问题，提出了一种基于参数变分原理的并行解法； i)实现了一步积分法的并行处理。 4）南京航空航天大学乔新教授等借助于Transputer芯片的分布式 MIMD系统实现了有限元方程组的并行直接解法，并提出了基于子结构的预处理共轭梯度法的并行计算方法。此外，浙江大学姚坚、中国科学院西南计算中心马寅国、东北工学院张铁以及国防科技大学六系也曾对有限元分析的并行计算开展了一些研究。上述研究结果表明，国内并行计算方法的研究，在硬件上基于向量机、分布式并行机和共享存贮式并行机；在内容上，似乎面很广，但系统性和深度还很不够，软件开发距实际应用和商品化还有很大距离，对不依赖并行机具体环境的通用并行算法研究还很少，同样对旨在进行结构有限元分析的并行计算的硬件研究也很少。 国外 自从美国国家宇航局（NASA）的A.K.Noor于1975年发表第一篇有限元并行计算的文章以来，有限元并行处理技术几乎与并行计算机同步发展。距不完全统计，到1992年，国外已发表了400余篇这方面的论文，其中后5年的文章篇数是前12年的总和。在研究内容上也由过去的算法研究发展到了算法、软件和硬件相结合的研究，并针对一些机型开发了一些实用的大型结构分析软件。 1）有限元机器FEM（Finite Element Machine）。早在70年代末，就有人发表了有关FEM的论文，1982年美国国家宇航局Langley研究中心的O.O.Storaasli等撰文详细地介绍了该中心设计的供研究 用的FEM。该机器由1个处理器阵列、1台作为控制器的微机和1个并行操作系统及一些模块化了的通用并行算法程序组成，用户使用系统的文本编辑器和制器的其它特殊功能，能建立有限元计算模型并进行分析。10多年来，又有一些人在这一方面进行了不懈的努力，但FEM的发展前景仍然不太令人乐观。 2）心动阵列并行机。心动阵列并行机主要应用于信号和图象的并行处理，但由于其高效的矩阵计算功能，近年来有人把它应用于有限元分析，并作了一些有益的尝试。 3）巨型向量机。在有限元分析中越来越显示出巨大的威力，处于领先的是美国思维公司的CM-2。许多结构分析家把这个具有65536个处理器的巨型向量机应用于有限元计算，如T.Belyschko等人采用显式方法，完成了具有32768个单元的壳的非线性有限元计算，并行效率极高，速度几乎比CRAY X-MP/14并行机高出1个数量级。 4）并行机网络和工作站网络。日本东京大学矢川等借助高速网络把3台CRAY Y-MP机联成网络进行有限元分析，有限元方程求解采用的是基于区域分裂技术的共轭梯度法（CGM）， 在求解三维弹性问题时自由度个数超过了100万，系统平均运行速度高达1.74GFLOPS。另外，他们还基于一个工程工作站网络，在并行环境下进行了类似的研究， 求解问题的自由度数高达20万个二）边界元方法及发展边界元方法边界元法是一种继有限元法之后发展起来的一种新数值方法,与有限元法在连续体域内划分单元的基本思想不同,边界元法是公在定义域的边界上划分单元,用满足控制议程的函数去逼近边界条件.所以边界元法与有限元相比具有单元的未知数少,数据准备简单等优点.但用边界元法解非线性问题时,遇到同非线性项相对应的区域积分,这种积分在奇异点附近有强烈的奇异性,使求解遇到困难.边界元法是在有限元法之后发展起来的一种较精确有效的工程数值分析方法 。 又称边界积分方程-边界元法。它以定义在边界上的边界积分方程为控制方程，通过对边界分元插值离散，化为代数方程组求解。它与基于偏微分方程的区域解法相比，由于降低了问题的维数，而显著降低了自由度数，边界的离散也比区域的离散方便得多，可用较简单的单元准确地模拟边界形状，最终得到阶数较低的线性代数方程组。又由于它利用微分算子的解析的基本解作为边界积分方程的核函数 ，而具有解析与数值相结合的特点，通常具有较高的精度。特别是对于边界变量变化梯度较大的问题 ，如应力集中问题 ，或边界变量出现奇异性的裂纹问题，边界元法被公认为比有限元法更加精确高效。由于边界元法所利用的微分算子基本解能自动满足无限远处的条件，因而边界元法特别便于处理无限域以及半无限域问题。边界元法的主要缺点是它的应用范围