公正分层仲裁器及其方法

摘要

公正分层仲裁器包含多个仲裁机构，每个仲裁机构按请求器遵守的循环顺序转发来自请求器的取胜请求。除了取胜请求之外，每个仲裁机构还转发有效请求位，有效请求位提供有关哪个请求器发出当前取胜请求，而在一些实施例中，有关那个特定仲裁机构仲裁多少个分立请求器的信息。公正分层仲裁器按循环顺序输出来自全体分立请求器的请求。

说明书

技术领域

本发明一般地涉及电子系统(尤其计算机系统)中多个请求器之间的竞争请求的仲裁，更具体地说，本发明涉及仲裁竞争请求的分层仲裁机构。

背景技术

在复杂的计算机系统中，多个处理单元可能共享诸如数据总线之类的某些硬件资源。在共享硬件资源中仲裁逻辑用于仲裁来自许多分立请求器的竞争请求。仲裁逻辑可以用单个中央仲裁器实现，也可以用分层或分布式仲裁器实现。这些类型的仲裁方法每一种都存在一些问题。

现有技术中的中央仲裁器100显示在图1中，它含有分别标为102A-102E的请求器J0-J4。请求器J0-J4分别通过总线104A-104E与选择逻辑112耦合。像如图1所示的中央仲裁器100那样的中央仲裁器的一个常见问题出现在存在大量请求器(在图1中，为了简单起见，只示出了5个请求器J0-J4)的时候或出现在请求器在物理上分散的时候。像中央仲裁器100那样的中央仲裁器需要复杂的连线。例如，请求器J0-J4驱动总线104A-104E。每条总线104A-104E通常包含许多条线，例如，64条线。总线104A-104E全部汇集到选择逻辑112；汇集到选择逻辑112的大量宽总线(例如，64位总线)会引起连线拥塞问题。由于总线104A-104E必须行进的物理距离，信号传播可能需要一些附加时间，从而使每个请求延迟。控制逻辑110为选择逻辑112提供控制，并且，例如，可以实现请求的循环排序或先进先出排序选择。

为了避免中央仲裁器遇到的连线拥塞和线长麻烦，当需要仲裁许多个请求器时，尤其当仲裁器在物理上分得很开时，往往使用分层仲裁器。现有技术的分层仲裁器也存在几个问题。分层仲裁器的一个常见问题出现在需要在多层仲裁机构中仲裁请求的时候。如果请求器在它们的请求方面不是一样多产的(较多产请求器比不多产请求器更频繁地将它的请求发送到仲裁机构)，那么，较不多产请求器在来自较不多产请求器的请求被选为取胜请求之前也许不得不等待相当长的时间。来自较低层请求器的请求只稀少地被选为最后取胜请求。与较高层请求器的请求相比，较低层请求器的请求必须穿过分层仲裁器中的更多仲裁层。

图2例示了进一步说明现有技术分层仲裁器中的固有问题的示范性现有技术分层仲裁器200。分层仲裁器200包含统称为仲裁机构210的仲裁机构210A、210B、210C和210D，所附字母用于表示仲裁机构210的具体示例。在下文中，附有字母字符的带标号项都是一般项的具体示例。

仲裁机构210A是最低层仲裁机构(即，离最后一级仲裁最远的仲裁机构)。仲裁机构210B和210C是较高层仲裁机构(即，与最后一级仲裁较近的仲裁机构)。仲裁机构210D是最高层仲裁机构(即，作出最后一级仲裁的仲裁机构)。

仲裁机构210A仲裁源自请求器L0、L1和L2的竞争请求。请求器L0-L2将请求发送到队列204A。请求器L0、L1和L2的每一个利用附加信令耦合(未示出)将它们正在驱动有效请求的时间通知给控制逻辑208A。在控制逻辑208A的控制下，在队列204A内循环地处理来自请求器L0-L2的请求，并且，在总线214A上将取胜请求转发到较高层仲裁机构210B。在一些仲裁机构210中，取代循环机制，实现FIFO(先进先出)过程。为了便于说明，在下文中将循环排序用于仲裁机构210。

仲裁机构210B仲裁来自请求器L3、L4和仲裁机构210A的竞争请求。仲裁机构210A作为仲裁机构210B的请求器出现；但是，仲裁机构210A是非基本请求器，因为仲裁机构210A仲裁几个请求器。与将称为非基本请求器的像仲裁机构210A那样的仲裁机构相反，“请求器”表示基本请求器。基本请求器被称为“分立请求器”，或简称为“请求器”。请求器L3和L4和仲裁机构210A向队列204B发送请求。在控制逻辑208B的控制下，在队列204B内循环地处理来自请求器L3、L4和仲裁机构210A的请求，并且，在总线214B上将取胜请求转发到仲裁机构210D。只有1/3时间选择在总线214A上发送的请求(假设对于仲裁机构210B，L3、L4和仲裁机构210A的每一个总是拥有激活请求)。如果请求器L0、L1和L2都是多产的，则L0、L1和L2的每一个因此赢得在总线214A上发送的请求的1/3，因此只赢得在总线214B上发送的竞争请求的1/3*1/3或1/9。仲裁机构210B作为仲裁机构210D的非基本请求器出现。

仲裁机构210C仲裁源自4个竞争请求器L5、L6、L7和L8的请求。请求器L5-L8将请求发送到队列204C。在控制逻辑208C的控制下，在队列204C内循环地处理来自请求器L5-L8的请求，并且，在总线214C上将取胜请求转发到仲裁机构210D。仲裁机构210C作为仲裁机构210D的非基本请求器出现。

