计算机仿真论文计算机仿真 论文高效能计算机互连网络拓扑结构的建模与仿真.docx

1、计算机仿真论文计算机仿真 论文高效能计算机互连网络拓扑结构的建模与仿真计算机仿真论文（计算机仿真 论文）：高效能计算机互连网络拓扑结构的建模与仿真摘要:该论文主要论述了高效能已成为超级计算机的追求目标,影响计算机效能的因素很多,其中一项重要因素就是互连网络拓扑结构,其直接决定着互连网络中数据传输的效率.论文基于此,首先对结点内部的处理器、适配器、链路和交换机进行抽象、提取主要特性、设置参数并建立模型;在此基础上,针对高效能计算机互连网络拓扑结构的选择问题,以Opnet网络仿真软件为平台,建立了Mesh结构、Torus结构以及Fat-tree结构3种网络拓扑结构的模型,从网络延时、接收有效包的比

2、例以及静态结构等方面,对网络性能进行分析,通过仿真结果的对比与总结,确定Torus结构网络性能最优.关键词:计算机互连网络; Opnet仿真;高效能计算机;拓扑结构;建模与仿真Modeling and simulation on high productivity computersinterconnecting network topologyAbstract:Presently, high-productivity has become one of the goals that supercomputers pursue.Among the many factors, topology

3、of the interconnection network is an important one which directlydetermines the efficiency of the data transportation in the interconnection network. This article, first-ly, abstracts the processors, adapters, links and switches, extract the major characters, set argu-ments, and then create models;

4、on this basis, taking the Opnet network simulation software as theplatform and the selection of the most suitable interconnection network for the high-productivity com-puters as the main goal, we build three network topology models-Mesh, Torus and Fat-tree to analyzethe performance of the networks f

5、rom the perception of network latency, packet reception ratio andstatic structure. The conclusion out of the comparison and summarization of the simulation result isthat Torus is the best solution.Keywords:interconnection network; Opnet simulation; high-productivity computer; topology; mod-eling and

6、 simulation11、问题的讨论当前,随着内存墙、I/O墙、功耗墙、编程墙、扩展性墙等诸多问题的日益突出,高效能计算机成为重点发展的技术方向1,2.影响高效能计算机性能的因素很多,包括结点机的硬件体系结构、互连网络的拓扑结构以及结点数量等诸多因素.其中,由于高效能计算机所执行的任务往往是大规模并行计算,需要多个节点机协同工作,因此互连网络就成为了这种体系结构中一个重要的性能瓶颈,其对整机性能的影响不容忽视.本文将从互连网络的拓扑结构对网络性能的影响方面进行分析.高效能计算机互连网络的拓扑结构建模和仿真是高效能计算机结构设计必不可少的前提.高效能计算机内部由成百上千个结点构成,由于其结构复

7、杂,内部结点个数庞大,单纯的理论分析很难得到期望的解析解,并且,通过物理实验进行验证的方法对于硬件需求强大,容易造成资源浪费,不具有可行性.因此,目前主要通过仿真手段对高效能计算机进行建模与仿真,通过构建反映真实网络情况的拓扑模型,在仿真软件上实现,对不同网络结构的性能进行合理评价,为网络设计提供客观可靠的定量依据.因而构建网络拓扑结构对于系统建模具有重要意义.文献3对各种互连网络的性能进行了对比.其中,InfiniBand是一种新型I/O体系结构,也是一种新的互连技术,不仅可用于服务器内部的互连,而且可以用于服务器间、集群系统间以及存储系统间的互连.在其之上实现了MPI和SDP4,5等协议,

8、具有高带宽、低时延的特性.在本研究的物理实现中,采用了这种新的高速互连网络,从而提高了整个集群的性能.本文的仿真模型中,采用实际的物理参数建立模型,对InfiniBand互连网络进行简化模拟.当前,高性能计算机中常用的互连网络模型主要有Mesh, Torus, Fat-tree这3种.其中Mesh和Torus都属于k-ary n-cube互连网络.文献610做了大量的相关研究,得到了一些研究成果.本文主要对比了结点间Mesh结构、Torus结构以及Fat-tree结构下的网络性能,从传输延时、接收有效包的比例以及静态网络结构3方面对仿真结果进行分析,从而对不同结构的网络性能进行对比与总结.实验

