用于在片上环形网络中减少时延的非对称环形网拓扑

摘要

一种包括芯片的设备，所述芯片包括多个节点、在具有第一拓扑的第一环形网络中使所述多个节点连接的第一多个链路以及在具有第二拓扑的第二环形网络中使所述多个节点连接的第二多个链路，其中第一拓扑不同于第二拓扑。

说明书

相关申请案的交叉参考

本发明要求2011年10月31日由罗希特·桑卡姆·拉马努詹（Rohit Sunkam Ramanujam） 等人递交的发明名称为“用于在片上环形网络中减少时延的非对称环形网拓扑（Asymmetric  Ring Topology for Reduced Latency in On-Chip Ring Networks）”的第13/285,733号美国非临时 专利申请案以及2011年2月3日由罗希特·桑卡姆·拉马努詹（Rohit Sunkam Ramanujam） 等人递交的发明名称为“用于在片上环形网络中减少时延的非对称环形网拓扑（Asymmetric  Ring Topology for Reduced Latency in On-Chip Ring Networks）”的第61/439,229号美国临时专 利申请案的在先申请优先权，这些在先申请的内容以全文引入的方式并入本文本中。

关于由联邦政府赞助的

研究或开发的声明

不适用。

参考缩微胶片附录

不适用。

技术领域

背景技术

当晶体管和其它组件的大小变得更小且制造技术不断改进时，越来越多的功能被安置 在单个集成电路或芯片上。术语片上系统（system on a chip；SoC）一般是指将计算机或其它 复杂的电子系统的所有功能集成到单个芯片上。SoC可包括一个或多个存储器、处理器或输 入/输出端口，以上各者都被集成到单一芯片中。使SoC的各个组件进行通信的一种方法是使 用片上网络（on-chip network，有时称作network-on-chip）。片上网络意图取代在复杂系统中 的电子组件之间进行通信的传统方法，例如，传统总线和纵横制互联。

已针对片上网络考虑了多种拓扑，且由于可采用的路由器相对较简单，因此有时使用 环形网拓扑。例如，在单向环形网络中，每个路由器包括两个端口：一个输入端口，用于接 收来自第一邻近路由器的数据；以及一个输出端口，用于将数据发射至第二邻近路由器。这 些路由器占用的面积较小，消耗的功率较小，且与较高基数的片上路由器，例如，网状网络 中的路由器相比，可在较高频率下被计时。然而，环形网络不能很好地随路由器数目的增加 而增大。这是因为平均和最坏情况的包带宽随路由器的数目线性增大。网络时延对许多SoC 应用来说可能至关重要，所述SoC应用要求超低时延通信且在严格控制功率预算的情况下进 行操作。

发明内容

本文中揭示了包括芯片的一种设备，所述芯片包括多个节点、在具有第一拓扑的第一 环形网络中使所述多个节点连接的第一多个链路以及在具有第二拓扑的第二环形网络中使所 述多个节点连接的第二多个链路，其中第一拓扑不同于第二拓扑。

本文中还揭示了一种方法，所述方法包括：在第一节点处确定，来自使多个节点互联 的多个环形网络的第一环形网络含有从第一节点到第二节点的最短路径；以及通过第一环形 网络将第一微片从第一节点发射至第二节点，其中所述多个节点包括第一节点和第二节点， 且其中环形网络关于彼此是非对称的。

本文中还揭示了一种包括芯片的设备，所述芯片包括多个节点、在第一环形网络中使 所述多个节点连接的第一多个链路以及在第二环形网络中使所述多个节点连接的第二多个链 路，其中所述多个节点中的第一节点用于确定第一环形网络与第二环形网络中哪个环形网络 包含从第一节点到第二节点的最短路径，以及根据所述确定通过第一环形网络或第二环形网 络选择性地发射第一微片，其中第一环形网络与第二环形网络形成非对称环形网络。

根据结合附图和所附权利要求书进行的以下详细描述，将更清楚地理解这些和其它特 征。

附图说明

为了更完整地理解本发明，现参考以下结合附图和详细描述进行的简要描述，其中相 同参考数字表示相同部分。

图1是片上系统的一个实施例的示意图。

图2A、2B、2C和2D是在不同环形网络中互联的十六个节点的实施例的示意图。