仲裁机构210D仲裁源自4个竞争请求器L9、L10、仲裁机构210B和仲裁机构210C的请求。在控制逻辑208D的控制下，在队列204D内循环地处理来自请求器L9、L10、仲裁机构210B和仲裁机构210C的请求，并且，在总线214D上输出取胜请求。总线214D可以进一步与请求管理器(未示出)耦合。请求管理器在不同电子系统中可以不同。例如，在第一电子系统中，请求是计算机可执行指令，并且请求管理器执行取胜请求。在另一个电子系统中，请求是有关数据移动的，而请求管理器将数据从第一位置移动到第二位置。这个取胜请求是分层仲裁器的取胜请求。

分层仲裁器200的总效果可能非常不公正，尤其对于与最高层仲裁机构(即，将取胜请求驱动到分层仲裁器之外的仲裁机构)相隔一个或多个中间层仲裁机构的请求器。如果在很长时间间隔之后和如果所有请求器都在提交多产请求，每个请求器近似相同次数地被选为公正分层仲裁器的赢家，那么，分层仲裁机构的行为是公正的。

例如，如果所有请求器L0-L10都是多产的，每个作出恒数的请求，L9和L10的每一个将有1/4时间(由于队列204D总是拥有与它的4个输入的每一个有关的激活请求)在信号214D上输出它们的请求(即，成为取胜请求)。请求器L5、L6、L7和L8的每一个将只有1/16时间(4个请求器的每一个共享到队列204D的一个输入，到队列204D的一个输入本身只有1/4时间被选到)给出取胜请求。类似地，请求器L3和L4的每一个将有1/12时间给出取胜请求。并且，请求器L0、L1和L2的每一个将有1/36时间给出取胜请求。由于存在11个请求器(L0-L10)，公正分层仲裁器将给予每个请求器1/11时间的取胜请求。

因此，需要一种为公正分层仲裁器提供保证的方法和装置。

发明内容

本发明提供了公正仲裁竞争请求器的分层仲裁器。如果在很长时间间隔之后和如果所有请求器都在提交多产请求，每个请求器近似相同次数地被选为公正分层仲裁器的赢家，那么，仲裁机构的行为是公正的。

使用“近似”是考虑到可能出现在如后所述的公正分层仲裁器的流水线实施例中的可能流水线延迟引起的、将每个请求器的请求选为取胜请求的次数的差异。在特定设计中，可能存在需要附加周期传播来自特定请求器的请求的特定设计所特有的其它原因，进一步降低了公正分层仲裁器近似相同次数地选择每个请求器的程度。

分层仲裁器包含多层仲裁机构。低层仲裁机构离最后一级仲裁最远，而较高层仲裁机构与最后一级仲裁较近。最高层仲裁机构是最后一级仲裁并将取胜请求驱动到请求管理器。

公正分层仲裁器中的每个特定仲裁机构知道包括直接与特定仲裁机构连接的请求器在内的它正在仲裁的分立请求器的总数，以及转发到特定仲裁机构的在较低层仲裁机构上仲裁的请求。在第一实施例中，通过让特定仲裁机构接收有效请求位，使每个特定仲裁机构知道它正在仲裁的分立请求器的总数。在第二实施例中，通过寄存器中的值，即，烧到熔丝中的值，或通过特定仲裁机构的逻辑设计，使每个特定仲裁机构知道包括直接与较低层仲裁机构连接的请求器在内的它正在仲裁的分立请求器的总数。

使每个特定仲裁机构知道有效请求和哪个请求器发出的输入特定仲裁机构的有效请求。在一个实施例中，通过未编码有效请求位值标识有效请求。在一个实施例中，编码有效请求位，有效请求位的编码值表示哪个请求器发出有效请求。

在特定仲裁机构中，存在接收请求的队列。队列可以是单个集中队列，每个请求器一个队列的多个队列，或集中队列和特定请求器的分立队列的组合。请求可以源自直接与特定仲裁机构连接的请求器。请求也可以由与较低层仲裁机构连接的请求器发出，较低层仲裁机构进一步与特定仲裁机构耦合。队列接收来自请求器的请求，并且在控制逻辑的控制下选择取胜请求输出。位于每个仲裁机构内的队列存储等待选为受那个仲裁机构驱动的取胜请求的一系列请求。仲裁机构根据强迫按循环顺序仲裁的控制逻辑，从队列中选择取胜请求。然后，将取胜请求转发到较高层仲裁机构或分层仲裁器的输出总线。将下面进一步描述的有效请求位从较低层仲裁机构转发到较高层仲裁机构。较高层仲裁机构接收这些信号，将它们用于公正仲裁来自包括处在一个或多个较低层仲裁机构上的请求器、在较高层仲裁机构中仲裁的全体请求器的请求。

每个仲裁机构将强迫请求器按循环顺序的称为控制逻辑的逻辑用于选择取胜请求。在仲裁机构的一个实施例中，控制逻辑允许来自较不多产请求器的请求超越来自多产请求器的请求。为了完成超越，仲裁机构必须检测队列包含来自第一请求器的多个请求。当新请求从第二请求器到达时，允许新请求穿过队列中的多个请求的一些或全部，从而，无需等待队列中的所有请求就可以成为那个仲裁机构的取胜请求器。因此，在仲裁机构内强制执行了循环仲裁。不言而喻，使用循环排序只是为了示范，也可以设想出其它排序。

