消息路由方案

摘要

节点阵列中的每个处理器节点具有各自的本地节点地址，并且每个本地节点地址包含地址重要性从最高到最低顺序排列的多个部分。每个节点包括：映射装置，用于将本地节点地址的每个部分映射到各个路由方向，以及切换装置，用于接收含有标识目标节点的目标节点地址的消息。该切换装置包括：用于比较本地节点地址与目标节点地址来识别最重要的非匹配部分的装置；以及用于在本地节点地址与目标节点地址不匹配的情况下，将消息沿映射到最重要的非匹配部分的方向路由到另一节点的装置。

权利要求

1.一种处理器节点阵列，每个节点具有各自的本地节点地址，所述本地节点地址用于在所述阵列中标识所述每个节点，每个本地节点地址包括寻址重要性从最高到最低排序的多个部分，每个节点包括：映射装置，用于将所述本地节点地址的每个部分映射到各自的路由方向；以及切换装置，用于接收具有标识目标节点的目标节点地址的消息，所述切换装置包括：用于将所述本地节点地址与所述目标节点地址进行比较以识别最重要的非匹配部分的装置；

以及用于在所述本地节点地址与所述目标节点地址不匹配的情况下，沿着所述映射装置映射到所述本地节点地址的最重要的非匹配部分的方向将所述消息路由到另一个节点的装置。

2.根据权利要求1所述的阵列，其中所述多个部分中的每一个是一位。

3.根据权利要求1或2所述的阵列，其中所述映射装置包括路由查询表。

4.根据权利要求3所述的阵列，其中所述路由查询表是软件可编程的。

5.根据权利要求1或2所述的阵列，其中所述映射装置被配置为执行路由算法。

6.根据权利要求1所述的阵列，其中每个节点包括至少一个本地处理器，所述切换装置被配置成在所述本地节点地址与所述目标节点地址匹配的情况下，将所述消息路由到所述本地处理器之一。

7.根据权利要求2所述的阵列，其中所述切换装置被配置成每次一位地执行所述比较，并在遇到最重要的非匹配位时中止比较。

8.根据权利要求1所述的阵列，其中所述目标节点地址是所述切换装置将要接收的消息的最前面的部分。

9.根据权利要求2所述的阵列，其中所述切换装置按照从最重要位到最不重要位的顺序接收所述目标节点地址。

10.根据权利要求1所述的阵列，其中所述阵列至少是二维的。

11.根据权利要求10所述的阵列，其中所述阵列至少是三维的。

12.根据权利要求11所述的阵列，其中阵列至少是四维的。

13.根据权利要求1所述的阵列，其中所述切换装置被配置成一旦检测到匹配并在将所述消息路由到处理器之前，丢弃所述目标节点地址。

14.根据权利要求1所述的阵列，其中至少一个节点包括多个处理器，其中所述消息还包括用于标识所述节点内的目标处理器的目标处理器地址，并且其中，所述切换装置被配置成在所述目标节点地址与所述本地节点地址匹配的情况下，将所述消息路由到所述目标处理器。

15.根据权利要求14所述的阵列，其中所述切换装置被配置成在将所述消息路由到所述目标处理器之前，丢弃所述目标处理器地址。

16.根据权利要求1所述的阵列，其中位于至少一个节点处的至少一个处理器包括多个I/O通道，其中所述消息还包括用于标识所述处理器内的目标通道的目标通道地址，并且其中，所述切换装置被配置成在所述目标节点地址与所述本地节点地址匹配的情况下，将所述消息路由到所述目标通道。

17.根据权利要求16所述的阵列，其中所述切换装置被配置成在将所述消息路由到所述目标通道之前，丢弃所述目标通道地址。

18.根据权利要求2所述的阵列，其中所述切换装置被配置成一旦所述目标节点地址中的一个或多个位与所述本地节点地址相匹配则从所述目标节点地址中丢弃所述一个或多个位。

19.一种在处理器节点阵列中路由消息的方法，每个节点具有各自的本地节点地址，所述本地节点地址用于在所述阵列中标识所述每个节点，并且每个本地节点地址包括寻址重要性从最高到最低排序的多个部分，所述方法包括：在节点处接收包括目标节点地址的消息；

