第12单元 互连网络与多.pptVIP

第12章 互连网络与多处理机 本章主要内容： 本章介绍多个处理机与多个计算机系统的互连网络基本概念、特性、种类、基本互连网络和多处理机互连网络,对于计算技术和通信技术结合的远程网也作了简单的介绍。最后讲述多处理机的结构和特点、机群系统以及多处理机的性能分析等内容。学习时主要掌握互连网络的连接方式及其特点和结构，掌握典型的寻径算法，并对典型实例有一定的了解。 12.1 互连网络的基本概念 12.2 静态互连网络 12.3 动态互连网络 12.4 互连网络的消息传递机制 12.5 多处理机系统特点与分类 12.6 典型的多处理机系统 12.7 机 群 系 统 12.1 互连网络的基本概念 12.1.1　互连网络在计算机系统中的作用 12.1.2　主要特性和性能参数 1．互连网络的特性 （1）网络规模 （2）结点度 （3）结点距离 （4）网络直径 （5）等分宽度 （6）结点间线长 （7）网络对称性 （8）可扩展性 2．传输性能参数 （1）频宽 （2）传输时间 （3）“飞行”时间 （4）发送方开销 （5）接收方开销 （6）总时延 12.1.3　互连函数 1．恒等置换 I(xn?1 xn?2 xn?3…… x1 x0)= xn?1 xn?2 xn?3…… x1 x0 2．交换置换（Exchange Permutation） E(xn?1 xn?2 xn?3……x1 x0)= xn?1 xn?2 xn?3……x1 3．方体置换（Cube Permutation） Ck(xn?1 xn?2…xk+1 xk xk?1…x1 x0)= xn?1 xn?2 …xk+1xk?1…x1 x0 4．均匀洗牌置换（Perfect Shuffle Permutation） σ(xn?1 xn?2……x1 x0)= xn?2 xn?3……x1 x0 xn?1 5．蝶式置换（Butterfly Permutation） β(xn?1 xn?2…… x1 x0)= x0xn?1 xn?2 ……x1 xn?1 6．位序颠倒置换（Bit Reversal Permutation） ρ(xn?1 xn?2……x1 x0)= x0x1 x2……xn?2 xn?1 7．移数置换（Shift Permutation） αx= (X+k) modN ， 0≤x≤N 8．加减2i置换 PM2+i(X)=(X+2i)modN PM2?i(X)=(X?2i)mod N 12.1.4　互连网络的种类 1．共享介质的网络 2．非阻塞网络 3．直接网络 4．间接网络 5．混合网络 12.2 静态互连网络 12.2.1　静态互连网络结构 1．一维线性阵列 2．环和带弦环 3．循环移数网络 4．树形和胖树形 5．网格形与环形网格 6．超立方体和带环立方体 7．k元n立方体 12.2.2　静态互连网络特性 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．消息的格式 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.5.2　多处理机系统特点 （1）结构灵活性和功能通用性 （2）主要开发高层次作业及任务级（粗粒度）并行性 （3）并行任务的派生需要用显式的专用语句或指令加以表示 （4）并发执行的进程间的同步需要采取特殊的措施 （5）对资源和任务分配如果要进行良好的调度 （6）MIMD计算机系统在执行条件语句时 （7）MIMD