每个仲裁机构将预定循环仲裁顺序用于仲裁竞争请求。一般说来，假定全体分立请求器需要仲裁(例如，R0、R1、R2、...、Rn)，仲裁机构将简单地选择R0，然后是R1，再然后是R2，以此类推，但也可以设想出其它顺序。例如，公正分层仲裁器的设计者可以将循环仲裁顺序定义成Rn、Rn-1、...、R2、R1、R0。当仲裁机构通过这个顺序处理到最后请求器时，它将按与所定义相同的顺序重复仲裁。不断地重复这个过程。当作为根据循环顺序选择的请求器，识别出发出取胜请求的请求器时，只能将源自特定请求器的请求选为取胜请求。如果在特定时间，仲裁器正好从没有当前请求的请求器中选择请求，仲裁器将按循环顺序移到肯定有请求的下一个可用请求器。

为了有效地将信息从较低层仲裁机构传递到较高层仲裁机构，需要实现有效请求位。较高层仲裁机构必须处理来自较低层仲裁机构的有效请求位和取胜请求。有效请求位说明较低层仲裁机构仲裁了多少个请求器。有效请求位还说明哪个较低层请求器(如果有的话)是在较低层仲裁机构中仲裁的取胜请求器。在接收到有效请求位之后，每个较高层仲裁机构就知道正在仲裁多少个分立请求器。例如，如果与较高层仲裁机构耦合的较低层仲裁机构仲裁了3个请求器(例如，R0、R1、R2)，而较高层仲裁机构含有直接与较高层仲裁机构耦合的2个请求器(例如，R3、R4)，则较高层仲裁机构将按正在仲裁的整组分立请求器的循环顺序，也就是说，在本例中，按R0、R1、R2、R3和R4处理请求。在可替代实施例中，循环顺序至少在与不同层仲裁机构连接的请求器之间提供一些变化。在本例中，R0、R3、R1、R4和R2的循环顺序至少使一些时间可用于发送来自较低层仲裁机构的请求和较高层仲裁机构的相应确认。

附图说明

图1是现有技术单个中央仲裁器的图形；

图2是现有技术非公正分层仲裁器的图形；

图3A是公正分层仲裁器的高层图；

图3B是用在图3A中的仲裁机构的方块图；

图3C是示出图3B的仲裁机构的一个实施例的进一步细节，包括示范性请求和时间的方块图；

图3D是示出图3B的仲裁机构的第二实施例的进一步细节，包括示范性请求和时间的方块图；

图3E是图3A的较高层仲裁机构的方块图；

图3F是示出图3E的仲裁机构的一个实施例的进一步细节，包括示出仲裁机构的操作，以及示范性请求和时间的方块图；

图3G是示出图3F的仲裁机构的进一步细节，包括作出新请求的例子的方块图；

图3H是示出图3F的仲裁机构的一个可替代实施例的方块图；

图3I是示出图3F的仲裁机构中的控制逻辑的进一步细节的方块图

图3J是例示没有直接连接的请求器，但接收来自两个较低层仲裁机构的输入的仲裁机构的方块图；

图3K是示出“知道”多少个分立请求器与仲裁机构接收的每个请求流相联系，和接收与仲裁机构接收的每个请求流相联系的编码请求器标识符的仲裁机构的方块图；和

图4是例示在公正分层仲裁器的仲裁机构中具体实现的方法的流程图。

具体实施方式

在如下优选实施例的详细描述中，将参照形成本说明书的一部分并在其中示出可以使本发明得到实际应用的例示性具体实施例的附图。不言而喻，在不偏离本发明范围的情况下，可以使用其它实施例，也可以作出结构改变。

本发明提供了公正仲裁竞争请求器的分层仲裁器。

如果在很长时间间隔之后和如果所有请求器都在提交多产请求，每个请求器近似相同次数地被选为分层仲裁的赢家，那么，仲裁机构的行为是公正的。

上面使用的“近似”是考虑到如后所述的流水线实施例中的公正分层仲裁器的流水线延迟引起的、将请求器的请求选为取胜请求的次数的差异。在特定设计中，可能存在需要附加周期传播来自特定请求器的请求的特定设计所特有的其它原因，进一步降低了公正分层仲裁器近似相同次数地选择每个请求器的程度。

公正分层仲裁器包含数层仲裁机构。低层仲裁机构逻辑上离公正分层仲裁器的最后取胜请求输出最远(也就是说，来自低层仲裁机构的取胜请求在成为取胜请求之前必须穿过一层或多层仲裁机构)，而较高层仲裁机构与最后一级仲裁较近。最高层仲裁机构是最后一级仲裁和驱动公正分层仲裁器的取胜请求。特定仲裁机构接收来自任何较低层仲裁机构的请求，以及来自直接与特定仲裁机构连接的任何请求器的请求，并输出取胜请求。较低层仲裁机构将有关有效请求位的信息转发到较高层仲裁机构，有效请求位标识较低层仲裁机构仲裁的哪个请求器发出驱动到较高层仲裁机构的当前请求。

仲裁机构利用与控制逻辑耦合的队列处理竞争请求。队列可以包含单个集中队列、每个请求器的队列或两者的组合。队列存储等待输出成取胜请求的请求。仲裁机构根据强迫按循环顺序仲裁的控制逻辑，从队列中选择取胜请求，两者都要在下面加以描述。然后，将取胜请求转发到较高层仲裁机构，或作为公正分层仲裁器的取胜请求。

现在参照图3A，图3A示出了公正分层仲裁器300。公正分层仲裁器300包含仲裁机构320的4个示例：在最低层上(即，离公正分层仲裁器300的输出最远)的仲裁机构320A；仲裁层比仲裁机构320A高的仲裁机构320B；仲裁机构320C；和在最高仲裁层上的仲裁机构320D。

