用于利用自适应路由来控制资源利用的机制

摘要

描述了涉及用于利用自适应路由来控制资源利用的技术的方法和设备。在一个实施例中，在路由逻辑中，确定用于传输将在输入端口处被接收的传入消息的输出端口。所述路由逻辑将基于在通信地耦合到所述路由逻辑的一个或多个其他路由逻辑中检测到的拥塞信息，从第一输出端口和第二输出端口中选择所述输出端口。所述第一输出端口将为所述传入消息提供确定性路由，所述第二输出端口将为所述传入消息提供自适应路由。还公开了其他实施例。

说明书

领域

本发明一般涉及电子器件领域。更具体而言，本发明的实施例涉及用 于利用自适应路由来控制资源利用的技术。

附图简述

参考附图提供了下列详细描述在附图中，附图标记中最左边的数字标 识该附图标记首次出现的附图。在不同附图中使用相同的附图标记指示相 似或相同的项。

图1示出了可以用来实现此处所讨论的各实施例的计算系统的实施例 的框图。

图2示出了可以用来实现此处所讨论的一个或多个实施例的计算系统 的实施例的框图。

图3示出了可以用于此处所讨论的一个或多个实施例中的路由逻辑的 框图。

图4示出了根据一实施例的路由功能的框图。

图5示出了根据一实施例的路由逻辑的输入端口的虚拟信道中的逻辑 划分。

图6示出了根据一实施例的对头部flits执行的方法的流程图。

图7示出了根据一实施例的用于检查拥塞的方法的流程图。

图8示出了根据一实施例的用于选择输出端口的方法的流程图。

图9示出了可以用来实现此处所讨论的一个或多个实施例的计算系统 的实施例的框图。

图10示出了可以用来实现此处所讨论的一个或多个实施例的计算系 统的实施例的框图。

详细描述

在下面的描述中，阐述了很多具体细节，以便全面地理解各实施例。 然而，在没有这些具体细节的情况下，也可实践一些实施例。在其他情况 下，没有详细描述已知的方法、过程、组件、和电路以便不至于不必要地 使特定实施例变得模糊。本发明的各实施例的各方面可以使用各种装置， 诸如半导体集成电路(“硬件”)、组织成一个或多个程序的计算机可读 指令(“软件”)，硬件和软件的某种组合，来执行。为本发明，对“逻 辑”的引用应该是指硬件、软件，或者其某种组合。

当设计网络系统时，一些主要考虑是最小化面积和功率耗散。这样的 局限性强制了对拓扑、切换策略、路由功能和架构实现的某些选择。平衡 这些选择进而对网络系统在速度、功率消耗，等等方面有多好地操作具有 直接影响。

一些实施例涉及用于利用自适应路由来控制资源利用的技术(也可以 被称为拥塞知晓的适应性阈值或CAAT)。在一个实施例中，在路由逻辑 (例如，参考图1-10所讨论的逻辑150)处确定用于传输传入消息(其将 在输入端口处被接收)的输出端口。所述路由逻辑将基于在通信地耦合到 所述路由逻辑的一个或多个其他路由逻辑处检测到的拥塞信息，来从第一 输出端口和第二输出端口中选择输出端口。所述第一输出端口将为所述传 入消息提供确定性路由，所述第二输出端口将为所述传入消息提供自适应 路由。

各种计算系统可以被用来实现此处所讨论的各实施例，诸如参考图1-2 和9-10所讨论的系统。更具体而言，图1示出了根据本发明的一个实施例 的计算系统100的框图。系统100可包括一个或多个代理102-1到102-M (此处统称为“代理102”或更一般的“代理102”)。在一个实施例中， 代理102中的一个或多个可以是诸如参考图9-10所讨论的计算系统之类的 计算系统的组件中的任何一个。

如图1所示，代理102可以通过网络结构(networkfabric)104进行通 信。在一个实施例中，网络结构104可包括允许各种代理(诸如计算设备) 传递数据的计算机网络。在一个实施例中，网络结构104可包括通过串行 (例如，点对点)链路和/或共享通信网络(在一个实施例中，可被配置成 环形)进行通信的一个或多个互连(或互连网络)。例如，一些实施例可 以助益允许与完全缓冲双列直插式存储器模块(FBD)进行通信的链路上 的组件调试或验证，例如，在FBD链路是用于将存储器模块耦合到主机控 制器设备(诸如处理器或存储器中枢)的串行链路的情况下。调试信息可 以从FBD通道主机传输，以便可以通过通道流量跟踪捕捉工具(诸如一个 或多个逻辑分析仪)沿着通道观察到调试信息。

在一个实施例中，系统100可以支持分层协议方案，该方案可包括物 理层、链路层、路由层、传输层，和/或协议层。结构104还可以进一步促 进从一个协议(例如，缓存处理器或缓存知晓存储器控制器)到用于点对 点或共享网络的另一个协议的数据传输(例如，以分组的形式)。在某些 实施例中，网络结构104还可以提供遵循一个或多个缓存一致性协议的通 信。

进一步地，如图1中的箭头方向所示，代理102可以通过网络结构104 传输和/或接收数据。因此，某些代理可以使用单向链路，而其他代理可以 使用双向链路来进行通信。例如，一个或多个代理(诸如代理102-M)可 以传输数据(例如，通过单向链路106)，其他代理(诸如代理102-2)可 以接收数据(例如，通过单向链路108)，而某些代理(诸如代理102-1) 可以传输与接收数据(例如，通过双向链路110)。