9、中采取了基于面向对象的建模机制11,使系统与模型具有直接的对应关系,符合正常思维习惯,易于理解,并且其封装性和继承性使模型具有可重用性,减少了代码量和模型数量.首先针对项目中高效能计算节点体系结构提出在Infiniband框架中分别实现Mesh,Torus和Fat-tree模型的方法,然后在此基础上,通过Opnet仿真,对这3种互连网络模型的性能进行对比分析.对于网络仿真过程中负载模型的选择目前主要有3种方法:人工合成消息,全系统模拟和应用轨迹.全系统模拟即模拟整个系统包括网络中的计算机及运行于其上的应用程序,这种仿真方法较为复杂,不便应用.因此,本文采用人工合成消息的方法.2高效能计算机结构

10、分析2007年我国就启动了“十一五”863计划“高效能计算机系统研制及关键技术研究”重大项目课题.在该项目中,高效能计算机的设计是由上百个结点构成的,每个结点内部包含16个Loongson3A处理器,处理器之间采用Hypertransport12总线互连,构成Mesh结构.由于每4片处理器能够实现缓存一致性,因此16个处理器划分为4组SMP,每组SMP通过一片MCP68南桥芯片与InfiniBand适配器互连,如图1所示.点之间通过InfiniBand总线互连,物理结构上,Infiniband适配器发送的数据通过QDR Switch进行转发,属于星型拓扑结构,由于一种物理拓扑结构可以对应多种逻

11、辑拓扑结构,逻辑结构上,结点之间的互连有Mesh,Torus以及Fat-tree133种拓扑结构可供选择.为了分析与物理拓扑对应的3种逻辑拓扑对于高效能计算机通信性能的影响,本文以该项目为背景,运用网络仿真软件对高效能计算机进行建模与仿真.3系统分析与实现3.1系统分析在本系统中,虽然结点间的拓扑结构有多种选择,从数据流的传输角度考虑,仍然存在一些共性.结点内部的16个loongson3A CPU既为发送节点又是接收节点,CPU创建数据包,按X-Y路由协议将数据包传送给结点内部的目的CPU,或者通过Infiniband适配器转发到网络上,之后通过Switch转发给其他的Infiniband适配

12、器,进而传送给相应的目的结点,最后通过X-Y路由协议到达正确的目的CPU.目的CPU接收数据包,记录需要的统计信息量后销毁该包,完成一次传输.包的传输流程包传输流程图由于同种类型的节点功能相同,抽象到模型的层面上存在很多的共性,因此采用面向对象的机制进行建模,同种类型的节点建立一种模型,如所有的loongson3A CPU建立一种模型,每个节点都是一种模型的实例化,每个节点都可以拥有自己特有的属性,从而使节点之间保持了各自的不同性.使用loongson3A CPU的新型节点机最大的特点在于将过去用于CPU间通信的HT总线用于系统间的互连,从而使得CPU间通信也成为互连网络中系统间通信的一部分.

13、因此,在设计高效能计算机互连网络仿真模型时,必须将处理器的通信模型作为一项重点.本文用IP/端口地址对标示一个CPU,IP地址标示该CPU所在的节点机,端口地址标示该CPU.另外,由于要对整个互连网络进行仿真,因此,需要对网络交换机进行建模,以精确模拟网络中数据包的转发过程.特别地,对于Fat-tree拓扑结构的互连网络,交换机分为叶交换机和主干交换机2种,其转发策略有所不同:叶交换机的主要工作是接受主干交换机发来的数据包并转发给目的主机和查看各主干交换机的工作状态,并将数据包发送给空闲的主干交换机;而主干交换机的主要工作是根据数据包的目的地址将其转发给相应的叶交换机.因此,对这2种交换机需要

