（管理科学与工程专业论文）大规模通信网并行分布式仿真的研究.pdf

摘要 网络仿真是近年来兴起的种网络研究技术，它利用数学建模和统计分析的 方法模拟网络行为，从而获取特定的网络参数。网络仿真在协议开发、标准制定、 网络规划设计和网络运营管理等各方面，可以极大地提高效率，节约投资，缩短 开发设计时间，为通信网络的发展提供了强有力的支持。 通信网的发展日益向大型综合多业务网络方向发展，在同一网络系统中可能 包含多个不同功能的子网，运行不同的网络协议，承载多种综合网络业务。单机 的能力在面对通信网仿真问题时，常常会无能为力。本文从理论、试验等多方面 研究，试图基于性能价格比高的微机网络系统，寻求通信网并行仿真的一般理论 及设计方案，从丽解决大规模通信网的仿真问题。 本论文共分五章。第一章介绍了通信网仿真的研究和实用概况，并对现有的 通信仿真技术作比较，明确大规模通信网的仿真技术的发展方向。第二章主要介 绍目前并行计算系统的发展状况，比较目前的并行系统。确定本论文的研究重点： 用微机网络系统来仿真大规模通信网的问题。第三章研究大规模通信网并分布式 仿真的方法，研究通信网仿真中并行划分，粒度确定，通信设计，任务分配的理 论及方法。第四章通过对中继电路网r t n r 选路模型的仿真，设计具体的仿真方 案，并分析系统的仿真性能。第五章研究无时钟法在通信网仿真中应用，研究其 优势及使用范围。 关键词：通信网仿真、并行计算、任务划分、粒度 a b s t r a c t a sa ne f f i c i e n tm e a 拇st o g a i n a n i n s i g h t i n t ot h en e t w o 呔s p e r f o r m a n c e s i m u l a t i o n t e c h n o l o g y i s p l a y i n g am o r ea n dm o r e i m p o r t a n tr o l e i n r e s e a r c h i n g c o m m u n i c a t i o nn e t w o r k si nr e c e n ty e a r n e t w o r kb e h a v i o rc a nb es i m u l a t e db y c o n s t r u c t i n gm a t h e m a t i c sm o d e la n du s i n gs t a t i s t i c a la n a l y s i s w i t ht h ea p p l i c a t i o no f s i m u l a t i o nt e c h n o l o g yi nd i f f e r e n tk i n d so ff i e l d ss u c ha sn e t w o r kp r o g r a m m i n ga n d d e s i g na sw e l la sn e t w o r ko p e r a t i o na n dm a n a g e m e n t e t c i tc a nb em o r ee 臻c i e n ta n d e c o n o m i c a lw h i l ef i n i s h e di nas h o r t e rt i m e s os i m u l a t i o nt e c h n o l o g yb e c o m e sa p o w e r f u l t o o li nd e v e l o p i n gc o m m u n i c a t i o nn e t w o r k h o w e v e r ，w i t hn e t w o r k s c o m p l e x i t ya n ds c a l ei n c r e a s i n ge x p o n e n t i a l l y ，s i n g l e c o m p u t e rc a l l tm e e tt h en e e do fs i m u l a t i n ge x t r e m e l yl a r g e s c a l ec o m m u n i c a t i o n s n e t w o r ke f f i c i e n t l ya n dq u i c k l y , w h i l ep a r a l l e ls i m u l a t i o np r o v i d e saf e a s i b l ew a y h a v i n g i n t r o d u c e dap cn e t w o r ks y s t e mf o ri t s h i g hc o m p u t i n gp o t e n t i a l ，g o o d p e r f o r m a n c e c o s ta n df e a s i b l ea r c h i t e c t u r e ，t h ea u t h o rh a st r i e dt os t u d yag e n e r a l m e t h o da sw e l ia sd e s i g nm o d e lf o rl a r g e s c a l ec o m m u n i c a t i o nn e t w o r k ss i m u l a t i o n b a s e do np cn e t w o r ks y s t e mj nt h i st h e s i s t h e r ea r et o t a lf i v ec h a p t e r si nt h i s p a p e f ic h a p t e ro n eg i v e s ar e v i e wo f c o m m u n i c a t i o nn e t w o r k s s i m u l a t i o n c h a p t e r t w o c o m p a r e s v a r i o u s p a r a l l e l c o m p u t i n gs y s t e m sa n d t h e np o i n t st ot h e e m p h a s e so f t h i sp a p e r , t h a ti st h em e t h o do f p a r a l l e ls i m u l a t i n gc o m m u n i c a t i o nn e t w o r k sb a s e do np cn e t w o r k ss y s t e m c h a p t e r t h r e ep r o v i d e st h e o r ym o d e li np a r a l l e ls i m u l a t i n gc o m m u n i c a t i o n n e t w o r k s c h a p t e r f o u rg i v e sa ne x p e r i m e n to fat r u n kg r o u pn e t w o r k ，t h e np o i n t so u ts o m ea s p e c t s n e e d e df u r t h e rr e s e a r c h c h a p t e rf i v ew o r k so v e rt h en o n - c l o c km e t h o du s e di n p a r a l l e ls i m u l a t i n gc o m m u n i c a t i o nn e t w o r k s k e yw o r d s c o m m u n i c a t i o n sn e t w o r k ss i m u l a t i o n 、p a r a l l e l c o m p u t i n g 、t a s k p a r t i t i o n 、g r a n u l a r i t y 北京邮电大学硕士生论文蚺1 页共3 7 页 第一章通信网仿真 1 1 通信网仿真的概述 1 、通信网仿真 通信网络仿真，是近年来兴起的种网络研究技术。它通过对通信网络的框 架结构和协议构成建立数学模型，以数学形式描述网络行为，通过定义业务事件、 协议流程等计算机手段仿真实际网络的运行，从仿真结果中给出所感兴趣问题的 评估报告，及时发现并解决设计问题，提出改进和优化方案。 目前，通信网仿真的方法已经应用于通信网络的协议开发、标准制定、网络 规划设计、网络流量控制策略研究以及网络运营管理等等各个方面。它可以极大 地提高效率，节约投资，缩短开发设计时间，为通信网络的发展提供了强有力的 支持。 2 、通信网仿真的技术特点 通信网络仿真是一种利用数学建模和统计分析的方法模拟网络行为，从而获 取特定的网络特性参数的技术。 数学建模包括网络建模( 网络设备、通信链路等) 和流量建模两个部分。模 拟网络行为是指模拟网络流量在实际网络中传输、交换和复用的过程。网络仿真 获取的网络特性参数包括网络全局性能统计量、网络节点的性能统计量、网络链 路的流量和延迟等，由此既可以获取某些业务层的统计数据，也可以得到协议内 部的某些特殊的参数的统计结果。一个优秀的通信系统仿真评估系统具备面向对 象、分层建模、模型定义、仿真自动生成等特征。 通信网仿真技术有两个显著的特点： 1 ) 通信网仿真能够为网络的规划设计提供可靠的定量依据。网络仿真技术能 够迅速地建立起现有网络的模型，并能够方便地修改模型并进行仿真，这使得网 络仿真非常适用于预测网络的性能，回答“w h a t i f ”这样的闻题。 2 ) 通信网仿真能够验证实际方案或比较多个不同的设计方案。在网络规划设 计过程中经常出现多个不同的设计方案。通过为不同的设计方案建立模型，进行 模拟，获取定量的网络性能预测数据，网络仿真能够为方案的验证和比较提供可 靠的依据。 3 、通信网仿真的应用 通信系统的仿真，具有广泛的使用范围。它可以用于网络建设的前期规划， 也可用于网络改造中的系统分析，其应用包括：通信网的网络建设规划；通信网 络的结构和协议的研究开发与验证；辅助网络的监控、管理及网络优化；资源规 划与网络性能分析；网络系统的构建与集成中对于多种不同的连接技术，多种协 议、算法建模仿真，模拟网络中断和恢复的通告，描述随机发生的网络危险等。 在网络规划和设计过程中，目前大都还采用的是经验、试验及计算等传统的 网络设计方法。当网络规模较小、网络拓扑结构比较简单、网络流量不大的时候， 大规模通信弼并行分布式仿真的研究 北京 i l j 电大学硕士生论文 以经验为主、辅之以试验和数学计算等手段进行网络规划设计还是可行的，不过， 当网络规模越来越大、网元类型不断增多、网络拓扑日趋复杂、网络流量纷繁交 织时，以经验为主的网络设计方法已经无法满足需要。网络仿真技术正是在这种 需求拉动下应运而生的。网络仿真技术以其独有的方法能够为网络的规划设计提 供客观、可靠的定量依据，缩短网络建设周期，提高网络建设中决策的科学性， 降低网络建设的投资风险。 1 2 通信网仿真软件 目前，比较优秀的、常用的通信网络仿真软件有：m i l 3 公司的0 p n e t 、c a d e n c e d e s i g ns y s t e m s 公司下属a l t a 小组开发的b o n e s 和c a c i 公司的c o m n e t i i i 。 o p n e t 是目前业界公认的最优秀的通信网络、设施、协议的仿真及建模工具。 它面向对象的建模方式和图形化的编辑器能够真实地反映实际网络及各网络成分 的结构，系统可以直接映射到模型上。它无与伦比的灵活性使得它几乎能够支持 所有类型的网络和网络技术，被广泛地用作网络的决策支持工具，用来对现有的 或设计中的网络、系统或进程的性能和行为进行细致洞察和分析。 b o n e s ( b l o c k o r i e n t e dn e t w o r ks i m u l a t i o nd e s i g n e r ) 是一个交互式的通信系统 体系结构和协议的设计、仿真及分析软件，功能强大并且十分灵活，适用于无线 通信、多媒体、网络、计算机体系结构以及其他电子系统。 c o m n e t i i i 也具有图形化的界面，使用也很方便，它适用于从简单的局域网 到复杂的企业级网络系统的性能分析和评估。总的来看，无论是在仿真功能、面 向对象的建模方式模型库的扩展继承性和可重用性方面，还是动态监视和统计分 析方面o p n e t 都更胜一筹。 通信网络仿真软件可以对特定的类型的通信网络进行仿真而不需要进行编 程，具有广泛可选的各种仿真模型，使编程时间大大缩短。但是，通信网仿真软 件也存在着不足之处： 1 ) 网络仿真软件的操作相当复杂，使用者一般需要半年左右时间的培训和熟 悉才能够熟练地掌握。不仅要求操作者熟悉这些工具，还要求操作者掌握 一定的网络技术基础和具有熟练地编程技术，也影响了这些工具的使用和 推广：可以说仿真结果的可靠性在很大程度取决操作者的技术素质。 2 、目前世界上的网络仿真软件可以分为高端和低端两类产品。高端产品价位 一般在数万美元每个用户l i c e n s e 左右，低端产品价位在数百至数千美元 之间。价格比较昂贵，一般的企业、机关、研究机构都难以承受。 3 1 无论是高端还是低端产品，基本都是来自于美国，技术垄断严重。而国内 在这一领域的研究大都针对某一个具体问题，从而没有形成一个通用的网 络仿真平台。 1 3 通信网建模与仿真的发展趋势 8 0 年代以前，仿真系统的研制主要是开发大量的面向微分方程、方框图、结 构图的仿真程序和仿真语言，而仿真语言所能提供的有限的建模语句难以适应大 型网络模拟的多样性和复杂性。 大规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文第3 页共3 7 页 近几年来，建模技术、图形技术、人工智能技术、知识工程技术、程序自动 设计技术等在仿真建模过程中的综合应用，成为网络仿真领域的“热门”，以自然 语言接口、交互式图形接口、交互式会话接口为主要形式的智能化人机界面，可 缩短用户描述问题的方式与仿真模型的最终表示之间的差距，产生简练、直观而 有效的输入方式，满足仿真输入的多样性和复杂性的要求。建模与仿真功能的智 能化、集成化、仿真软件设计和自动化，是仿真系统开发的主要趋势，这也是下 一代网络仿真的发展方向。 近年来，由于数据网络日趋复杂、网络规模日趋庞大，网络仿真技术应用于 网络规划和设计的需求日渐强烈。此外，仿真系统起着越来越重要的作用，导致 对仿真置信度要求的提高。这样，对仿真技术和计算机系统的要求大幅提高。于 是，仿真系统向分布式仿真发展，也是通信网络仿真发展的一个重要方向。 1 4 并行计算平台的引入 通信网络的仿真一般运用离散事件模拟( d e s ) 方法。网络用户对网络资源的 占用要求、网络按一定的协议对资源的分配及网络资源最终的回收等，从时间上 看都是顺序进行的。无论是早期的通信网络模拟方法( 采用像g p s s 这样的通用 模拟语言) ，还是近年来出现的图形化的、面向通信的模拟软件包( 像o p n e t 、 b o n e s 、c o m m n e t 之类) ，其核心大多基于离散事件模拟方法，这种方法特别 适用于单处理器计算机的模拟环境。但是，我们注意到： 1 ) 完全顺序的模型与通信网络的本质存在着一定的差别 通信网络运行中，某一时刻在网络的不同部分，完全有可能同时发生网络资 源的占用请求、分配和回收等事件。这些并发的事件对网络性能的影响是传统的 d e s 方法难以表达的。因此，根据其本质的并行性，并行计算平台更适宜于仿真 通信网的网络行为。 2 1 单台处理机的仿真环境难以有效地模拟日益扩大的通信网络 以前通信网络仿真往往局限于短时间内小网络模型的仿真。随着网络普及， 网络硬件设备呈指数增长，不论纯数学分析方法、建立原型系统模型，还是常规 串行离散事件仿真肯定对这样的呈指数增长的、大规模复杂问题无能为力。采用 并行计算平台可以按需扩充系统的计算能力，从而提高对庞大网络的仿真效率。 这是解决问题的一个有效途径。 本论文主要是研究通信网络的并行分布式仿真技术与方法，利用并行分布式 系统提高大规模通信网的仿真效率。 大规接通信网并行分布式仿真的研究 北京邮电大学硕士生论文笫4 页共3 7 页 第二章并行计算系统 目前，人们获得超级计算能力主要是依靠各种高性能的并行计算系统。并行 处理是指同时对多个任务、多条指令或多个数据项进行处理。如前所述，随着通 信网规模的日益庞大，网上业务量的迅猛增长，某些通信网仿真问题已成为了一 个规模巨大的问题。当单机的处理能力无法满足需求时，引入并行处理是唯一有 效的途径。 2 1 并行计算的发展 自从2 0 世纪6 0 年代起，人们就开始探索数值计算方法的并行化技术和并行 计算机结构。至今，并行计算机的发展已有3 0 多年的历史。在这期间，人们研制 了各种不同类型的并行计算机系统，并行处理方式经历了从阵列机( s i m d ) 、向 量机及向量并行机、共享存储的对称多处理器系统( s m p ) 、分布存储的大规模并 行处理系统( m p p ) 到n u m a ( 非一致访问的分布基享存储) 并行机系统和计算 机集群系统( c l u s t e r s ) 的演变过程。 向量机、对称多处理机( s m p ) 、大规模并行机( m p p ) 和工作站集群( c o w 或n o w ) 是四类应用比较广泛，技术相对成熟的并行计算机。向量机由于应用 范围窄，实际问题向量化困难已经逐步退出历史舞台，当代主流并行机是s m p 、 m p p 和c o w 。s m p 目前被广泛应用于并行服务器；m p p 可以提供其它并行机无 法达到的超级计算能力，但价格昂贵，制造困难；c o w 是用商品处理器和商品网 络连接而成的并行系统，具有性能价格比高等许多优点，因此发展很快，已经成 为并行领域新的主流。 2 2 并行机系统 i 、对称多处理机( s m p ) 对称多处理机( s y m m e t r i cm u l t i p r o c e s s o r , s m p ) 普遍采用。它是应用最广泛的并行计算机。 结构在现今的并行服务器中 s m p 的存储器系统结构一般属于均匀存储访问 ( u n i f o r mm e m o r ya c c c s s u m a ) 模型。s m p 系统中所有 处理器通过高速总线或交叉开关连向共享存储器。每个处 理器可带私有的高速缓存( p c 表示处理器和高速缓存， s m 表示共享存储器) 。每台处理器访问共享存储器的任何 部分都要通过互连网络，所有处理器访问共享存储器同一 总线或交叉开关 地址单元的时间相同，物理存储器被所有处理器均匀共享。 i n 2 - 1s m p 结构模型 s m p 系统中任何处理器均可访问任何存储单元和i 0 设备。操作系统可按各 处理机的负载灵活地调节处理机的任务，负载平衡很容易完成。各处理机通过共 享同一内存地址单元来相互通信。这种通信方式不仅快捷可靠，而且简化了s m p 上编程。s m p 系统每个处理器可以平等地访问内存及i o 的对称的逻辑结构及其 大规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文第5 页共3 7 页 对称的硬件结构有利于开发较高的并行性。如果系统中只有一台处理器可以访问 i o ，其它处理器就不能独立地工作，这就限制了并行度的提高。 对称性是s m p 的优点，但它也给s m p 带来了一些问题：所有的处理器都可 以访问存储器和i o 设备使得存储器和i o 的负载很大，容易成为系统的瓶颈。 在许多应用环境中由于争用共享总线和争用共享存储器，能有效使用的处理器不 超过4 个”1 ，这就限制了系统中处理器的数量；所有处理器共用一个存储器和一 个操作系统，所以总线、存储器、操作系统中有一个失效就会导致整个系统的崩 溃，系统不够可靠和稳定。s m p 系统的互连网络使用总线，总线是不可扩展的， 限制了系统中处理器的数量。 目前人们采用c c - n u m a 体系结构来解决s m p 的可扩展性问题。c c n u m a 是将一些s m p 机器作为结点用互连网络连接起来形成的一个较大的系统，它是 s m p 的扩展。c c n u m a 系统中各结点间不用总线连接，因此可以包含更多的结 点，保证了系统的可扩展能力。同时c c n u m a 系统仍然是单一地址空间，所有 结点中的存储器统一编址，构成一个统一的地址空间，该地址空间被所有的处理 器共享，保持了s m p 系统易于编程的特点。 2 、大规模并行机( m p p ) 大规模并行机( m a s s i v e l yp a r a l l e lp r o c e s s o r ，m p p ) 是指由几百或几千台处理 机组成的大规模并行计算机系统。 图2 2m p p 结构模型 m p p 使用物理上分布的存储器，专门设计制造 的高速互连网络。每个结点内有一个或多个处理器、 高速缓存、一个本地存储器，有的m p p 系统结点内 还有磁盘。结点内用本地互连网络将各部件连接起 来。在早期m p p 中，结点内通常使用总线结构，目 前的m p p 多使用交叉开关。 从存储系统的角度，m p p 系统大多采用非远程 存储访问( n o r e m o t em e m o r ya c c e s s ，n o r m a ) 结构。在这种结构中，所有的存储器在物理上是分 布的，而且都是私有的。每个处理器能直接访问的 只有本地存储器，而不能直接访问其它处理器的存储器。结点之间的通信采用消 息传递的方式。分布存储的优点是系统的可扩展性好，但是消息传递方式使得编 程困难，即可编程性不好。 开发m p p 的目的是通过大量的硬件得到高性能。所以m p p 开发中的一个重 要问题是：系统的性能是否随着处理器数量( 近似) 线性地增长。另一个问题是 系统的成本。因为m p p 要使用大量的硬件，因此要尽量降低每一部件的成本。 目前的m p p 都是通用的系统，能支持不同的应用，不同的算法；都支持异步 m i m d 模式，支持流行的标准编程模式( p v m 、m p i ) 。 总之，处理器数量大是m p p 区别于其它系统的主要特点。m p p 巨大的计算能 力来源于大量的处理器，它的许多问题和技术困难也与此有关，例如通信困难， 成本高等。m p p 可达到很高的峰值速度，但由于通信、算法等原因，持续速度通 常只有峰值速度的3 1 0 。m p p 是最有希望达到3 t 性能目标和解决重大挑战性 大攫填通信网并行分布式仿真的研究 北京邮电大学硕士生论文第6 页共3 7 页 问题的系统，但鼹如何能提高持续速度仍是一个问题。 3 、工作避集瓣( c o w 工作站集群( c l u s t e ro f w o r k s t a t i o n s ，c o w ) 是实现并行计算的一种新主流技 术。c o w 又称为n o w ( n e t w o r ko f w o r k s t a t i o n s ) ，是指用商龋网络将工作站连 接起来构成的并行计算瓤系统。这里静工作蘩泛指高档计算枫，可以是高档徽梳， 也可以是正作站或s m p 对称多处理机。 图2 3c o w 结构模黧 集群跫处理器和网终技术不龋提高的产物。商品处理器运算速度飞速提麓， 并且成本不断下降。网络技术的进步使得商品阐络的带宽已经很高。目前，徽多 商品网络的带宽已达g b p s 量级。高速的网络辫加上特殊设计的网络协议，典传 输速度己能达嚣甚至超过菜些m p p 专门定鬣静羯络。遮藏为势行诗算豹逶信键供 了有力的保障。 与m p p 握毙，集群搜爆蠢熬网络，每个结点枣宠黢的操臻系统，这绘集耧繁 米了一蟪特殊的技术问题。集群系统中的关键技术包括通信技术、并行程序设计 环境、单一系统映像( s i n g l es y s t e mi m a g e ，s s i ) 等。 随旃商品处瑾器性煞的不断提高，簇群各络点静鲶理速度邑稻当藤，翻约集 群性能的主要是结点间的通信遮度。如果通信速度跟不上，备结点的处理能力就 发挥苓窭来。提凑逶镶速度曩懿麸硬 睾软 孛黎采取了揍憨。骥终方瑟楚尽量傻羁 高速网络。近来出现了许多新型的高速网络，比如快速以太网、a t m 、m y r i n e t 等。它们的带宽已达g b p s 数爨级。 为了便于用户使用，集群系统必须给用户提供一个方便荔糟的并行程序设计 环境。躅前集群系统上广泛使用的并行程序设计环境谢p v m 、m p i 、e x p r e s s 、p 4 簿。它稻餐是基手港患传递方式静。其中p v m 器m p i 应焉褥簸多。p v m 是美国 橡树岭豳家实验室及美国几所大学联含开发的并行计簿工具软件，支持c 、c + + 鞠f o r t r a n 。m p i 是一个消息传递标准，是由m p i 委员会在1 9 9 2 年1 1 月至1 9 9 4 年l 胃举行的系列会议上逐渐产生的。它的设计菲常审馕，博采众长。p v m 和 m p i 都是免费软件，它们最大的优点是可以方便地进行再开发。 集群系统撼蹬之磊发震褥中分逐猿，已经成为銎藤研究翁热蠢。集群受到广 泛关注的原因鼹它有许多过去的并行系统不可比拟的优势。 大规模通信潮并行分布式仿真的研究 北京邮电大学硕：七生论文 第7 页共3 7 页 4 、总结 向量多处理机、s m p 、m p p 和集群系统是四类实用的并行计算机。向量机用 向量处理部件来提高向量处理速度，使用了向量链接、向量循环和向量递归技术， 但性能受到问题向量化的制约，需要算法和编译的支持。s m p 对称，共享存储器， 编程容易，广泛应用于并行超级服务器中。m p p 可以提供巨大的计算能力，其特 点是大规模并行计算，价格昂贵。集群系统使用商品网络和工作站，它是处理器 和网络技术飞速发展的产物。集群系统具有性能价格比高等优点，是新的主流技 术。 2 3 分布式系统 从硬件设备的组成和互联方式看，分布式系统，尤其是局域网与集群系统并 无本质区别。但不同的是，局域网中的各节点基本都是各自独立地工作的，只是 通过局域网共享资源，并没有单一系统图象；开发环境通常为d i s ，c o r b a 这样 的软件总线。 分布式系统是在地域上分散的，相对独立但相互联系和制约的各部分( 子系 统) 通过网络互联构成的，完成特定功能的整体。网络中的每个计算机都只控制 或管理一个子系统，有各自的目标与运作方式，并按照分布式系统的整体目标加 以交互、协调。各节点的耦合关系很灵活，依对应的子系统，或处于同等地位， 或有主从之分，即可以是异构的。分布式系统具有多系统图像，各系统图像与子 系统一一对应。子系统的自治性较强，相互之间耦合较为松散，可以对自己的功 能和信息加以控制，制定自己的策略和方法。 表2 1 各类并行系统的比较 特掰m p ps m p集群分布式系统 结点个数 1 0 0 1 0 0 01 0 1 0 01 0 0 左右1 0 】0 0 0 结点复杂性细、中粒度中或粗粒度中粒度大范围 结点间通信 娑霎篓递或者共共享存储器 消息传递 慧喜蠢件、r 9 c 、消 任务调度主机单一队列单一运行队列多队列协同运行独立的运行队列 单一系统映像部分支持支持完全的s s i某一层次支持目前不支持 结点操作系统 ；禾衰琶寝核和独立完整的o s n 个同类。s同类o s 或异构o s 多，单地址空间 地址空间( 分布式共享内单一 多多 存) 系统可用性低或中低高或者容错 中等 归属单位一个组织一个组织可以多个组织 多组织 紧耦合，在一个紧耦合，在一个松耦合，楼区范围松耦合，跨地域 连接距离 物理空间内机箱内( 依赖连接介质)( 地区或国家) 大规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文 第8 页共3 7 页 2 4 微机网络系统 微机网络系统是利用高速通信网络将一组高性能的p c 机连接起来构成的系 统。为了获得高效的并行性，系统需要并行程序和集成开发环境的支持，实现统 一调度、协调处理。这时系统可以归属于上述的集群系统。系统中的计算机和网 络可以是同种结构的，也可以是异种结构的，利用消息传递方式实现各个计算机 之间的通信。发挥多台p c 机的协同作用，实现p c 机对处理大的计算量，可以大 大缩短计算时间。 微机网络并行计算系统的出现和应用得益于计算机技术、网络技术和并行编 程环境的快速发展。首先、超大规模集成电路的发展，使微处理机的性能不断提 高，计算机价格不断降低，从而使直接采用p c 机作为节点机的系统具有高的性 能价格比。其次，网络技术的进步使系统的通信瓶颈得到缓解。并行编程环境的 开发使用户编写并行程序或改写串行程序更加容易。 同传统的并行处理系统相比，微机网络系统有以下几个特点： 1 1 并行计算系统的开发周期短：由于采用商用的p c 机，使得节点机和系统 的管理相对容易，不必重新设计节点机、操作系统和编译系统，节省了时 间，同时构成的系统可靠性较高。 2 ) 系统的扩展性好：系统采用通用网络，扩展容易。 3 ) 节约系统资源：系统可以将不同性能的计算机连接在一起，结构灵活，充 分利用现有设备。资源利用率比单机系统高得多。 4 1 投资风险小：系统总体看是一个并行计算环境，但是它的每一个节点又是 一个独立的微机。性能较低的机器也可以在系统中发挥作用。 5 1 用户编程方便：在微机网络并行计算系统中，程序的并行化只是在原有的 c 、c + + 和f o r t r a n 的等语言中加入相应的通信原语。 6 1 较高的性能价格比：由几台或几十台高档微机组成的集群系统就可以满足 相当广泛的应用要求。而且价格较低，具有较高的性能价格比。 大规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文第9 页共3 7 页 第三章通信网并行分布式仿真的研究 在前两章全面讨论了通信网仿真问题及并行计算系统，随着通信网规模的目 益庞大、网上业务量的迅速增长，应用并行计算系统来解决通信网仿真问题已成 为大势所趋。微机网络系统由高速通信网络连接一组高性能p c 机所组成，该系 统仿真大规模通信网由其不可比拟的优势。下面将重点研究利用微机系统来仿真 大规模通信网的方法。 3 1 通信网的并行分布式仿真 并行分布式仿真，即在多台微型计算机组成的平台上运行离散事件的仿真程 序，其中每台微机仿真一个通信子网的网络行为，多台微机协同工作所形成系统 以实现对一个规模庞大、拓扑结构复杂的通信网络进行仿真。 针对通信网，用并行分布式的仿真方法，步骤一般分为：问题的分析、通信 网络仿真模型的建立、并行的划分、通信的确定、粒度的确定、任务的分配、网 络实际仿真、结果_ 自勺统计分析。同时，由于问题本身的复杂性，有必要对整个过 程进行反复的回溯，以达到一个满意的结果。仿真基本流程如下： 问题分析描述 通信网络仿真模型建立 并行划分、粒度的确定 处理机分配、进程调度 瞬态模拟 稳态模拟 仿真结果的统计分析 图3 1 ：通信网并行分布式仿真的流程图 大规模通信网并行分布式仿真的研究 北京邮电太学硕士生论文 第1 0 r 共3 7 页 3 2 通信网共纾划分的研究 3 2 。1 弗霉划分 l 、并行划分方法 并行鬃分，就是将原慕仿真嗣麓分割戏一些小豹计算任务，叛充分搦示并行 执行的机会。划分的方法有两种：域分解( 集中数据的分解) 、功能分解( 计算功 能兹分鼹) 。越分的簧点是力匿逮免数据耜诗冀熬复铡，疲健数据集露诗舅集互不 相交。 1 ) 域分解( d o m a i nd e c o m p o s i t i o n ) 也叫数据划分。所要划分的对象怒数据， 数摇可以包括输入数据，傍囊过程中靛输蕊数据，算法掰产生的中闻结巢。域分 解的一般方法是，茵先分解与问题相关的数据，如果可能的话，_ 陂使这些小的数 据片尽霹戆大致楣等；其次薅将每个诗算关联到它麓产生豹数豢土。 2 ) 功能分解( f u n c t i o n a ld e c o m p o s i t i o n ) 分解也叫计算划分，它关注于并行执 行的计算上。 在域分解中通常难以确定通信黉求，鞠为将数据划分成不相交的子集并未充 分考虑在数据上执行操作时可能产生的数据交换。计算划分后再继续研究计算所 需懿数据，黧暴数撵鸯稳当兹重叠，裁会产生大鬣翁逶绩，魏露裁应重耨考虑数 据分解。尽翁域分解是绝大多数并行算法所使用的，但有时功能分解却能揭示问 题匏内在结构展示出侥化鲍机遇，褥对数据单独遴季亍研究却往往难以l 乍用到这一 点。所以两种划分方法要综合互补使用。 2 、并行划分的判据 对于同一个通信网仿真问题可有多种并行划分的方法，下面的判剧可所作的 划分有无明显缺陷的检验。 1 ) 舞麓分懿 壬务数一般离于弱标凝上楚理器数鼙豹令量缀，否黧在嚣继豹 设计步骤中将缺少爱活性。 2 划分应尽塞避免冗余靛计算秘存健餮求，褥则鼹产生鳃算法对大型滔题可 能魑不可扩散的。 3 ) 诸划分的任务粒度应大致棚当，否则分配处理器时很难做到工作凝均衡。 4 ) 确认是否氍考虑了城分解又考虑了功戆分解，采_ 薅l 了冗耱不同豹划分法w 以提高灵活性。 3 2 2 通信两的并行划分方法 1 、逶臻瓣囊孽势霞麓分阗惩 通信网的并行分布式仿真，一般分配每台节点机仿舆一个通信予网的网络行 为，多台繁点提与服务器协同工佟宠成整网的仿真。将邋信网划分为多个子露楚 一个图的搿划分问题。下面先给出图一定划分问题的定义。 图g = ( 动为一无向图。其中v - - n 如，以 为图的顶点集，或称为初始划分 元集，e 为透集，建义g ，严( 玩，表示戴分元珏麓琢之潮有边撩接，逡接强度为 大规模通信剩并行分布式仿真的研究 北京邮电大学硕士生论文笫l l 页共3 7 页 c , jo 若把无向图g = ( e ) 的顶点集y 划分成t 个满足条件的子集：) l 仁 慨，m 2 。， m k ) ，应满足下述( 1 ) ( 2 ) 两项条件： 1 ) 对任意子集有： k u m 。= 欧m ，n m ，= 中，( f ，j = 1 , 2 ，t i _ ，)( 3 2 1 ) i = l 2 ) 各划分子集尬间的通信量最小： m i nz c ，m ，一m ，s ，r l ，2 ，) ，且s f ( 3 2 2 ) l s j 如 根据上面的问题描述，我们可以看出对通信网络进行k 划分时，具有以下的 划分原则： 1 ) 予网间的通信流量应尽可能小。将彼此之间通信量较少的网络节点分配到 不同的子网中，以减少通过网络互连设备的开销； 2 ) 子网内的通信流量应尽可能大。将彼此之间通信量较大或通信频繁的网络 节点分配到同一个子网中，以提高子网的资源利用率、增强子网内聚力： 此外，为了便于后面的设计，提高并行计算的效率。进行划分时，应尽量使 各子网的流量趋于平衡，从而保证网络负载均衡。 2 、解释结构模型技术 1 ) 解释结构模型的思想方法 解释结构模型法( i n t e r p r e t a t i v es t r u c t u r a lm o d e l i n g ，i s m ) 处理大规模复杂系 统的思想方法为：尽可能地把对象作为小规模、简单的系统来认识，在认识系统 部分构造的基础上，认识系统的整体构造；把大规模复杂系统分解为能够处理的 小规模、简单的子系统，通过对子系统的处理和变换，以达到对整个系统的处理； 将子系统的特性集约化，以达到处理整个系统。根据结构图形与结构矩阵之间的 一一对应关系，通过对矩阵的演算和变换，把错综复杂的系统，变成简单、易理 解和直观的结构模型。 随着应用的发展，通信网日益成为一个规模庞大的复杂系统，而且规模和复 杂性均呈指数增长，并行仿真大规模通信网的需求应运而生。它的解决思想正是 基于：将大规模的通信网划分为相对简单、规模较小的几个联系极少的通信子网。 通过多节点机分别对子网的仿真，协同完成大规模复杂通信网的仿真问题。这和 解析结构模型技术处理大规模复杂系统的思想方法完全一致。 2 1 结构模型的建立 无论什么系统总是由若干的要素所组成，且这些要素之间存在一定的关系。 通信网系统中，网络节点集定义为系统的要素集，网络节点之间的通信集定义为 系统的关系集。因为通信网系统中元素间的联系可以用网络节点间的到达率矩阵 来表示，所以二元矩阵b 可以按如下方法建立。 假定通信网中有n 个通信节点，这h 个通信节点间的呼叫到达率可以形成一 个 月的呼叫到达率矩阵，用2 来表示。 大规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文 第1 2 页共3 7 页 a = 旯l l 旯1 2 兄1 2如2 。 旯2 h 其中： z 代表由点i 到点，的呼叫到达率； 如代表由点，到点f 的呼叫到达率。 应用解释结构模型法，首先须要把到达率矩阵转换成二元矩阵。设定系统的 限界值q d ，可得二元矩阵b 如下： b = 口1 月 b 2 。 ： ! 一b 。 舯铲帖2 ：妻 z 固 由于系统的限界值囟所取的值可以从最小“的到最大的a ，( 通信网中九j - o ) ， 一共可以取n ( n - 1 ) 个值，故可以形成一个二元限界矩阵族。 3 ) 结构模型的分解 将二元矩阵雪进行区域划分，把系统的元素分解成k 个分离的区域，使任何 区域的成员没有一个是与其它区域的成员有关系。 在矩阵曰中，将元素在系统中所处位置，划分为可达性集合( r e a c h a b l es e t ) r ( ) 和先行集合( a n t e c e d e n ts e t ) a ( ) ，它们的定义分别是： a 月( 以) 包括所有可以从巧元素到达的元素。用数学通式表示：曰( k ) = 巧 h v ，b u = 1 ) ，b ，表示矩阵b 中i 行，列元素 b 月( 蚱) 包括所有可达到 的元素。用数学通式表示：一( ”) = 巧j 巧v ， 6 ，= 1 ) ，6 “表示矩阵b 中，行i 列元素 当啤( 以) u 4 ( 以) 】n 【r ( 巧) u 一( 巧) 】- 驴时，巧与巧分属于不同的区域。经运算 后所得集合m 为区域的分解，即：m = m i ，m 2 ，慨 ，其中k 为所划分 区域的数目。 只要通信网络是可分离的系统，就可以将系统加以分解。当网络规模较小时， 根据观察也能找出计算方法。但对于大规模的通信网，就无法再使用观察的方法。 对于不容易划分的系统，如果是可分离系统，可按下列步骤进行分解： a 从矩阵中选出非零元素最多的一列一一第，列； b 构成新的二元矩阵丑( o ：保留原出现矩阵中的第f 列内每个为零的元素所 对应的行。而把各个为1 的元索所对应的行进行布尔代数相加，放在后面 几行： c 重复以上做法，又得到一个新的矩阵b ( n 。再从占( 1 得到b ( 2 ) ，直到最后 得到的b ”) 止。町中每一列只含一个非零元素，它的每一行对应原系统 中一个独立子系统。 注意，设定不同的限界值函，可以得到不同程度的可约二元矩阵。因此，在 丈规模通信网并行分布式仿真的研究 北京邮电大学硕士生论文 第1 3 页共3 7 页 划分后需检验限界值q 0 设定的合理性，必要时应重新设定限界值q d ，直至获得 较为合理的划分，以便于下一步的优化。 3 、划分方案的优化方法 解析结构模型，是定性模型，它只是表示对象的大致特点。根据结构图形与 结构矩阵之间的一一对应关系，通过对矩阵的演算和变换，把错综复杂的系统， 变成简单、直观的结构模型。它的优点在于集中表示系统相互间如何关联，而不 表示量的关系，具有很强的解释功能。然而划分中必然存在很多不精确的方面， 此外，解析结构模型子系统的划分也没有保证划分的均衡性，所以有必要对其划 分方案做进一步优化，以获得更满意的划分。 网络一划分问题是n p 完全问题，所以可以用启发式算法，以解析结构模型中 得到的方案为初始解，对划分方案进行优化。算法的目标就是：获得使总的子网 间流量最小化的满意解。模拟退火、神经网络以及遗传算法等多种启发式算法均 可以应用于这个优化问题。 口业务量较轻的点对囡业务量较重的点对 图3 2 网络卜划分示意图 3 3 通信的设计 l 、通信 通信就是为了进行并行计算，子任务之间进行的数据传输流。仿真问题经并 行划分后产生了多个并行执行的子任务，这些子任务一般都不能完全独立的执行， 一个子任务中的计算可能需要用到另一个子任务中的数据，从而就产生了通信要 求。 2 、通信模式的分析 通信可以分成以下四种模式： 1 ) 局部全局通信 局部通信时，每个任务只与较少的几个近邻通信，全局通信时。每个任务与 很多别的任务通信。全局通信的方式可能会导致过多的通信从而限制了并行执行 的机会。 2 ) 结构化，非结构化通信 结构化通信时，一个任务和其近邻形成规整结构( 如树、网络等) ；非结构化通 大规模通信同并行分布式仿真的研究 北京邮电大学硕士生论文 第1 4 页共3 7 页 信中，通信网则可能是任意图。非结构化的通信模式，对算法设计的前期不会产 生实质性的困难，但却复杂化了任务的组合与处理器的映射，特别是当要求组合 策略既能创建尺寸大致相当的任务，又能尽量减少任务间的通信要求时，会复杂 算法。 3 1 静态动态通信 静态通信，通信伙伴的身份不随时间改变，动态通信中，通信伙伴的身份则 可能由运行时所计算的数据来决定而且是可变的。 4 ) 同步，异步通信 同步通信时，接收方和发送方协同操作；异步通信中，接收方获取数据无需 与发送方协同。消息传递( m e s s a g e p a s s i n g ) 式通信方式就属于异步通信。 3 、通信的设计 通信网仿真问题初步进行并行划分后，在通信设计的阶段任务有： 1 ) 分析通信量，检验并行划分是否合理 通信网仿真问题中，在并行划分后，就需要仔细研究各子任务之间的通信要 求。子任务间的通信量在并行程序和算法中，通信的复杂性有时比计算的复杂性 还高。这是因