首页 > 其他分享 >《片上互联网络》第三章 拓扑

《片上互联网络》第三章 拓扑

时间:2024-09-09 16:20:58浏览次数:5  
标签:拓扑 网络 片上 带宽 互联网络 ring 节点 路由器

拓扑确定了网络中节点和通道之间的物理布局和连接,决定了节点之间的可用路径总数。拓扑的实现复杂度取决于两个因素:每个节点的链路数量(即节点度)和芯片上布局拓扑的难易程度(所需的导线长度和金属布线层数)

3.1 指标

常用片上网络拓扑结构:

 3.1.1 与网络流量(traffic)无关的指标

①度(degree):节点拥有的链路数量

②对分带宽(bisection bandwidth): 将网络划分为两个相同部分后,两部分之间的通信带宽。上图ring mesh torus的对分带宽分别为2,3,6。

③网络直径(diameter): 拓扑中任意两个节点之间的最短路径跳数的最大值。上图ring mesh torus的网络直径分别为4,4,2。

3.1.2 与网络流量相关的指标

①跳数(hop count):很简单,拓扑平均跳数可以很好的反应网络延迟。

②最大通道负载(maximum channel load):描述了网络中最繁忙的信道在最繁忙时的负载情况。最大注入带宽,也就是每个节点在网络饱和前每秒可注入的最大比特数与最大通道负载成反比,可规定最大注入带宽 = 1/最大通道负载

        对于网络当前最繁忙信道的通道负载,我们难以具体得到具体数值,因此引入一个相对指标:注入带宽系数,因此当我们说通道负载为2,即注入带宽系数为2,表示当前该信道通道负载是最大注入带宽的2倍。此时,注入带宽为原来的1/2时,网络就已经饱和。

        以通过单一通道连接的两个ring 结构为例。首先,我们假设网络流量均匀且随机,即每个节点向网络中其他节点(包括其自身)发送消息的概率相等。要计算最大通道负载,首先要确定瓶颈通道。在这个例子里,瓶颈通道就是连接两个ring结构的通道,即图中加粗显示的部分。我们假设它为一个双向链路。

        在理想路由方法下,每个节点注入流量的一半将保持在其所在的ring 结构内,而另一半将通过瓶颈通道到达另外一个ring 结构中的节点。例如,对于由节点A输出的每个数据包,它有1/8的概率到达节点B、C、D、E、F、G、H或它本身。当数据包的目的地为节点 A、B、C、D 时,数据包不经过瓶颈通道;但当它的目的地为节点E、F、G、H时,它就必须通过瓶颈通道。所以,节点A注入带宽的1/2将会通过瓶颈通道,对于其余节点也是如此。因此,这个瓶颈通道的负载为2(由于瓶颈通道是双向的,它能在两个方向上独立传输流量。也就是说,在EFGH到ABCD的方向上,同样有2的负载通过。所以单向瓶颈通道的负载 = 4 *1/2)。

        相应地,节点的最大注入带宽为1/2。结果是,网络在节点注入带宽达到1/2时,整个网络就会饱和(对于向右的通道,4*1/2*1/2(注入瓶颈通道的注入带宽) = 1)。向两个ring结构中添大更多的节点将进一步增大通道负载,从而减小网络带宽。

③路径多样性:Rsrc-dst 表示源节点和目的节点之间最短路径的个数。

