互连网络设计

并行机器中的互连网络负责在任意源节点与任意目标节点之间传输信息。此任务应以尽可能小的延迟完成。它应该允许大量此类传输同时进行。此外，与机器其余部分的成本相比，它应该价格低廉。

网络由链路和交换机组成，有助于将信息从源节点发送到目标节点。网络由其拓扑结构、路由算法、交换策略和流量控制机制指定。

组织结构

互连网络由以下三个基本组件组成：

• 链路 − 链路是一根或多根光纤或电线的电缆，每端都连接到交换机或网络接口端口的连接器。通过它，模拟信号从一端传输，在另一端接收以获得原始数字信息流。

• 交换机 − 交换机由一组输入和输出端口、连接所有输入和所有输出的内部“交叉开关”、内部缓冲区和控制逻辑组成，以在每个时间点实现输入输出连接。通常，输入端口的数量等于输出端口的数量。

• 网络接口 − 网络接口的行为与交换机节点大不相同，并且可以通过专用链路连接。网络接口格式化数据包并构建路由和控制信息。与交换机相比，它可能具有输入和输出缓冲区。它可以执行端到端错误检查和流量控制。因此，其成本受其处理复杂性、存储容量和端口数量的影响。

互连网络

互连网络由交换元件组成。拓扑结构是将各个交换机连接到其他元件（如处理器、存储器和其他交换机）的模式。网络允许在并行系统中的处理器之间交换数据。

• 直接连接网络 − 直接网络在相邻节点之间具有点对点连接。这些网络是静态的，这意味着点对点连接是固定的。直接网络的一些示例包括环形网络、网格网络和超立方体网络。

• 间接连接网络 − 间接网络没有固定的邻居。通信拓扑可以根据应用程序的需求动态更改。间接网络可以细分为三个部分：总线网络、多级网络和交叉开关。

  • 总线网络 − 总线网络由许多位线组成，许多资源连接到这些位线上。当总线使用相同的物理线路进行数据和地址传输时，数据线和地址线是时间复用的。当有多个总线主控连接到总线时，需要仲裁器。

  • 多级网络 − 多级网络由多个交换机级组成。它由“axb”交换机组成，这些交换机使用特定的级间连接模式 (ISC) 连接。小的 2x2 交换元件是许多多级网络的常见选择。级数决定了网络的延迟。通过选择不同的级间连接模式，可以创建各种类型的多级网络。

  • 交叉开关 − 交叉开关包含一个简单的交换元件矩阵，这些元件可以打开和关闭以创建或断开连接。打开矩阵中的交换元件，就可以在处理器和存储器之间建立连接。交叉开关是非阻塞的，也就是说所有通信排列都可以无阻塞地执行。

评估网络拓扑中的设计权衡

如果主要关注的是路由距离，则必须最大化维度并构建超立方体。在存储转发路由中，假设交换机的度数和链路数量不是重要的成本因素，并且链路数量或交换机度数是主要成本，则必须最小化维度并构建网格。

在每个网络的最坏情况流量模式下，最好使用高维网络，其中所有路径都很短。在每个节点仅与一个或两个附近的邻居通信的模式中，最好使用低维网络，因为实际上只使用少数维度。

路由

网络的路由算法决定了从源到目标的哪些可能路径用作路由，以及如何确定每个特定数据包遵循的路由。维度顺序路由限制了合法路径的集合，以便从每个源到每个目标都只有一条路由。该路由首先在高阶维度上行进正确的距离，然后是下一个维度，依此类推。

路由机制

算术、基于源的端口选择和表格查找是高速交换机用来根据数据包报头中的信息确定输出信道的三种机制。所有这些机制都比在传统局域网和广域网路由器中实现的通用路由计算更简单。在并行计算机网络中，交换机需要在每个周期内为所有输入做出路由决策，因此该机制需要简单快捷。

确定性路由

如果消息所走的路由完全由其源和目标决定，而不是由网络中的其他流量决定，则路由算法是确定性的。如果路由算法只选择通向目标的最短路径，则它是最小化的，否则是非最小化的。

无死锁

死锁可能发生在各种情况下。当两个节点试图相互发送数据并且每个节点都在另一个节点接收之前开始发送时，可能会发生“对头”死锁。另一种死锁情况是，当有多个消息在网络内竞争资源时。

证明网络无死锁的基本技术是清除由于消息通过网络移动而可能在信道之间发生的依赖关系，并表明整体信道依赖图中没有循环；因此，没有可能导致死锁的流量模式。执行此操作的常用方法是对信道资源进行编号，以便所有路由都遵循特定的递增或递减序列，从而避免出现依赖循环。

交换机设计

网络的设计取决于交换机的设计以及交换机的连接方式。交换机的度数、其内部路由机制及其内部缓冲区决定了可以支持哪些拓扑以及可以实现哪些路由算法。与计算机系统的任何其他硬件组件一样，网络交换机包含数据路径、控制和存储。

端口

引脚总数实际上是输入和输出端口总数乘以通道宽度。由于芯片的周长比面积增长缓慢，因此交换机往往受到引脚限制。

内部数据路径

数据路径是每组输入端口和每个输出端口之间的连接。它通常被称为内部交叉开关。非阻塞交叉开关是指每个输入端口可以同时连接到任意排列中的不同输出的交叉开关。

通道缓冲区

交换机内缓冲存储的组织对交换机性能有重要影响。传统的路由器和交换机倾向于在交换机结构外部具有大型 SRAM 或 DRAM 缓冲区，而在 VLSI 交换机中，缓冲区位于交换机内部，并与数据路径和控制部分来自相同的硅预算。随着芯片尺寸和密度的增加，可用的缓冲区更多，网络设计人员有更多选择，但缓冲区空间仍然是首要选择，其组织非常重要。

流量控制

当网络中的多个数据流尝试同时使用相同的共享网络资源时，必须采取一些措施来控制这些流。如果我们不想丢失任何数据，则必须阻塞某些流，而其他流则继续进行。

流量控制问题出现在所有网络和许多级别。但它在并行计算机网络中的性质与在局域网和广域网中的性质有本质区别。在并行计算机中，网络流量需要像跨总线的流量一样准确地交付，并且在非常短的时间范围内存在大量并行流。