图3是非对称环形网络的一个实施例的示意图。

图4是非对称环形网络中的微片路由方法的一个实施例的流程图。

具体实施方式

9.[0015]首先应理解，尽管下文提供了一个或多个实施例的说明性实施方案，但可使 用许多种技术，不管是当前已知的还是现有的，来实施所揭示的系统和/或方法。本发明 决不应限于下文所说明的说明性实施方案、图式和技术，包含本文中所说明并描述的示 例性设计和实施方案，而是可在所附权利要求书的范围以及其等同物的完整范围之内进 行修改。

10.[0016]本文揭示了非对称环形网拓扑以及在非对称环形网拓扑中进行路由的方法。 非对称环形网拓扑，也称作非对称环形网络，使用超过两个环形网，所述环形网通过给 定组的节点以非对称形式进行路由，从而使得给定组的节点可按照不同次序进行连接， 形成包括不同环形网络的网络。非对称环形网络可兼备传统环形网络的优势，同时，与 传统环形网络相比，可产生减少的时延和较高的吞吐量，因此能改进系统性能。非对称 环形网络对片上网络来说可能是有吸引力的。

片上网络可用于在位于单个芯片中的各个组件之间提供通信能力。图1是具有片上网 络112的片上系统（SoC）100的一个实施例的示意图。具体来说，SoC100包括片上网络112， 所述片上网络112包括多个节点116。片上网络112可用于在组件118、120、122和124之间 经由节点116提供通信能力，其中，片上网络112以及组件118、120、122和124位于单个 芯片110上。虽然图1中图示了四个组件118、120、122和124，但是应了解，片上网络112 可使任意数目个和/或任意类型的组件118、120、122和124连接。此外，虽然图1绘示了四 个节点116，但是片上网络112可包括任意数目个链路114和节点116。

片上网络112中的链路114和节点116可布置在任何拓扑中。例如，如图1中所示， 链路114和节点116可布置在环形网拓扑中，所述环形网拓扑也可称作环形网络。环形网络 可指特定的网络拓扑，在所述网络拓扑中，每个节点连接至刚好两个其它节点。根据另一个 实例，链路114和节点116可布置在网状拓扑中，所述网状拓扑也可称作网状网络。网状网 络可指特定的网络拓扑，在所述网络拓扑中，一个或多个节点直接连接至超过两个其它节点。

链路114可以是在各节点116之间和/或组件118、120、122与124之间传送微片的 任何装置。链路114通常是电学链路，但可以是光学或无线链路。虽然链路114一般是双向 的，但链路114也可以是单向的。例如，通过将可用链路114资源（例如，时间和/或频率） 分割成传送所述微片的多个缝隙（例如，时隙和/或频隙），可将至少一些链路114划分成多 个虚拟信道。虚拟信道可在仅仅两个邻近节点之间延伸，或者可延伸经过多个节点。

节点116可以是在片上网络112之内促进微片的路由的任何装置。如果未通过组件 118、120、122和124使传入包（例如，互联网协议（IP）包或以太网帧）分裂成称作流量控 制数字或微片的信息的单元，则可由至少一些所述节点进行此操作；并且/或者如果未通过组 件118、120、122和124使所述微片重新组合成传出包，则可由所述节点中的至少一些节点 进行此操作。另外，节点116可执行微片路由，方式为：节点116接收微片并在多个虚拟信 道中确定发射微片所处的信道并/或在多个路由中确定发射微片所处的路由。以类似方式，节 点116可执行包路由，方式为：节点116接收包并在多个虚拟信道中确定发射包所处的信道 并/或在多个路由中确定发射包所处的路由。作为路由的部分，节点116可对竞争公共资源（例 如，链路114中的虚拟信道）的两个微片或多个微片进行仲裁。

为执行节点116的多种功能，每个节点116可包含与存储器进行通信的处理器，所述 存储器是，例如，只读存储器（ROM）、随机存取存储器（RAM）或任何其它类型的存储器。 每个处理器可以是通用处理器或者可以是专用处理器。或者，至少一些节点116可以不实施 成具有本地存储器，但可访问可能位于SoC100的另一部分上且可能由其它节点116共享的 外部存储器。最后，至少一些节点116可以实施成没有本地存储器，也不能访问存储器。

