片上网络NoC（3）——拓扑指标

目录

一、概述

二、指标

2.1 与网络流量无关的指标 

2.1.1 度（degree）

2.1.2 对分带宽（bisection bandwidth）

2.1.3 网络直径（diameter）

2.2 与网络流量相关的指标

2.2.1 跳数（hop count）

2.2.2 最大通道负载（maximum channel load）

2.2.3 路径多样性（path diversity）

三、总结

---

一、概述

        片上网络的拓扑（topology）确定了网络中节点和通道之间的物理布局和连接。拓扑对网络的整体成本效率（cost-performance）有相当重要的影响。拓扑决定了一条消息的跳数或经过的路由器个数，以及每跳经过的互连线的物理距离，因此会对网络延迟产生显著的影响。因为信息经过路由器（router）和链路（link)需要消耗能量，所以拓扑对跳数的影响会直接反映在网络的功耗方面。此外，拓扑决定了节点之间可用路径的总数，从而影响网络扩散流量及满足带宽需求的能力。拓扑的实现复杂度取决于两个因素：每个节点上的链路数量（即节点度）和在芯片上布局拓扑的难易程度（即所需的导线长度和金属布线层数）。
        总线是最简单的拓扑之一，它使用一个共享的通道来连接一组组件。总线上的所有组件都可以观察到总线上的每一条消息。因此，总线是一种有效的广播方式。然而，由于不断增加组件会造成共享通道趋近饱和，总线的可扩展性是十分受限的。
        在本文中，我们将重点研究交换拓扑（switched topology)。在交换拓扑中，一组组件通过路由器和链路进行连接。

二、指标

        在设计片上网络时，首先需要考虑拓扑。对于拓扑设计，有几个重要的指标来对拓扑进行一个直觉性的解释。下图中给出了几种常见的简单拓扑结构：

2.1 与网络流量无关的指标 

        首先我们考虑一组在设计阶段考虑的、与网络流量无关的指标。

2.1.1 度（degree）

        一个拓扑的度表示每个节点拥有的链路数量。以上图为例，ring结构的度为2，tours结构的度为4，mesh结构比较特殊，其中处于不同位置节点的度是不同的。

        度是一个可以有效衡量网络开销的指标，节点的度越大，表示节点路由器需要更多的端口。相应地，路由器的实现复杂度及面积和功耗都会有所增大。我们把每个路由器的端口数称为路由器基数（router radix）。

2.1.2 对分带宽（bisection bandwidth）

        对分带宽指的是将网络划分成两个相同部分后，两部分之间的通信带宽。（一个网络通常很难划分成完全相同的两部分，这里的对分一般只要求近似相同，通常只要求对分后的网络各个维度上的节点数相等或只能在一个维度上节点数相等。）还是以上图为例，穿过ring结构的对分线的链路数量为2，穿过mesh结构的对分线的链路数量为3，穿过torus结构的对分线的链路数量为6。

        这一带宽指标可以有效地反映特定网络在最坏工作情况下的性能，因为对分带宽限制了可以从系统一端移动到另一端的总数据量。另外，这一指标同时也表示了实现片上网络时所必需的全局连线数量，所以它也可以用来衡量网络的开销。相当于评价片上网络而言，对分带宽其实并不能很好地评价片上网络，因为片上网络的全局连线资源同芯片与片外通信的引脚带宽资源相比，连线资源要丰富得多。

2.1.3 网络直径（diameter）

        网络直径指的是拓扑中任意两个节点之间的最短路径组成的集合中的最大值（即网络中所有源—目的节点对的最短路径中的跳数最大值）。例如，之前例子中的ring结构和mesh结构的网络直径为4，torus结构的网络直径为2。在没有链路竞争的情况下，网络直径可以作为衡量拓扑中最大延迟的指标。

2.2 与网络流量相关的指标

        接下来，我们定义一组和网络流量（traffic，指源—目的节点对之间的通信）有关的指标。

2.2.1 跳数（hop count）

        我们定义从一个节点路由至另一个节点称为一跳（hop）。跳数是指一条消息从源节点路由到目的节点需要跳的总次数，或者指这条消息所通过的链路总数。

        这是一个可以简单有效地反映网络延迟的指标，因为即使在网络内部没有竞争的情况下，网络中的每一个节点和链路还是会引入传输延迟的。网络的最大跳数取决于其直径。除了最大跳数，平均跳数也可以很好地反映网络延迟，其表示网络所有可能的源—目的节点对之间的路径的跳数的平均值。

2.2.2 最大通道负载（maximum channel load）

        这一指标可用于估计网络所能支持的最大带宽，或者每个节点在网络饱和前每秒可注入的最大比特数。最大通道负载与最大注入带宽（maximum injection bandwidth）之间存在如下关系。

最大注入带宽＝1／最大通道负载

        直观上，想要估计网络能够支持的最大带宽，首先需要确定在特定流量模式下网络中哪个链路或通道最拥挤，因为该链路将限制整个网络的带宽。在均匀随机流量下，限制网络带宽的瓶颈链路大多情况下是将网络对分切割后连接切割后两部分网络的链路。接下来估计该通道负载。由于在设计的早期阶段，我们无法得知通道的具体使用情况（每个通道有多少个实际的物理互连及每个互连的带宽大小），所以我们需要一个能够相对地测量通道负载的指标，即注入带宽相对系数。所以，当我们说通道负载为2时，意味着该通道负载是注入带宽的两倍。

        举例来说，假设通道负载是 2，那么如果每个节点的每个时钟周期将一个flit（flow control unit，流控制单元，可以认为时流控制中最小粒度数据单元）注入网络，则意味着会出现两个flit在同一时钟周期内都需要穿过该通道的情况。如果这个通道每个时钟周期只能处理一个flit，则这个通道会成为瓶颈通道。这个瓶颈通道会将网络的最大注入带宽限制为链路带宽的一半，即每个节点最多可以每隔一个时钟周期向网络中注入一个flit（而不是每周期注入一个）。由于每个通道工作时的实际负载量一定，因此最大通道负载越大，相应的网络最大注入带宽越小。

2.2.3 路径多样性（path diversity）

        在给定源节点和目的节点的前提下，如果这个节点在对某个拓扑中拥有多条最短路径，而在另一个拓扑中只有一条 最短路径，则认为前者的拓扑具有更大的路径多样性。

        拓扑中的路径多样性使路由算法在处理负载均衡问题时具有更大的灵活性，从而通过减小通道负载，提高了网络吞吐量。路径多样性还使得数据包能够拥有绕过网络中故障的潜力。

三、总结

        本文中，我们介绍了片上网络的拓扑指标，这些指标可以分成与网络流量无关的指标和与网络流量有关的指标，这些指标给出了拓扑及其性能的直觉性描述。