第12章互连网络与多

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,12,章 互连网络与多处理机,本章主要内容,本章介绍多个处理机与多个计算机系统的互连网络基本概念、特性、种类、基本互连网络和多处理机互连网络,对于计算技术和通信技术结合的远程网也作了简单的介绍。最后讲述多处理机的结构和特点、机群系统以及多处理机的性能分析等内容。学习时主要掌握互连网络的连接方式及其特点和结构，掌握典型的寻径算法，并对典型实例有一定的了解。,12.1,互连网络的基本概念,12.2,静态互连网络,12.3,动态互连网络,12.4,互连网络的消息传递机制,12.5,多处理机系统特点与分类,12.6,典型的多处理机系统,12.7,机 群 系 统,12.1,互连网络的基本概念,12.1.1,互连网络在计算机系统中的作用,图,12-1,互连网络的连接结构,12.1.2,主要特性和性能参数,1,互连网络的特性,（,1,）网络规模,（,2,）结点度,（,3,）结点距离,（,4,）网络直径,（,5,）等分宽度,（,6,）结点间线长,（,7,）网络对称性,（,8,）可扩展性,2,传输性能参数,（,1,）频宽,（,2,）传输时间,（,3,）,“,飞行,”,时间,（,4,）发送方开销,（,5,）接收方开销,（,6,）总时延,图,12-3,互连网络的传输性能参数,12.1.3,互连函数,1,恒等置换,相同编号的输入端与输出端一一对应互连所实现,置换称为恒等置换。其表达式为：,I,(,x,n,1,x,n,2,x,n,3,x,1,x,0,)=,x,n,1,x,n,2,x,n,3,x,1,x,0,2,交换置换（,Exchange Permutation,）,E,(,x,n,1,x,n,2,x,n,3,x,1,x,0,)=,x,n,1,x,n,2,x,n,3,x,1,3,方体置换（,Cube Permutation,）,C,k,(,x,n,1,x,n,2,x,k,+1,x,k,x,k,1,x,1,x,0,)=,x,n,1,x,n,2,x,k,+1,x,k,1,x,1,x,0,4,均匀洗牌置换（,Perfect Shuffle Permutation,）,(,x,n,1,x,n,2,x,1,x,0,)=,x,n,2,x,n,3,x,1,x,0,x,n,1,5,蝶式置换（,Butterfly Permutation,）,(,x,n,1,x,n,2,x,1,x,0,)=,x,0,x,n,1,x,n,2,x,1,x,n,1,6,位序颠倒置换（,Bit Reversal Permutation,）,(,x,n,1,x,n,2,x,1,x,0,)=,x,0,x,1,x,2,x,n,2,x,n,1,7,移数置换（,Shift Permutation,）,x,=,(,X+k,),mod,N,，,0,x,N,8,加减,2,i,置换,PM2,+,i,(,X,)=(,X,+2,i,)mod,N,PM2,i,(,X,)=(,X,2,i,)mod,N,12.1.4,互连网络的种类,1,共享介质的网络,2,非阻塞网络,3,直接网络,4,间接网络,5,混合网络,图,12-11,互连网络的分类,12.2,静态互连网络,12.2.1,静态互连网络结构,1,一维线性阵列,2,环和带弦环,3,循环移数网络,4,树形和胖树形,5,网格形与环形网格,6,超立方体和带环立方体,7,k,元,n,立方体,12.2.2,静态互连网络特性,表,12-1,静态网络的性能一览表,网络类型,结点度,d,网络直径,D,链路数,l,等分带宽,B,对称性,网络规格评注,线性阵列,2,N,1,N,1,1,非,N,个结点,环形,2,N,/2,N,2,是,N,个结点,全连接,N,1,1,N,(,N,1)/2,(,N,/2),2,是,N,个结点,二叉树,3,2(,h,1),N,1,1,非,树高,h=,log,2,N,星形,N,1,2,N,1,(,N,/2),非,N,个结点,2D,网络,4,2(,r,1),2,N,2,r,r,非,r,r,网络，,N=r,2,Illiac,网,4,r,1,2,N,2,r,非,与,N=r,2,的带弦环等效,2D,环网,4,2(,r,/2),2,N,2,r,是,r,r,环网，,N=r,2,超立方体,n,n,nN,/2,N,/2,是,N,个结点，,n=,log,2,N,(,维数,),带环立方体,3,2,k,1+,k,/2,3,N,/2,N,/(2,k,),是,N=k,2,k,个结点，环长,3,k,元,n,立方体,2,n,n,(,k,/2),nN,2,k,n,-,1,是,N=,k,n,个结点,12.3,动态互连网络,12.3.1,动态互连网络的互连形式,1,基于公共介质的互连,2,交叉开关,3,多级互连,（,1,）开关模块,（,2,）级间连接模式,（,3,）控制方式,12.3.2,多级互连网络,1,网络（,Omega,网络）,2,STARAN,网络,3,基准网络,4,间接二进制,n,方体网络,5,Benes,二进制置换网络,6,多级,Close,网络,Benes,网络的置换函数表达式为：,12.4,互连网络的消息传递机制,12.4.1,消息寻径,1,消息的格式,图,12-34,消息的组织方式,2,寻径方式,（,1,）线路交换（,Circuit Switch,）,（,2,）存储转发（,Store and Forward,）,（,3,）虚拟直通（,Virtual Cut Through,）,（,4,）虫蚀寻径（,Wormhole,）,12.4.2,死锁和虚拟通道,1,虚拟通道,2,死锁的产生,3,死锁的避免,12.4.3,单播方式的寻径,1,包阻塞及其应对措施,2,固定寻径方式,3,自适应寻径,12.4.4,广播方式下的寻径,（,1,）单播模式,（,2,）选播模式,（,3,）广播模式,（,4,）会议模式,12.5,多处理机系统特点与分类,12.5.1,基本结构,图,12-43,多处理机系统的两种基本结构,12.5.2,多处理机系统特点,（,1,）结构灵活性和功能通用性,（,2,）主要开发高层次作业及任务级（粗粒度）并 行性,（,3,）并行任务的派生需要用显式的专用语句或指令加以表示,（,4,）并发执行的进程间的同步需要采取特殊的措 施,（,5,）对资源和任务分配如果要进行良好的调度,（,6,）,MIMD,计算机系统在执行条件语句时,（,7,）,MIMD,系统的异步特性使得它在执行完成 时间可变的指令时，比,SIMD,具有更高的效率。,12.5.3,多处理机系统的,Cache,一致性问题,1,产生,Cache,一致性问题的原因,（,1,）共享可写数据引起的不一致性,（,2,）进程迁移引起的不一致性,2,解决,Cache,一致性问题的方法,（,1,）以硬件为基础的方法,（,2,）以软件为基础的方法,12.6,典型的多处理机系统,12.6.1 MPP,大规模并行多处理机系统,12.6.2 CM-5,系统,1,CM-5,的系统结构,2,CM-5,的网络结构,（,1,）数据网络,（,2,）控制网络,（,3,）诊断网络,3,控制处理机和处理结点,12.6.3 SGI Origin 2000,系列服务器,图,12-53,S2MP,系统的体系结构,1,SGI Origin 2000,系列服务器性能,2,SGI Origin 2000,服务器结构,3,存储组织,12.7,机 群 系 统,12.7.1,机群系统的结构特点,（,1,）系统开发周期短,（,2,）系统价格低,（,3,）用户投资风险小,（,4,）节约系统资源,（,5,）系统的可扩展性好,（,6,）用户编程方便,12.7.2,机群系统的关键技术,1,高效的通信系统,2,并行程序开发环境,3,多种语言支持,4,全局资源的管理与应用,5,机群负载平衡技术,12.7.3,几种典型的机群系统,目前国内外许多科研机构都在对机群系统下的通信技术进行深入的研究，如,UCB,（,University of California,，,Berkeley,）提出的,NOW,计划，,Cornell,大学研制的,U-Net,系统，清华大学提出的精简通信协议,RCP,和快速消息传递机制,EMP,等。这些系统从实现技术上来看，可以分为两类，一类是采用精简通信协议的方法，另一类是使用,Active Message,通信机制。,