路由与交换技术详解

# 并行计算机网络中的路由与交换技术 ## 1. 二维网格网络的路由算法 ### 1.1 最小自适应路由算法 在二维网格网络中，可将带有虚拟通道的网络划分为 +X 网络和 -X 网络，以应用最小自适应路由算法。当源节点和目的节点的 x 坐标相同时（xA = xB），可以任意选择两个网络中的一个，还可结合负载信息进行选择，该算法能避免死锁。 ### 1.2 非最小自适应路由算法 当不存在最小路径时，非最小自适应路由算法可以通过更长的路径发送消息。维度反转路由算法可应用于任意网格和 k 元 d 立方体网络。该算法在任意由物理链路连接的节点对之间使用 r 对虚拟通道，将网络划分为 r 个虚拟网络。每个待传输的消息被分配一个类 c，初始化为 c = 0，在消息传输过程中可增加到 c = 1, …, r - 1。类 c = i 的消息可在网络 i 的每个维度中转发，但维度必须按升序遍历。若消息需按相反顺序传输，其类增加 1（维度顺序反转）。参数 r 控制允许的维度反转次数，当 c = r 时，消息按维度有序路由转发。 ## 2. Omega 网络的路由 ### 2.1 分布式路由算法 Omega 网络采用分布式算法进行消息转发，每个交换机可独立转发消息，无需与其他交换机协调。为描述该算法，可将 n 个输入通道和输出通道分别用长度为 log n 的位串表示。要将消息从位表示为 α 的输入通道转发到位表示为 β 的输出通道，网络第 k 级（k = 0, …, log n - 1）的接收交换机考虑 β 的第 k 位（从左起）βk，并根据以下规则选择输出链路： - 若 βk = 0，消息通过交换机的上链路转发； - 若 βk = 1，消息通过交换机的下链路转发。 ### 2.2 并发传输与冲突 在 n × n 的 Omega 网络中，最多可同时无冲突地发送 n 条来自不同输入通道到不同输出通道的消息。然而，许多由排列描述的同时消息传输无法并发执行，因为会发生网络冲突。例如，在 8 × 8 的 Omega 网络中，从输入通道 α1 = 010 到输出通道 β1 = 110 和从输入通道 α2 = 000 到输出通道 β2 = 111 的两条消息传输会发生冲突。这种网络被称为阻塞网络，冲突可通过多次网络传输解决。 ### 2.3 可实现的排列数量 对于从 n 个输入通道到 n 个输出通道的连接，总共有 n! 种可能的排列。Omega 网络中共有 n/2·log n 个交换机，每个交换机有两种状态，因此整个网络共有 2n/2·log n = nn/2 种不同的交换状态，对应 n 条并发路径。所以，只有 nn/2 种可能的排列可以无冲突地执行。 ### 2.4 阻塞与非阻塞网络 除了 Omega 网络，蝴蝶或榕树网络、基线网络和 delta 网络也是阻塞网络。相比之下，Beneš 网络是非阻塞网络，因为从输入通道到输出通道有不同的路径。对于每个排列 π : {0, …, n - 1} → {0, …, n - 1}，都存在 Beneš 网络的一种交换状态，可同时无冲突地实现从输入 i 到输出 π(i) 的连接。 ## 3. 消息交换策略 ### 3.1 交换策略的作用 交换策略决定了消息如何沿着路由算法选择的路径传输，具体包括： - 消息是否以及如何分割成数据包或流控制单元（flits）； - 从源节点到目的节点的传输路径如何分配； - 消息或消息片段如何从交换机或路由器的输入通道转发到输出通道。 ### 3.2 相邻处理器间的消息传输 #### 3.2.1 发送步骤 1. 将消息复制到系统缓冲区。 2. 计算校验和，并为消息添加包含校验和及其他传输相关信息的头部。 3. 启动定时器，通过网络接口发送消息。 #### 3.2.2 接收步骤 1. 将消息从网络接口复制到系统缓冲区。 2. 计算数据的校验和，并与头部存储的校验和进行比较。若两者相同，向发送方发送确认消息；若不相同，丢弃消息，发送方定时器超时后将重新发送消息。 3. 若校验和相同，将消息从系统缓冲区复制到应用程序提供的用户缓冲区，应用程序收到通知后可继续执行。 #### 3.2.3 发送后的处理 1. 若收到发送消息的确认消息，可释放包含消息副本的系统缓冲区。 2. 若定时器超时，将重新发送消息，并再次启动定时器，可能设置更长的时间。 ### 3.3 性能指标 - **带宽**：网络链路允许数据发送的最大频率，单位为比特每秒或字节每秒。 - **字节传输时间**：传输单个字节所需的时间，若带宽以字节每秒为单位，字节传输时间是带宽的倒数。 - **飞行时间**：消息的第一位到达接收方所需的时间，主要取决于发送方和接收方之间的物理距离。 - **传输时间**：消息通过网络链路传输所需的时间，等于消息大小（字节）除以网络链路的带宽（字节每秒），不考虑与其他消息的冲突。 - **传输延迟**：消息通过网络链路传输的总时间，是传输时间和飞行时间之和。 - **发送方开销**：发送方准备消息传输所需的时间，包括计算校验和、添加头部和执行路由算法的时间。 - **接收方开销**：接收方处理传入消息所需的时间，包括校验和比较和生成确认消息的时间。 - **吞吐量**：应用程序实际体验到的有效带宽。 消息大小为 m 的总延迟 T (m) 可表示为： T (m) = Osend + Tdelay + m/B + Orecv 其中 Osend 和 Orecv 分别是发送方和接收方的开销，Tdelay 是飞行时间，B 是网络链路的带宽。该表达式未考虑由于校验和错误、网络争用或拥塞导致的消息多次传输。 通过合并常数项，可将上式改写为： T (m) = Toverhead + m/B 其中 Toverhead = Tsend + Trecv。使用字节传输时间 tB = 1/B，可进一步表示为： T (m) = Toverhead + tB · m ### 3.4 不同交换技术 #### 3.4.1 电路交换 在电路交换中，从源节点到目的节点的整个路径在消息传输结束前被建立并保留。消息可内部拆分为物理单元（phits）进行传输，phit 大小取决于物理通道并行传输的比特数