将所述本地节点地址与所述目标节点地址进行比较以识别最重要的非匹配部分；以及在所述本地节点地址与所述目标节点地址不匹配的情况下，咨询将所述本地节点地址的每个部分映射到各个路由方向上的映射装置，并且沿着所述映射装置映射到所述本地节点地址的最重要的非匹配部分的方向将所述消息路由到另一节点。

20.根据权利要求19所述的方法，其中所述多个部分中的每一个是一位。

21.根据权利要求19或20所述的方法，其中所述映射装置包括路由查询表。

22.根据权利要求21所述的方法，其中所述路由查询表是软件可编程的。

23.根据权利要求19或20所述的方法，其中所述映射装置被配置为执行路由算法。

24.根据权利要求19所述的方法，其中每个节点包括至少一个处理器，并且所述方法还包括在所述本地节点地址与所述目标节点地址匹配的情况下，将所述消息路由到本地处理器之一。

25.根据权利要求20所述的方法，其中比较的步骤包括：每次一位地执行所述比较，并且在遇到最重要的非匹配位时中止比较。

26.根据权利要求19所述的方法，其中所述目标节点地址是将要接收的消息的最前面的部分。

27.根据权利要求20所述的方法，其中按照从最重要位到最不重要位的顺序接收所述目标节点地址。

28.根据权利要求19所述的方法，其中所述阵列至少是二维的。

29.根据权利要求28所述的方法，其中所述阵列至少是三维的。

30.根据权利要求29所述的方法，其中所述阵列至少是四维的。

31.根据权利要求19所述的方法，还包括：一旦检测到匹配并在将所述消息路由到处理器之前，丢弃所述目标节点地址。

32.根据权利要求19所述的方法，其中至少一个节点包括多个处理器，其中所述消息还包括用于标识所述节点内的目标处理器的目标处理器地址，并且其中，该方法还包括在所述目标节点地址与所述本地节点地址匹配的情况下，将所述消息路由到所述目标处理器。

33.根据权利要求32所述的方法，进一步包括：在将所述消息路由到所述目标处理器之前，丢弃所述目标处理器地址。

34.根据权利要求19所述的方法，其中至少一个节点的至少一个处理器包括多个I/O通道，其中所述消息还包括用于标识所述处理器内的目标通道的目标通道地址，并且其中，该方法还包括在所述目标节点地址与所述本地节点地址匹配的情况下，将所述消息路由到所述目标通道。

35.根据权利要求34的方法，包括：在将所述消息路由到所述目标通道前，丢弃所述目标通道地址。

36.根据权利要求20的方法，包括：一旦所述目标节点地址中的一个或多个位与所述本地节点地址相匹配，则从所述目标节点地址中丢弃所述一个或多个位。

37.一种在n维处理器阵列的节点之间路由消息的方法，其中n是整数，该方法包括：确定所述阵列中维度n的数量；

在维度k＝1...n的每个维度中，确定所述阵列的最大范围L(k)，其中L按节点数进行计量；

沿着维度k＝1...n的每个维度，定义以二进制依次编号的坐标，该坐标覆盖的长度至少为L(k)，使得每个节点由n维的每个维度中的相应的坐标进行描述；

分配m(k)位的地址部分，用于沿着每个维度k＝1...n寻址每个节点，使得m(k)

2 ≥L(k)，并且沿着每个维度k将所述节点的坐标存储在相应的m(k)位地址部分；以及对于所述阵列中每个节点的每个地址部分，将各个第一方向映射到值为0的任意位上，以及将各个第二方向映射到值为1的任意位上；以及通过参考多个所述地址和所述方向来路由消息。

说明书

消息路由方案

技术领域

[0001] 本发明涉及在处理器之间路由消息，特别涉及一种在处理器阵列的各节点间路由消息的方案或协议。

背景技术

[0002] 如图1所示，集成电路1可被构造为处理器核(tile)2的阵列，每个处理器核包括一个独立的处理器4、存储器6和通信器8。多个处理器核2之间通过在芯片1内传输数据和控制消息的内部连线10进行连接。芯片上少量的处理器核通过外部连线12与外部设备耦合。可选地，或者另外，不同芯片上的处理器可以排列在一起来形成一个电路。

[0003] 这种体系结构的优点在于，通过在设计阶段将若干较小的模块化处理器连接起来，厂商可以依据考虑中的应用或设备的处理与存储要求，甚至是它们特殊的成本、功率和区域目标(area target)，容易地创造一种具有特殊性能的芯片或电路。

