用于避免数据饥饿的集成电路和方法

摘要

本发明提供一种能够用在集成电路的网络内的路由器。该路由器能够处理属于多个业务类别的输入数据。该路由器还能保证在容许的业务内，所有输入数据能以可接受的代价被充分处理和输出。本发明基于以下理解：竞争问题是由输入竞争和输出竞争这两个具体问题组成。因为将路由器所包括的交换器设计成能同时为多个耦合到输入端口的队列服务，所以不再产生输入竞争的问题。由于持续优先选择高优先级业务而不选择低优先级业务而导致的饥饿问题，通过允许在服务包含来自高优先级业务类别的数据的队列的同时，也服务包含来自低优先级业务类别的数据的队列而得到解决。

说明书

技术领域

本发明涉及一种集成电路，该集成电路包括一个网络，该网络包括多个路由器，这些路由器中的至少一个包括多个输入端口，这些输入端口用于接收与至少两种业务类别相对应的输入数据，所述路由器还包括多个队列，这些队列用于存储与单个业务类别相对应的输入数据，其中上述输入端口与这些队列中的至少两个相耦合，所述路由器还包括一个交换器。

本发明还涉及一种用于在集成电路中避免数据饥饿(starvation)的方法，该集成电路包括一个网络，该网络包括多个路由器，这些路由器中的至少一个包括多个输入端口，这些输入端口接收与至少两种业务类别相对应的输入数据，所述路由器还包括多个队列，其中这些队列存储与单个业务类别相对应的输入数据，上述输入端口与这些队列中的至少两个相耦合，所述路由器还包括一个交换器。

技术背景

由于对现有功能进行创新和改进的需要不断增加，硅上系统(system on silicon)在复杂程度上持续增高。通过提高元件集成在集成电路上的密度能使上述情况变成可能。同时，电路运行的时钟速度也有升高的趋势。更高的时钟速度与增大的元件密度相结合会减少在相同时钟域内同步运行的电路面积。这产生了对模块化方法的需要。根据这样的模块化方法，处理系统包括多个相对独立、复杂的模块。在传统的处理系统中，模块经由总线互相通信。然而随着模块数目的增加，这种通信方式由于以下原因而不再实用。首先，大量的模块形成太高的总线负载；其次，由于许多模块将耦合到总线而使时钟频率下降；第三，由于总线只能使一个器件向它发送数据，所以总线会形成通信瓶颈。

一种通信网络形成了克服这些缺陷的有效方法。在文章“Tradeoffs in the Design of a Router with Both Guaranteed and Best-EffortServices for Networks on Chip”published at the Conference on Design，Automation and Test in Europe，7March 2003，Munich(Germany)中描述了这种网络的优点。另外，这种网络能够组织和管理全局互接线路，并共享这些线路，从而降低了线路数目并提高了线路的利用率。

上述通信网络包括多个部分连接的节点。来自模块的请求可以通过这些节点改变方向传到一个或多个其他节点。文献和当前的研究显示，对于大型片上系统来说这些片上网络是不可避免的。这样的网络典型地包括经由诸如导线的物理连接而互相连接的路由器。

因为输入排队缓冲结构在低成本下能提供合适的性能，所以片上网络(NoC)中路由器的已知结构就是输入排队缓冲结构。在传统输入排队中，单个队列耦合到路由器的每一输入端口。将路由器的输入数据分类成多个业务类别，这些业务类别定义了输入数据所属于的数据类别。传统输入排队不能区分来自不同业务类别的输入数据，因而只能支持单个业务类别。

通过多个网络可以实现需要多个业务类别的系统，但是将多个网络合并成单个网络具有共享用来连接路由器的物理连接的优点。因此，希望拥有一种支持多个业务类别的单个网络。获得该单个网络的标准方法是扩展路由器的输入排队机制使得每一输入端口接收多个队列。通常，因为一个大存储器比多个小存储器具有更高的面积效率，所以耦合到一个输入端口的队列集合映射到一个存储单元(例如RAM存储器)。在图1B中说明了这种支持多个业务类别的路由器的标准结构。