请求器R0、R1和R2分别在总线10、11和12上将它们的请求传递给仲裁机构320A中的队列326A。控制逻辑325A接收分别来自请求器R0、R1、R2的有效请求位360、361、362。有效请求位360、361、362上的“1”表示在相应总线10、11和12上正在驱动有效请求。控制逻辑325A强迫来自请求器R0、R1和R2的请求的循环排序。在队列326A内，可能发生请求超越的过程，以便每个请求器按循环顺序取胜。在一个实施例中，来自第一请求器的请求可以超越来自第二请求器的请求，在来自第二请求器的所有多个请求得到处理之前成为来自仲裁机构320A的取胜请求。仲裁机构320A的输出是有效请求位340A(3个位，每个位用于仲裁一个请求器)和在总线342A上转发到如下所述的仲裁机构320B的取胜请求。

有效请求位340A携带说明分立请求器R0、R1和R2被仲裁机构320A仲裁，和哪个请求器R0、R1和R2发出在总线342A上驱动的取胜请求的信息。对于被仲裁的每个分立请求器，在有效请求位340A中存在一个位。与特定请求器相对应的位位置中的位“1”意味着在总线342A上驱动的请求源自那个特定请求器。例如，如果来自R0的请求是在总线342A上驱动的取胜请求，有效请求位340A将是“100”。如果来自R1的请求是在总线342A上驱动的取胜请求，有效请求位340A将是“010”。如果来自R2的请求是在总线342A上驱动的取胜请求，有效请求位340A将是“001”。如果没有来自请求器R0、R1和R2的未处理请求，有效请求位340A将是“000”。将有效请求位340A转发到仲裁机构320B。

较高层仲裁机构320B必须仲裁分别在总线13，14上发送的来自直接相连请求器R3，R4的请求和在总线342A上由仲裁机构320A转发的取胜请求。因此，仲裁机构320A起仲裁机构320B的请求器作用；但是，仲裁机构320A不是简单请求器，因为请求来自分立请求器(R0、R1、R2)，而不是来自单个请求器。因此，仲裁机构320B按循环顺序仲裁全体分立请求器(R0、R1、R2、R3和R4)。

仲裁机构320B接收通知控制逻辑325B由仲裁机构320A转发的请求可以是来自3个分立请求器(R0、R1、R2)的请求的有效请求位340A，并且通知控制逻辑325B来自仲裁机构320A的哪个请求器当前在总线342A上发出取胜请求。如果当前在总线342A上没有驱动取胜请求，有效请求位340A通知控制逻辑325B在总线342A上没有受到驱动的激活请求。控制逻辑325B还接收分别来自请求器R3和R4的有效请求位363的364。分别在有效请求位363和364上的“1”表示分别在总线13和14上正在驱动有效请求。仲裁机构320B包含存储请求的队列326B和提供强迫在来自分立请求器R0、R1、R2、R3和R4的请求之间按循环顺序仲裁的控制的控制逻辑325B。仲裁机构320B将有效请求位340B(5个位，每个位用于仲裁一个分立请求器，即，R0、R1、R2、R3和R4)和在总线342B上将取胜请求转发到最高层仲裁机构320D。有效请求位340B携带说明在仲裁机构320B中仲裁来自5个分立请求器(R0、R1、R2、R3、R4)的请求，和哪个请求器(R0、R1、R2、R3或R4)发出选为在总线342B上转发的取胜请求的请求的信息。例如，如果来自仲裁机构320B的取胜请求源自请求器R1，有效请求位340B将是“01000”。如果来自仲裁机构320B的取胜请求源自请求器R4，有效请求位340B将是“00001”。如果没有在总线342B上驱动的有效请求，有效请求位340B将是“00000”。

仲裁机构320C必须仲裁都直接与仲裁机构320C连接的4个竞争请求器R5、R6、R7和R8。请求器R5、R6、R7和R8分别在总线15、16、17和18上将它们的请求发送到队列326C。控制逻辑325C强迫在来自请求器R5-R8的请求之间按循环顺序仲裁。控制逻辑325C接收分别从请求器R5、R6、R7和R8发送的有效请求位365、366、367和368。有效请求位365、366、367和368上的“1”表示分别在总线15、16、17和18上正在驱动有效请求。仲裁机构320C将有效请求位340C(4个位，每个位用于仲裁一个分立请求器)和在总线342C上将取胜请求输出到仲裁机构320D。有效请求位340C携带说明在仲裁机构320C中仲裁4个请求器(R5、R6、R7和R8)，和哪个请求器(R5、R6、R7或R8)发出在总线342C上转发的仲裁取胜请求的信息。例如，如果请求器R5发出在总线342C上驱动的取胜请求，有效请求位340C将是“1000”。

最高层仲裁机构320D必须仲裁来自直接相连请求器R9和R10的请求和从仲裁机构320B和仲裁机构320C转发的取胜请求。也就是说，仲裁机构320D必须按循环顺序仲裁整组11个分立请求器(R0-R10)。

