计算机系统结构_26482.pptVIP

计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机 第七章 互连网络 7.1 互连网络的基本概念 7.2 消息传递机制 7.3 互连网络实例 第七章 互连网络 定义: 一种由开关元件按照一定的拓扑结构和控制方式构成的网络 作用:实现计算机系统内部多个处理机或多个功能部件之间的相互连接 7.1 互连网络的基本概念 7.1.1互连网络的作用 7.1.2互连函数 7.1.3互连网络的特性和传输的性能参数 7.1.4互连网络的种类 7.1.1互连网络的作用 计算机系统内部多个处理机或多个功能部件间的相互连接 并行处理系统的核心组成部分 对整个计算机系统的性能价格比有决定性的影响 处理机系统的互连结构 具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构 1 IPMN(处理机-存储器网络) 2 PION(处理机-I/O网络) 3 IPCN(处理机之间通信网络) P(处理机)C(高速缓冲存储器)SM(共享存储器)LM(本地存储器) 7.1.2互连函数 常用的互连函数 2 交换置换Exchange 3 方体置换Cube 3 方体置换Cube C0, C1, C2 变化发生在0, 1, 2位 分别是高 2, 1, 0位相同的为一个组 组数 4, 2, 1 组内加/减 1, 2, 4 C0循环表示(0,1), (2,3), (4,5), (6,7) 4 均匀洗牌置换Perfect shuffle 把二进制位循环左移一位 子混洗(subshuffle)S(k) 最低k位循环左移一位 超混洗牌(supershuffle) S(k) 最高k位循环左移一位 显然成立 逆混洗函数 教材P397L2,3,5,6错 4 均匀洗牌置换Perfect shuffle 4 均匀洗牌置换Perfect shuffle 5 蝶式置换Butterfly 5 蝶式置换Butterfly 与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连 蝶式函数循环表示(0), (2), (5), (7), (1,4), (3,6) 6 位序颠倒置换Bit Reversal 将输入端二进制地址的位序反过来就得相应输出的地址 子反位序函数：最低k位的位序反过来 超反位序函数：最高k位的位序反过来 对于n=3的情况，正好有 R=B，R(2)=B(2)，R(2)=B(2) 教材P398 6. L5,6错 7 移数置换 8 加减2i置换 其中：0 ? x ? N-1，0 ? i ? n-1，n = log2 N i=+0 循环表示(0,1,2,3,4,5,6,7) i=+1 循环表示(0,2,4,6), (1,3,5,7) 8 加减2i置换 采用移数函数可构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网 如Illiac函数是构成Illiac IV阵列的基础，包含PM2?0和PM2?n/2四个互连函数 采用全部移数函数构成网络称为移数网 7.1.3互连网络的特性和传输的性能参数 1 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成 互连网络的主要特性 (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数。包括入度和出度 入度： 进入结点的边数 出度：从结点出来的边数 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值 用结点间的连接边数表示 7.1.3互连网络的特性和传输的性能参数 (5) 等分宽度 当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示 线等分宽度B=b×w，w为通道宽度(用位表示) 等分宽度是说明沿等分网络最大通信带宽的一个参数 网络的所有其它横截面都应限在等分宽度之内 (6) 结点间的线长 两个结点间连线的长度。用米、公里等表示 (7) 对称性 从任何结点看到拓扑结构都是一样的网络称为对称网络。 对称网络比较易实现，编程也较容易 2 互连网络传输的性能参数 一台机器发送消息给另一台机器时，发送方的步骤 (1) 用户程序把要发送的数据拷贝到操作系统的缓冲区 (2) 操作系统把缓冲区中的数据打包，发送到网络接口部件 (3) 网络接口硬件开始发送消息 数据包的接收步骤 (1) 把数据包从网络接口部件拷贝到操作系统缓冲区 (2) 检查收到的数据包，如果正确，给接收方发回答信号 (3) 把接