[0004] 然而，通过阵列路由消息也存在一个困难。消息可能被延迟，可能未按最有效的路径进行路由，或者也可能被死锁。此外，在大的阵列中，路由协议可能会变得复杂而难以使用。

发明内容

[0005] 根据本发明的一个方面，提供了一种处理器节点阵列，每个节点具有一个在阵列中标识自己的各自本地节点地址，每个本地节点地址包括多个寻址重要性(addressing significance寻址有效性)从最高到最低顺序排列的部分，并且每个节点包括：用于将本地节点地址的每个部分映射到各个路由方向的映射装置，以及一个用于接收含有标识目标节点的目标节点地址的消息的切换装置，该切换装置包括：用于比较本地节点地址与目标节点地址以识别最重要的非匹配部分的装置，以及装置，用于在本地节点地址与目标节点地址不匹配的情况下，沿该映射装置映射到本地节点地址的最重要的非匹配部分的方向将消息路由到另一个节点。优选地，但非必要地，每个所述部分是一位。

[0006] 令人惊讶地是，发明人已经发现了通过将路由方向映射到节点地址的各个位上，就可以提供一种有效、快速、易实现的并免死锁的在n维处理器阵列中路由消息的协议。另一优点是，相同的简单方案对于具有任意数量的维度的任意尺寸的阵列都有效。

[0007] 在实施例中，切换装置可以被配置成按每次一位的方式执行所述比较，并在遇到最重要非匹配位时中止比较。目标节点地址可以是切换装置所接收消息的最前面部分。目标节点地址可以被切换装置按从最重要位到最不重要位的顺序进行接收。

[0008] 这些实施例是非常有益的，因为在许多节点处，切换装置在将消息转发到另外一个节点之前仅需要读取该消息的最前面几位。由于地址在消息剩余部分到达前就可以起作用，本技术有助于特快的“虫孔路由”(wormhole routing)。这样切换装置就可以迅速地以最小延迟建立起消息的路由。

[0009] 映射装置可以包括一路由查询表。路由查询表可以是软件可编程的。映射装置可以包括一种路由算法。

[0010] 多个节点可以排列成一个至少两维、至少三维或者至少四维的阵列。

[0011] 每个节点可以包含至少一个本地处理器，并且切换装置可以被配置成在本地节点地址与目标节点地址匹配的情况下，将消息路由到本地处理器之一。切换装置可以被配置成一旦检测到匹配并在将消息路由到一个处理器之前，丢弃目标节点地址。

[0012] 至少一个节点可以包括多个处理器，此外消息还可以包括一个标识节点内目标处理器的目标处理器地址，并且切换装置可以被配置成在目标节点地址与本地节点地址匹配的情况下，将消息路由到目标处理器。切换装置可以被配置成在将消息路由到目标处理器之前，丢弃目标处理器地址。

[0013] 在至少一个节点处的至少一个处理器可以包括多个I/O通道，消息可进一步包括一个标识处理器内目标通道的目标通道地址，并且切换装置可以被配置成在目标节点地址与本地节点地址匹配的情况下，将消息路由到目标通道。

[0014] 切换装置可以被配置成一旦那些位与本地节点地址相匹配，就从目标节点地址中丢弃一位或多位。例如，节点地址中涉及一个特定维度的部分，可以在消息位置被缩小到该维度内的具体坐标时被丢弃。

[0015] 根据本发明的另一方面，提供了一种在处理器节点阵列中路由消息的方法，每个节点具有一个在阵列中标识自己的各自本地节点地址，并且每个本地节点地址包括多个寻址重要性从最高到最低顺序排列的部分，该方法包括：在一个节点处接收一条包含目标节点地址的消息；比较本地节点地址与目标节点地址来识别最重要的非匹配部分；以及在本地节点地址与目标节点地址不匹配情况下，咨询将本地节点地址的每个部分映射到各个路由方向上的映射装置，并且将消息(朝着由该映射装置映射到本地节点地址中最重要的非匹配部分的方向)路由到另一节点。