将来自R9、R10、仲裁机构320B和仲裁机构320C的请求与队列326D耦合。控制逻辑325D从仲裁机构320B接收，如上所述，通知控制逻辑325D由仲裁机构320B在总线342B上转发的请求可以是来自5个分立请求器(R0、R1、R2、R3、R4)的请求，以及哪个请求器(R0、R1、R2、R3、R4)在总线342B上发出当前请求的有效请求位340B。如果没有来自R0、R1、R2、R3或R4的未处理请求，有效请求位340B中的所有位都是“0”(即，“00000”)。控制逻辑325D还接收通知控制逻辑325D由仲裁机构320C转发的请求可以是来自4个分立请求器(R5、R6、R7和R8)的请求的有效请求位340C。有效请求位340C表示哪个请求器(R5、R6、R7和R8)在总线342C上发出当前请求。如果没有来自R5、R6、R7和R8的未处理请求，有效请求位340C是“0000”。控制逻辑325D还接收有效请求位369和370。有效请求位369和370上的“1”表示分别在总线19和20上正在驱动有效请求。控制逻辑325D强迫在整组要仲裁的请求器(R0-R10)上按循环顺序仲裁。仲裁机构320D在总线342D上驱动分层仲裁器300的取胜请求。公正分层仲裁器的总取胜请求是仲裁机构按循环顺序选择的、源自请求器R0、R1、R2、R3、R4、R5、R6、R7、R8、R9或R10之一的请求。不言而喻，循环顺序无需是R0、R1、...、R10。例如，设计者可以选择R10、R9、...、R0的循环顺序。

尤其，在如下所述的流水线实施例中，在将特定请求从较低层仲裁机构发送到较高层仲裁机构，并且等待来自较高层仲裁机构的确认的过程中预期产生一些延迟。定义不连续选择来自特定较低层仲裁机构上的选择器的请求的循环顺序将部分或全部“隐藏”这样的延迟。在如图3所示的公正分层仲裁器的例子中，(R0、R5、R3、R9、R6、R1、R4、R7、R2、R10、R8)的特定循环排序保证了从特定较低层仲裁机构的选择被多个周期隔开，使得有时间发送从较低层仲裁机构到较高层仲裁机构的请求，以及从较高层仲裁机构返回到较低层仲裁机构的确认。特定循环排序保证了在从请求器R0、R1、R2中选择请求之间至少有2个周期；在从请求器R3、R4中选择请求之间至少有3个周期；在从请求器R5、R6、R7、R8中选择请求之间至少有1个周期；和在从请求器R9、R10中选择请求之间至少有4个周期。

虽然如上给出的循环顺序的明智选择在许多情况下将部分或全部“隐藏”流水线延迟，但可能出现这样的情况，如果在特定设计中需要许多周期将请求较低层仲裁机构发送到较高层仲裁机构，或者，如果特定较低层仲裁机构仲裁大量请求器，一些数量的流水线延迟无法隐藏。在这样的情况下，公正分层仲裁器只能提供“近似”理想的公正循环仲裁，使用“近似”是考虑到不能隐藏一些数量的流水线延迟。

图3B示出了为了方便起见从图3A中摘出的仲裁机构320A。仲裁机构320A接收来自请求器R0、R1和R2的请求。控制逻辑325A以这样的方式控制队列326A，那就是，强迫来自请求器R0、R1和R2的请求按循环顺序。分别在信号360、361和362上将分别由请求器R0、R1和R2作出的有效请求通知控制逻辑325A。例如，如果请求器R0正在将有效请求驱动到队列326A，请求器R0在信号360上驱动“1”。如果请求器R0未正在将有效请求驱动到队列326A，请求器R0在信号360上驱动“0”。如前所述，控制逻辑325A在340A上驱动有效请求位。在总线342上驱动取胜请求。不言而喻，在需要给予特定请求器，比如说，R0更高权重的实施例中，例如，R0和R1是相同的请求器(即，R0也是R1)。因此，在循环排序中给予R0两倍于R2的取胜请求。

图3C示出了仲裁机构320A的第一实施例320Aa。在仲裁机构320Aa中，将队列326A实现成具有三个分立队列，即，队列327A1、327A2和327A3的队列326Aa。队列327A1排队源自请求器R0的请求；队列327A2排队源自请求器R1的请求；和队列327A3排队源自请求器R2的请求。

控制逻辑325Aa保证了当来自R0、R1和R2的请求到达时，往下尽可能远地将这些请求存储在每个各自队列中。控制逻辑325Aa利用有效请求位360、361、362识别请求器R0、R1和R2正在驱动有效请求的时间。例如，如果R0正在总线10上将有效请求驱动到队列327A1，此时的请求器R0将在有效请求位360上驱动“1”。不言而喻，当特定请求器R0、R1和R2未在它们各自的总线10、11、12上驱动有效请求时，驱动到队列326Aa的值“不值得关心”，并且不写入各自队列327A1、327A2和327A3中。

下文将小写“r”用于表示特定请求器发出的请求。因此，rR0表示请求器R0发出的请求。所附下标表示特定请求器发出的请求的顺序。因此，rR0₁表示请求器R0发出的第1请求；rR0₂表示请求器R0发出的第2请求。

在图3C中，为了示范初始状况，将队列327A1显示成空的；队列327A2被显示成满的，存在来自请求器R1的3个请求(rR1₁、rR1₂和rR1₃)；和队列327A3包含一个来自请求器R2的请求rR2₁。图3C示出了利用显示成初始状况的请求，并且假设没有产生进一步的请求，在时间T1、T2、T3和T4在有效请求位340A上发送的有效请求位和在总线342A上发送的请求，其中，时间T1、T2、T3和T4是相继时间。控制逻辑325Aa强迫按循环顺序选择取胜请求。控制逻辑325Aa控制选择器328Aa依次(假设在各自队列中存在有效请求)从队列327A1、327A2和327A3中选择请求，然后，重复该选择顺序。在时间T1，将rR1₁(源自请求器R1的第1请求)驱动到总线342A上。在时间T1，在有效请求位340A上发送“010”，表示存在在总线342A上发送的有效请求，并且请求在请求器R1上发出。在时间T2，在总线342A上驱动rR2₁(源自请求器R2的第1请求)，并且在有效请求位340A上驱动“001”。分别在时间T3和T4，在总线342A上驱动rR1₂和rR1₃。在时间T3和T4，在有效请求位340A上驱动“010”。如果在时间T1请求器R0已经作出请求rR0，控制逻辑325Aa将把那个请求放置在队列327A1的底部，并且在时间T3在总线342A上驱动那个请求，以及在时间T3在有效请求位340A上驱动“100”的值。