路由器在离散时间点做出决策，上述离散时间点将时间划分成所谓的“时隙”。路由器可能在一个时隙内试图通过相同链路(即相同输出)发送多个数据项；这个问题称为竞争。因为在一个时隙内通过一个链路只能传送一个数据项，所以在该多个数据项中必须做出选择；这种处理称为竞争解决。竞争解决典型地是通过对业务进行调度来进行的；例如调度器可以在选择与低优先级业务相对应的数据项之前，选择与高优先级业务相对应的数据项。调度通常通过一个或者多个仲裁器来执行，上述仲裁器能够允许和拒绝时隙之内的请求；每一时隙只允许一个传到输出端口的请求。

该标准结构具有两个主要问题。第一个问题是可能发生饥饿。饥饿意味着某一输入数据，例如属于低优先级业务类别的数据，永远得不到服务而因此使输入数据“滞留”在路由器里。事实上，这意味着在该网络中该数据永远不能到达它的目的地。饥饿可以分成两种类型。第一种类型的饥饿主要是由网络引起，其原因是分配到路由器的输出端口的数据项比输出端口的带宽允许的数据项更多。在这种情况下，输出端口的业务被称为“不容许的业务(non-admissible traffic)”。第二种类型的饥饿是由路由器自身所引起的，例如因为没有适当地执行竞争解决。在这种情况中，输出端口的业务称为“容许的业务(admissible traffic)”。本发明涉及与容许的业务相对应的数据项；本文档的其余部分只考虑容许的业务。

第二个问题与仲裁器的设计有关，仲裁器必须对输出端口的访问进行调度。每一输出端口对应一个仲裁器。仲裁器必须在路由器中执行竞争解决。这些仲裁器的设计是相对复杂的。

发明内容

本发明的一个目的是提供一种可以用在集成电路的网络内的路由器，该路由器能够处理属于多种业务类别的输入数据，并且在容许的业务下保证所有输入数据能以可接受的代价被充分地处理和输出。通过提供一种以权利要求1的特征部分为特征的集成电路实现上述目的。也可以通过提供一种以权利要求6的特征部分为特征的方法实现该目的。

本发明基于以下理解：竞争问题是由输入竞争和输出竞争这两个具体问题组成的。当耦合到输入端口的多个队列都包含数据时，在该输入端口发生输入竞争。当多个输入端口试图同时(即在一个时隙中)访问单个输出端口时，发生输出竞争。

已知的路由器结构典型地包括多个复用器和一个交换器，上述复用器允许在一个时隙内每个输入端口最多一个队列接受服务。本发明还基于以下理解：所述复用器可以省略，因为设计一个能够同时为耦合到输入端口的多个队列服务的交换器是可能的。饥饿问题是由持续优先选择高优先级业务而不选低优先级业务而导致的，该问题可以通过允许在服务包含来自高优先级业务类别的数据的队列的同时，也服务包含来自低优先级业务类别的数据的队列而解决。因为不再存在输入竞争的问题，所以可简化仲裁器的设计。包括在路由器中的交换器必须适合于同时处理来自每个输入端口的多个队列的输入，这将在优选实施例的描述中进行说明。

在权利要求2中定义了上述集成电路的一个实施例，其中队列的第一选择用于存储与高优先级业务类别相对应的输入数据，队列的第二选择用于存储与低优先级业务类别相对应的输入数据。该实施例的优点在于可分别对高优先级业务和低优先级业务进行调度。权利要求3定义了另一个实施例，其中所述第一选择用于在网络中提供确保通信服务(guaranteed communication service)。所述第二选择用于在网络中提供尽力而为通信服务(best-effort communication service)。

如果所述业务类别中的至少一个的仲裁器(例如高优先级业务类别的仲裁器)执行预定调度，那么在网络中源和目的地之间可获得业务的无竞争处理。该实施例在权利要求4中进行了定义。