14、分别建模和仿真.综上所述,从数据包的传输流程分析,总共需要建立4种模型:处理器模型、Infiniband适配器模型、叶交换机模型和主干交换机模型,模型与网络实际对象的对应模型与网络的对应关系网络对象对应模型Loongson3A CPU处理器模型Infiniband互连网络Infiniband适配器节点模型Fat-tree结构中第一层交换机主干交换机模型Fat-tree结构中第二层交换机叶交换机模型3.2系统实现3.2.1处理器模型处理器模型是对loongson3A CPU的一种抽象和实现,分为10个模块,主要实现了3种功能:产生数据包、加工数据包以及转发数据包,其中包括1个数据包产生模块、1个

15、包处理模块、1个队列模块、1个转发模块、3个收信机以及3个包发送模块.数据包产生模块按照设置的时间间隔创建指定分布大小的数据包(包A),并发送出去;包处理模块接收包A,并为其添加目的IP地址、目的端口地址、包序列号等相关信息,在该模块中维护有一个大小为50的滑动窗口,用以记录已发送的数据包的信息,当计时器计时到达时,检查滑动窗口内的信息,重传仍未收到反馈信息的数据包;收信机用于接收外部数据流中到达的数据包,它会丢弃出错的包,将正确的包发送到队列模块中;队列模块中设置4个工作单元,任何空闲的工作单元都会从队列头部取出数据进行处理;转发模块取出队列模块中的数据包进行处理,若本节点为包的目的节点,则

16、记录相关的信息后销毁包;若本节点不是包的目的节点,则按照X-Y路由协议的方式,查找节点内的路由表,将包发按正确的方向送出去;包发送模块一方面承担数据包的发送功能,另一方面监视当前链路状态,并将这些链路状态信息返回给转发模块,用于数据包转发决策.转发模块的具体实现转发进程模型块初始化,首先创建自己的路由表.每个转发模块的路由表中保存着与其相连的邻节点地址.B.初始化完毕后无条件转移到st-1状态.当有包到达时,满足PK-ARRVL转移条件,转发模块首先判断包的时效性.若包的创建时间距离当前仿真时间超过限制,则丢弃该包,否则检查包所携带的信息.检验时将分3种情况进行处理:a.若本节点为包的目的节点

17、,则记录包的源IP地址,源端口地址,包的标识号,重传标志以及创建时间等信息,收集包的端对端时延后,触发反馈自中断;b.若本节点为包的目的节点,且该包是ACK反馈包,则销毁该包,将滑动窗口对应该ACK包的标号的窗口占用状态置为无效,说明该包已经被成功接受;c.本节点只是该包的中转节点,包的转发采用X-Y路由协议.C. st-1状态满足情况a,即满足Self-Intrpt条件时,从st-1跳转到ACK强制状态:创建ACK反馈包,将原包的IP地址,端口号,重传标志及创建时间等信息复制到本包中,并发送该包.D. st-1状态满足情况c,即满足FREE条件时,进入send状态:将等待队列中的所有数据包一

18、一发送出去,发送完毕后返回st-1状态.E.转发前,通过发信机到转发模块的状态线检查要转发的链路的状态,若链路上已有数据传输,则实现BUSY转移条件,进入wait等待状态;直到链路空闲,状态线上产生下降沿出发的状态中断,满足GOES FREE条件,转移到send状态,将本节点积累的数据包传输出去,返回st-1状态.3.2.2InfiniBand适配器模型Infiniband适配器节点模型是对Infiniband芯片的抽象,其主要完成了数据包的转发功能,其由16个模块组成:5个收信机模块;5个发信机模块;5个先进先出的队列,每个队列对应一个收信机,收信机将到达的包被放到队列中,队列满时包被丢弃;

19、一个转发模块,转发模块中维护一张转发表,记录了与本节点模型相连的其他节点的IP地址以及对应的转发端口号.转发模块将信用度数值的变化通知给各队列模块.当信用值低于原值的一半时,转发模块通过状态线产生下降沿中断,队列接收到中断后将处理速度降低为原来的1/2,从而减少需要转发的数据包.直到信用值恢复,再次产生上升沿中断,队列将恢复原来的处理速度,从而恢复原来的处理状态.3.2.3叶交换机模型在Fat-tree拓扑结构中,Infiniband适配器通过两层交换机互连实现,分别为叶交换机和主干交换机.叶交换机节点模型主要由收信机、发信机及转发模块构成.收信机模块用于接收Infini-band适配器节点模