图3D示出了仲裁机构320A的第二实施例，即，仲裁机构320Ab。仲裁机构320Ab中的队列326Ab含有存储来自请求器R0、R1和R2的请求的单个集中队列327Ab。控制逻辑325Ab能够将队列327Ab中的请求重新排序成强迫按循环顺序。不言而喻，在各种各样的实施例中，重新排序可以是将请求放置在队列327Ab中的不同位置中的物理重新排序，或利用，例如，指针对请求的逻辑重新排序。在图3D的例子中，三个请求rR1(rR1₁、rR1₂和rR1₃)处在队列327Ab中，后面接着来自请求器R2的新到达请求rR2(rR1₂)。如箭头所指，在发送了第1rR1(rR1₁)之后，控制逻辑325Ab将rR1₂移到队列327Ab的底部。因此，利用显示成初始状况的请求，并且假设没有进一步的请求到达，在时间T1驱动rR1₁；在时间T2在总线342A上驱动rR1₂(由控制逻辑325Ab移到队列327Ab的底部)；在时间T3驱动第2rR1(rR1₂)；和在时间T4驱动第3rR1(rR1₃)。此外，还示出了在有效请求位340A上驱动的有效请求位：在T1上，“010”；在T2上，“001”；在T3上，“010”；和在T4上，“010”。应该注意到，仲裁机构320A的两个实施例320Aa和320Ab在有效请求位340A和总线342A两者上产生相同的结果。

实施例仲裁机构320Aa通常实现起来更简单。实施例仲裁机构320Ab更好地接纳多产和非频繁请求器的混合。例如，如果请求器R1是多产的，在队列中需要相应大量的寄存器来管理由请求器R1作出的大量请求。如果R0是非频繁请求器，在队列中仅仅几个寄存器就足以支持来自请求器R0的请求，分立队列中用于请求器R0的另外寄存器是多余的。因此，与含有诸如队列327A1、327A2和327A1之类的分立队列的队列327Aa相比，集中队列327Ab的有利之处在于将多产和非频繁请求器混合在一起。

图3E示出了为了方便起见从图3A中摘出的仲裁机构320B。如果请求器R3和R4在它们的各自总线13和14上正分别将有效请求驱动到队列326B，信号363和364是“1”，并且如果请求器R3和R4未分别将有效请求驱动到队列326B，信号363和364是“0”。

图3F示出了与如图3C所示的仲裁机构320Aa的实施例相似，也就是说，对于仲裁机构320B支持的每个分立请求器，含有分立队列的仲裁机构320B的实施例。不言而喻，也可以设想出含有参照图3D所述的集中队列的仲裁机构320B的实施例。控制逻辑325Ba接收有效信号位340A，并且将在有效信号位340A上发送的值用于将在总线342A上发送的请求分配到队列326Ba。如果有效信号位340A是“100”，将在总线342A上发送的请求发送到队列327B1(源自请求器R0的请求)；如果有效信号位340A是“010”，将在总线342A上发送的请求发送到队列327B2(源自请求器R1的请求)；或如果有效信号位340A是“001”，将在总线342A上发送的请求发送到队列327B3(源自请求器R2的请求)。当如有效请求位信号363上的“1”所指，请求器R3驱动有效请求时，将来自请求器R3的请求放入队列327B4中。当如有效请求位信号364上的“1”所指，请求器R4驱动有效请求时，将来自请求器R4的请求放入队列327B5中。控制逻辑325Ba保证了往下尽可能远地将每个请求放在每个各自队列中。然后，控制逻辑325Ba利用选择器328Ba按循环顺序从每个队列(327B1-327B5)的底部开始选择，将请求驱动到总线342B上。

图3F还示出了队列327B1-327B5中的请求的示范性初始状况集合。没有rR0请求处在队列327B1中。三个rR1(rR1₁、rR1₂和rR1₃)请求处在队列327B2中。一个rR2(rR2₁)请求处在队列327B3中。三个rR3(rR3₁、rR3₂和rR3₃)请求处在队列327B4中。一个rR4(rR4₁)请求处在队列327B5中。假设没有进一步的请求到达，在图3F中示出了在时间T1-T8与发送的有效请求位一起发送的请求。请注意，原请求器按循环顺序发送取胜请求，和有效信号位340B标识哪个请求器发出在总线342B上驱动的取胜请求。

图3G是图3F的例子的延续，只多了一个在时间T6到达的来自请求器R2(rR2₂)的新请求。该请求可通过等于“001”的有效请求位340A的值标识成源自请求器R2。图中示出了在T6队列326Ba(队列327B1-327B5)的内容。与图3F的例子一样，在T6期间，在总线342B上驱动rR3₂，作为仲裁机构324B的取胜输出。强迫请求器按循环顺序的控制逻辑325Ba在时间T7选择rR1₃作为取胜请求。在时间T8，rR2₂是取胜请求，并且在时间T9，rR3₃是取胜请求。在每个发送时间都示出了在有效请求位340B上发送的有效请求位。请注意，rR2₂已经有效地超越在rR2₂到达之前仲裁机构324B已经接收到的rR3₃。

