计算机系统结构 (第24讲) 主讲人： 郑纬民教授 清华大学计算机系
计算机系统结构 （第24讲） 主讲人： 郑纬民 教授 清华大学计算机系
7.1.2互连网络的特性 互连网络通常是用有向边或无向边连接有 限个结点的组成。 互连网络的主要特性有： (1)网络规模：网络中结点的个数 (2)结点度：与结点相连接的边数称为结 点度。包括入度和出度。进入结点的边 数叫入度，从结点出来的边数则叫出度 (3)距离：两个结点之间相连的最少边数 (4)网络直径：网络中任意两个结点间距 离的最大值。用结点间的连接边数表示
7.1.2 互连网络的特性 互连网络通常是用有向边或无向边连接有 限个结点的组成。 互连网络的主要特性有： (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数称为结 点度。包括入度和出度。进入结点的边 数叫入度，从结点出来的边数则叫出度 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距 离的最大值。用结点间的连接边数表示
(⑤)结点间的线长：两个结点间连线的长 度。用米、公里等表示 (6)对称性：从任何结点看到拓扑结构都 是一样的网络称为对称网络。对称网络 比较易实现，编程也较容易
(5) 结点间的线长：两个结点间连线的长 度。用米、公里等表示 (6) 对称性：从任何结点看到拓扑结构都 是一样的网络称为对称网络。对称网络 比较易实现，编程也较容易
71.3互连网络的性能参数 台机器发送消息给另一台机器时，发送 方的步骤如下： (1)用户程序把要发送的数据拷贝到操作 系统的缓冲区。 (2)操作系统把缓冲区中的数据打包，并 发送的网络接口部件。 (3)网络接口硬件开始发送消息。 数据包的接收步骤如下： (1)把数据包从网络接口部件拷贝到操作 系统缓冲区
7.1.3 互连网络的性能参数 一台机器发送消息给另一台机器时，发送 方的步骤如下： (1) 用户程序把要发送的数据拷贝到操作 系统的缓冲区。 (2) 操作系统把缓冲区中的数据打包，并 发送的网络接口部件。 (3) 网络接口硬件开始发送消息。 数据包的接收步骤如下： (1) 把数据包从网络接口部件拷贝到操作 系统缓冲区
(2)检查收到的数据包，如果正确，给接 收方发回答信号。 (3)把接收到的数据拷贝到用户地址空间。 发送方接收到回答信号后，释放系统缓 冲区 互连网络在传输方面的主要性能参数： (1)频带宽度(Bandwidth):互连网络传输 信息的最大速率。 (2)传输时间(Transmission time):等于消 息长度除以频宽。 (3)飞行时间(Time of flight):第一位信 息到达接收方所花费的时间
(2) 检查收到的数据包，如果正确，给接 收方发回答信号。 (3) 把接收到的数据拷贝到用户地址空间。 发送方接收到回答信号后，释放系统缓 冲区 互连网络在传输方面的主要性能参数： (1) 频带宽度(Bandwidth)：互连网络传输 信息的最大速率。 (2) 传输时间(Transmission time)：等于消 息长度除以频宽。 (3) 飞行时间(Time of flight)：第一位信 息到达接收方所花费的时间
(4)传输时延(Transport latency): 等于 飞行时间与传输时间之和。 (⑤)发送方开销(Sender overhead: 处理 器把消息放到互连网络的时间。 (6)接收方开销Receiver overhead):处 理器把消息从网络取出来的时间。 个消息的总时延可以用下面公式表示： 总时延=发送方开销十飞行时间十 消息长度/频宽十接收方开销
(4) 传输时延(Transport latency)：等于 飞行时间与传输时间之和。 (5) 发送方开销(Sender overhead)：处理 器把消息放到互连网络的时间。 (6) 接收方开销(Receiver overhead)：处 理器把消息从网络取出来的时间。 一个消息的总时延可以用下面公式表示： 总时延＝发送方开销＋飞行时间＋ 消息长度/频宽＋接收方开销
例71： 假设一个网络的频宽为10Mb/S,发送 方开销为230us,接收方开销为270us。 如果两台机器相距100米，现在要发送 一个1000字节的消息给另一台机器，试 计算总时延。如果两台机器相距1000公 里，那么总时延为多大？ 解： 光的速度为299792.5KM/S,信号在导 体中传递速度大约是光速的50%，相距 100米时总时延为：
例7.1： 假设一个网络的频宽为10Mb/S，发送 方开销为230us，接收方开销为270us。 如果两台机器相距100米，现在要发送 一个1000字节的消息给另一台机器，试 计算总时延。如果两台机器相距1000公 里，那么总时延为多大？ 解： 光的速度为299792.5KM/S，信号在导 体中传递速度大约是光速的50％，相距 100米时总时延为：
7=发送方开销+飞行时间+消息长度 +接收方开销 频宽 0.1Km 1000×8位 =230S+ +270s 0.5×299792.5Km/s 10兆位/秒 =230s+0.67S+800S+270S=1301s 相距1000公里时的总时延为： 1000×109 000×8 T=23045+ 0.5×299792.5+ S+270s 10 =230s+6671s+800s+270s=7971s
相距1000公里时的总时延为： s s s s s s Km s Km s T 230 0.67 800 270 1301 270 10 / 1000 8 0.5 299792.5 / 0.1 230 = + + + = + + = + = + + + 兆位 秒 位 接收方开销 频宽 消息长度 发送方开销 飞行时间 s s s s s T s s s s = 230 6671 800 270 = 7971 270 10 1000 8 0.5 299792.5 1000 10 230 6 + + + + + = +
7.1.4互连网络的表示方法 为了在输入结点与输出结点之间建立对应关 系，互连网络有三种表示方法： (1)互连函数表示法： 如：fxn-1..x1x0)=x0xn-2..xlxn-1 自变量和函数可以用二进制表示， 也可以用十进制等表示 (2)图形表示法 3)输入输出对应表示法 0 +0 1→ 互连 输入：01234567 网络 输出：10325476 n-H n-
7.1.4 互连网络的表示方法 为了在输入结点与输出结点之间建立对应关 系，互连网络有三种表示方法： (1) 互连函数表示法： 如：f(xn-1…x1x0)=x0xn-2…x1xn-1 自变量和函数可以用二进制表示， 也可以用十进制等表示 (2) 图形表示法 (3) 输入输出对应表示法 互连 网络 … 0 0 1 … 1 n-1 n-1 输入: 0 1 2 3 4 5 6 7 输出: 1 0 3 2 5 4 7 6
第七章互连网络 本章主要内容：并行处理机和 多处理机系统中的互连网络 7.1互连网络的基本概念 7.2互连网络的种类 7.3消息传递机制 7.4互连网络实例
第七章 互连网络 7.1 互连网络的基本概念 7.2 互连网络的种类 7.3 消息传递机制 7.4 互连网络实例 本章主要内容：并行处理机和 多处理机系统中的互连网络