3.2 直连拓扑

        直连拓扑指每个终端节点都配备一个路由器的网络拓扑,所有路由器即使流量的产生与绘入段,又是流量的中转站。到目前为止,大多数片上网络的设计都使用了直连网络,因为将路由器与终端节点放在一起考虑,通常适合芯片这种存在电路面积限制的环境。

        直连拓扑可以描述为k-ary n-cube,其中k时每个维度上的节点数,n是维度数。举个例子,4x4的mesh或torus 结构可以描述为4-ary 2-cube,它们的维度数都是2,每个维度上的节点数是4,一共有4x4=16个节点;8x8的mesh或torus 结构有64个节点,可以描述为8-ary 2-cube。同理,一个 4x4x4的 mesh或torus结构有64个节点,可以描述为4-ary3-cube。绝大多数片上网络使用2Dmesh拓扑,以方便在平面基板上进行电路映射(最多三维?)。

        最简单的直连拓扑:ring,mesh,torus

        torus的平均最小跳数:n为维度,k为每个维度上的节点数。

        mesh的平均最小跳数:

        对于均匀随机流量下参数k为偶数的 torus网络,其对分切割后两部分之间的最大通道负载是 k/8,其将网络最大注入带宽限制在了 8/k flit/node/cycle。对 mesh 来说,最大通道负载将会增大到k/4,因此网络最大注入带宽减小至 4/kflit/node/cycle。 

3.3 非直连拓扑

        非直连拓扑中终端节点与交换节点是彼此分离的。只有终端节点是流量的源(发出新的流量)或目的地(处理输入的流量而不向下继续传递),中间交换节点只是流量的中转站(将流量从输入送到指定的输出),以下具体介绍常见的几个非直连拓扑。

1.交叉开关(crossbar):

        一个交叉开关通过nxm个简单的交换节点连接了几个输入和m个输出。其中,n个输入和m个输出进行全连接,每个输入都连接到所有的m个输出。这种结构是非阻塞的(严格非阻塞,即可以在不影响其他连接的情况下建立任何输入端口与输出端口之间的连接),因为它总是可以将发送方与特定的接收方直接连起来。

2.蝶形网络(bufferfly):

        可以描述为k-ary n-fly。k是交换节点的入度/出度,n是交换节点的级数。网络有k的n次方个终端节点,n级交换节点,每级含k的n-1次方个k×k的交换节点。交换节点的度是2k,蝶形网络源节点到目的节点间路由的跳数并不会根据源-目的节点对的变化为变化,始终为n-1,在流量均匀分布的情况下,蝶形网络的最大通道负载是1,所以网络的最大注入带宽也为1fitnode/cycle。其他需要将大量流量从网络的一端发送到另一端的流量模式将增大最大通道负载,从而减小最大注入带宽。

        扁平蝶形网络:将每一行的交换节点合并为一个交换节点,将非直连拓扑转化为直连拓扑。

3.clos网络

        对称 clos 网络是一个可以用三元数组(m,n,r)表示的3级”网络,其中m指的是中间级交换节点数,n指的是输入/输出级交换节点(网络的第一级和最后级交换节点)的输入/输出端口数,r表示的是网络的第一级或最后一级交换节点数。当 m>2n-1 时,对应的 clos 网络是严格无阻塞的,与交叉开关类似,任意一个输入端口都可以连接到任何一个输出端口。一个clos网络包含rxn个终端节点。一个3级clos 网络中所有源-目的节点对的跳数都是4。clos 网络中的每一级交换节点并不完全相同,第一级和最后一级交换节点的度是n+m,而网络中间级交换节点的度是2r。一个具有m个中间级交换节点的clos网络的路径多样性为|Rsmc-dsl=m。clos 网络的一个缺点是它并不能利用源-目的节点对之间的局部性。图 3-6 展示了一个可以用三元数组(5,3,4)表示的对称 clos 网络。 

4.fat tree网络

        fat tree 网络在逻辑上是一个如图 3-7(a)所示的二叉树结构,物理上各个节点内部的布线资源不同,距离根节点越近的节点内部的连线资源越多。如图 3-7(b)所示,一个fat tree 网络可以由 clos 网络折叠而成,因为fattree 网络实际上是 clos 网络在根节点处将自己对折,因此fat tree 网络逻辑上是一个5级的 clos 网络(即信号从输入路由到输出需要最多5跳)。此外,如图3-7(b)所示,根节点处存在多个可以连接左右两边的节点,因此 fat tree 网络具有路径多样性。在fattree 网络中,消息先沿着树结构向上路由,直到找到目的地节点的祖先节点,之后向下路由到指定目的节点。这种路由方式使 fat tree 网络可以很好地利用节点之间的局部性。尽管更高层级的节点之间的链路更宽,我们始终认为fat tree 网络中每一个交换节点的逻辑上的度为4。