[0016] 根据本发明的另一方面，提供了一种在n维处理器阵列的各节点之间路由消息的方法，其中n是一个整数，该方法包括：确定阵列中维度n的数量；在k＝1...n的每个维度上，确定阵列的最大范围L(k)，其中L按节点数进行计量；沿着k＝1...n的每个维度，定义按二进制依次编号的坐标，该坐标覆盖的长度至少为L(k)，使得每个节点通过在n维的每个维度中的各个坐标进行描述；沿着k＝1...n的每个维度，分配m(k)位的地址部分来m(k)定位每个节点，使得2 ≥L(k)，并且在各个m(k)位的地址部分沿着每个维度k存储节点的坐标；对于阵列中每个节点的每个地址部分，将一个独立的第一方向映射到值为0的任意位上以及将一个独立的第二方向映射到值为1的任意位上；以及通过参考多个所述地址与所述方向来路由消息。

[0017] 根据本发明的另一方面，提供了一种为n维处理器阵列的节点分配地址的计算机程序产品，其中n是一个整数，该计算机程序包括用于执行下列步骤的代码：确定阵列中维度n的数量；在k＝1...n的每个维度中，确定阵列的最大范围L(k)，其中L按节点数计量；沿着k＝1...n的每个维度，定义按二进制依次编号的坐标，该坐标覆盖的长度至少为L(k)，使得每个节点可以通过一个在n维的每个维度上的各个坐标进行描述；沿着k＝1...n的每个维度，分配m(k)位的地址部分来定位每个节点，使得2m(k)≥L(k)，并且在各个m(k)位的地址部分沿着每个维度k存储节点的坐标；以及对于阵列中每个节点的每个地址部分，将一个独立的第一方向映射到值为0的任意位上以及将一个独立的第二方向映射到值为1的任意位上。

具体实施方式

[0018] 为了更好地理解本发明，并表明其是如何实现的，现在通过实例参考相应的附图，附图中：

[0019] 图1示出一个处理器阵列的实例；

[0020] 图2是一个处理器节点的示意图；

[0021] 图3示出一个适用于路由的消息格式；

[0022] 图4示出一个一维处理器阵列；

[0023] 图5示出一个二维4x4处理器阵列；

[0024] 图6示出一个二维3x3处理器阵列；

[0025] 图7示出一个三维3x3x2处理器阵列；

[0026] 图8示出一个四维2x2x2x2处理器阵列；

[0027] 图9是一个表示路由方法的流程图；以及

[0028] 图10是一个表示分配地址与路由方向的方法的流程图。

[0029] 图2示意性地示出了根据本发明的一个示例性实施例的处理器核2’。多个这样的核排列在一起形成一个组合结构或者阵列，并且阵列中的每个核2’包括一个系统切换装置16和多个双向系统链路18，每一个该链路均连接到阵列内的另一个核。系统链路18的一些或者全部均可以在各个方向上连接各个其他处理器，并且/或者系统链路18中的一些可以在同一个方向上连接至同一个处理器，使得一组系统链路18可以有效地作为一个具有更大容量的链路。该系统链路18可以是片上的或者是片间的。每个系统切换装置16限定了阵列内的一个节点。

[0030] 在本实例中，核2’包括4个处理器4。每个处理器4可以具有多个不同的、可通过双向通道链路22和一个处理器切换装置14访问的I/O通道。处理器切换装置通过一个或多个双向处理器链路20连接到系统切换装置。该核2’还包括一个通过系统切换装置16可访问的路由查询表，后文将详细讨论。此外该核2’还可以包括外部链路和存储器，如RAM和ROM(图中未示出)。

[0031] 在操作中，系统切换装置16接收来自一个本地处理器(即相同节点的一个处理器)或者一个不同节点的处理器的一条输入消息26。每个节点被分配一个用于在阵列内标识自己的地址，每个处理器被分配一个用于在各个节点内标识自己的地址，并且每个通道被分配一个用于在各个处理器内标识自己的地址。地址包括地址数据的部分总量(component quanta)，在大多数情况下即单个的位。如图3所示，该消息包括一个报头27，该报头包括一个指定目标节点地址的目标节点部分28，一个指定目标处理器地址的目标处理器部分30，和一个指定目标通道地址的目标通道部分32。该消息还包括一个有效载荷34。在一个优选的实施例中，报头是2个字节(16位)长，包含8位的目标节点部分，4位的目标处理器部分以及4位的目标通道部分。这样允许上限到256个节点，4096个处理器与
65536个通道，每个节点有16个处理器，每个处理器有16个通道。

