计算机组成原理与系统结构 马礼 第12章 互连网络与多

《计算机组成原理与系统结构 马礼 第12章 互连网络与多》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12章互连网络与多处理机本章主要内容本章介绍多个处理机与多个计算机系统的互连网络基本概念、特性、种类、基本互连网络和多处理机互连网络,对于计算技术和通信技术结合的远程网也作了简单的介绍。最后讲述多处理机的结构和特点、机群系统以及多处理机的性能分析等内容。学习时主要掌握互连网络的连接方式及其特点和结构，掌握典型的寻径算法，并对典型实例有一定的了解。12.1互连网络的基本概念12.2静态互连网络12.3动态互连网络12.4互连网络的消息传递机制12.5多处理机系统特点与分类12.6典型的多处理机系统12.7机群系统12.1互连网络的基本概念12.1.1互

2、连网络在计算机系统中的作用图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(xn−1xn−2xn−3……x1x0)=xn−1xn−2xn−3……x1x02．交换置换（Excha

3、ngePermutation）E(xn−1xn−2xn−3……x1x0)=xn−1xn−2xn−3……x13．方体置换（CubePermutation）Ck(xn−1xn−2…xk+1xkxk−1…x1x0)=xn−1xn−2…xk+1xk−1…x1x04．均匀洗牌置换（PerfectShufflePermutation）σ(xn−1xn−2……x1x0)=xn−2xn−3……x1x0xn−15．蝶式置换（ButterflyPermutation）β(xn−1xn−2……x1x0)=x0xn−1xn−2……x1xn−16．位序颠倒置换（BitRever

4、salPermutation）ρ(xn−1xn−2……x1x0)=x0x1x2……xn−2xn−17．移数置换（ShiftPermutation）αx=(X+k)modN，0≤x≤N8．加减2i置换PM2+i(X)=(X+2i)modNPM2−i(X)=(X−2i)modN12.1.4互连网络的种类1．共享介质的网络2．非阻塞网络3．直接网络4．间接网络5．混合网络图12-11互连网络的分类12.2静态互连网络12.2.1静态互连网络结构1．一维线性阵列2．环和带弦环3．循环移数网络4．树形和胖树形5．网格形与环形网格6．超立方体和带环立方体7．k元n

5、立方体12.2.2静态互连网络特性表12-1静态网络的性能一览表网络类型结点度d网络直径D链路数l等分带宽B对称性网络规格评注线性阵列2N−1N−11非N个结点环形2N/2N2是N个结点全连接N−11N(N−1)/2(N/2)2是N个结点二叉树32(h−1)N−11非树高h=log2N星形N−12N−1(N/2)非N个结点2D网络42(r−1)2N−2rr非r×r网络，N=r2Illiac网4r−12N2r非与N=r2的带弦环等效2D环网42(r/2)2N2r是r×r环网，N=r2超立方体nnnN/2N/2是N个结点，n=log2N(维数)带环立方体3

6、2k−1+k/23N/2N/(2k)是N=k×2k个结点，环长≥3k元n立方体2nn(k/2)nN2kn-1是N=kn个结点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

7、．寻径方式（1）线路交换（CircuitSwitch）（2）存储转发（StoreandForward）（3）虚拟直通（VirtualCutThrough）（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）结构灵活性和功能通用

8、性（2）主要开发高层次作业及任务级（粗粒度）并行性（3）并行任务的派生需要用显式的专用语句或指