在权利要求5中定义的实施例提供了依据本发明的交换器的一种可能实现。

附图说明

下文中将通过参考附图对本发明进行更加详细地描述，其中：

图1A说明了一种包括具有路由器的网络的集成电路；

图1B说明了集成电路上的网络中包括的已知路由器的一种结构；

图2说明了在这样一种结构中属于多个业务类别的输入数据的饥饿问题；

图3说明了几个队列的状态，用于解释图2所示的饥饿问题；

图4说明了在所述结构中导致饥饿的周期性撤销(retraction)的一个例子；

图5说明了几个队列的状态，用于解释图4所示的饥饿问题；

图6说明了这样一种结构中交换器的实现；

图7说明了依据本发明的集成电路上的网络内的路由器的结构；

图8说明了依据本发明的交换器的实现。

具体实施方式

图1A说明了一种已知的集成电路IC，该集成电路IC包括一个具有路由器R₁、R₂直到并包括R_x的网络。路由器R₁、R₂直到并包括R_x用于传递数据通过网络。将路由器R1、R2直到并包括Rx的输入数据分类成多个业务类别，这些业务类别定义了输入数据所属于的数据类别。本发明涉及能够传递属于多个业务类别的数据的路由器。本领域的技术人员知道，所述网络可扩展到一个或者多个其它集成电路，使得集成电路IC和其它集成电路共享单个网络。在这种情况下，NoC跨越多个芯片。本发明也涉及在这样一个共享网络中的路由器。

图1B说明了在集成电路上的网络内包括的路由器的一种结构。在该例中，路由器包括控制器100，该控制器100耦合到多个输入端口102、104、106并耦合到交换器120，该交换器120也称为纵横交换器。注意可能存在其它可供选择的结构。输入端口102、104、106接收输入数据input_1、input_2、inupt_3，这些输入数据属于多个业务类别；将这些输入数据传递给队列108a、108b、110a、110b、112a、112b。队列108a、108b、110a、110b、112a、112b中的每个都能存储属于单个业务类别的输入数据input_1、input_2、input_3。因此，每一输入端口耦合到多个队列；队列的数目取决于所支持的业务类别的数目。在所给实施例中，每一输入端口有两个队列，例如队列108a和108b与输入端口102相对应，这意味着支持属于两种业务类别的输入数据。很清楚存在其它可能的实施例，并且依据所支持业务类别数目的不同，每一输入端口的队列数目将会不同。

上述路由器也包括多个复用器114、116、118，该复用器允许在每单位时间(时隙)每一输入端口最多有一个队列接受服务。通常，复用器114、116、118也与控制器100相接(没有示出)。控制器100包括多个执行调度机制的仲裁器(没有示出)，例如控制器100计算交换器的设置。

如果在一个输入端口的多个队列都包含数据，那么在该输入端口会发生输入竞争。同样，当多个输入端口试图访问单个输出端口时，则发生输出竞争。用在该结构中的交换器102用来接收临时存储在队列中的输入数据input_1、input_2、input_3，在这个约束下，在一个时间单元(时隙)内每一输入端口的最多一个队列接受服务。在该例中，交换器102可以最多同时接收来自三个队列的数据，但它不能同时接收来自耦合到同一输入端口的两个队列的数据。然后交换器102传送数据，作为输出数据Output_1、Output_2、Output_3，这些输出数据将由网络进一步处理。

图2说明了图1所示结构中属于多个业务类别的输入数据的饥饿问题。饥饿是网络的一个主要问题。在该例中，耦合到输入端口102、104、106的上部队列108a、110a、112a包含属于高优先级业务类别的数据，而耦合到输入端口102、104、106的下部队列108b、110b、112b包含属于低优先级业务类别的数据。图2中的虚线箭头表示获得对交换器120的特殊输出端口(没有示出)进行访问的请求。换句话说，临时存储在队列108b中的输入数据将改变方向传到交换器120的第二输出端口并作为输出数据Output_2输出。然而，正如图3所说明的，从队列108b到交换器120的第二输出端口的请求不会被允许。图3说明了队列108a、108b、110a的状况。当分别在偶数和奇数时隙期间允许队列108a和110a(包含属于高优先级业务类别的数据)访问输出端口时，队列108b得不到服务，这是因为：