3.4 不规则拓扑

        定制一个拓扑主要有两种方法:分解法与合并法。分解法就是首先建立一个能够连接所有节点的交叉开关,然后迭代地将它分成多个小的交换节点以适应相应的一组设计约束。合并法是直接创建一个含较多交换节点的网络,如mesh或torus网络,并以此为起点逐渐合并交换节点以减小系统的面积和功耗。

3.5 层级拓扑

        最简单的层级拓扑使用集线器(concentrator)连接多个计算核心并共享同一个路由器。如图3-11(a)所示,这个结构中4个终端节点(计算核心、缓存等)共享同一个路由器。集线器的使用减少了网络所需要的路由器数量,从而网络的跳数及电路面积也会相应减小,这样做也有助于将网络扩展到更大的规模。在图3-11(a)中,集线器的引入使一个3x3的mesh结构使用9个路由器可连接36个节点,而不再必须使用36个路由器。另外,集线器会增加网络的复杂性。集线器必须确立一个策略,从而在其所连接的各个计算核心之间共享注入带宽。共享策略既可以是动态的共享带宽,也可以是静态的带宽均分,从而使得每一个节点拥有1/c的注入带宽,此处的c指的是集线器所连接的组件数。引用集线器的另一个缺点是,在突发通信期间,注入端口带宽可能会成为瓶颈。

         (b)展示了另一种层级拓扑。一个32个计算核心的芯片被切割成4个集群。每一个集群由通过双向ring结构连接的8个计算核心构成。这4个ring 结构通过另外一个ring 结构连在一起,从而构成了两级ring网络结构(第一级ring 结构选择指定的集群,第二级ring 结构在集群中选择具体的目的地节点)。这一层级拓扑的设计挑战在于如何设计对于中心ring结构的带宽仲裁。

3.6 实现

1布局布线

        链路会根据通道宽度和需要跨越的距离被选择性地布置在半全局或全局金属布线层上。导线的电容比晶体管要大一个数量级,如果不进行良好的优化它就会导致大量的功耗。目标时钟频率决定了需要插入电路以满足时序要求的中继器(repeater)的大小和距离(高频率意味着时钟周期更短,信号需要在更短的时间内传输,因此需要在较短的间隔内插入更多的中继器以确保信号按时传递。)。中继器通常是一个反相器或一对反相器)。

2 跳数

        跳数是一个广泛用于评估整个网络延迟和功耗的度量指标。直觉上来说这很合理,因为fit会在每一跳的路由器处停留,通过路由器的流水线和链路产生一定的延迟,总延迟记为流水线所有跳的延迟之和。但是,实际上跳数并非总是与网络延迟相关,因为网络延迟很大程度上取决于路由器的流术线深度及链路的传播延迟。

        在片上网络(NoC)中,路由器的流水线深度指的是数据包通过路由器时需要经过的不同处理阶段的数量。每个阶段负责数据包处理中的一个特定部分,例如解码、路由计算、交换分配、链路分配以及数据传输等。

        举个例子,假如存在一个网络,信息路由共两跳,流水线深度为5个时钟周期,而且路由器间距较大,需要4个时钟周期进行链路传输,那么它的实际网络延迟是18个时钟周期。相反地,一个跳数为3的网络,假如每个路由器只有一级流水线,而且链路延迟只需一个时钟周期,那么这个网络的总延迟只有6个时钟周期。如果上述两个网络的时钟频率相同,后者虽然跳数更大,但是其实际工作表现反而更快。不幸的是,类似于路由器的流水线深度的重要参数常常在设计的后期才能得到。