[0032] 系统切换装置16将它的本地节点地址(即它自己的节点地址)与消息的目标节点地址进行比较。如果匹配，则系统切换装置检查消息的目标处理器地址并将其路由到对应的处理器切换装置14。处理器切换装置14然后检查消息的目标通道地址并将其路由到对应的通道。注意在消息最终被发送到一个处理器4之前，报头27可以被丢弃，使得接收软件有利地从不需要看到报头。报头可以被部分地丢弃，使得节点地址部分28与处理器地址部分可以在消息被路由到处理器切换装置14前被丢弃，并且通道地址部分32可以在消息被路由到处理器切换装置14之后但是在消息被路由到处理器4之前被丢弃。

[0033] 但是如果不匹配，系统切换装置16接收了一个去往另一个节点的消息，并且必须决定往哪个方向转发它，即在哪个系统链路18上转发消息以及接下来哪个节点应当接收它。记住阵列可以包括数十、数百甚至数千个节点，因此一个消息在到达目标之前，可能不得不在诸多节点之间进行中继。于是找出在阵列内最有效的路由不是一个简单工作。

[0034] 根据本发明，这要通过咨询查询表24来实现。查询表24包括多个可能的路由方向，所述路由方向按照本地节点地址的各个位排列成表格形式，一个方向映射到每个独立的位。基于节点本地地址与消息目标地址之间的比较，系统切换装置16识别一个非匹配的位并查阅查询表24来确定哪个方向映射到该位上。

[0035] 优选地，查询表是软件可编程的，使得用户可以把任意数量的处理器按照模块形式组合在一起，然后在必要时对路由进行编程。可选地，如果阵列是由供应商提前设计好的，该查询表可以替换为对该阵列的硬件编程。

[0036] 图2中仅示出了一个查询表，但在实施例中每个节点上可以提供多个这样的查询表。例如，每个系统链路可以有一个查询表。这样有利于加快消息路由，因为减少了消息对查询表资源的竞争，从而可以允许多个消息同时进行路由。

[0037] 在一个尤为有利的实施例中，系统切换装置16逐位地比较本地节点地址与目标节点地址，即每次比较一位，并且一旦发现最前面的非匹配位就中止比较。这使得路由特别快，因为在大多数节点中系统切换装置16在将消息转发到另一个节点前仅需要读取消息目标地址的一小部分。有时该切换装置仅需要读取1位。优选地，系统切换装置16从比较最重要的位开始，然后比较次重要的位，以此类推直到发现一个不匹配的位。在一个优选的实施例中，目标节点地址的最重要的位被正好放在报头27的开始处，使得路由方向常常仅通过读取消息的最前面的几位就可确定，有时甚至仅需读取第1位。

[0038] 本技术有助于特别快的“虫孔路由”，因为地址在消息剩余部分到达前就可以起作用。这样系统切换装置16就可以迅速地以最小延迟建立起消息的路由。

[0039] 路由查询表的应用通过参考图4中的实例被进一步详细说明，该图示出了根据本发明的一个实施例的简单一维阵列。

[0040] 在本实例中，每个核2’仅包括一个单独的处理器4，因此处理器地址与节点地址相同。每个核还包括一个路由查询表24与一个系统切换装置16。此外，由于阵列是一维的，每个核2’至多与两个系统链路18相连。为了简洁，诸如处理器切换装置14、处理器链路20与通道链路22等细节未包括在内。

[0041] 为了容纳8个节点，每个节点被分配一个3位的地址。因此，每个查询表24有三个条目，每个条目对应节点地址的每个位。每个条目可以指定两个可能的路由方向之一，向上(U)与向下(D)。查询表如下：

[0042] 节点 节点地址 查询表

[0043] N1 000 DDD

[0044] N2 001 DDU

[0045] N3 010 DUD

[0046] N4 011 DUU

[0047] N5 100 UDD

[0048] N6 101 UDU

[0049] N7 110 UUD

[0050] N8 111 UUU