类似地，仲裁机构320D按R0-R10的循环顺序提供仲裁，利用有效请求位340B和有效请求位340C确定有多少分立请求器“隐藏”在总线342B和342C的后面和哪个请求器在总线342B和342C上发出当前请求。与如图3C所示的仲裁机构320Aa类似，仲裁机构320D可以利用11个分立队列具体化。可替代地，仲裁机构320D也可以利用与用在如图3D所示的仲裁机构320Ab中的那个相似的集中队列具体化。

队列326不局限于只含有集中队列或分立队列。图3H例示了仲裁机构320的一个实施例-仲裁机构320Bc，它含有对于输入到仲裁机构320Bc的每个数据流包含一个分立队列的队列326Bc。队列327B10是在总线342A上接收从仲裁机构320A发送的所有请求的集中队列。队列327B11接收来自直接相连请求器R3的所有请求。队列327B12接收来自直接相连请求器R4的所有请求。请注意，队列327B10、327B11和327B12未局限于相同个数的寄存器。控制逻辑325Bc管理每个队列中请求的位置(逻辑的或物理的)。在一个实施例中，控制逻辑325Bc为队列327B10中由仲裁机构320A仲裁的来自非频繁请求器的请求超越一个或多个仲裁机构320A仲裁的来自频繁请求器的请求提供保证。控制逻辑325Bc控制选择器328Bc根据循环顺序或原请求器从队列327B10、327B11和327B12中选择请求。

图3I例示了图3H的仲裁机构320Bc的控制逻辑325Bc的进一步细节。含有集中队列的队列326B的一个实施例要求相应控制逻辑325Bc为集中队列中的每个请求保留在有效请求位340上发送的值。图3H中的队列327B10是接收来自请求器R0、R1和R2的请求的集中队列。伴随着在总线342A上发送的每个请求的是有效请求位340A上的相应有效请求位值。VRB队列323包含队列326Bc的队列327B10中相应队列位置中的请求的有效请求位(VRB324，示出2个)。来自请求器R3的有效请求位信号363和来自请求器R4的有效请求位信号364被耦合到循环逻辑322。VRB队列323也被耦合到循环逻辑322。因此，循环逻辑322知道在集中队列327B10和分立队列327B11和327B 12中那些请求悬而未决，并且可以控制选择器328Bc(显示在图3H中)根据循环顺序或原请求器在队列326Bc中选择请求。

图3J例示了仲裁来自两个较低层仲裁机构320X和320Y的请求的仲裁机构320Z。仲裁机构320Z没有任何直接相连的请求器。分别在总线342X和342Y上将来自仲裁机构320X和320Y的请求发送到仲裁机构320Z。分别在有效请求位340X(M个位)和340Y(N个位)将从320X和320Y发送的有效请求位发送到控制逻辑325Z。仲裁机构320Z进一步包含队列326Z和选择器328Z，队列326Z进一步包含集中队列327Z1和327Z2。如果仲裁机构320Z不是最高层仲裁机构，在有效请求位340Z(M+N个位)上发送有效请求位。在总线342Z上驱动取胜请求。不言而喻，在一些实施例中，队列326Z可以像前面所述那样，用每个原请求器的分立队列，或集中队列和分立队列的组合来实现。

在一个实施例中，如果在特定仲裁机构320的队列326中没有未处理请求，进入那个特定仲裁机构320的新请求马上作为取胜请求经过那个特定仲裁机构320的总线。在这个实施例中，不会导致额外请求延迟。也就是说，假设沿途(即，在仲裁器324A、仲裁器324B、仲裁器324C或仲裁器324D中)没有其它请求悬而未决，图3A的仲裁机构320A中来自请求器R0的请求可以作为分层仲裁器300的取胜请求直接从R0传播到总线342D。在一些实现中，无论从物理长度上来讲，还是从需要的逻辑块(例如，控制逻辑325A、控制逻辑325B、控制逻辑325C和控制逻辑325D)的数量上来讲，这么长的路径可以导致比用在包含公正分层仲裁器300的电子装置(未示出)中的周期时间更长的延迟。

通常，公正分层仲裁器300的实施例使用流水线。例如，在一个实施例中，一个或多个第一周期用于产生来自仲裁机构320A的取胜请求。即使在仲裁机构320A的取胜请求输入仲裁机构320B中时，在仲裁器324B中没有其它请求悬而未决，也需要一个或多个第二周期使来自仲裁机构320A的取胜请求变成来自仲裁机构320B的取胜请求。即使仲裁器324D没有其它请求悬而未决，也需要一个或多个第三周期使来自仲裁机构320B的取胜请求变成来自仲裁机构320D的取胜请求。有利的是，正如前面举例所述的那样使用了不连续从同一较低层仲裁机构中挑选请求器的明智选择循环顺序，否则，与完美循环排序的近似度会降低。

如前所述，现有技术的分层仲裁器将逐渐减少的取胜请求提供给较低层仲裁机构中的请求器。例如，如在背景技术中针对现有技术的分层仲裁器200所示的那样，“请求器L0、L1、L2的每一个将只有1/36时间给出取胜请求”。如上所述，在可以隐藏流水线延迟的程度上，无论使用多少层仲裁机构，公正分层仲裁器300都为每个请求器提供数量相同的取胜请求，或数量近似相同的取胜请求。

