Interconnection_Networks-ch2

CH2 A Simple Interconnection Network

2.1网络规范和限制

有关网络设备的规范和约束，规范比如端口数量，传输速率。约束有关带宽，消耗。

2.2拓扑

蝶形网络拓扑

speedup 加速比网络总输入带宽与网络理想容量的比值。也被称为蝶形基数。

2.5路由器

路由器的数据路径包括四个18位输入寄存器，四个18位4：1多路复用器，四个移位器（用于移位标头phits的路由字段）和四个18位输出寄存器。数据路径由144位寄存器和大约650个门（等效于2个输入NAND）组成。

Allocator

分配器由四个几乎相同的位片组成，每个位片分为三个部分：解码，仲裁和保持。

在解码部分中，对每个输入phit的高四位进行解码。每个解码器生成两个信号。如果输入i是一个head phit并且路由字段的高两位与输出端口号匹配，则信号i请求为true。此信号指示输入phit请求使用此头phit开始使用输出端口路由数据包。如果输入i上的点是有效载荷点，则解码器还会生成信号有效载荷i。分配器的保持逻辑使用此信号在数据包持续时间内保持信道（只要有效载荷位在所选输入端口上）

性能分析

通过三种方法来判断互连网络：成本，延迟和吞吐量。延迟和吞吐量都是性能指标：延迟是数据包穿越网络所花费的时间，吞吐量是网络可以从输入传输到输出的每秒位数。

对加权延迟求和，我们将平均延迟计算为

延迟和吞吐率的曲线

相对延迟是简单网络的所提供流量（注入速率）的函数。实线显示了本文中介绍的简单模型，而虚线则包含了额外的排队延迟。

CH3 T opology Basics

重要性

是设计第一步，决定了策略路由和流控制方法；
拓扑不仅指定网络的类型（例如，蝶形），还指定详细信息，例如交换机的基数，级数以及宽度和比特率每个频道

考虑的东西

端口数量以及每个端口的带宽和占空比的驱动
每个芯片和板可用的引脚，线密度，可用的信号速率以及驱动器的驱动
成本和性能。性能包括带宽和延迟，由拓扑以外的因素决定，例如，流量控制，路由策略和流量模式。

评价

二等分带宽，信道负载和路径延迟之类的措施，这些措施反映了拓扑对性能的影响。

设计的陷阱

尝试使网络的拓扑结构与当前问题的数据通信相匹配。

原因：专用网络通常不是好主意，问题中的动态负载不平衡，或者问题大小与计算机大小之间不匹配，因此此类网络上的负载通常平衡不佳。如果重新分配数据和线程以平衡负载，则问题和网络之间的匹配将丢失。特定问题的网络通常无法很好地映射到可用的封装技术，需要较长的导线或较高的节点度。最后，这样的网络是不灵活的。如果算法更改为使用其他通信模式，则无法轻松更改网络。

拓扑案例

3.1 Nomenclature（命名法）

3.1.1 Channels and Nodes

互连网络的拓扑结构由一组节点N *指定，该节点N *通过一组通道C连接。消息在一组终端节点N（其中N≥N *）中发起和终止。

拓扑有向图

channel c = (x, y) ∈ C。x是源节点$sc$，y是目的节点$dc$

信道特征：

width($w_c$,$w_{xy}$) 包含的并行信号数
frequency, $f_c$or $f_{xy}$ 每个信号上的比特传输速率
latency, $t_c$or$ t_{xy}$ 从x到y所需的时间。与传播速度和信道的物理长度直接相关$l_c = vt_c$.信道带宽$b_c=w_cf_c$

3.1.2 Direct and Indirect Networks

3.1.3 Cuts and Bisections

网络切割点$C(N_1,N_2)$是一组通道，它将所有节点N *的集合划分为两个不相交的集合$N_1$和$N_2$

$C(N_1,N_2)$每个元素都是一个通道，其源位于N1，目标位于N2，反之亦然。cut的带宽：

Bisection二等分，就网络几乎分为一半的cut满足$N_2\le N_1 \le N_2+1$

有最小信道数

3.1.4 Paths

信道的有序集合$d_{c_i} = s_{c_{i+1}}$

minimal path 节点x到节点y的跳数最小的路径

$R_{xy}$所有x到y的最小路径的集合

$H(x,y)$是最小路径的节点跳数

网络的直径。所有节点对中$R_{xy}$ 的最大值

平均最小跳数

3.1.5 对称性

节点对称，边对称

3.2 交通模式

考虑互连网络中消息的空间分布是很有用的。利用流量矩阵$\wedge$. 每个矩阵元素$\lambda_{s,d}$给出从节点s发送到节点d的流量份额

评估互连网络的常见静态流量模式

随机流量：网络评估中最常用的流量模式是随机流量，其中每个源均可能发送到每个目的地。随机流量非常有益，因为通过使流量均匀分布，即使是通常负载平衡非常差的拓扑和路由算法，它也可以平衡负载。仅使用随机流量进行评估时，某些非常差的拓扑和路由算法看起来非常好。

permutation（置换流量）：为了强调拓扑或路由算法，我们通常使用置换流量，其中每个源s将其所有流量发送到单个目标d =π（s）。用于排列的流量矩阵是一个排列矩阵（其中每一行和每一列包含一个条目，所有其他条目均为零。由于它们将负载集中在单独的源－目的地对上，因此排列会强调拓扑和路由算法的负载平衡。