[0051] 因此在本实例中，最重要的位标识了阵列的具体一半。在给定的一半中，次重要的位标识了阵列中的具体四分之一，而在给定的四分之一中，最不重要的位缩小到了一个具体节点。因此，如果一个消息在错误的一半中开始，相应的系统切换装置16仅通过本地地址与目标地址中最重要的位的一次比较就可以发现。参考查询表24，系统切换装置然后确定哪个方向映射到最重要的位，以及因此在哪个方向上路由消息以将其移向正确的一半。一旦消息是在正确的一半，相关的系统切换装置16必须执行至少两次比较，一是在最重要的位之间的比较，一是在次重要的位之间的比较。在次重要的位之间的比较告知系统切换装置16消息是否在错误的四分之一，并且如果是，则告知需要在哪个方向路由消息以将其移向正确的四分之一。然后应用类似的原理，用于在一旦消息被路由到正确的四分之一，则使用最不重要的位找到最终的目标节点。

[0052] 出于说明的目的，考虑从节点N7到节点N2路由一个消息。在N7，N6与N5的任一节点中，系统切换装置仅比较最重要的位，并且由于它们不匹配，则参考查询表24来决定消息应当被向上路由。注意到在节点N7-N5，通过仅检查所收到的消息的单个位就可以快速地进行路由消息。在节点N4与N3，系统切换装置16必须凭借比较次重要的位来决定消息应当仍旧被向上路由，直到其到达目标节点N2。

[0053] 当然要注意到最重要的位到最不重要的位命名的顺序仅是一个常规的约定。但是，为了本发明的目的，“重要”的含义被关联到节点在阵列内的位置，因此最重要的位将阵列分成两部分，次重要的位将这两部分分别再分成两个子部分，以此类推。也就是说，地址位的从最高到最低的重要性顺序对应于阵列的逐步缩小的空间划分。重要性顺序既不意味着这些位在消息的地址部分的排列顺序，也不意味着其在任何存储器等中的排列顺序。这些因素对于本发明并非必需的(即使如上面论述到的，在优选的实施例中最重要的位被放在报文27的开始处)。最重要的位到最不重要的位按照从左到右的形式读取，纯粹是为了文字表达的需要。

[0054] 本方案的速度与简单性在更复杂的多维阵列中优势尤其显著。图5示意性示出了一个将本发明扩展到4x4二维阵列的示例。为了方便，每个核2’仅用其独立的系统链路18与独立的节点地址0000到1111来表示。

[0055] 每个节点地址可以被视为包括两个不同部分：一个指定了在左右方向上坐标的部分，和一个指定了在上下方向上地址的坐标的部分。在本例中，两个最重要的位在阵列内从左到右记为00，01，10，11，两个最不重要的位在阵列内从上到下记为00，01，10，11。因此路由查询表将两个额外的方向，向左(L)和向右(R)，映射到节点地址。每个节点的查询表如下：

[0056] 节点 节点地址 查询表

[0057] N1 0000 RRDD

[0058] N2 0001 RRDU

[0059] N3 0010 RRUD

[0060] N4 0011 RRUU

[0061] N5 0100 RLDD

[0062] N6 0101 RLDU

[0063] N7 0110 RLUD

[0064] N8 0111 RLUU

[0065] N9 1000 LRDD

[0066] N10 1001 LRDU

[0067] N11 1010 LRUD

[0068] N12 1011 LRUU

[0069] N13 1100 LLDD

[0070] N14 1101 LLDU

[0071] N15 1110 LLUD

[0072] N16 1111 LLUU

[0073] 在应用中，系统切换装置16首先接收一个消息并比较该消息目标节点地址的最重要的位与本地节点地址的最重要的位。通过确定最重要的位是否匹配，告知该切换装置16消息是否在该阵列左右方向上正确的一半内，即是在最左的两列还是最右的两列。如果不是，通过映射到最重要的位的路由方向，该查询表告知切换装置按哪个方向进行路由从而将消息传送到正确的一半。一旦在正确的一半内，次重要的位就可以缩小到正确的列。一旦在正确的列内，就将相同的处理方式应用于上下方向上最不重要的两位。

[0074] 注意到这仅是一个关于哪一维的地址位被设定为最重要和最不重要的术语。也就是说，本发明同样可以很好地读取指定上下方向的位来首先为消息找出正确的行，而后读取在左右方向上的一对(pair)位来缩小到正确的列。为了本应用的目的，最重要的维简单地被作为第一地址部分来使用，最不重要的维作为最后一部分来使用。不同维的各部分的位也可以以交叉的方式使用和/或排列。本质上，这些及其他变动并不会改变本发明的基本原理，因为本质上讲，从最高到最低的地址位的重要性顺序意味着阵列的逐步缩小的空间划分。