因为复用器114约束队列108a、108b中每次只有一个能得到服务，所以队列108b不能和队列108a同时得到服务；

因为队列110a“占用”队列108b请求访问的输出端口，并且队列110a包含来自更高优先级业务类别的数据，所以队列108b不能和队列110a同时得到服务。

如果上面描述的在奇数和偶数时隙期间发生的模式不断重复，那么队列108b不会得到服务并产生数据的饥饿。

已经采取若干克服上述问题的尝试，特别是以仲裁器应用的仲裁机制的形式，所有这些尝试都没有得到真正的解决办法。而且，实现这些方案会更加困难，并会导致硬件设计变得复杂。典型地，这些方案也会降低低优先级业务的性能。

在下文中将讨论下列仲裁机制：

撤销请求；

锁定请求；

随机仲裁；

多级优先。

第一种已知的仲裁机制使用一种称为撤销请求的方法。这意味着如果发生来自于相同输入端口或者输出到相同输出端口的请求，并且假定来自该输入端口的数据或者送到该输出端口的数据属于高优先级业务类别(也称为高优先级请求)，则撤销从包含属于低优先级业务类别的输入数据的队列来的访问输出端口的请求(也称为低优先级请求)。这种方法的硬件代价低，但低优先级仲裁器(调度低优先级请求)只能在高优先级仲裁器(调度高优先级请求)结束后起动。这会导致更高的计算延迟。而且，这种仲裁机制并不公平，并甚至会导致单个队列的低优先级请求的周期性撤销。该队列可能再次发生饥饿。

在图4和图5中给出了导致队列饥饿的周期性撤销的例子。来自第一输入端口102的属于低优先级业务类别的输入数据Input_1被传送到队列108b，然而属于高优先级业务类别的输入数据Input_1被传送到队列108a。队列110b和112b分别包含属于低优先级业务类别的输入数据Input_2、Input_3。从图5中可以看出队列108b得不到服务，这是因为：

因为复用器114约束队列108a和108b中每次只有一个能接受服务，所以队列108b不能和队列108a同时接受服务；

因为队列108a对应于相同的输入端口，所以从队列108b来的低优先级请求被撤销；

在撤销后调度器可以服务队列110b、112b，但是如果队列108b再次需要得到服务，且又有从队列108a来的高优先级请求，则从队列108b来的低优先级请求再次被撤消，等等。

另一种仲裁机制使用一种称为锁定请求的方法。为了避免撤销请求的长时间延迟，并避免周期性撤销，通过只考虑输出竞争，该方法同时对高和低优先级业务类别进行调度。如果在某一输入端口已允许的低优先级请求和高优先级请求之间发生输入竞争，则忽略该低优先级请求的允许，并在允许任何其它低优先级请求之前，把低优先级仲裁器锁定到首先允许刚刚被忽略的低优先级。如果在图4所示例子中使用该仲裁机制，则如果队列110b和112b曾经寻址过包含输出数据Ouput_2的输出端口，那么该锁定除了导致队列108b饥饿外，还会导致队列110b和112b发生饥饿。这意味着低优先级请求不会得到有效服务，并且低优先级带宽的利用也远没达到最佳状况。

另一个仲裁机制由上文说明的请求撤销与随机仲裁器相结合构成。随机仲裁器在每一输出端口随机地允许“竞争请求”(寻址相同输出端口的请求)中的一个。这样，通过随机选择就解决了周期性撤销的问题。然而，该仲裁机制的缺点是随机仲裁器的实现是相对昂贵的。