双向环形网络，例如图1中所示，可作为两个单向环形网络来实施，所述两个单向环 形网络使节点以相同的次序进行连接但在相反方向上发射微片。对于双向环形网络，每个节 点116可包括两个路由器，组成双向环形网络的每个单向环形网络使用一个路由器。每个路 由器可包括一个输入端口和一个输出端口，并且，由于这种路由器的实施相对较简单，因此 每个路由器可在高频率下计时。

如上文所述，通过对IP包或以太网帧等进入片上网络的包进行分割，可形成微片。 进入片上网络的微片也可称作是注入片上网络。请参阅作为示例性实例的图1，组件122等 组件可将包发射至对应节点116。微片进入片上网络时所处的节点可称作源或源节点，微片 离开片上网络时所处的节点可称作目标或目标节点。

节点116可用于接收包并将包分割成信息的较小单元。或者，122等组件可将包分割 成较小单元。信息的每个单元可放置在微片中。可以存在不同类型的微片，例如，头微片、 体微片和尾微片。分割成较小单元的包可分布在一个头微片、一个或多个体微片以及一个尾 微片上，且当这些微片在芯片110上被路由和/或处理时，这些微片可维持指定次序（例如， 首先是头微片，随后是体微片，然后是尾微片）。头微片可用于为对应于包的一系列微片获得 片上网络中的资源，而尾微片可用于释放资源。头微片还可包括包的头部（例如，包的目标 地址、源地址等），且可含有一些包负载，但是体微片和尾微片一般不含有包的头部中的任何 部分。在包的头部特别长的情况下，包的头部可包含在头微片和一些体微片中，但不包含在 其余体微片或尾微片中。用于将信息指配给微片的任何方案都在本申请案的范围之内。此外， 除微片之外或者取代微片，发射和接收包的片上网络也在本申请案的范围之内。为方便起见， 本申请案的剩余部分针对微片进行描述，但本申请案也可适用于包。

组件118、120、122和124可以是处理微片的任何类型的装置。一般来说，组件118、 120、122和124可以是能执行比节点所执行的功能更为专业的某种功能的装置。例如，组件 118、120、122和124可包含存储器、处理器、入端口或出端口等输入/输出（I/O）装置或任 何其它电子组件。虽然节点116可包括处理器和/或存储器，但是组件118、120、122和124 中的处理器和/或存储器的容量和/或吞吐量通常远超过节点116中的处理器和/或存储器的容 量和/或吞吐量，因此，对于节点116来说，执行由组件118、120、122和124执行的功能是 不可能或不实际的。在组件118、120、122和124中的一个组件是入端口的情况下，所述未 通过节点116从传入包（例如，IP包或以太网帧）除去协议层并/或使传入包分裂成微片，则 可由该入端口组件来进行此操作。在组件118、120、122和124中的一个组件是出端口的情 况下，如果未通过节点116使所述微片重新组合成传出包（例如，IP包或以太网帧），并/或 将协议层添加到传出包，则可由该出端口组件来进行此操作。

片上网络中的节点可按照不同次序进行互联，从而得到具有不同拓扑的多个不同环形 网络。图2A、2B、2C和2D是以四种不同次序进行互联而得到四个不同环形网络的十六个 节点的实施例的示意图。所述节点中的四个节点表示为210、212、214和216。图2A至2D 仅图示了十六个节点可互联成双向环形网络的可能的方式中的四种方式。请注意，图2A至 2C可描述成不同定向的“U形”环形网络。即，图2A可描述成倒立的U形，图2B可描述 成U形，图2C可描述成侧向一边的U形。此外，图2D可描述成“H形”。对于十六个节点 双向环形网络，可存在其它可能的形状，例如，侧向一边的H形或镜像的侧向一边的U形。 [0027]多个节点使用第一多个链路可互联成第一环形网络，使用第二多个链路可互联成第二 环形网络。在第一和第二环形网络中，节点可按照不同次序进行互联，从而形成非对称环形 网络。以不同次序进行互联并不能代表以相反的方向进行互联。例如，以相同的次序但以相 反的方向连接到相同节点的两个单向网络（即，双向环形网络）不能视作是非对称网络。再 举例来说，图3中绘示了包含十六个节点的非对称环形网络300的一个实施例的示意图。非 对称环形网络300可以视作是包含两个双向环形网络——用实线双向链路表示的第一双向环 形网络以及用虚线双向链路表示的第二双向环形网络。用实线链路表示的双向环形网络对应 于图2A中的双向环形网络，用虚线链路表示的双向环形网络对应于图2B中的双向环形网络。 虽然图3中绘示成包含两个双向环形网络，但是非对称环形网络不限于两个双向环形网络。 非对称环形网络可包括任何数目个单向和/或双向环形网络。例如，图3中的十六个节点也可 互联成具有四个环形网络的非对称环形网络，所述四个环形网络中的每个网络分别如图2A 至2D中所示进行配置。此外，非对称环形网络可包含任意数目个节点。