[0075] 图6示出了一个3x3二维阵列的示例。还是为了方便，每个核2’仅用它独立的系统链路18与其独立的节点地址0000到1010表示。本例示出了本发明如何在不规则的阵n列或不具有方便地长度2(n是整数)大小的边的阵列中提供路由。纯粹出于说明的目的，还给出了冗余节点地址的假设位置2”。3x3阵列的查询表如下：

[0076] 节点 节点地址 查询表

[0077] N1 0000 RRDD

[0078] N2 0001 RRDU

[0079] N3 0010 RRUx

[0080] N4 0100 RLDD

[0081] N5 0101 RLDU

[0082] N6 0110 RLUx

[0083] N7 1000 LxDD

[0084] N8 1001 LxDU

[0085] N9 1010 LxUx

[0086] 现有节点2’的地址和查询表与图5中4x4阵列中的相应节点相同，除了由于冗余节点地址，查询表中的一些条目因为没有可能被咨询到而实际上成为了“无关的(don’t care)”(x)。因此可以看到一个3x 3阵列如何可以有效地从一个4x4网格“裁剪”而来。相同的原理可以用于寻址(address，定位)不规则形状的阵列。

[0087] 图7示出了一个将本发明扩展到3x3x2三维阵列的示例。它创建了两个新的方向，向前(F)和向后(B)。对于利用附加到节点地址上的一个额外的位来指定在向前-向后方向上的节点位置，本发明的原理是完全一致的。查询表如下：

[0088] 节点 节点地址 查询表

[0089] N1 00000 RRDDB

[0090] N2 00010 RRDUB

[0091] N3 00100 RRUxB

[0092] N4 01000 RLDDB

[0093] N5 01010 RLDUB

[0094] N6 01100 RLUxB

[0095] N7 10000 LxDDB

[0096] N8 10010 LxDUB

[0097] N9 10100 LxUxB

[0098] N10 00001 RRDDF

[0099] N11 00011 RRDUF

[0100] N12 00101 RRUxF

[0101] N13 01001 RLDDF

[0102] N14 01011 RLDUF

[0103] N15 01101 RLUxF

[0104] N16 10001 LxDDF

[0105] N17 10011 LxDUF

[0106] N18 10101 LxUxF

[0107] 因此在操作中，消息首先被路由到如图5和图6所描述的正确的列和行。系统切换装置16进而进行本地地址与目标地址的最不重要的位的比较。这样会告知切换装置16消息是否在正确的平面内(即前面或后面)。如果不是，则切换装置16参考路由表来决定按照哪个方向路由消息以到达正确的平面。

[0108] 根据本发明的一个实施例，当消息的位置被缩小到一个具体维内的具体坐标上时，与特定维相关的节点地址部分可以被丢弃。因此以图7中阵列为例，一旦消息已经路由到正确的列，最重要的位与次最重要的位就不再需要且可以被丢弃了。类似地，一旦消息已经路由到正确的行，那么第三最重要的位与第四最重要的位就不再需要且可以被丢弃了。

[0109] 当消息被路由时，个别的位甚至可以被丢弃，即一旦匹配就丢弃最重要的位，随后一旦匹配就丢弃次重要的位，以此类推。

[0110] 丢弃目标地址中的某些部分或者个别位提高了路由速度，因为需要进行位比较的次数减少了。但是为了允许丢弃某些部分或者位，必须采用某种方法以基于缩短的地址来路由消息。一种实现该目的的方法就是为每个系统链路18提供分离的查询表24，位可以从某些链路的查询表中去掉。例如，再次参考图7的例子，如果消息首先在左右方向上进行路由，则链路18在上下方向和前后方向就不需要通过任何位来比较原始地址的前两个最重要的位。类似地，如果消息随后在上下方向上路由，则向前-向后方向链路18的查询表仅需要包含单个位。这也降低了某些查询表的大小，节省了资源。

[0111] 本发明也可以扩展到四维或者更多维。当然，阵列仍然存在于三个空间维——术语“维”在这里简单地表示一个“自由度”。因此，对于有四维或者更多维的阵列来说，在阵列内至少有一个节点连接至四个或多个其他节点。这就意味着有四个或者多个可能的方向供消息进行路由。