本发明的实施例包括多少个分立请求器共享特定总线342，即，来自较低层仲裁机构、设计成控制逻辑，或可替代地，在构建包含控制逻辑的电子系统时供应的知识。当实现大量请求器时，这样的实施例尤其有利，如果像在本发明的前面实施例中所述的那样完全不编码，这会使有效请求位340的数量非常大。例如，如果总共实现64个分立请求器，在前面的例子中总共将需要64个有效请求位340。但是，在本发明的实施例中，编码哪个请求器(如果有的话)在总线342上发出请求将显著减少有效请求位340的数量。图3K例示了这样的实施例。仲裁机构320P接收来自请求器RP₀-RP_M-1的请求。仲裁机构320Q接收来自请求器RQ₀-RQ_N-1的请求。仲裁机构320P将总线342P上的请求转发到仲裁机构320R的队列326R。仲裁机构320Q将总线342Q上的请求转发到队列326R。仲裁机构320P在有效请求位340P上发送有关哪个(如果有的话)请求器RP₀-RP_M-1发出在总线342P上发送的当前取胜请求的编码信息。由于仲裁机构320P总共仲裁“M”个请求器，有效请求位340P必须具有LOG₂(M+1)个位。例如，如果仲裁机构320P仲裁63个请求器(即，M＝63)，有效请求位340P必须具有6个位。使用“M+1”而不是M是考虑到“M”个请求器中没有一个拥有当前有效请求的可能性。类似地，仲裁机构320Q仲裁“N”个请求器。有效请求位340Q需要LOG₂(N+1)个位来标识哪个(如果有的话)请求器RQ₀-RQ_N-1发出在总线342Q上发送的当前取胜请求。控制逻辑325R被设计成知道仲裁机构320P和320Q仲裁多少个请求器。控制逻辑325R中的表380包含用于值“M”的字段381P和用于值“N”的字段381Q。字段381P和字段381Q可以在设计控制逻辑325R时“硬编码”，或者，可以在构建包括仲裁机构320R的电子系统期间扫描进去。可替代地，字段381P和381Q也可以是熔丝编程的。不言而喻，存在大量可以接纳有关将请求输入仲裁机构的较低层仲裁机构仲裁的请求器的数量的信息的方式。控制逻辑325R驱动指示哪个请求器(如果有的话)发出当前在总线342R上驱动的取胜请求的有效请求位340R。有效请求位340R必须考虑到总共“M+N”个请求器，以及没有在总线342R上驱动的当前有效请求的可能性。

图4是含有至少一层仲裁机构的公正分层仲裁器使用的方法实施例的流程图。如前所述，最高层仲裁机构将取胜请求从公正分层仲裁器输出到请求管理器。较低层仲裁机构将取胜请求从那个较低层仲裁机构输出到可能是最高层仲裁机构的较高层仲裁机构。

该方法从步骤S502开始。

在步骤S504中，特定仲裁机构从多个请求器中的一个请求器接收新请求。新请求可以来自较低层仲裁机构，或新请求可以直接来自直接与同一仲裁机构连接的请求器。

在步骤S506中，如果有效请求位从特定较低层仲裁机构输入特定仲裁机构，接收有效请求位，和特定仲裁机构从有效请求位中确定特定较低层仲裁机构仲裁多少个分立请求器，以及特定较低层仲裁机构仲裁的哪个请求器发出新请求。

在步骤508中，将新请求放置在特定仲裁机构中的队列中，队列中的位置由哪个请求器发出请求决定。不言而喻，“位置”包括物理位置(即，请求在物理上被放入哪个寄存器中)或逻辑位置(譬如，作为确定集中队列中请求的逻辑顺序的装置的指针的实现)。

在步骤510中，特定仲裁机构根据特定仲裁机构仲裁的所有请求器的循环排序从队列输出取胜请求。例如，如果存在N个请求器，所有请求器都存在一个或多个在特定仲裁机构上悬而未决的有效请求，特定仲裁机构将按顺序输出来自请求器1、2、3、...、N的请求，然后，从来自请求器1的下一个请求开始重复。如果某个请求器在按循环顺序轮到它时没有悬而未决请求，仲裁机构按循环顺序选择肯定含有悬而未决请求的下一个请求器。如前所述，在给定仲裁机构中实现的循环顺序可以是遍及给定仲裁机构仲裁的一组请求器的任何序列。尤其，在流水线公正分层仲裁器中，由于流水线延迟，连续选择特定较低层仲裁机构中的请求器可能使那些请求器在给定时间量内给不出一样多的从公正分层仲裁器输出的取胜请求。有利的是，循环顺序被选择成尽可能多地隐藏流水线延迟。

我们记得，如果特定请求器需要更多的吞吐量，可以简单地在给定仲裁机构中将至少一个请求器位置或“时隙”指定给那个特定请求器。在前面给出的例子中，仲裁机构将两个仲裁“时隙”给予请求器R0，并且将一个仲裁“时隙”给予请求器R2。

在步骤S512中，特定仲裁机构输出指示特定仲裁机构正在仲裁多少个分立请求器和那个请求器发出由特定仲裁机构输出的取胜请求的有效请求位。例如，如果特定仲裁机构正在仲裁12个分立请求器，特定仲裁机构将输出12个位，每个位位置对应于12个请求器之一。除了与发出从特定仲裁机构输出的当前取胜请求的请求器对应的位位置中的位之外，所有位都是“0”。如果没有从特定仲裁机构输出的当前有效取胜请求，所有12个位都是“0”。重复该方法，当请求器作出新请求时，接收它们。

这样，当像所述的仲裁机构的示例那样得到处理时，分层仲裁器的总取胜请求得到公正选择。因此，在特定时间选择每个请求器的可能性不依赖于多产请求器、层次或仲裁机构，只依赖于请求器在特定循环仲裁顺序中的位置。