20、型或主干交换机模型发送的数据包;发信机模块用于将数据包发送给Infini-band适配器节点模型或主干交换机模型;转发模块用于判断数据包需发送的模型类别和端口号.转发模块内部进程设计转发进程a.进程模型入口为init状态入口程序.在进程中定义了转发路由表和包等待队列.路由表用数据结构链表实现,每条数据项保存与本节点特定发送机相连的节点的IP地址和与该发送机对应的转发端口号.b.初始化完毕,从init状态转移到idle状态.在idle状态时,转发模块等待包的到达,当产生流中断,即满足PK-ARRVL条件时,若包是从主干交换机发往本节点,将该数据包发送至下一层;若包是从叶节点发送到本节点,则查询主

21、干交换机的工作状态:若得知目前某个主干交换机处于空闲状态,则将数据包发送到该交换机对应的端口,并将该交换机的工作状态设置为忙状态;若所有的交换机都处于忙状态,并且包等待队列已满,则丢弃该包;若包等待队列不满,则将包储存到等待队列中,然后触发自中断.c.产生自中断,即满足Self-intrpt条件,从而沿路径转移到st-2状态.在该状态,若有包到达,等待队列满则丢弃包,不满则将包插入队列中;若包等待队列中还有未发送的包,则检测主干交换机的工作状态,一旦交换机空闲就将包发送出去.之后产生预定义自中断,相当于计时器.当包等待队列空闲时,满足Unfull条件,返回idle状态.3.2.4主干交换机模型

22、主干交换机的节点模型也是由收信机、发信机和转发模块组成的.主干交换机模型的功能是接收叶交换机模型传送的数据包,并将该包转发给与目的结点联通的叶交换机模型.该功能主要由转发模块实现.转发模块内维护一张转发表,的每条信息记录了与该主干交换机相连的叶交换机的IP地址和对应的端口号.转发模块接收到数据包后,根据数据包的目的IP地址查询转发表,获得正确的转发端口,将数据包转发给与其目的地址相连接的叶交换机.收信机丢弃出错的数据包时会通知转发模块,使其恢复到空闲状态.3.2.5网络模型为了对比不同网络拓扑结构下的通信性能,创建了3个场景 ,结点间互连结构依次为Mesh结构、Torus结构和Fat-tree

23、结构.圆形节点代表了一个结点,结点是一个子网,内部放置了16个处理器节点模型,通过HT总线相连成Mesh结构,方形节点为InfiniBand适配器节点模型.这里所指的Mesh,Torus以及Fat-tree结构是指InfiniBand适配器模型之间的互连结构.结果分析对网络性能进行定量研究,需要选择合适的网络性能指标.评价信息网络性能好坏的主要技术指标包括网络吞吐量、链路利用率、响应时间、包延迟时间、延迟抖动、丢包率等.针对本实验中以包传输为基础的计算机通信网络的特征,通过静态结构分析网络的传输效率,以收包率和链路吞吐率评价数据包的传输特性,以各种延时评价交互式通信网络对时间的要求.从结构上进

24、行分析,静态的对比3种拓扑结构的特征,.网络直径是评价网络通信性能的一种重要指标,2个节点之间的距离越短,其传输延时就越低.因此,从网络直径分析,Torus结构最具优势.静态结构对比分析表结构节点度网络直径网络总连接数对剖宽度二维Mesh结构1616 5 2( 16-1) 24 16二维Torus结构1616 5 2 16/2 32 2 16胖树结构4元2树InfiniBand芯片的节点度恒为2,叶交换机的节点度为8,主干交换机的节点度为44 32 8目前结点内部16个CPU将设置在2块相同的PCB板子上,2块PCB板间采用高速连接器对插方式实现互连,对剖宽度反映了流经上下板接插件的信号数量,