[0112] 图8示出了一个本发明扩展到2x2x2x2四维超立方体的示例，通常所说的octachoron。N1...N16的每个节点连接至其他四个节点，因此在任意给定的节点均有四个自由度来路由消息。

[0113] 如图7中示例，存在左右、上下、前后三个自由度。图8的示例则提供了另外的链路18来增加一个第四自由度来路由消息。按随意的术语，创建的两个新方向在这里记为黄(Y)与绿(G)，黄是绿的相反方向。每个节点的路由表如下：

[0114] 节点 节点地址 路由表

[0115] 1 0000 RDBY

[0116] 2 0001 RDBG

[0117] 3 0010 RDFY

[0118] 4 0011 RDFG

[0119] 5 0100 RUBY

[0120] 6 0101 RUBG

[0121] 7 0110 RUFY

[0122] 8 0111 RUFG

[0123] 9 1000 LDBY

[0124] 10 1001 LDBG

[0125] 11 1010 LDFY

[0126] 12 1011 LDFG

[0127] 13 1100 LUBY

[0128] 14 1101 LUBG

[0129] 15 1110 LUFY

[0130] 16 1111 LUFG

[0131] 图9是根据本发明的方法的流程图。当一个节点的系统切换装置16接收到消息的目标节点地址的第一位时，该方法从步骤100开始。为了便于描述，这里将任何给定时刻考虑中的地址位记为第i位。在步骤102，目标节点地址的第i位与本地节点地址的第i位进行比较。在步骤104，该方法根据目标地址的第i位是否与本地地址匹配来分支。如果它们不匹配，该方法继续执行步骤106，通过咨询查询表来决定基于第i位所映射的方向。在步骤108，消息在该方向上进行路由。然而，如果目标地址与本地地址的第i位匹配，该方法改为执行步骤110，在该步骤中确定节点地址的最后一位是否已经到达。如果已经达到，则消息已经到达了目的地，并且该方法分支到步骤112，在该步骤中将消息路由到一个本地处理器。如果最后一位未被获取，则该方法继续步骤114来考虑下一个地址位，并从步骤102开始重复本方法。

[0132] 根据以上描述，也出现了一种模式用于对节点进行寻址并分配相应查询表的优选方法。该模式通过参考图10的流程图来描述。在步骤200，确定了阵列的维数n。在步骤202，对于k＝1...n的每个维度，确定阵列的最大范围L(k)，其中L按节点数计量。在步骤204，在k＝1...n的每个维度上定义了坐标。坐标按二进制依次编号，该坐标覆盖的长度至少为L(k)。于是每个节点的位置可以通过一个在n维的每个维度上的各个坐标进行描述。在步骤206，沿着k＝1...n的每个维度，分配m(k)位的地址部分来寻址每个节点，限m(k)
制条件为2 ≥L(k)，并且沿着维度k的节点的坐标可以这样被存储在各个m(k)位地址部分。在步骤208，通过将方向映射到节点地址位，得到每个节点的查询表。对于阵列中每个节点的每个地址部分，这包括将各个第一方向(例如右、下、后、黄)映射到值为0的任意位上，且将各个第二方向(例如左、上、前、绿)映射到值为1的任意位上。

[0133] 例如，参照图7，地址与相应的查询表如下分配。第一，注意到阵列是三维的并有最1 2
大范围为3x3x2的节点。三个节点的一边需要两位地址部分，因为2 ＜3＜2。两个节点的一边仅需要一位地址部分。因此该阵列采用五位地址来定位节点，其中两个最重要的位用于在左右方向上定位节点，第三和第四最重要的位用于在上下方向上定位节点，最不重要的位则用于在前后方向定位节点。为了得出查询表，0和1在两个最重要位上分别被映射到右和左，在第三到第四最重要的位上分别映射到下和上，在最不重要的位上分别映射到后和前。

[0134] 上述实施例仅通过示例方式进行描述。在其他实施例中，其他的定位模式对所属领域人员来说是显而易见的。此外，从最重要的位到最不重要的位的排列顺序可以改变，使得消息首先按面、其次按行、再次按列或者按行、然后按面、然后按列等顺序进行路由。此外，路由查询表可以被次优选的方式如路由算法所取代。其他配置也可以被本领域技术人员所实施，例如不同大小、形状和维数的阵列，包括未形成方便的几何形状的不规则阵列和树形结构的阵列。本发明的范围不限于所描述的实施例，其仅由权利要求限定。