CH4 Torus Networks

圆环和网状网络（ k-ary n-cubes）在规则的n维网格中打包$N=k^n$个节点，每个维中都有k个节点，并且最近邻之间有通道。

优点：

  • 这种规则的物理布置与包装约束非常匹配。
  • 具有良好的路径分集，即使在排列流量上也可以具有良好的负载平衡。
  • 通道是双向的,可以利用双向信令，从而更有效地利用引脚和电线。

缺点：

  • 它们的跳数比对数网络大；
  • 增加了网络的引脚成本。

4.1The Structure of T orus Networks

  • $N=k^n$个节点
  • 每个维中都有k个节点
  • 每个节点同时充当网络的输入端，输出端和交换节点
  • 每个节点被分配一个n-digit radix-k地址{an−1,…,a0}
  • 通过一对通道（每个方向一个）连接到地址相差±1（mod k）的所有节点。只需一个地址位。
  • 每个节点每个维度需要2个通道，总共2nN个通道。

规则的（所有节点的度数相同），并且也是边缘对称的。
网状网络和环状网络的区别：

  1. 网状网络 在每个方向上都省略了从地址ak−1到地址a0的连接
  2. 网状网络具有相同的节点度，但是对等通道的数目是具有相同基数和尺寸的圆环的一半
  3. 放弃了圆环的边缘对称性，对中央通道的需求可能会大大高于对边缘通道的需求

image-20200720140511291

环面网络的每个维度都可以具有不同的基数。例如，下图说明了一个2,3,4-ary 3-mesh，其y方向的基数为2image-20200720141524634

5.2 performance

throughput, latency, and path diversity.

5.2.1 Throughput

在两层封装模型中，吞吐量受引脚带宽或二等分带宽限制。我们首先考虑对分限制并计算网络的信道对分为:

k为偶数

image-20200722161336861

由于圆环既是节点对称的，又是边缘对称的，从平分信道负载中确定均匀流量下的信道负载。

image-20200722161423232

由于圆环的边缘对称性：

​ image-20200722161456946

由于网格是不对称的，由于上面用于圆环的跳数，它无法达到下限。相反，在统一流量下网格的信道负载为image-20200722161558619

对于最坏情况的流量，所有流量都会越过平分线，并且通道负载会加倍。

​ image-20200722161807795

每个节点四个信道：image-20200722161854710

圆环的最大通道宽度image-20200722161920581

网格的：image-20200722161938362

计算均匀负载下的吞吐量：

​ image-20200722161959797

5.2.2 Latency

环形网络的延迟在很大程度上取决于尺寸。在低维度上，延迟是由高跳数决定的。在维度的极端情况下，串行延迟由于通道宽度w的狭窄而占主导地位。最佳等待时间通常发生在较低的中间维度。

环型网络的串行化等待时间

image-20200722162116800

网格网络

image-20200722162144750

圆环网络中的平均最小跳数是通过对所有节点对上的最短距离求平均来确定的，从而得出image-20200722162239212

网格网络：在均匀的流量和偶数基数的情况下，数据包平均在n个维度中的每个维度上四分之一地传播，即$\frac{k}{4}$跳。因此偶数k，跳数为$\frac{nk}{4}$,对于奇数k，平均距离包括一个小的附加系数。

​ image-20200722163218184

5.2.3 Path Diversity

路径数量，我们只考虑最短路径，并且所有路径在每个维度（单向路线）都采用相同的方向。

  • 一维网络，只有一个路径

  • 二维网络，考虑节点a，b，如果在x方向，二者被$\Delta x$跳分割，y方向上，$\Delta y$跳，那么路径数量为：

    $$
    \begin{vmatrix}
    R_{ab}
    \end{vmatrix}=\binom{\Delta_x+\Delta_y}{\Delta_x}
    $$

  • 三维网络，增加z的维度

$$
\begin{vmatrix}
R_{ab}
\end{vmatrix}=\binom{\Delta_x+\Delta_y+\Delta_z}{\Delta_x}\binom{\Delta_y+\Delta_y}{\Delta_y}=\frac{(\Delta_x+\Delta_y+\Delta_z)!}{\Delta_x!\Delta_y!\Delta_z!}
$$

  • n维：从a到b的最小单向路线的总数为image-20200722181511667