《国家大学生创新性试验计划.doc》由会员分享，可在线阅读，更多相关《国家大学生创新性试验计划.doc（7页珍藏版）》请在金锄头文库上搜索。
1、燕山大学国家大学生创新性试验计划进度报告课题名称：并行边界元方法及应用指导教师：陈一鸣项目负责人：杨永章 小组成员：杨永章 璩秋龙 董彩超 所在院系：理学院06级信息与计算科学2009年2月25日一）并行计算并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程。为执行并行计算，计算资源应包括一台配有多处理机（并行处理）的计算机、一个与网络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且复杂的计算问题。此外还包括：利用非本地资源，节约成本 使用多个“廉价”计算资源取代大型计算机，同时克服单个计算机上存在的存储器限制。传统地，串行计算
2、是指在单个计算机（具有单个中央处理单元）上执行软件写操作。CPU 逐个使用一系列指令解决问题，但其中只有一种指令可提供随时并及时的使用。并行计算是在串行计算的基础上演变而来，它努力仿真自然世界中的事务状态：一个序列中众多同时发生的、复杂且相关的事件。 为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（M
3、IMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。 基本体系结构并行计算或称平行计算是相对于串行计算来说的；所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。MIMD类的机器又可分为以下常见的五类：并行向量处理机(PVP)，对称多处理机(SMP)，大规模并行处理机(MPP), 工作站机群(C
4、OW)，分布式共享存储处理机(DSM)。访存模型 并行计算机有以下四种访存模型：均匀访存模型（UMA），非均匀访存模型（NUMA），全高速缓存访存模型（COMA），一致性高速缓存非均匀存储访问模型（CC-NUMA）和非远程存储访问模型（NORMA）平行计算模型不像串行计算机那样，全世界基本上都在使用天才计算机科学家冯诺依曼的计算模型；并行计算机没有一个统一的计算模型。不过，人们已经提出了几种有价值的参考模型：PRAM模型，BSP模型，LogP模型，C3模型等。并行计算机网络并行计算机是靠网络将各个处理机或处理器连接起来的，一般来说有以下几种方式1）.静态连接：一维线性连接，网孔连接，超立方体连
5、接，树连接，立方环连接，洗牌交换连接，蝶形连接，金字塔连接等。 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方法，即
6、划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。总之，并行算法还需要相当多完善的地方。 并行算法与串行算法最大的不同之处在于，并行算法不仅要考虑问题本身，而且还要考虑所使用的并行模型，网络连接等等。常见的非数值算法设计方法举例 并行播送与并行求和 并行排序算法； 并行选择算法：所谓选择问题就是在一给定的序列中选择出某组（个）满足给定条件的元素。 关于图论中的一些并行算法： 图论作为一门到近代
7、才发展起来的科学。在图论中有很多关于如何设计算法的问题，比如求最小生成树，单源最短路径等等。事实上，这些算法中有很多是可以并行化的，而且并行化时运用的思想具有很大的启发性，下面是几个常见的并行图论算法。 关于串处理的并行算法： KMP算法的并行化。常见的数值算法设计方法举例 并行快速傅里叶变换并行计算的发展从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。 并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与
8、协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 节点性能不断进步20世纪60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现。这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机。IBM 360是这一时期的典型代表。 到了20世纪60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行
9、特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs公司此时开始实施Illiac 计划，研制一台64颗CPU的SIMD主机系统，它涉及到硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小的原型系统（仅使用了16颗CPU）终于在1975年面世时，整个计算机界已经发生了巨大变化。 首先是存储系统概念的革新，提出虚拟存储和缓存的思想。以IBM 360/85和IBM 360/91为例，两者是属于同一系列的两个机型，IBM 360/91的主频高于IBM 360/85，所选用的内存速度也较快，并且采用了动态调度的
10、指令流水线。但是，IBM 360/85的整体性能却高于IBM 360/91，惟一的原因就是前者采用了缓存技术，而后者则没有。 其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器中被用作缓存，而CDC7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到计算机中。元器件技术的这两大革命性突破，使得Illiac 的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。 处理器高速发展 1976年Cray-1问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15年。Cray-
11、1对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列技术手段的使用，使Cray-1的主频达到了80MHz。 微处理器随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基梅隆大学开始在当时流行的DEC PDP-11小型计算机的基础上研制一台由16台PDP-11/40处理机通过交叉开关与16个共享存储器模块相连接而成的共享存储多处理器系统C.mmp。 从20世纪80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议。而伯克利加州大学则对总
12、线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，C.mmp开创出的共享存储多处理器之路越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。 通信机制稳步前进 同一时期，基于消息传递机制的并行计算机也开始不断涌现。20世纪80年代中期，加州理工学院成功地将64个i8086/i8087处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。 20世纪80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的
13、发展。IBM将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性。20世纪90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。 20世纪90年代至今，主要的几种体系结构开始走向融合。 属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息。 Cray T3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减
14、少消息传递延迟的技术。 随着微处理器商品化、网络设备的发展以及MPI/PVM等并行编程标准的发布，集群架构的并行计算机出现开始。IBM SP2系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。 有限元并行计算的发展和现状 目前，在计算力学领域内，围绕着基于变分原理的有限元法和基于边界积分方程的边界元法，以及基于现在问世的各种并行计算机，逐渐形成了一个新的学科分支有限元并行计算。它是高效能的，使得许多现在应用串行计算机和串行算法不能解决或求解不好的大型的、复杂的力学问题能得到满意的解答，故其发展速度十分惊人。在国际上已经掀起了利用并
15、行机进行工程分析和研究的高潮。从1975到1995年的二十年间，有关有限元方法 和相应的数值并行计算的文章已发表1000余篇。有限元并行计算正在向两个方向发展。一是对系统方程组实 施并行求解的各种算法。二是并行分析方法，包括有限元并行算法和边界元并行算法，前者趋向成熟，而后者的研究较少。对这一方面的研究，是为了挖掘有限元计算自身潜在的并行性，是有限元并行计算的根本问题。 国内 并行算法的设计和有效实现强烈地依赖于并行机的硬软件环境。国内仅极少数单位拥有并行机，且机型杂乱，因此研究人员少，起步晚，而且局限于特定的硬件环境。从有限元分析方法的内容来看，发表的几十篇研究论文（报告）还未显示出较强的系统性。 1）南京航空航天大学周树荃教授等在YH-1向量机上实现了刚度矩阵计算、对称带状矩的Cholesky分解和线性方程组的求解等并行处理。针对不规则结构工程分析问题，他们还采用了变带宽存贮方法，并实现了刚度矩阵的并行计算以及求解变带宽稀疏线性方程组的并行直接解法。 2）中国科学院计算中心王荩贤研究员等在基于Transputer芯片的分布式MIMD系统上，提出了有限元分析中变带宽线性方程组的并行直接解法，初步完成了一个静力分析程序。 3）重庆大学张汝清教授等借助于ELXSI-6400共享存贮器型MIMD系统，先后开展了范围比较广
