计算机系统结构 (第25讲) 主讲人： 郑纬民教授 清华大学计算机系
计算机系统结构 （第25讲） 主讲人： 郑纬民 教授 清华大学计算机系
第七章互连网络 本章主要内容：并行处理机和 多处理机系统中的互连网络 7.1互连网络的基本概念 7.2互连网络的种类 7.3消息传递机制
第七章 互连网络 7.1 互连网络的基本概念 7.2 互连网络的种类 7.3 消息传递机制 本章主要内容：并行处理机和 多处理机系统中的互连网络
73消息传递机制 研究各种寻径方法，并分析它们的通信时 延问题 7.3.1消息寻径方式 四种寻径方式：线路交换，存储转发、虚 拟直通和虫蚀寻径等。 1、线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通 路，然后再传递消息。传输时延公式： T=(Lt/B)xD+L/B
7.3 消息传递机制 研究各种寻径方法，并分析它们的通信时 延问题 7.3.1消息寻径方式 四种寻径方式：线路交换，存储转发、虚 拟直通和虫蚀寻径等。 1、线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通 路，然后再传递消息。传输时延公式： T = (Lt/B)D+L/B
其中：Lt为建立路径所需小信息包的长度 L为信息包的长度，D为经过的结点数， B为带宽。 优点：实际通信时间较短，使用缓冲区少。 缺点：建立源结点到目的结点的物理通路 开销很大，占用物理通路的时间长。 2、存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经 过中间结点到达目的结点。 存储转发网络的时延与源和目的地之间的 距离成正比。传输时延公式：
其中：Lt为建立路径所需小信息包的长度 L为信息包的长度，D为经过的结点数， B为带宽。 优点：实际通信时间较短，使用缓冲区少。 缺点：建立源结点到目的结点的物理通路 开销很大，占用物理通路的时间长。 2、存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经 过中间结点到达目的结点。 存储转发网络的时延与源和目的地之间的 距离成正比。传输时延公式：
7.3消息传递机制 研究各种寻径方法，并分析它们的通信时 延问题 7.3.1消息寻径方式 四种寻径方式：线路交换，存储转发、虚 拟直通和虫蚀寻径等。 1、线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通 路，然后再传递消息。传输时延公式： T=(Lt/B)xD+L/B
7.3 消息传递机制 研究各种寻径方法，并分析它们的通信时 延问题 7.3.1消息寻径方式 四种寻径方式：线路交换，存储转发、虚 拟直通和虫蚀寻径等。 1、线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通 路，然后再传递消息。传输时延公式： T = (Lt/B)D+L/B
其中：Lt为建立路径所需小信息包的长度 L为信息包的长度，D为经过的结点数， B为带宽。 优点：实际通信时间较短，使用缓冲区少。 缺点：建立源结点到目的结点的物理通路 开销很大，占用物理通路的时间长。 2、存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经 过中间结点到达目的结点。 存储转发网络的时延与源和目的地之间的 距离成正比。传输时延公式：
其中：Lt为建立路径所需小信息包的长度 L为信息包的长度，D为经过的结点数， B为带宽。 优点：实际通信时间较短，使用缓冲区少。 缺点：建立源结点到目的结点的物理通路 开销很大，占用物理通路的时间长。 2、存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经 过中间结点到达目的结点。 存储转发网络的时延与源和目的地之间的 距离成正比。传输时延公式：
T=(LB)×D+L/B=(D+1)×L/B 优点：占用物理通路的时间比较短。 缺点：包缓冲区大，时延大（与结点距离 成正比)。 3、虚拟直通(virtual cut through) 当接收到用作寻径的消息头部时，即开始 路由选择。通信时延公式： T=(Lh/B)x D+L/B=(Lh x D+L)/B 其中：Lh是消息的寻径头部的长度，一 般有，L>Lh×D;通信时延可以近似为： T=LB,与结点数无关
T = (L/B) D + L/B = (D + 1) L/B 优点：占用物理通路的时间比较短。 缺点：包缓冲区大，时延大（与结点距离 成正比）。 3、虚拟直通(virtual cut through) 当接收到用作寻径的消息头部时，即开始 路由选择。通信时延公式： T=(Lh/B) D + L/B = (Lh D+ L)/B 其中：Lh是消息的寻径头部的长度，一 般有，L>>Lh×D；通信时延可以近似为： T＝L/B，与结点数无关
当出现寻径阻塞时，只能将整个消息存储 在寻径结点中。 主要优点：通信延迟与结点数无关。 主要缺点：每个结点需要有足够大的缓冲 区来存储最大信息包。在最坏的情况下 与存储转发方式的通信时延是一样的， 经过的每个结点都发生阻塞，都需缓冲 4、虫蚀寻径(wormhole) 把包分成更小的片。每个结点的寻径器中 有片缓冲区。 用头片直接开辟一条从输入结点到输出结
当出现寻径阻塞时，只能将整个消息存储 在寻径结点中。 主要优点：通信延迟与结点数无关。 主要缺点：每个结点需要有足够大的缓冲 区来存储最大信息包。在最坏的情况下 与存储转发方式的 通信时延是一样的， 经过的每个结点都发生阻塞，都需缓冲 4、虫蚀寻径(wormhole) 把包分成更小的片。每个结点的寻径器中 有片缓冲区。 用头片直接开辟一条从输入结点到输出结
点的路径。每个消息中的片以流水方式在 网络中向前“蠕动”。 当消息的头片到达一个结点A的寻径器后， 寻径器根据头片的寻径消息立即做出路 由选择 如果所选择的通道或的结点的片缓冲区不 可用时，头片必须在该结点的片缓冲区 中等待，其它数据片也在原来的结点上 等待。通信时延用公式： T=TfxD+L/B=(Lf/B)x D+L/B =Lf×D+L)/B
点的路径。每个消息中的片以流水方式在 网络中向前“蠕动”。 当消息的头片到达一个结点A的寻径器后， 寻径器根据头片的寻径消息立即做出路 由选择 如果所选择的通道或的结点的片缓冲区不 可用时，头片必须在该结点的片缓冲区 中等待，其它数据片也在原来的结点上 等待。通信时延用公式： T = TfD + L / B = (Lf/B) D + L/B = (Lf D + L) / B
其中：Lf是片的长度，T是片经过一个 结点所需时间。一般有L>>Lf×D,通信 时延公式近似为T=LB,与结点数无关 虫蚀寻径的优点： 每个结点的缓冲区较小，易于VLSI实现。 较低的网络传输时延。 通道共享性好，利用率高。 易于实现选播和广播通信方式。 虫蚀寻径的缺点： 当消息的一个片被阻塞时，整个消息都 被阻塞，占用了结点资源
其中：Lf是片的长度，Tf是片经过一个 结点所需时间。一般有L>>Lf×D，通信 时延公式近似为T＝L/B，与结点数无关 虫蚀寻径的优点： 每个结点的缓冲区较小，易于VLSI实现。 较低的网络传输时延。 通道共享性好，利用率高。 易于实现选播和广播通信方式。 虫蚀寻径的缺点： 当消息的一个片被阻塞时，整个消息都 被阻塞，占用了结点资源