最后，在本文档其余部分将介绍一种使用称为多级优先的方法的仲裁机制。该方法与上面说明的撤销请求相结合，在低优先级业务类别范围内提供多个优先级。如果一个请求被撤销，则递增该请求的优先级，使得该请求被允许的机会也增加。那么用于低优先级业务类别的仲裁器需要是优先化的仲裁器，然而该仲裁机制的缺点是，由于该优先化的仲裁器和对优先级的管理导致硬件相对复杂且成本相对较高。

现有技术中已知的路由器采用在图6中说明的交换器120。在本例中采用3×3纵横交换器。该交换器120具有三条输入线，分别表示复用器114、116、118的输出。交换器120本身也包括三个复用器600、602、604。根据所寻址的输出端口，数据经由每条输入线被送到复用器600、602、604。复用器600为第一输出端口接收作为输出数据Output_1输出的数据，复用器602为第二输出端口接收作为输出数据Output_2输出的数据，复用器604为第三输出端口接收作为输出数据Output_3输出的数据。该交换器120运行如下。例如，属于高优先级业务类别的输入数据Input_3经由输入端口106传到队列112a。让我们假设队列112a请求访问具有输出数据Output_2的输出端口。那么复用器118首先转接该数据，然后该数据经由下部输入线进入交换器120。随后，复用器602转接该数据，并且最终将该数据作为输出数据Output_2输出。

结果，因为输入竞争不再出现并且调度机制更加简单，所以可以简化控制器100。现有技术的路由器也有持续“线端阻塞(head-of-lineblocking)”的问题；其结果是在一个输入端口的队列头部发生数据的饥饿，将导致该输入端口处所有数据的饥饿。在依据本发明的路由器中，线端阻塞不会无限地发生并且其发生的频率比现有技术的路由器更低，这对于路由器的性能也有积极的效果。

在一个实施例中，高优先级业务类别和低优先级业务类别之间的差异可被有利地用来提供一种路由器，该路由器一方面能够提供确保服务，另一方面可提供尽力而为服务。在文章“Trade offs in theDesign of a Router with Both Guaranteed and Best-Effort Services forNetworks on Chip”，published at the conference on Design，Automationand Test in Europe，7March 2003，Munich(Germany).中对这样一种组合路由器结构进行了描述。应该通过网络传送的数据，如果其传送具有诸如确保吞吐量和确保延迟等方面的要求，则将它分类为高优先级业务。对于其传送要求在尽力而为的基础上来执行的数据，则适合将它分类为低优先级业务。如果采用称为静态调度的方法，也就是一种预定的仲裁机制，那么在网络中在源和目的地之间可获得高优先级业务的无竞争业务处理。在这种情况下，源和目的地之间的连接是在编译时间而不是在运行时间建立的；建立这些连接是为了提供有保证的服务。

图7说明了依据本发明在集成电路上的网络内的路由器的结构。该结构消除了现有技术中的约束，该约束也就是，对于输入端口102、104、106中的每个端口，每次只能使用队列108a、108b、110a、110b、112a、112b中的一个。这是通过将队列108a、108b、110a、110b、112a、112b中的每个直接耦合到交换器700来实现的。换句话说，可以省略复用器114、116、118。在这种方式中，该结构不会遭受输入竞争。依据本发明的交换器700必须将上述情况变成可能，这显示在图8中。交换器700是6×3纵横交换器，能够从六条输入线而不是三条输入线(图6实施例中的情况)接收数据。交换器700还包括三个复用器800、802、804。这些复用器800、802、804用于从六条输入线接收输入，其中每条输入线与从队列108a、108b、110a、110b、112a、112b中的一个来的数据相对应。因此，交换器700用于同时接收来自所有队列108a、108b、110a、110b、112a、112b的输入。

注意本发明的保护范围不限于在这里描述的实施例。本发明的保护范围也不受权利要求中参考符号的限制。单词“包括”不排除权利要求所提到的那些部分以外的部分。元件前的单词“一个”并不排除多个这样的元件。构成本发明一部分的装置既可以以专用硬件的形式也可以以可编程通用处理器的形式来实现。本发明体现在每个新的特点或者这些特点的综合中。