25、Torus结构和胖树结构相对于Mesh结构有较大的优势.网络总连接数,反映了网络成本的高低,连接数越多,网络越复杂,网络的成本越高.Mesh结构的总连接数最低,Torus结构和Fat-tree结构次之.不同的拓扑结构对于包的延时有很大影响,延时越大网络响应速度越慢,用户等待时间越长,性能和应用性越差.实验结果表明:Mesh结构中包的端对端平均延时为0.004 331 s;Torus结构包的端对端平均延时为0.003 675 s;的端对端平均延时为0.005 682 s.在Infiniband适配器中设置有接收队列和发送队列,数据包从到达队列,等待队列中优先于该数据包到达队列的数据被处理完发送出

26、去,到处理该数据包,数据包等待了队列的排队延时的时间,队列延时体现了网络数据传输的通畅性,在3种拓扑结构中,实验研究结果表明:Mesh结构队列延时为0.000 104 s;Torus结构的队列延时与Mesh结构几近重合为0.000 104 s;Fat-tree结构的队列延时相对比较高为0.000 105 s.收包率一方面反映了网络传输的通畅性,另一方面反映了网络的利用率.随着网络拓扑的改变,网络的性能也会不同程度改变.分别显示了3种拓扑结构下的收包率,横轴为单位时间发送的包的个数,纵轴为单位时间接收到的有效包的个数.单位时间接收到的有效包的比例可以通过曲线上任意点的纵坐标与横坐标之比获得,曲线

27、的斜率反映了随着发包总数的增多接收到的有效包的比例的变化趋势.,Mesh结构中曲线斜率为0.611 960,起点收包率为0.654 989,终点收包率为0.616 460.Torus结构中曲线斜率为0.617 213,起点收包率为0.633 860,终点收包率为0.619 013.随着发包个数的增多,2种结构的收包率均有所下降,但Torus结构比Mesh结构收包率下降趋势略微平缓.在Fat-tree结构中,如图9所示,起初曲线斜率为0.108 673,该段收包率迅速下降,起点收包率为0.617 688,第一个转折点收包率为0.412394,之后曲线斜率迅速提高,达到1.622 682,收包率逐

28、渐增高,在第二个转折点回升至0.613179,最后曲线斜率下降至0.184 250,终点收包率下降至0.447 180,虽然中间有段时间收包率增加,但很快恢复,各点的收包率都不高于Torus结构中的收包率,因而没有起到改善作用.整体比较如表3所示,Torus结构下的收包率优于Fat-tree结构和Mesh结构.3种拓扑性能对比Mesh结构Torus结构Fat-tree结构网络延时中低高队列延时中中高收包率中中低网络直径高低中对剖宽度低高高总连接数低高高综合分析,在互连网络中高负载高数据传输率的情况下,Torus互连网络结构可以更好地分配带宽,降低网络拥塞程度,更充分地体现高效能计算机的计算性能

29、.因此根据本文仿真的结果,Torus拓扑结构更适用于高效能计算机互连网络.本文使用Opnet网络仿真软件对高效能计算机进行建模,针对高效能计算机内部结点间物理拓扑可以对应多种逻辑拓扑的问题,主要建立了结点间Mesh、Torus以及Fat-tree这3种逻辑拓扑结构的网络模型,3种结构下仿真结果的对比与分析显示Torus结构的网络性能最优,从而为结点间拓扑结构的选择提供了依据.致谢在此,向对本文的工作给予支持和建议的同行,尤其是北京航空航天大学计算机学院肖利民教授领导的小组的老师和同学表示感谢.参考文献1曾宇.高效能计算机技术及标准现状J.信息技术与标准化, 2008(7): 17-20.2陈左

30、宁.从高性能计算走向高效能计算J.计算机教育, 2004, 6: 26-28.3李涛,陈字明,赵精龙,等.集群高速互连网络分析J.计算机科学, 2005, 32(10): 20-22.4 Balaji P, Bhagvat S, Panda D K, et al. Advancedflow-control mechanisms for the sockets direct proto-col over infiniBandCThe International Conferenceon Parallel Processing (ICPP 2007). Xian: s.n.2007: 501-506.