（固体力学专业论文）异构网络平台上的分布式有限元并行计算.pdf

西南交通大学硕士研究生学位论文第 i i 页 a b s t r a c t 卜 t h e f i n i t e e l e m e n t m e t h o d i s w i d e l y u s e d i n e n g i n e e r i n g c o m p u t a t i o n w i t h t h e r a p i d d e v e l o p m e n t o f t h e c o m p u t e r s s o f t w a r e a n d h a r d w a r e 山e f i n i t e e l e m e n t m e t h o d p l a y s a m o r e a n d m o r e i m p o r t a n t r o l e i n d o m a i n s o f e n g i n e e r i n g c o m p u t a t i o n d u r i n g t h i s s t a g e m u c h e x c e l e n t f e m c o m p u t i n g s o f t w a r e e m e r g e d s o m e a r e g o o d a t p r e a n d p o s t 一 p r o c e s s i n g s u c h a s t h e c o m m o d i t y s o f t w a r e a n s y s a n d s o m e a r e g o o d a t d e a l i n g w i t h s p e c i a l e l e m e n t s a n d s p e c i a l s i t u a t i o n s d i s t r i b u t e s y s t e m i n o n di f f e r e n tc o m p u t e r s a n d lu e d i f f e r e n t o s s t h e s o f t w a r e o p e r a t i n g f a c t i t g i v e s r i s e t og r e a t m a t e r i a l r e s o u r c e s i t a n d p o r t a b i l i t y o f f e m i n t h e o t h e r h a n d c o m p u t a t i o n t h a n b e f o r e i s anu r g e n t p r o j e c t t o w a s t a g e o f h u m a n a n d r e s o l v e t h e r e u s e n e s s s o f t w a r e p e o p l e p a y m o r e a t t e n t i o n o n t h e n e t w o r k w i t h t h e d e v e l o p m e n t o f t h e n e t w o r k t e c h n i q u e s a n d i n t e r n e t t h e d i s t r i b u t e d c o m p u t i n g o n n e t w o r k m o s t l y r e l y o n t h e c o m p o n e n t s a n d m i d w a r e s t h e m o s t l y u s e d m i d w a r e i s o m g s c o r b a a n d m i c r o s o f t s d c o m t h i s t h e s i s g i v e s i n t r o d u c t i o n t o t h e t w o t e c h n i q u e s a n d c o m p a r e s t h e m i n d e t a i l i n t h e t h e s i s t h e a s s o c i a t i o n o f c o r b a n d j a v a i s u s e d j a v a p r o v i d e s t h e g o o d m o b i l e c o d e s y s t e m a n d c o r b a p r o v i d e s t h e e x c e l l e n t p e r f o r m a n c e w o r k i n g o n d i f f e r e n t p l a t f o r m s l h i h i n d i n g o f c o r b a a n d j a v a i s p e r f e c t a l m o s t l y h e i m p r o v e m e n t o f c o m p u t i n g a b i l i t y c a n t r e l y o n t h e d e v e l o p m e n t f h a r d w a r e c o m p l e t e l y r e s e a r c h e r s t r y t o r e s o l v e i t u s i n g a l g o r i s m m e t h o d a n d p a r a l l e l a l g o r i s m i s a g o o d s e l e c t i o n w i t h o u t s u s p i c i o n a s a r a s f e m i s c o n c e r n e d i t h a s t h e g o o d i n h e r e n t f e a s i b i l i t y t o l i s t r i h u t e d f o r e x a m p l e t h e s u b d o m a i n m e t h o d i s u s e d i n t h i s h c s i s i h e h i n d i n g o f d i s t r i b u t i n g a n d p a r a l l e l i s j u s t an e w f o c u s n a m e d m e t a 一 m p u t i n g t o h e s i m p l y i n t e r p r e t e d i t i s r u n n i n g a s i m p l e j o b n t h e d i s t r i b u t e d c o m p u t e r s c o n n e c t e d b y n e t w o r k d u r i n g m o t r t c o m p u t i n g t h e p r o b l e m s s u c h a s t h e d i s t r i b u t e p a r a l l e l l o a d i n g 西南交通大学硕士研究生学位论文第i 日页 e y u i h r i u m r e s o u r c e s m a n a g e m e n t s e c u r i t y f a u l t 一 t o l e r a n c e r u n s p f k f k g k 随 着问 题的 不断分 解 g k 将 相 应地增大 使得 分治方 法的 性能 降 低 性能 好的 并 行算法 就是设法把一个待求解问 题均匀地分配到各个处理器上去做 使各处理器 都处于 计算 状态 为求解问题忙碌地工作着 2 1 4并行语言 早期的大规模并行计算机 m p p 的并行程序设计是由消息传递程序设 计技术支持的 因此要求程序员自己处理共享数据到各处理机的分布 并 行任务到各处理机的分布和处理机间的同步 通讯等 编程难度较大 9 0 年代以来 为支持 mp p程序设计 人们提出了几种数据并行语言并研制了 相应的 编译系 统 如v i e n n s f o rt r a n f o rt r a n d c m f o rt r a n h i g h p e r f o r m a n c e f o rt r a n 和c r a y m p p f o rt r a n 1 9 9 7 年 著名的 数 据并 行语言又 推出了2 0 版 目 前 实现通用语言并行化的方法有三种 1 在原语言的基础上增加一些并行处理的语言描述成份 2 增加一个并行程序库 用户通过使用库函数实现并行处理 3 把前两种方法结合起来 即在语言中增加必要的描述成份和一 个并行程序库 采用第三种方法的好处是与原语言兼容性好 西南交通大学硕士研究生学位论文第9 页 编译系统改造较容易 研制周期短 使用方便等 如在c 语言 中引入关键字 s h a r e d 凡带有该关键字的变量均作为共享变量 采用函数调用方法 描述程序的并行成份 提供任务的划分 控制 通信与同步等一组并行程序库函数 供用户设计并行程 序时使用 数据并行语言有两个特点 一是继承了传统程序设计语言统一地址空间 编程的风格 二是在语言中增加了描述数据分布和并行执行的能力以适应 mp p分布存储器体系结构 数据并行语言较大地降低了mp p编程的难度 程序员只是在描述数据分布时需要考虑分布存储器 而在描述程序执行时 可以把所有分布存储器看作是一个大的存储器 而把并行任务对各个处理 器的分配 处理机的同步 通讯等交给编译系统去完成 5并行编译 编译系统并行化的技术难点是对一个源程序自动识别出可并行执行的部 并将其并行化 同时保证整个程序正确运行 并行识别的目 标是完成 2 分 串行程序向并行程序的自 动转化 由语言编译器实现 关键是充分开发并 行性 它主要包括相关性分析及程序重构两部分 循环是该领域研究的主 要对象 程序中的数据相关可分为流相关 反相关及输出相关 若循环的 不同迭代之间没有数据相关 则该循环是可并行的 而程序重构技术是尽 可能消除相关性 是获得大小适当的并行粒度的关键 程序重构手段主要 有循环分布 循环交换 循环扭曲和子程度嵌入等 并行机并行效率的发 挥关键在于并行软件 其中算法和编译的并行化水平影响最大 它们己成 为当今国际上计算机界研究的热点 2 1 6并行计算机的现状与前景 在微电子技术和并行处理技术的支持下 各类并行机快步进入计算机大 家庭 当前 世界上凡是有能力研制巨型机的厂商 已大多转向研制并行 机或者是研制向量技术与并行技术相结合的向量处理机高度并行化的系 统 美 日以及西欧各国围绕超级计算机已开展激烈的争夺战 都想捷足 先登 先发制人 为此他们各施高招 组织了大量人力物力财力 制订了 发展超级计算机的五年或十年计划 美国政府制订了 超级计算机与通信 的发展计划 美国国防部也把超级计算机列为 2 1世纪科研关键技术 之 一 如果此项计划得以圆满完成 将使美国今后十年的国民经济总产值增 加3 0 0 0 亿美元左右 日 本也不甘落后 他们动用了 三倍于美国的巨 额投资 开展高技术的基础设施建设 日 本政府于 1 9 9 2年制订了由国家直接领导 西南交通大学硕士研究生学位论文第1 0 页 组织政府相关部门 计算机界厂商 高等学府等单位 联合研究成果共享 的国策 并把大规模并行计算机列为国家9 0 年代的重点发展项目 德 英 法 对发 展并 行 机系 统 十 分 重 视 并 于1 9 9 1 年 制 订了 t e r a fl o p 计 划 旨 在 5 年内推出万亿次量级的超级计算机 目前 美国 日本和西欧等国已经 初步成功地研制出亿次至万亿次超级计算机 如美国的 i n t e l 公司已研制出 每秒运算 1 8 万亿次浮点运算的超级计算机 该系统采用 9 0 0 0多个 i n t e l 公 司生产的 p e n t i u m p r o p 6 微处理器 日 本多所大学经过三年的共同努力 已 研制出每秒万亿次浮点运算的超级计算机 我国自 行研制的具有世界一 流水准的 曙光 1 0 0 0 大规模并行计算机系统已于 1 9 9 5 年5 月通过了国家 级鉴定 该系统每秒运算速度超过 1 0亿次浮点运算 曙光 1 0 0 0 的研制 成功标志着我国并行处理技术迈入世界先进行列 目前 曙光 1 0 0 0 己分 别在北京 上海 沈阳 西安 武汉 合肥的国家高性能计算中心正常运 行 正在为我国的经济建设和科学研究发挥着巨大的作用 我国并行计算 机的发展前景是光明的 2 2 并行计算的消息传递方式p v m和m p i 介绍 消息传递方式是广泛应用于一些并行机 特别是分布存储并行机的一种 模式 p v m和mp i 都是目 前广受欢迎的基于消息传递的并行程序库 p v m 应用程序实际上是在普通c 和f o r t r a n语言中加入了p v m函数调用 它 的 全称是p a r a ll e l v ir tu a l m a c h in e 并 行 虚 拟 机 m p i 的 全 称是 m e s s a g e p a s s i n g i n t e r f a c e 消息传递接口 p v m 是美国国家基金会资助的公开软件系统 具有通用性强及系统规 模小的特点 既支持 t c p i p网络环境 又适用于 mp p大型并行系统 当 前所有的并行机公司都己宣布支持 p v m3 一些大公司还针对自己产品的 特点推出高效率的 p v m 产品 与 p v m3配套的异构计算机网络环境 h e n c e 及可视化工具 x p v m 3在世界范围内 推广 一批标准的软件 如u n p a c k e i s p a c k l a p a c k 等正 在移 植到p v m平台 2 6 1 0 mp i 是多个计算机中的进程之间进行通信的机制 通过mp i 不同子任 务之间 可以 进 行通信 从而达到 并 行计算的目 的 m p i 与p v m e x p r e s s 等 并行编程环境相比 使用简单 编程方便 主要有以下特点 1 通用性强 既适用于t c p i p网络 又适用于mp p大规模并行 系统 2 系统规模小 约几兆字节 3 成熟度高 4 使用简单 编程方便 p v m 和 m p i 的设计目 的与侧重点是不同的 p v m 的 研制工作是围绕 虚拟机 的中心思想展开的 可移植性 p o r t a b i l i t y 比 速度得到了 更多 西南交通大学硕士研究生学位论文第i 1 页 的重视 可伸缩性 s c a l i n g 容错能力 f a u l tt o l e r a n c e 和异构性 h e t e r o g e n e it y 也 是 研究的 重 点 而m p i a 在 创 建一 种 标 准的 消 息 传递 界 面 速度是mp i 设计中的焦点问 题 因此 在大型并行机系统m p p 上 mp i 被认为要比p v m速度快 尽管如此 最近的研究表明 在c r a y t 3 d与i b m s p 2 f p v m与m p i 的速度差别并不很大 2 2 1 p v m 和 m p i 的比较 p v m和mp i 的关系就好象网络协议方面的t c p i p和 i s o的o s i 之间 的关系 前者已经成为了事实上的业界标准 但存在一些问题 而后者试 图统一标准但确难以被大家全面接受 表2 1 从几个方面对两种不同的消息 传递方式作一个简单的比较 表2 1 p v m 和 m p i 比较 p vm mp i 可移植性可在异构机器上移植并可以互 相通信 可互协 可在异构单机上运行 动态特性可通过资源控制函数集灵活地 进行动态控制 实际上是静态的 容错特性有基本的错误信息反馈mp i i i 扩充了容错机制 但无 法恢复意外失效的进程 运行速度不错强于 p v m p v m 并行虚拟机 和 m p i 消息传递接口 是两种成功的并行编程环 境 通过高速网络连接一组工作站和计算机 求解复杂的科学和工程计算 问题 在这两种编程环境中 我们遇到两个问题 仍然必须调整和缩小计 算模型和目 标机体系结构上的差异 编程人员应该在应用任务的并行化和 目 标机体系结构两方面有很好的经验 而且并行化过程仍是手工操作的 2 2 2 p v m p i 从上方的归纳可以看到 p v m 和 mp i 各有优劣 能不能将这两种消息 传递模式综合起来使它们优势互补呢 美国田纳西大学和橡树岭国家实验 室已经开始了一个名为 p v mp i 的研究项目 研究是否可以将 p v m和 mp i 的功能结合起来形成一个统一的编程环境 p v m p i 1 0 o p v m p i 应具有三 个 共生 功能 在多处理机上应能使用厂家随机提供的 m p i 实现 应用程序应能使用p v m的资源控制与容错能力 应允许透明地使用p v m 的网络通信功能 在不同的mp i 实现之间进行数据传输 西南交通大学硕士研究生学位论文第1 2 页 2 2 3 p j v m 前面所说的分布式并行处理方法 如c l i n d a p v m等 往往都只能在 完全同构或不完全同构的网络环境中进行 p j v m1 3 p a r a l l e l j a v a v ir t u a l ma c h i n e 是武汉大学软件工程国家重点 实验室 1 9 年研制成功的一个基于异构环境的并行 分布程序设计工具 p j v m p j v m 利用最近出现的 j a v a语言的许多突出优点 发挥了 i n t r a n e t 和 a t m 的高速传输特征 通过扩充 j a v a功能 提供了基于分布式共享存 储 器的 编程接口d s m d i s t r i b u t e d s h a r i n g m e m o ry 和基于消息传递的 编 程接口m p i m e s s a g e p as s i n g i n t e r f a c e 用户可以 利用j a v a 语言和扩充的 两个编程接口 方便地设计在异构环境下运行的并行 分布程序 2 2 4 j a v a m p i m p i 只支持 c f o r tr o n和 c 什语言的网络分布并行计算环境 这就存 在 mp i 应用程序应用程序在不同系统之间的二进制兼容的问题 从而导致 它们不能很好地适应用户的各种异构型网络 特别是i n t e r n e t 网络 为了解决mp i 系统的平台兼容问题 充分利用i n t e rn e t 网络上的现有计 算机资源 进行网络并行技术解决大型问题 长沙国防科技大学计算机系 张晓军等利用j a v a 的 本地接口 技术j n i 在m p i 系统中提供了 库函 数的j a v a 的语言接口 类 j m p i l 使用户可以 使用j a v a 语言编写m p i 应用程序 j a v a 与mp i 的结合既能发挥j a v a 语言可移植性强的优势 又能通过mp i 充分利用网上的计算机资源 实现大型问题的网络并行计算 2 3 并行计算的基本问题 2 3 1并行性的表现形式及并行性条件 在计算环境中 并行性在不同处理级别可表现为多种形式 如先行方式 流水方式 向量化 并发性 同时性 数据并行性 划分 交叉 重叠 多重性 重复 时间共享 空间共享 多任务处理 多道程序设计 多线 程方式和分布式计算 所有这些形式可以认为是由并行性级别 计算粒度 时间和空间的复杂性 通信时延 调度策略和负载平衡的不同而造成的 通常一个合理的设计方案需要在时间 空间 性能和价格因素之间进行折 西南交通大学硕士研究生学位论文第1 3 页 衷 为了更好地表达并行性条件 给出 定义如下 定义一 i 设有一程序段同时满足条件 有一个唯一的输入向量 有一个 唯一的输出向量 则该程序段在某一环境下的一个执行即为一个进程 进 程具有动态的属性 定义2 如 果进程a a a z 人分 别 在n 个不同 处 理机上按任意 顺序执行的结果相同 那么以上n 个进程可以并行执行 定义3 设a b为 某一 程序中的两 个 程序段 i a o a i b o b 分别为 a b的 输入和输出 变量集 若 a b满足条件 i a n o b u a n o u i 人 门 o b 半 则 称a与b 数 据 相 关 否 则 称 数 据 武官 在以 上 条 件中 i a n o b d 称为 流不相 关 o n o a d 称为 反不相关 o a n o 称为输出 不相关 这就是判定数据相关与否的b e r s t e i n 条件 定义4 设l l 为 某一 程序中的 两个语句 若l 的 执行结果能 够决 定l z 是否执行 则称l 2 控制相关于l 定义5 与 系 统进行的 工作无关 与 并 行事 件利用共享资 源s 时 发生的 冲突有关的 相 关性 称之为 s 资 源相关 这类 共享资 源包括整数部件 浮 点部件 寄存器和存储器 数据相关与否 控制相关与否 资源相关与否就是在一定的并行性级别 上实现并行计算的三个基本条件 2 3 2问题划分及并行级别 问题划分是针对并行分解而言的 所谓的并行分解 就是将一个问题说 明 包括程序 分解成为多个子问题说明 使对于该问题说明的求解能归 结为被分解的多个子问题说明的并行求解 对并行分解有以下几点要求 各子问题的解能很容易组合成整个问题的解 而且分解后的子问题的求 解相对原问题应该容易些 各子问题相对独立 没有紧密的数据相关关系 没有频繁的交互作用 在一定的阶段或场合下是相对独立的 确保问题定义与需求不变 对于所有的结构单元 相互之间的关系 控 制相关和数据相关性 输入 输出关系 不变 完成准则必须与问题匹配 问题的性能指标能够从子问题的性能指标计 算而得 根据抽象级的不同 并行性可以分成多个级别 这里首先介绍一个粒度 g r a n u l a r it y 的 概念 又 称 颗 粒 尺 度 g r a i n s i z e 粒 度决 定了 并 行处理的 基本程序段 一般用细 中 粗来描述 这与处理级别有关 并行性在不 同的处理级别中得到开发利用 如图2 1 所示 五种程序执行级别体现了不 西南交通大学硕士研究生学位论文第1 4 页 同的算法粒度规模以及通信和控制要求的变化 级别越低 软件进程的粒 度愈细 而另一方面 粒度越细 并行性潜力越大 但通信和调度的开销 也越大 粗粒度 级 z 中粒度 级 3 级 4 细粒度 图2 1 并行性级别划分 另外一种划分方法 20 将并行性级别划分六个抽象并行级 也就是问题 级 自 然并行性 说明级 论域分解 系统级 系统分解 算法级 数 据结构与求解过程的分解 程序级 并行语句与并行结构的识别和划分 以及指令级 并行操作指令的识别 如向量化 流水线等 问题级并行处理中的问题可以 被看作是由多个基于各种不同自 然规律动 态连接而成而又彼此相关的实体组成的复杂系统 而在这些物理系统中 物理法则的操作本质上是并行的 而说明级实质上是一种数学模型级 为 了能使计算机模拟某些物理过程 必须将某些复杂系统的实体映射到便于 计算机处理的特定数据结构上 这就需要将时间和空间离散成数字栅格形 式 但仅做到这一点是不够的 要保证计算过程的并行性 还必须也将该 数据结构分解使之能被一定系统的处理机并行操作 这些物理过程是相对 独立的 从而反映这些物理过程的数学模型可以分成多个进程或任务 这 样的分解称之为功能分解 在系统级上 并行性是通过论域功能分解来实 现的 每一进程在一被分解的子论域上并行运行 在算法级是通过将数据 结构与求解过程的分解而实现算法的并行化 程序级主要根据相关分析理 西南交通大学硕士研究生学位论文第1 5 页 论识别程序中可以并行执行的语句 指令级主要是指可并行执行的操作 通常有向量操作 流水线操作以 及脉动操作 开发细粒度并行性可借助于优化编译器 它能自 动检测并行性扩并将源 代码变成运行系统能够识别的并行形式 循环并行性是在并行或向量计算 机上运行的最优程序结构 但递归循环要并行优化相当困难 过程级是中 粒度规模 与任务 过程 子程序 协同程序级相对应 作业步可重叠跨 越各种不同的作业 子程序级通常是在消息传递性多计算机上以s p m d 单 程序多数据 或 m p m d 多 程序多数据 模式调度给不同的处理机运行 另外 单处理机或多处理机的多道程序设计是在这一级进行的 作业 程 序 级对应的是在并行计算机上并行执行的独立程序 对于用少量性能较 高的处理机构成的超级计算机来说 开发这种粗粒度并行性是切实可行的 作业级并行性一般由加载程序和操作系统来处理 概括地说 细粒度并行性常借助于并行化或向 量化编译器来开发 中粒 度并行性的开发要求程序员以及编译器一起发挥作用 粗粒度并行性主要 取决于高效的操作系统和所用算法的效率 在通信方式上来说 共享变量 常用来支持细粒度和中粒度计算 消息传递方式己 用于中粒度和粗粒度 大规模并行性常常是在细粒度级上开发的 在并行性级别和调度 同步开销 之间进行折衷 用粒度组合和静态多处理机调度中的结点复制结合起来可 以确定最佳粒度和响应的调度方案 折衷调度优化过程包括四个主要步骤 构造细粒度程序图 调度细粒度运算 进行粒度组合得到粗粒度 在组合图基础上产生并行调度方案 2 4 元计算的提出 上一节中已 经提到 并行计算的实现可以在大规模并行处理系统 m p p 或者说 在并行机器上 而另一种方法是利用网络使众多的p c机协同工作 提供给用户一个高性能的虚拟并行机器 这种做法有两个显而易见的好处 1 可以充分利用大量闲置的计算资源 成功地实现 c p u周期窃取 2 可以突破硬件发展导致的速度提升的瓶颈 满足更高的大型计算的 需求 又有一种说法 将传统的并行计算机称为 紧凑型并行计算机 相应 地 将这种通过网 络连接提供的 虚拟的并行机称为是 松散祸合的并行机 1 9 9 7年美国 将 h p c c计划 高 性能计算与通信 计划 扩展为c i c计划 c o m p u t i n g i n f o r m a t i o n a n d c o m m u n i c a t i o n s p r o g r a m 1 9 9 8 年度的c i c 计划的主题是面向2 1 世纪的技术 修改其战略计划 其重点由 研制超级计 算机技术转变成研究二个方面的重大技术问题 第一个方面以原有的计划 为中心 即围绕a s c i 的战略联盟中心 提出研制每秒一千万亿次 1 0 1 5 p e t a f l o p s的超高性能计算机 第二个方面是根据目 前的技术发展和应用需 西南交通大学硕士研究生学位论文第1 6 页 求 面向2 1 世纪社会而提出的一个重要的研究领域 即研究和建立基于高 速网络的国家级先进计算基础设施 这两个方面的技术将成为下个世纪初 一个国家的经济和国防实力的重要标志 基于高速网络的国家级先进计算 基础设施计划的技术实质上是基于高速广域网络的高性能并行与分布式计 算技术 简称元计算技术 m e t a c o m p u t i n g r 1 3 由于计算机和网络通信技术 的迅猛发展 人类的应用需求朝着高性能 多样性 多功能发展 许多大 规模计算应用不仅仅需要一台超高性能的计算机 它还更需要由多种机器 组成 多个系统合作的网络虚拟超级计算机 这些应用要求将地理上分布 的 异构的多种计算资源通过高速网络连接起来 共同完成计算问题 促进网络高性能计算的原因包括 广阔的前景 随着工 n t e r n e t 的迅猛发展 网上已 有数千万的各类计 算机 包括为数众多的高性能计算中心 如何更好地扩展和利用网络资源 已成为人们日益关注的课题 显然 信息并不是网上唯一能获得的资源 网上计算机如果能被组织加以协调工作 将会形成有巨大潜力的并行计算 环境 直至形成一能力无比的全球计算环境 应用的驱动 实际的网络资源利用率是很低的 据有关统计 系统 平均使用率仅为 3 0 左右 有的空闲率竟达 9 1 如何利用闲散资源形成相 当强大的并行计算能力成为一个重要研究方向 单个的p c变得越来越功能强大 也就是说 p c机的性能在过去几 年中迅速增长 每1 8 2 4 个月就增长一倍 随着更快的处理器 效率更高的 多处理器计算机将进入市场 未来几年内这种趋势似乎将继续 此外 p c 机被广大的用户熟悉和使用 网络技术的突破 通信带宽在增长 延迟在降低 这归功于新的网 络技术和协议域网中的使用 t b p s 级传输速率和 1 0 z 比特以下的传输差错 率将成为现实 网络的带宽局限将得到极大缓解 安全性大大增加 网络 的瓶颈将从 低速传输 转移到 高速传输 低速管理软件 上 网络高性能计算具有独特的优势 可扩展性强 计算资源几乎可方 便地任意扩展 可靠性高 己存在大量成熟的网络技术和开发工具 许多 公用程序已逐渐标准化 据资料统计 33 一般计算机系统平均使用率仅为 3 0 左右 有的空闲 率竟达9 1 而许多桌面网络工作站和微机的c p u利用率都小于 1 0 因 此 自 然想到要利用这些闲散的 c p u处理能力 这也称之为 c p u周期窃 取 如果我们能够有效地利用这些资源 将形成如图1 1 所示的金字塔效应 网络高性能计算的根本目 标是使用网络技术连接一组机群或组织网络上 分散计算资源形成一个类似m p p 并行机的高性能计算环境 九十年代初 研究人员开始将他们的串 并行程序分解到联网的机器上 执行 应用 c o n d o r 对串行任务 和 p v m 对并行任务 等软件工具 西南交通大学硕士研究生学位论文第1 7 页 研究人员可以 利用联网的异构工作站和超级计算机提高计算效率 1 9 9 4年左右 元计算 在西方开始流行起来 通常它表示在联网 一 般是局域网 的计算机上执行一个单个的 通常是较大和复杂的 任务 这些机器可以是向量机 并行机和一般的个人计算机 当时的主要目的是 把计算的主要部分分散到最优资源上 例如把 c a d 栅格生成和其它的前 处理放到用户工作站上进行 将仿真部分放到向 量机上进行 将大量运算 部分放到并行机上 将后处理 图形输出 动画 虚拟现实 放在图形终 端上进行 此后 元计算的研究迎来了一个高潮 各种研究组织设计和实 行了各种不同的 元计算环境将串 行和并行任务分布到l a n w a n和i n t e rn e t 上不同的计算资源上执行 今天 一台 元计算机 可以 包含成千上万的宿主机 从p c到超级并 行计算机 跨越各种不同的网络平台 其目的一般是用以建立一个强大的 用户友好的硬件 软件环境 提供一个对网络上可用资源的统一的 透明的 应用接口 面向 用户的广域元计算系统的程序设计环境它应当能够允许集成各种独 立开发的软件包 以便广域区域中用户可以通过底层基础平台访问它们 达到软件重用和模块可交互性 其中 对象技术将会成为主要的实现技术 之一 基于 c o r b a j a v a或 w e b等技术的分布式对象程序设计环境和 工具将适合于建造复杂的计算对象和移动计算对象 但是高性能和实时性 要求是对分布式对象技术的一个严峻挑战 除此之外 在元计算中还涉及到很多其它的问题 如分布式并行计算 负载平衡 资源管理 可靠性 安全性 容错性 异构性 地址透明 可 伸缩性 另外 要引起重视的还有分布式计算资源 独立的本地文件系统 和分布于网络的各文档的 无缝 接口 以及保护计算客户方和计算资源 提供者双方的安全机制 保证传输信息置信度的校验机制 川 最后 受网 络带宽相对较窄的影响 元计算的效率和延迟也必须引起足够的重视 如图2 2 所示 横坐标为参加元计算的独立的机器数目 这里假定每台 机器的计算能力都是一样的 竖坐标为一个元计算任务的完成时间 曲 线i 表示随 着机器数目 的 增加 单纯消耗在计算任务上的总的时间在 减少 曲 线n 表示随着机器数目 的增加 消耗在诸如计算控制 负载平衡 等方面的 额外 支出时间在增加 所以需要寻找图中 所示的最佳点 a 使用这个数目 的机器参与元计算 任务的完成时间会降到最少 目 前 美国在此方面的研究工作己经开展起来了 并取得了一些实验性 研究成果 但总体上讲 整个研究处于起步阶段 国内的研究基本集中在 局部网的并行计算 对广域并行与分布计算的研究较少 且无实验环境 国防科学技术大学并行与分布处理国家重点实验室在此方面开展了初步的 研究工作0 3 但是 该技术的 相关领域 m p p 网 络 通信领域 中间件 虚拟现实和并行算法等在我国都有大量而深入的研究和技术储备 也有一 西南交通大学硕士研究生学位论文第1 8 页 定的网络基础设施 时间 机器数 目 图2 2 机器数与计算时间曲线图 西南交通大学硕士研究生学位论文第1 9 页 第3 章 有限元法的基本原理及其并行分解的可 行性 本章将简单介绍有限元法及弹性接触问题有限元法的基本思想 并分析 有限元法并行求解实现的可行性和方法 3 1有限元法的基本原理 有限元法的基本思想是将连续的求解区域离散为一组有限个 且按一定 方式相互联结在一起的单元的组合体 由于单元能按不同的联结方式进行 组合 且单元本身又可以有不同形状 因此可以模型化几何形状复杂的求 解域 有限元法作为数值分析方法的另一个重要特点是利用在每一个单元 内假设的插值函数来分片地表示全求解域上待求的未知场函数 单元内的 插值函数通常由在单元的各个结点的数值及其导数表示 这样一来 一个 问题的有限元分析中 未知场函数或及其导数在各个结点上的数值就成为 新的未知量 也即自由度 从而使一个连续的无限自由度变成离散的有限 自由度问题 一旦解出这些未知量 就可以通过插值函数计算出各个单元 内场函数的近似值 从而得到整个求解域上的近似解 显然随着单元数目 的增加 也即单元尺寸的 缩小 或者随着单元自由度的增加及插值函数精 度的提高 解的近似程度将不断改进 如果单元是满足收敛条件的 近似 解最后将收敛于精确解 2 6 有限元法分析计算的思路和作法可归纳如下 1 物体离散化 将某个工程结构离散为由各种单元组成的计算模型 这一步称为单元剖 分 离散后单元与单元之间利用单元的节点相互连接起来 单元节点的设 置 性质 数目 等应视问题的性质 描述变形形态的需要和计算精度而定 一般情况 单元划分越细则描述变形情况越精确 即越接近实际变形 但计算量越大 所以有限元法中分析的结构已不是原有的物体或结构物 而是同样材料的由众多单元以一定方式连结成的离散物体 这样 用有限 元分析计算所获得的结果只是近似的 如果划分单元数目 非常多而又合理 则所获得的结果就与实际情况相符合 2 单元特性分析 1 选择位移模式 在有限元法中 选择节点位移作为基本未知量时称为位移法 选择节点 西南交通大学硕士研究生学位论文 第2 0 页 内力作为基本未知量时称为力法 取一部分节点内力和一部分节点位移作 为基本未知量时称为混合法 有限元法中位移法应用范围最广 当采用位移法时 物体或结构物离散化之后 就可把单元中的一些物理 量如位移 应变和应力等由节点位移来表示 这时可以对单元中位移的分 布采用一些能逼近原函数的近似函数予以描述 通常 有限元法中我们就 将位移表示为坐标变量的简单函数 这种函数称为位移模式或位移函数 如 一 艺 a w 其 中 是 待 定 系 数 是 与 坐 标 有 关 的 某 种 函 数 2 分析单元的力学性质 根据单元的材料性质 形状 尺寸 节点数目 位置及其含义等 找出 单元节点力和节点位移的关系式 这是单元分析的关键一步 此时可以通 过虚功原理或最小势能原理导出单元刚度矩阵 这是有限元法的基本步骤 之一 3 计算等效节点力 物体离散化后 假定力是 通过一个单元传递到另一个单元 但是 对于 实际的连续体 力是从单元的公共边界传递到另一个单元中去的 因而 这种作用在单元边界上的表面力 体积力或集中力都需要等效地转移到节 点上去 也就是用等效的节点力来替代所有作用在单元上的力 3 单元组集 利用结构力的平衡条件和边界条件把各个单元按原来的结构重新联接起 来 形成整体的有限 元方程k q f 其中 k是整体结构的刚度矩阵 9 是结点位移列阵 f 是载荷列阵 4 求解未知结点位移 解有限元方程式得出位移 这里 可以根据方程组的具体特点来选择合 适的计算方法 通过上述分析 可以看出 有限元法的基本思想是 一分一合 分 是为了进 行单元分析 合 则是为了对整体结构进行综合分析 3 1 1静力分析问题 首先考察结构的静力分析问题 设所给定的问题中 待求函数为u 使 它在求解域q中满足微分方程组 a u a u a 2 u 1 t 0 设在该域的边界r 上满足某些边界条件 3 1 西南交通大学硕士研究生学位论文第2 1 页 b u 二 b u b u 一 t 0 3 2 对所求的函数可以是一个标量 也可以是若干变量组成的一个向量 同 样 微分方程可以是单个方程或联立方程组 因此 我们在上面使用了矩 阵符号 如果微分方程是线性的 可把式 3 1 和 3 2 改写成 a u 二 l u p 0 在 内 3 3 b u m u b 0 在r 上 3 4 以 上就是边值问 题的微分方程提法 我们不去寻找式 3 1 和 3 2 或 3 3 和 3 4 的解 因为对于大多数问 题 要得到它的解是十分 困难的 现在 若把它改提为与之等价的求泛函的极值或驻值问题 即是 寻求边值问题的变分解法 设有一下积分形式定义的泛函 r 1 工 式中 a 户 u u r7 x 工 e u 立 d l 一欲 3 5 u 是未知函数 而f和e是给定的算子 对于小变化8 u 使11 取极值的函数u 就是连续体静力问题的解 因此 对于连续体静力问题 的解 有极值条件 s r 1 0 3 6 这叫做变分原理 不难得知 为使泛函r 1 取极值 由式 3 5 经过某些运算之后 就可 写出 s n 一 工 5 u t a u d f 2 工 5 u t b u d r 一 0 3 7 因为上式必须对任意的变分6u 都成立 所以 必有 a u 0 3 8 a b u 0 3 8 b 不难证明 a u 0 正好对应于原给定问题的控制微分方程 而 b u 0 正好对应于原给定问 题的边界条件 而式 3 8 称为e u l e r 微分 方程 对于任一变分原理都可建立相应的e u l e r 方程 但不是所有的微分方 程都存在对应的变分原理 以上说明了把问题提成微分方程的求解问题是等价于把问题提成泛函的 极值求解问题 另一方面 如能找到问题的变分原理 则能对所给问题提供近似解法 当然 由此得出的近似解与所采用的近似解法的精度有关 西南交通大学硕士研究生学位论文第2 2 页 3 1 2 r i t z 近似解法 这个方法是研究变分命题而得到的一个古老的方法 但仍是一种有效的 近似解法 假设由式 3 5 形式的泛函 其极值条件为6 r 1 0 设试函数取为通 常的形式 即 u 二 3 9 a 从 艺间 式中 n 为 通 过自 变 量 所选定的函 数 而ai 是 待定的 未知函 数 r it z 方 法的实质 就是挑选这些未知参数 而使式 3 5 的 泛函达到极值 而且 要求所选定的函 数n i 应满足边界条件 在当n 时 只 要函数n 是完备 的 则u 就在能量的意义上收敛于问题的真实解 现将式 3 9 代入泛函 式 5 中 s r l 一 契 5 十 弊 5 a a o a 并写成 塑 s 二 0 占a 3 1 0 上式对于任意的6 a 均成立 于是有方程组 3 1 1 姐一拟 击一飒 胡一由 由 此可求出参数al 这就是r i t z 近似解法 显然 对于许多问题 要在 整个求解区域上选择恰当的试函数 在域内或域的边界上均满足问题所提 的条件 这是十分不易办得到的 这也就是 r it z方法不能广泛应用的一个 重要的原因 3 1 3有限元近似解法 有限元近似解法 可以说是在 r i t z法的基础上发展起来的 就其本质 上来讲 仍是r i t z 方法 假设仍有式 3 5 形式的泛函 其极值条件为s r l 0 对于有限元近 似解法而言 它寻求如下形式的近似解 即 西南交通大学硕士研究生学位论文第2 3 页 八 u u 艺n a n a 3 1 2 应当指出 现己 把问 题的求解区域离散为有限个单元 而函数 n 是在 有限单元内 选 取的 因 此 上 式中的n 为单 元 节点i 的 形状函 数矩阵 而a 为未知的单元节点变量向量 n 为单元的节点总数 若将式 3 1 2 代入泛函式 3 5 中 并把决定未知参数 31的方程写 成积分形式 有 工 g u d q 十 工 g u d r 0 3 1 3 这些积分形式将允许逐个单元的作出近似 并且可按有限元分析中对离 散系统所建立的方法来实 现组集 这是因为如果函 数 g及9 是可积的 就 有 工 g d q 工 g d r 一 e i g d q f g j d r 3 1 4 式中s 2 是单元的域 而r 是单元的边界 从上面的分析可以看出 r i t z 近似解法与有限元近似解法的重要区别 r i t z 近似解法是在 整个域上挑选 n 而且要 求该函 数在域内 和域的 边界 上 均满足一定的 条件 有限 元近似解法是在单元上挑选函 数 n 它只要求在 单 元内 部和单 元 边界 上 满 足 一 定的 条 件 实践 表明 在单 元上 挑 选n 是 较 容易的 这个差别 具有十分重要的意义 它使有限元的实用价值远远超 过了r i t z 法 若将式 3 1 2 代入泛函式 3 5 中去 并写出 s ii 留 s 一 癸 s 一 a r1 9as 上式对任意的 5 a 均成立 于是得方程组 3 1 5 nu 一一 一一lweesj 3 1 6 如果泛函1 1 是二次泛函 即函数u 及其导数以 幂次不超过2 的形式出现 则式 1 6 可化为一般的线性形式 即 西南交通大学硕士研究生学位论文第2 4 页 k a f 0 3 1 7 k 一 叉k j f 一 艺 f 3 1 8 3 2有限元并行解法 据美国康奈尔大学d o n a ld w wh i t e 和j o h n r a w 在 1 9 8 7 年的不完全 统计0 1 从 1 9 7 7年到 1 9 8 7年十年间 有关有限元方法和相应的数值并行 计算的文章己发表近 2 0 0篇 近几年 有关这方面的研究和应用性文章的 数量更是有增无减 有限元并行计算的