另外，代理102中的至少一个可以是归属代理，并且代理102中的一 个或多个可以是请求或缓存代理。一般而言，请求/缓存代理向归属节点/ 代理发送对对应的“归属代理”与其相关联的存储器地址的访问的请求。 进一步，在一个实施例中，代理102中的一个或多个(只示出了一个，代 理102-1)可以访问诸如存储器120之类的存储器(该存储器可以专用于代 理或与其他代理共享)。在某些实施例中，代理102中的每一个(或者至 少一个)可以耦合到存储器120，该存储器120要么与代理在同一个管芯上， 要么以别的方式可被代理访问。如图1所示，网络结构104可包括一个或 多个路由逻辑150，以耦合两个代理，以允许代理间的通信。此外，在一个 实施例中，非常薄的硬件网络接口将每个代理102耦合到一个或多个路由 逻辑150。薄的硬件网络接口可以类似于但是互补于下面所描述的Y单元 (Yunit)和垫片(Shim)硬件块。

图2是根据一实施例的计算系统200的框图。系统200包括多个插槽 202-208(示出了四个，但是一些实施例可以具有更多或更少插槽)。每一 个插槽都包括处理器。而且，系统200中的各个代理还可以通过路由逻辑 150进行通信。尽管路由逻辑150只被示为耦合202-208，但是，路由逻辑 150可以耦合系统200中的其他代理。此外，取决于实现，在系统中可以存 在更多或更少的路由逻辑块。另外，每一个插槽都通过点对点(PtP)链路， 或差分互连，诸如快速路径互连(QPI)，MIPI(移动行业处理器接口)， 等等，耦合到其他插槽。如参考图1的网络结构104所讨论的，每一个插 槽都耦合到系统存储器的本地部分，例如，通过包括动态随机存取存储器 (DRAM)的多个双列直插存储器模块(DIMM)形成的。

在另一个实施例中，网络结构可以用于任何片上系统(SoC或SOC) 应用，使用自定义或标准接口，诸如，用于AMBA(高级微控制器总线体 系结构)、OCP(开放内核协议)、MIPI(移动行业处理器接口)、PCI (外围组件互连)或PCIe(外围组件互连快速)的ARM兼容的接口。

一些实施例使用允许在基于PC(个人计算机)的系统(诸如基于PCI 的系统)使用异构资源而无需对IP资源本身作出任何更改的技术，诸如 AXI/OCP技术。一些实施例提供两个非常薄的硬件块(此处称为Y单元和 垫片)，它们可以被用来将AXI/OCPIP插入到自动生成的互连结构中，以 创建PCI兼容系统。在一个实施例中，Y单元的第一(例如，北)接口连 接到适配器块，该适配器块接口至PCI兼容总线，诸如直接媒体接口(DMI) 总线，PCI总线，或外围组件互连快速(PCIe)总线。第二(例如，南)接 口直接连接到非PC互连，诸如AXI/OCP互连。在各实现中，此总线可以 是OCP总线。

在某些实施例中，Y单元通过将PCI配置周期转换为目标IP能够理解 的事务，来实现PCI枚举。此单元还执行从可重新定位的PCI地址到固定 的AXI/OCP地址以及相反的地址转换。Y单元还可以进一步实现一种排序 机制，用以满足生产者-消费者模型(例如，PCI生产者-消费者模型)。单 个IP又通过专用PCI垫片，连接到互连。每一垫片都可以为对应的IP实 现整个PCI头部。Y单元将对PCI头部和设备存储器空间的所有访问路由 到垫片。垫片消耗所有头部读/写事务，并将其他事务传递到IP。在某些实 施例中，垫片还为IP实现所有功率管理相关特征。

如此，并非是单块兼容性块，实现Y单元的一些实施例采取分布式方 法。在Y单元中实现了跨所有IP共同的功能，例如，地址转换和排序，而 在垫片中实现针对IP定制的诸如功率管理、错误处理等等之类的IP专用功 能。

如此，可以利用对Y单元的最小的更改，添加新IP。例如，在一种实 现中，可以通过在地址重定向表中添加新条目，来进行更改。尽管垫片是 IP专用的，但是，在某些实现中，大量的功能(例如，多于90％)是跨所 有IP共同的。这允许新IP的现有垫片的快速重新配置。如此，一些实施例 还允许在没有修改的情况下使用自动生成的互连结构。在点对点总线体系 结构中，设计互连结构是一项具有挑战性的任务。上文所描述的Y单元方 法利用最小的努力将行业生态系统贯彻到PCI系统中，而不要求对行业标 准工具的任何修改。

