互连网络设计

并行机器中的互连网络将信息从任何源节点传输到任何所需的目标节点。此任务应以尽可能小的延迟完成。它应该允许大量此类传输同时进行。此外，与机器其余部分的成本相比，它应该便宜。

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

组织结构

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

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

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

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

互连网络

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

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

• 间接连接网络 − 间接网络没有固定的邻居。通信拓扑可以根据应用需求动态更改。间接网络可以细分为三个部分:总线网络、多级网络和纵横制交换机。

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

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

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

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

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

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

路由

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

路由机制

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

确定性路由

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

无死锁

死锁可能发生在各种情况下。当两个节点试图向对方发送数据，并且每个节点在接收之前都开始发送数据时，可能会发生"正面"死锁。另一种死锁情况是，当网络中有多条消息争夺资源时。

证明网络无死锁的基本方法是清除由于消息在网络中移动而可能在通道之间发生的依赖关系，并表明整个通道依赖图中没有循环；因此不存在可能导致死锁的流量模式。常见的方法是对通道资源进行编号，使所有路由都遵循特定的递增或递减顺序，这样就不会出现依赖循环。

交换机设计

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

端口

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

内部数据路径

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

通道缓冲器

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

流量控制

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

流量控制问题出现在所有网络和多个层面。但并行计算机网络与局域网和广域网在性质上有所不同。在并行计算机中，网络流量需要像总线上的流量一样精确地传输，并且在非常小的时间尺度上存在大量并行流量。