拓扑通常在节点度和跳数之间进行权衡。例如,一个拓扑可能节点度小但平均跳数大(如 ring结构),而另一个拓扑可能节点度大但平均跳数小(如 mesh结构)。这样比较两种不同的拓扑就变得更加棘手。因此,必须充分考虑网络的实现细节,才能在设计中做出明智的选择。

标签:拓扑,网络,片上,带宽,互联网络,ring,节点,路由器
From: https://blog.csdn.net/weixin_52173987/article/details/141961343

相关文章

  • 泛函分析-0:前置准备——拓扑空间
    拓扑空间是比度量空间更一般的定义,或者说,度量空间是在拓扑空间中引入了关于‘距离’的概念,它比一般拓扑空间更侧重于不同的‘距离’测量方法。Def(Topology):givensetX,atopologyisacollectionofX'ssubsets\(\mathscr{J}\)suchthat:\(\emptyset\)andX\(\in\)......
  • 图特征工程实践指南:从节点中心性到全局拓扑的多尺度特征提取
    图结构在多个领域中扮演着重要角色,它能有效地模拟实体间的连接关系,通过从图中提取有意义的特征,可以获得宝贵的信息提升机器学习算法的性能。本文将介绍如何利用NetworkX在不同层面(节点、边和整体图)提取重要的图特征。本文将以NetworkX库中提供的Zachary网络作为示例。这个广为人......
  • 简便、易用又专业的网络拓扑管理工具
    什么是网络拓扑图?网络拓扑图是一种图形表示方法,用于展示网络中组件的物理或逻辑布局。它详细描述了网络中各个节点(如计算机、路由器、交换机等设备)以及它们之间的连接方式和通信路径。网络拓扑图是网络管理员的重要工具,通过查看网络拓扑图,管理员可以清晰地了解网络的连接关系和设备......
  • 短视频源码,大文件切片上传的实现逻辑
    短视频源码,大文件切片上传的实现逻辑逻辑梗概将大文件分割成多个文件块逐个上传文件块服务端将文件块顺序合并成完整文件优势分析减轻服务器压力:如果一次性上传大文件,服务器的存储和网络带宽压力都会非常大,而通过切片,可以将这些压力分散到多个小文件中,减轻服务器的压......
  • 在图片上加二维码,并且添加文字
    //设置响应头,输出图片//header('Content-Type:image/png');$domain=$this->request->domain();//$public=public_path();//echo$domain.'/mask.png';die;//$res=file_get_contents("./ba......
  • Go实现大文件分片上传
    index.html<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>uploadfile</title></head><bodyid="app"><h1style="text-align:center"&......
  • JAVA实现文件分片上传、大文件秒传
    该说不说,最近这块挻火的。今天早上有网友加我微信,也是咨询这块的技术问题,最近不知道啥情况,加我的网友还是挻多的。实际上我的微信很早就在网上公开了,但是还是有很多网友说找不到。昨天晚上论坛里面有位网友发私信给我,聊了一下这个问题,这个网友是一个自由职业者,他也是刚开始......
  • C++ 有向图拓扑排序算法
    代码 #include<algorithm>#include<cassert>#include<functional>#include<map>#include<memory>#include<queue>#include<set>#include<unordered_set>#include<vector>namespacejc{templa......
  • 水凝胶结机器人咋自主运动?利用拓扑调用的自我调节!
     大家好,今天我们来聊聊一项有趣的研究——水凝胶结机器人。这篇文章《Animatinghydrogelknotbotswithtopology-invokedself-regulation》发表于《NatureCommunications》。想象一下,小小的机器人能够像生物一样自主运动,这是不是很神奇?科学家们通过巧妙地运用拓扑结构,......
  • 拓扑排序
    拓扑排序(所有点按照先后顺序排成序列)注:图必须是有向无环图Kahn(卡恩)算法核心思想:用队列维护一个入度为0的节点的集合具体代码如下:vector<int>e[N],tp;intdin[N];e[x]用来存点x的邻点,tp存拓扑序列,din[x]用来存点x的入度booltoposort(){ queue<int>q;......