如图2所示，每一个插槽都耦合到存储器控制器(MC/归属代理(HA) (诸如MC0/HA0到MC3/HA3)。存储器控制器耦合到对应的本地存储器 (被标记为MEM0到MEM3)，本地存储器可以是系统存储器(诸如图9 的存储器912)的一部分。在某些实施例中，存储器控制器(MC)/归属代 理(HA)(诸如MC0/HA0到MC3/HA3)可以与图1的代理102-1相同或 类似，被标记为MEM0到MEM3的存储器可以与参考此处的图形中的任何 一个所讨论的存储器设备相同或类似。在一个实施例中，MEM0到MEM3 也可以被配置成镜像数据，例如，作为主和从。在某些实施例中，系统200 中的一个或多个组件也可以被包括在同一个集成电路管芯中。

进一步地，一种实现(诸如在图2中所示出的)用于带有镜像的插槽 无粘接(socketglueless)配置。例如，分配给存储器控制器(诸如MC0/HA0) 的数据通过PtP链路被镜像到另一个存储器控制器(诸如MC3/HA3)。

一般而言，当设计网络系统时，一些主要考虑是最小化面积和功率耗 散。这样的局限性强制了对拓扑、交换策略、路由功能和架构实现的某些 选择。此外，网络设计可以使用互连在一起的多个路由器(诸如路由逻辑 150)，以满足特定系统的带宽要求。

图3示出了可以用于一些实施例中的路由逻辑的架构。一个或多个链 路控制器(“LC”，未示出)用于协调(此处也可互换地称为分组)跨两 个相邻交换机的物理链路的消息流。缓冲区(诸如输入缓冲区302和输出 缓冲区304)存储跨路由逻辑150传输的消息。路由单元逻辑306通过为输 入端口310中的传入分组选择输出端口308，来实现路由功能。交叉开关单 元逻辑312将交换机输入缓冲区302连接到交换机输出缓冲区304。调度器 单元逻辑314(例如，同步地)通过将输出端口可用性与来源于位于输入端 口中的消息的请求进行匹配，来在每个周期配置交叉开关单元逻辑312。路 由单元逻辑306是驱动网络的最终性能的最重要的参数之一。设计路由单 元对于带有多个虚拟信道的无损网络而言是具有挑战性的，因为它需要争 取获得网络的最大潜力(即，在实现高带宽和低延迟的同时，消耗低功率)， 同时使网络保持完全连接，并免受死锁、活锁等等的危险。消息一般在头 部flit中携带目的地地址。对于通过特定输入端口(例如，S)到达路由逻 辑150的每个头部flit，检测目的地地址(例如，D)，并选择所有可能的 输出端口(例如，P)。在某些实施例中，使用基于表的方法，该方法存储 可以用于每一个目的地节点的输出端口。在其他实施例中，使用基于最小 路径分布式路由方案，该方案存储可以用于每一个目的地节点的输出端口。 后一种方法可以使用最小的逻辑并允许使用不同的路由算法，并将交换机 中的昂贵的路由表(就能量消耗和面积而言)替换为快速并高效的逻辑块 组。

图4示出了根据一实施例的路由功能的主要组件的框图。在一个实施 例中，路由功能通过图3的路由单元逻辑306来实现。如图4所示，当设 计路由功能时，有两个主要组件要考虑，高效并且有效的路由框架的设计 以及对路由算法的选择以及与它相关联的选择功能。

一般而言，路由算法规定网络上的分组所使用的路径。设计人员面临 着设计提供尽可能最低的通信延迟、尽可能高效地使用内部带宽，以及甚 至，当发生拥塞或检测到瓶颈时修改流量的路由算法的问题。路由算法可 以被分为三个不同的类别：确定性的，自适应的，以及不在意的(oblivious)。

确定性路由算法始终为源-目的地节点对选择相同路径。确定性的方法 的主要优点之一是其简单性，延迟可预测性以及分组的有序到达的维持。 然而，确定性路由可能会导致网络资源的低效使用，因为它始终为每个源 以及目的地对提供相同路径。如此，使用确定性路由算法的网络不能动态 地对由于吞吐量退化导致的网络拥塞或瓶颈作出响应。

另一方面，不在意的路由考虑与相同源-目的地节点对不同的路径，但 是，在源节点中，在对当前网络负载没有任何了解的情况下选择路径。

其他备选方案是使用其中分组采取不同的路径的自适应路由。然而， 取决于当前流量条件，在网络内决定轮次；如此，通过使用替代的路由路 径，避免网络中的竞争。这在低和中等流量状况下导致更高的吞吐量以及 资源利用。令人遗憾的是，当存在高负载或瓶颈时，自适应路由具有跨网 络轻松地分散拥塞的倾向，当存在这样的状况时导致吞吐量的显著的丧失。

此外，自适应路由机制还带有两个不同的功能：路由和选择。如图4 所示，根据一实施例，路由功能提供一组输出通道，这些输出通道在节点 之间提供死锁自由度和完全连通性。选择功能负责基于从其他节点收集到 的关于流量状况的信息，只选择所有可能的选项之中的一个选项。

设计人员通常使用用于支持确定性路由算法(诸如维序路由(DOR)， 其中，分组首先在水平维度被路由，然后在垂直维度被路由)的有限态机 器，来实现简单路由框架。用于实现分布式路由的另一方法使用存储应该 用于每一目的地节点的输出端口的表。此方法的主要优点是，相同的通用 设计可以反复用于实现任何网络拓扑和路由算法。主要挑战是设计高效(就 面积和能量而言)路由框架，该路由框架组合两种路由算法的优点，即， 在高负载状况下的确定性路由的延迟可预测性和由自适应路由方案所提供 的中等和低负载状况下的高资源利用。

一般而言，互连上的流量是指消息正在两个代理(诸如参考图1所讨 论的代理102)之间传输。这些消息可以作为多个flits来传输。“flit”(流 控制位(flowcontroldigit)的缩写)是流控制的最小的单位。消息一般由 多个flits构成。另外，在一个实施例中，“flit”还可包括80比特，例如， 8比特用于错误检测，8比特用于链路层头部，64比特用于数据，但是也可 以使用其他配置。路由器(例如，逻辑150)可以被设计为能支持多个虚拟 信道，以允许所有消息类型被映射到相同物理网络；如此，在任何时间和 在网络中的任何一点为给定流量混合提供可用带宽的最佳使用。

一个网络体系结构实施例使用虚拟信道流控制来实现对各种类型的确 定性的，容错的，以及自适应路由中的无死锁路由的支持。而且，尽管缓 冲区是每个微片地分配的，但是虚拟信道(VC)是在分组级别分配的。在 一个实施例中(诸如图5所示出的)，虚拟信道(VC)的组被灵活地分为 两个逻辑组：路由VC(例如，VC0-VC3)以及性能VC(例如，VC4-VC9)。

路由VC可以用于满足所使用的特定完全路由算法的死锁-自由度要 求。在此情况下，路由VC提供支持无死锁路由算法所需的逃逸(escape) 资源。它们还用于在各消息类别之间提供将确保带有死锁自由度的协议的 流量分隔。为此，实施例实现至少与存在于协议中的消息类别一样多的路 由VC，只让属于正确的消息类别的分组使用分配给该消息类别的路由VC。 此外，图5还示出了根据实施例的路由器的输入端口的十个虚拟信道中的 逻辑划分。VC中的四个(例如，VC0-VC3)是路由VC，其余六个(例如， VC4-VC9)属于性能VC类别。

在某些实施例中，支持无死锁的路由算法和协议流量分隔是指，为使 路由VC向另一个路由VC发送分组，它遵循下列规则：(a)目的地路由 VC位于“逃逸”端口中(如果要求死锁-自由度，对于相同消息类别，网 络中的路由VC之间依赖关系图不能呈现周期)；和/或(b)目的地路由 VC消息类别匹配(协议流量分隔)。

每一路由VC都可以具有其自己的预留的用于接收flit的信用(确保如 果路由VC不在使用中，那么，它至少为一个flit提供空间)。性能VC可 以属于用于性能改善的VC的公用的共享的池(例如，对于自适应或确定 性路由方案两者)。性能VC由于它们的消息类别亲缘关系，可以形成可 被任何分组使用而不会有任何限制的虚拟信道的池。与路由VC相反，性 能VC可能没有任何预留的信用，如此，任何潜在的传入分组都必须借助 于共享信用池来检查是否有空间。

一旦带有所需路由信息的头部flit到达输入端口，它就试图访问耦合到 后面的下游路由逻辑的对应的输出端口。如果不是这样，它需要检查那里 的资源((包括缓冲区空间和空闲VC可用性)。

在某些实施例中，当请求下一路由器的输入端口处的空闲VC时，使 用优先级排序，通过如下：

(a)首先，检查空闲性能VC和信用可用性(后者不由前者确保)。 如果两个条件都被满足，那么，准备这样的对交换机分配流水线的请求。

(b)否则，检查是否有属于分组的消息类别的空闲路由VC。如果发 现，那么，准备这样的对交换机分配流水线的请求。

在一个实施例中，每个分组地分配虚拟信道。因此，只有当先前分组 的所有flits都已被逻辑150转发时，VC才可被重复使用。因此，一旦分组 的尾flit离开输入端口，那么，使VC可用于下一传入的分组。

图6示出了根据一实施例的在在输入端口处接收时对头部flits(消息 的第一flit)执行的方法的流程图。每当新消息头部到达交换机(例如，路 由逻辑150)时，都可以重复此方法。

参考图6，在操作602，一旦头部消息(例如，消息的第一flit)到达 输入端口，路由功能(例如，通过逻辑150)在操作604，基于底层路由算 法，收集关于所有可能的输出端口的信息。对于完全自适应路由和部分自适 应路由，寄存器输出_部分_0(output_port_0)存储逃逸路由的输出端口，而寄 存器输出_部分_1(output_port_1)存储提供自适应性的输出端口。同时(或 在操作604之后)，路由逻辑150可在操作606处(例如，持续地)更新关于 在近邻路由器(例如，接近另一逻辑150的逻辑150，其中接近指示经由一个 或多个其他逻辑150的通信能力)中检测到的任何拥塞的信息。基于此信息， 路由逻辑150在操作608选择关于两个可能的输出端口的适当的信息并对照可 配置参数(例如，UPPER_PERFVC(较高性能VC)、UPPER_CREDIT(较高信 用值)、LOWER_PERFVC(较低性能VC)、以及LOWER_CREDIT(较低信用 值))比较它们。可通过(例如，同时地)更新用于潜在输出端口的每一个的 拥塞标志寄存器来概括此例程。此外，选择功能负责基于在先前步骤期间更 新的拥塞标志寄存器以及输出端口处可用的VC的类型来选择最方便的输出端 口。一旦路由功能完成，可在交换机处更新分组上下文，并且分组继续进行 竞争跟随交换机流水线的适当的输出端口。

进一步地，路由算法负责提供一组输出端口(基于路由算法)，该一 组输出端口在节点之间提供死锁自由度和完全连通性。例如，在由路由算 法所提供的两个可能的输出端口之间，output_port_0被指定为向路由功能 提供确定性的端口。当处理完全自适应路由时，此端口是提供逃逸路由的 端口。另一方面，output_port_1被视为自适应选项，且此端口提供带有变 得自适应的能力的路由功能。在某些情况下，output_port_0可以是存在的 唯一选项(即，当只向一个维度路由时)，而在某些其他情况下，output_port_0 和output_port_1两者都可以存在。在后一种情况下，选择功能负责基于从 其他节点收集到的关于流量状况的信息，只选择所有可能的选项之中的一 个选项。

一个路由器实施例依赖于实现内容感知的自适应节制(CAAT)机制以 执行选择功能的路由框架。具体而言，在一个实施例中，一个完全自适应 路由算法将自适应输出端口的使用约束到已经使用了逃逸VC的那些消息。 另外，当拥塞出现在当前节点上时，CAAT机制约束自适应性的使用。如 此，在拥塞过程中，大多数流量遵循逃逸路径(确定性路线)，从而避免 拥塞跨整个网络的快速分散，以及当网络稳定时性能的不愉快的减弱。

图7示出了根据一实施例的用于检查拥塞的方法的流程图。更具体而 言，图7所示出的方法可以被用来执行图6的操作606。对于路由逻辑150 中的每一个输出端口，一个周期接一个周期地，重复此方法。例如，同时， 每个周期都更新有关在近邻路由器中可用的性能VC的数量(#perfVCs)和 共享信用的数量(#ShCred)的新信息。进一步，为了检测拥塞，CAAT依 赖于下列可配置参数UPPER_PERFVC、UPPER_CREDIT、 LOWER_PERFVC，以及LOWER_CREDIT。

在操作702中，拥塞标志(“congestion_flag”)被复位(例如，到0， 或另一个值，这取决于实现)。一些实施例使用两组可配置阈值。每一组 都包括若干个空闲性能VC(UPPER_PERFVC和LOWER_PERFVC)和空 闲共享信用(UPPER_CREDIT和LOWER_CREDIT)。例如，下阈值可以 被设置为2个性能VC和2个空闲共享信用，而上阈值可以被设置为5个 性能VC和5个空闲共享信用。利用此方法，显然，较低的参数 (LOWER_PERFVC，LOWER_CREDIT)的值越大，路由算法的行为变得 越确定。

对于路由逻辑150上的每一个输出端口，如果在操作704中端口上的 资源大于上阈值(例如，在性能VC的数量(#perfYCs)大于高性能VC (UPPER_PERFVC)并且共享信用的数量(#ShCred)大于高信用值 (UPPER_CREDIT)的情况下)，则在操作706中清除状态比特(例如， congestion_flag(拥塞_标志))。如果在操作708中，端口上的资源等于 或小于下阈值(例如，在性能VC的数量(#perfVCs)小于或等于低性能 VC(LOWER_PERFVC)或共享信用的数量(#ShCred)小于或等于下信用 值(LOWER_CREDIT)的情况下)，则在操作710中，状态比特(例如， congestion_flag)被设置为指示输出端口处于拥塞中。在操作712中，返回 状态比特(例如，congestion_flag)。完全自适应路由算法通过确保参数 LOWER_PERFVC比0大，来确保死锁自由度。这又确保输出端口1决不 会阻止逃逸路由(路由VC)。

在图8的下一流程图中示出了路由逻辑150中的选择功能(例如，图 6的操作608)。图8的方法检查在输出端口1(例如，其是指提供自适应 性的输出端口)中是否有拥塞存在，如果检测到，返回确定性的端口作为 获胜者，废弃路线上的任何可能的自适应性。因此，基于拥塞标志的值、 路由算法，以及在输出端口中可用的VC的类型(例如，优先权被给予性 能VC)。

更具体而言，在操作802中，输出端口1被设置为有效(valid)，其 拥塞标志被清除。操作804检测输出端口1处的拥塞标志的值。如果在操 作806存在拥塞，则在操作808，清除输出端口1有效性比特/标志；否则， 如果在操作810中输出端口1有效，在操作812中，返回输出端口1。如果 输出端口1在操作810中被判断为无效，则在操作812中返回输出端口0 而不是输出端口1。

相应地，此处所描述的CAAT机制在利用完全自适应路由来缩短分组 等待时间变化方面非常有效。具体而言，当使用带维度次序路由的完全自 适应路由算法作为逃逸路由时，CAAT机制可以有效地降低平均分组等待 时间的标准偏差的变化，而同时在网络处于拥塞中时将吞吐量维持在可接 受的水平。因此，CAAT允许基于网络的拥塞状况来审慎地在确定性和自 适应路由之间切换。

图9示出了计算系统900的实施例的框图。图1的代理102中的一个 或多个可以包括计算系统900的一个或多个组件。系统900的各种组件也 可包括如图9所示的路由逻辑150。然而，可以在系统900中的多个位置， 包括或排除所示出的那些，提供逻辑150。计算系统900可包括耦合到互连 网络(或总线)904的一个或多个中央处理单元(CPU)902(可以统称为 “处理器902”)。处理器902可以是任何类型的处理器，诸如通用处理器、 网络处理器(可以处理通过计算机网络905传递的数据)，等等(包括精 简指令集计算机(RISC)处理器或复杂指令集计算机(CISC))。此外， 处理器902还可以具有单核或多核设计。带有多核设计的处理器902可以 将不同类型的处理器核集成在同一个集成电路(IC)管芯上。带有多核设 计的处理器902还可以实现为对称的或不对称的多处理器。

处理器902可包括一个或多个高速缓存，在各实施例中，这些高速缓 存可以是专用的和/或被共享。一般而言，高速缓存存储对应于存储在别处 或较早的计算出的原始数据的数据。为降低存储器访问延迟，一旦数据被 存储在高速缓存中，可以通过访问缓存的副本而并非预取或重新计算原始 数据，来进行未来的使用。高速缓存可以是任何类型的高速缓存，诸如1 级(L1)高速缓存、2级(L2)高速缓存、3级(L3)、中级高速缓存、 末级高速缓存(LLC)，等等，用于存储被系统900的一个或多个组件使 用的电子数据(例如，包括指令)。另外，这样的高速缓存可以位于各种 位置(例如，在此处所讨论的计算系统的其他组件内，包括图1，2，9或 10的系统)。

芯片组906可以另外耦合到互连网络904。进一步，芯片组906可包 括图形存储器控制中枢(GMCH)908。GMCH908可包括耦合到存储器912 的存储器控制器910。存储器912可以存储数据，例如，包括由处理器902， 或与计算系统900的组件进行通信的任何其他设备执行的指令序列。在本 发明的一个实施例中，存储器912还可包括一个或多个易失性存储器设备， 诸如随机存取存储器(RAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、 静态RAM(同步RAM)，等等。还可以使用非易失性存储器，诸如硬盘。 额外的设备可以耦合到互连网络904，诸如多个处理器和/或多个系统存储 器。

GMCH908还可以包括耦合到显示设备916的图形接口914(例如，在 一个实施例中，通过图形加速器)。在一个实施例中，图形接口914可以 通过加速图形端口(AGP)耦合到显示设备916。在本发明的一个实施例中， 显示设备916(诸如平板显示器)可以耦合到图形接口914，通过，例如， 将存储在存储设备(诸如视频存储器或系统存储器(例如，存储器912)) 中的图像的数字表示转换为被显示器916解释和显示的显示信号的信号转 换器。

如图9所示，中枢接口918可以将GMCH908耦合到输入/输出控制中 枢(ICH)920。ICH920可以提供到耦合到计算系统900的输入/输出(I/O) 设备的接口。ICH920可以通过外围桥接器(或控制器)924，诸如可以与 PCIe规范兼容的外围组件互连(PCI)桥接器，通用串行总线(USB)控制 器，等等，耦合到总线922。桥接器924可以在处理器902和外围设备之间 提供数据路径。可以使用其他类型的拓扑。此外，多个总线还可以耦合到 ICH920，例如，通过多个桥接器或控制器。进一步，总线922可以包括其 他类型的总线系统和配置。此外，耦合到ICH920的其他外围设备可包括， 在本发明的各实施例中，集成驱动器电子电路(IDE)或小型计算机系统接 口(SCSI)硬盘驱动器、USB端口、键盘、鼠标、并行端口、串行端口、 软盘驱动器、数字输出支持(例如，数字视频接口(DVI))，等等。

总线922可以耦合到音频设备926、一个或多个磁盘驱动器928，以及 网络适配器/接口930(在一个实施例中，可以是NIC)。在一个实施例中， 网络适配器930或耦合到总线922的其他设备可以与芯片组906进行通信。 此外，在本发明的某些实施例中，各种组件(诸如网络适配器930)也可以 耦合到GMCH908。另外，处理器902和GMCH908还可以被组合成单个 芯片。在一个实施例中，可以在CPU902中的一个或多个中提供存储器控 制器410。进一步，在一个实施例中，GMCH908和ICH920可以合并成外 围控制中枢(PCH)。

另外，计算系统900可包括易失性和/或非易失性存储器。例如，非易 失性存储器可包括下列各项中的一项或多项：只读存储器(ROM)、可编 程ROM(PROM)、可擦PROM(EPROM)、电EPROM(EEPROM)、 磁盘驱动器(例如，928)、软盘、光盘ROM(CD-ROM)、数字多功能 盘(DVD)、闪存、磁光盘，或能够存储电子数据(例如，包括指令)的 其他类型的非易失性机器可读取的介质。

在一个实施例中，存储器912可包括下列各项中的一项或多项：操作 系统(O/S)932、应用程序434，目录901，和/或设备驱动程序936。存储 器912也可以包括专用于存储器映射的I/O(MMIO)操作的区域。存储在 存储器412中的程序和/或数据可以作为存储器管理操作的一部分被交换到 磁盘驱动器928中。应用程序934可以执行(例如，在处理器902上)， 以与耦合到网络905的一个或多个计算设备交换一个或多个分组。在一个 实施例中，分组可以是一个或多个符号和/或值的序列，它们可以通过从至 少一个发送方向至少一个接收方(例如，通过诸如网络905之类的网络) 传输的一个或多个电信号来编码。例如，每一个分组都可以具有头部，该 头部包括在路由和/或处理分组时可以使用的各种信息，诸如源地址、目的 地地址、分组类型，等等。每一个分组都也可以具有有效负载，该有效负 载包括分组通过计算机网络(诸如网络905)在各种计算设备之间传输的原 始数据(或内容)。

在一个实施例中，应用程序934可以使用O/S932来与系统900的各 种组件进行通信，例如，通过设备驱动程序936。因此，设备驱动程序936 可包括网络适配器930特定的命令，以在O/S932和网络适配器930，或， 例如，通过芯片组906，耦合到系统900的其他I/O设备之间提供通信接口。

在一个实施例中，O/S932可包括网络协议堆栈。协议堆栈一般是指一 组过程或程序，它们可以被执行以处理通过网络905发送的分组，其中， 分组可以符合指定的协议。例如，可以使用TCP/IP堆栈来处理TCP/IP(传 输控制协议/因特网协议)分组。设备驱动程序936可以可以指出存储器912 中要被处理(例如，通过协议堆栈)的缓冲区。

网络905可包括任何类型的计算机网络。网络适配器930还可以包括 直接存储器访问(DMA)引擎，该引擎将分组写入到分配给可用的描述符 (例如，存储在存储器912中的)缓冲区(例如，存储在存储器912中)， 以通过网络905传输和/或接收数据。另外，网络适配器930还可包括网络 适配器控制器，该网络适配器控制器可包括执行适配器相关的操作的逻辑 (诸如一个或多个可编程处理器)。在一个实施例中，适配器控制器可以 是MAC(媒体访问控制)组件。网络适配器930还可以包括存储器，诸如 任何类型的易失性/非易失性存储器(例如，包括一个或多个高速缓存和/ 或参考存储器912所讨论的另一存储器类型)。

图10示出了根据本发明的一个实施例的按点对点(PtP)配置排列的 计算系统1000。具体而言，图10示出了其中处理器、存储器，以及输入/ 输出设备通过若干个点对点接口来互连的系统。参考图1-9所讨论的操作 可以由系统1000的一个或多个组件来执行。

如图10所示，系统1000可包括多个处理器，为清楚起见，只示出了 其中两个，处理器1002和1004。处理器1002和1004可以各自都包括本地 存储器控制器中枢(GMCH)1006和1008，以实现与存储器1010和1012 的通信。存储器1010和/或1012可以存储各种数据，诸如参考图10的存储 器1012所讨论的那些。如图10所示，处理器1002和1004(或系统1000 的其他组件，诸如芯片组1020，I/O设备1043，等等)也可以包括一个或 多个高速缓存，诸如参考图1-10所讨论的那些。

在一个实施例中，处理器1002和1004可以是参考图10所讨论的处理 器1002中的一个。处理器1002和1004可以分别使用PtP接口电路1016 和1018，通过点对点(PtP)接口1014，交换数据。处理器1002和1004 还可以各自使用点对点接口电路1026，1028，1030，以及1032，通过单个 PtP接口1022和1024，与芯片组1020交换数据。芯片组1020还可以进一 步通过高性能的图形接口1036，例如，使用PtP接口电路1037，与高性能 的图形电路1034交换数据。

在至少一个实施例中，可以在处理器1002，1004和/或芯片组1020中 的一个或多个中提供目录高速缓存和/或逻辑。然而，本发明的其他实施例， 可以存在于图10的系统1000内的其他电路、逻辑单元，或设备中。进一 步地，本发明的其他实施例可以分布在图10中所示出的多个电路、逻辑单 元，或设备中。例如，系统1000的各种组件可包括图1的逻辑150。然而， 可以在系统1000中的多个位置，包括或排除所示出的那些，提供逻辑150。

芯片组1020可以使用PtP接口电路1041，与总线1040进行通信。总 线1040可以具有与它进行通信的一个或多个设备，诸如总线桥接器1042 和I/O设备1043。通过总线1044，总线桥接器1042可以与其他设备，诸 如键盘/鼠标1045，通信设备1046(诸如调制解调器、网络接口设备，或可 以与计算机网络1005进行通信的其他通信设备)，音频I/O设备，和/或数 据存储设备1048，进行通信。数据存储设备1048可以存储可以由处理器 1002和/或1004执行的代码1049。

以下示例关于进一步的实施例。示例1包括一种设备，包括：路由逻 辑，用于确定用于传输将在输入端口处被接收的传入消息的输出端口，其 中所述路由逻辑将基于将在可通信地耦合到所述路由逻辑的一个或多个其 他路由逻辑处被检测到的拥塞信息，来从第一输出端口和第二输出端口中 选择所述输出端口，其中所述第一输出端口将为所述传入消息提供确定性 路由，所述第二输出端口将为所述传入消息提供自适应路由。示例2包括 示例1的设备，其中所述确定性路由能够为源和目的地节点对选择相同路 径。示例3包括示例1的设备，其中所述自适应路由能够基于流量信息， 为源和目的地节点对选择不同的路径。示例4包括示例1的设备，其中所 述拥塞信息将基于能够传递所述传入消息的数个性能虚拟信道与较低性能 虚拟信道阈值的比较来确定。示例5包括示例1的设备，其中所述拥塞信 息将基于对应于能够传递所述传入消息的一个或多个虚拟信道的数个共享 信用与较低信用阈值的比较来确定。示例6包括示例1的设备，其中所述 路由逻辑将响应于检测到所述传入消息的第一flit，确定所述输出端口。示 例7包括示例1所述的设备，包括用于将所述输出端口的可用性与所述传 入消息匹配的调度器逻辑。示例8包括示例1所述的设备，包括用于通信 地耦合所述输入端口和所述输出端口的交叉开关逻辑。示例9包括示例1 所述的设备，包括用于通过以每个flit为基础分配一个或多个缓冲区以存储 对应于所述传入消息的数据来支持无死锁路由的逻辑。示例10包括示例1 所述的设备，包括用于通过以分组级别为基础分配一个或多个虚拟信道以 传递对应于所述传入消息的数据来支持无死锁路由的逻辑。示例11包括示 例10所述的设备，其中所述分组将包括多个flit。示例12包括示例1所述 的设备，其中所述路由逻辑将基于多个路由虚拟信道，提供无死锁路由。 示例13包括示例1所述的设备，其中所述路由逻辑将通过链路，将第一代 理耦合到第二代理，其中所述链路将包括点对点互连。示例14包括示例13 所述的设备，其中所述第一代理和所述第二代理中的一个或多个将包括多 个处理器核。示例15包括示例13所述的设备，其中所述第一代理和所述 第二代理中的一个或多个将包括多个插槽。示例16包括示例13所述的设 备，其中所述第一代理、所述第二代理、所述路由逻辑，以及存储器中的 一个或多个位于同一集成电路管芯上。

示例17包括一种方法，包括：在路由逻辑中，确定用于传输将在输入 端口处被接收的传入消息的输出端口，其中所述路由逻辑将基于将在通信 地耦合到所述路由逻辑的一个或多个其他路由逻辑处被检测到的拥塞信 息，从第一输出端口和第二输出端口中选择所述输出端口，其特征在于， 所述第一输出端口将为所述传入消息提供确定性路由，所述第二输出端口 将为所述传入消息提供自适应路由。示例18包括示例17所述的方法，进 一步包括将所述输出端口的可用性与所述传入消息匹配。示例19包括示例 17所述的方法，进一步包括通信地耦合所述输入端口以及所述输出端口。 示例20包括示例17所述的方法，进一步包括通过以每个flit为基础分配一 个或多个缓冲区以存储对应于所述传入消息的数据来支持无死锁的路由。 示例21包括示例17所述的方法，进一步包括通过以分组级别为基础分配 一个或多个虚拟信道以传递对应于所述传入消息的数据来支持无死锁的路 由。

示例22包括一种系统，包括：存储拥塞信息的存储器；以及，耦合到 所述存储器的路由逻辑，用于确定用于传输将在输入端口处被接收的传入 消息的输出端口，其中所述路由逻辑将基于将在通信地耦合到所述路由逻 辑的一个或多个其他路由逻辑处被检测到的拥塞信息，来从第一输出端口 和第二输出端口中选择所述输出端口，其中所述第一输出端口将为所述传 入消息提供确定性路由，所述第二输出端口将为所述传入消息提供自适应 路由。示例23包括示例22的系统，其特征在于，所述确定性路由能够为 源和目的地节点对选择相同路径。示例24包括示例22的系统，其中所述 自适应路由能够基于流量信息，为源和目的地节点对选择不同的路径。

示例25包括一种设备，包括：用于在路由逻辑处确定用于传输将在输 入端口处被接收的传入消息的输出端口的装置，其中所述路由逻辑将基于 将在通信地耦合到所述路由逻辑的一个或多个其他路由逻辑处被检测到的 拥塞信息，来从第一输出端口和第二输出端口中选择所述输出端口，其中 所述第一输出端口将为所述传入消息提供确定性路由，所述第二输出端口 将为所述传入消息提供自适应路由。示例26包括示例25所述的设备，进 一步包括用于将所述输出端口的可用性与所述传入消息匹配的装置。示例 27包括示例25的设备，进一步包括用于通信地耦合所述输入端口以及所述 输出端口的装置。示例28包括示例25的设备，进一步包括用于通过以每 个flit为基础分配一个或多个缓冲区以存储对应于所述传入消息的数据来 支持无死锁路由的装置。示例29包括示例25的设备，进一步包括用于通 过以分组级别为基础分配一个或多个虚拟信道以传递对应于所述传入消息 的数据来支持无死锁路由的装置。

示例30包括其中包括一个或多个指令的计算机可读介质，所述指令在 处理器上执行时，导致处理器执行如示例17到21中任一示例所述的一个 或多个操作。示例31包括示例17和18中的任一项所述的方法，进一步包 括通信地耦合所述输入端口以及所述输出端口。示例32包括示例17到19 中的任一项所述的方法，进一步包括通过以每个flit为基础分配一个或多个 缓冲区以存储对应于所述传入消息的数据来支持无死锁路由。示例33包括 示例17到20中的任一项所述的方法，进一步包括通过以分组级别为基础 分配一个或多个虚拟信道以传递对应于所述传入消息的数据来支持无死锁 路由。

在本发明的各实施例中，例如，此处参考图1-10所讨论的操作，可被 实现为硬件(例如，电路)、软件、固件、微代码，或其组合，它们可以 作为计算机程序产品提供，例如，包括有形的(例如，非瞬时的)机器可 读的或(例如，非瞬时的)在其上存储了用于编程计算机以执行此处所讨 论的过程的指令(或软件过程)的计算机可读介质。术语“逻辑”作为示 例可包括软件、硬件，或软件和硬件的组合。机器可读取的介质可包括存 储设备，诸如参考图1-10所讨论的那些。另外，这样的计算机可读介质还 可以被作为计算机程序产品下载，其中，经由通信链路(例如，总线、调 制解调器和/或网络连接)，通过在载波或其他传播介质中提供的数据信号， 可将程序从远程计算机(例如，服务器)传输到请求计算机(例如，客户 机)。

说明书中对“一个实施例”、“实施例”的引用意味着结合该实施例 所描述的特定特征、结构或特性可以被包括在至少一个实现中。在本说明 书中的不同位置出现短语“在一个实施例中”可以或可以不都是指同一个 实施例。

此外，在说明书和权利要求书中，可使用术语“耦合”和“连接”及 其衍生词。在本发明的某些实施例中，可以使用“连接”来表示两个或更 多元件彼此处于直接的物理和/或电接触的状态。“耦合的”可表示两个 或更多个元件直接物理或电接触。然而，“耦合的”也可表示两个或更多 个元件可以不彼此直接接触，但是仍然彼此协作、彼此相互作用。

如此，尽管已经用对结构特征和/或方法动作专用的语言描述了本发明 的各实施例，但可以理解，所要求保护的主题可以不必受所描述的这些具 体特征或动作的限制。相反，具体特征和动作是作为实现所要求保护的主 题的示例形式来公开的。