非对称网络300的实施例中的每个节点可包括处理器和四个路由器，两个双向网络中 的每个双向网络的两个方向中的每个方向使用一个路由器。所述路由器可以是在单向环形网 络中使用的简单的双端口路由器。例如，在节点210中，可存在：从节点212接收并以节点 214为目标（通过用实线链路表示的网络）的业务所用的一个双端口路由器；从节点214接 收并以节点212为目标（通过用实线链路表示的网络）的业务所用的一个双端口路由器；从 节点214接收并以节点216为目标（通过用虚线链路表示的网络）的业务所用的一个双端口 路由器；以及从节点216接收并以节点214为目标（通过用虚线链路表示的网络）的业务所 用的一个双端口路由器。一般来说，对于具有n个双向环形网的非对称网络，每个节点可包 括一个处理器和2n个双端口路由器。或者，非对称网络300中的每个节点可包括一个处理器 和两个路由器。路由器可以是四端口路由器，所述四端口路由器具有用于在双向环形网络中 对业务进行路由的两个输入端口和两个输出端口。一般来说，对于具有n个双向环形网的非 对称网络，每个节点可包括一个处理器和n个四端口路由器。在一些情况下，路由器还可具 有一端口，所述端口到达该节点处的处理器。

图4所示为非对称环形网络中的微片路由方法400的一个实施例的流程图。所有步骤 都可以在片上网络中的节点中执行。所述非对称环形网络可包括n个单向环形网。如果n是 偶数，则这样一个实施方案可当做n/2个双向环形网。路由指配触发事件发生在步骤410中。 路由指配触发事件是指将微片指配给非对称环形网络中的环形网中的一个环形网的事件。路 由指配触发事件可以是指微片在一个节点处进入片上网络，其中，微片的进入可定义成一个 时刻，在所述时刻，在片上网络中的节点中的输入端口处从SoC中的组件接收到一个微片， 或者在所述时刻，一个微片首先进入片上网络中的节点中的队列。

在步骤410中的路由指配触发事件发生之后，在步骤412中确定n个环形网中的每个 环形网中到达微片的目标节点的最短路径。例如，假定微片在节点214处进入图3中的非对 称环形网络300，且所述微片以节点216为目标。从任一节点到任一其它节点存在四条可能 的路径，两个双向环形网中的每个双向环形网使用两条路径。如果使用虚线链路表示的环形 网络，则从节点214到节点216的最短路径的长度是两次跳跃，而如果使用实线链路表示的 环形网络，则从节点214到节点216的最短路径的长度是六次跳跃。因此，从节点214到节 点216的最短路径是在用虚线链路表示的环形网络中，且经由节点210。

接下来，在步骤414中，所述微片指配给对应于最短路径的环形网。通过使用上文中 来自图3的实例，节点214处的微片指配给用虚线链路表示的双向环形网。如果使用两个单 向环形网来构造所述双向环形网，则所述微片进一步指配给在节点210的方向上的单向环形 网。最后，在步骤416中，将所述微片发射至对应于最短路径的环形网上的下一个节点。通 过使用上文中的实例，将微片从节点214发射至节点210。

一旦微片指配给了一个环形网并通过该环形网被发射出去，那么，当所述微片横穿所 述网络时，就不需要在任何其它节点处为所述微片再次执行流程图400中的步骤。通过使用 简单的双端口路由器可实现从一个节点到另一个节点的微片的路由。

通过与传统环形网络和更为复杂的网状网络的时延和带宽进行比较，可证明非对称环 形网络的一些优势。图3中的“双U”形非对称环形网络与图2A或2B中的单U形网络以及 与网状网络的比较在表1中呈现。请注意，单U形网络也可视作传统环形网络。在此上下文 中，网状网络可以是：在所述网络中，十六个节点中的每个节点经由双向链路连接至该节点 以北、以南、以东和以西的相邻节点。例如，如果图3中的十六个节点在网状网络中进行连 接，则节点210可连接至节点216、212、214以及位于210左侧的无标记节点。所述表格的 一个假设是，每个双向链路在每个方向上的宽度是W个位。另一个假设是，在每个网络中采 用从源到目标的最短路径路由。例如，通过使用如之前所述的图4中的微片路由方法400的 实施例，可在非对称环形网络中完成最短路径路由。平分带宽可以是系统吞吐量的度量，且 在传统上，平分带宽可以定义成可在网络被切分成两半的情况下切分的单向链路的最小数目。 或者，平分带宽可定义成网络的两个相等部分之间的最小带宽。

表1：图3中的非对称环形网与其它网络拓扑的比较

参阅表1，虽然所有拓扑可具有相同的平分带宽，但是，与传统环形网络相比，图3 中的双U形网络具有实质上较低的平均和最长时延。此外，网状网络可仅具有比双U形网络 低14%的平均跳跃计数，但代价是复杂性高出很多。因此，双U形网络可在性能与复杂性之 间提供令人满意的折衷方案。

揭示至少一个实施例，且所属领域的一般技术人员对所述实施例和/或所述实施例的 特征进行的改变、组合和/或修改在本发明的范围之内。因组合、集成和/或省略所述实施例的 特征而产生的替代性实施例也在本发明的范围之内。在明确陈述了数值范围或限制的情况下， 应将这些明确的范围或限制理解成包含属于明确陈述的范围或限制的类似量值的重复范围或 限制（例如，从约1到约10包含2、3、4等；大于0.10包含0.11、0.12、0.13等）。例如， 每当揭示下限为R_l且上限为R_u的数值范围时，都特别地揭示属于所述范围的任何数字。具 体来说，特别揭示所述范围之内的以下数字：R=R_l+k*(R_u-R_l)，其中k是以1%的增量从 1%变化至100%的变量，即，k是1%、2%、3%、4%、5%、…、50%、51%、52%、…、95%、 96%、97%、98%、99%或100%。此外，还特别地揭示由如上文所述的两个R数字界定的任 何数值范围。关于权利要求中的任一要素，使用术语“可选择地（optionally）”意味着需要所 述要素，或者，不需要所述要素，两种选择均在所述权利要求的范围之内。使用包括、包含 和具有等较广术语应理解成对由……组成、基本上由……组成以及实质上由……组成等较窄 术语提供支持。因此，保护范围不受上文所陈述的描述限制，而是由所附权利要求书进行界 定，该范围包含权利要求书的标的物的所有等同物。每项和全部权利要求作为进一步的揭示 内容并入说明书中，且权利要求书是本发明的实施例。揭示内容中的参考的论述并不是承认 其为现有技术，尤其是公开日期在本申请案的在先申请优先权日期之后的任何参考。在本发 明中引用的所有专利、专利申请案和公开案的揭示内容以引用的方式并入本文中，从而为本 发明提供示例性、程序性或其它具体细节的补充。

虽然本发明中提供了若干实施例，但应理解，在不脱离本发明的精神或范围的情况下， 所揭示的系统和方法可用许多其它特定形式来体现。本发明的实例应被视为说明性的而非限 制性的，且本发明不限于本文中给出的具体细节。例如，各种元件或组件可在另一系统中进 行组合或集成，或者某些特征可省略或不实施。

另外，在不脱离本发明的范围的情况下，各种实施例中描述并说明为离散或单独的技 术、系统、子系统和方法可与其它系统、模块、技术或方法组合或集成。展示或论述为彼此 耦合或直接耦合或通信的其它项目也可用电方式、机械方式或其它方式通过某一接口、装置 或中间组件间接耦合或通信。改变、替代和更改的其它实例可由所属领域的技术人员确定， 且可在不脱离本文中揭示的精神和范围的情况下进行所述改变、替代和更改。