信息处理系统、信息处理装置、信息处理装置的控制方法、信息处理装置的控制程序以及计算机可读记录介质

摘要

本发明涉及信息处理系统、信息处理装置、信息处理装置的控制方法、信息处理装置的控制程序以及计算机可读记录介质。在信息处理装置相互多维地连接而成的信息处理系统中，在信息处理装置中进行以下控制：对发出数据的维度的发送目的地和本装置的同维度的位置进行比较，在该比较的结果为，本装置的位置是前一台信息处理装置的位置的情况下，变更该数据所属的虚拟通道。

说明书

技术领域

本发明涉及信息处理系统，涉及例如多个信息处理装置相互多维连 接的信息处理系统、信息处理装置、信息处理装置的控制方法、信息处 理装置的控制程序以及保存控制程序的计算机可读记录介质。

背景技术

多个信息处理装置相互连接的信息处理系统被称作并行计算机系 统。在并行计算机系统中，作为连接多个信息处理装置的网络，最理想 的方式之一是各信息处理装置与系统上的其他所有信息处理装置一一 对应地连接的、被称作全连接(full connection)的方式。然而，在全 连接方式中，能够想到将各信息处理装置连接时的电缆的成本会增加， 电缆布线变得复杂之类的问题。因此，认为在具备非常多的信息处理装 置的系统中应用全连接方式是比较困难的。

作为其代替方案，当前被广泛使用的方式是，利用多维环、多维网 格之类的拓扑结构来形成网络的方式。该方式中，对一个信息处理装置 一一对应地连接多个信息处理装置，并连续地实施该连接方法。其结果， 使系统中所包含的所有信息处理装置相互连接。根据该方式，通过在信 息处理装置间经由其他信息处理装置，从任意的信息处理装置最终能够 访问系统中所包含的所有的信息处理装置。即、在理论上，能够从任意 一个信息处理装置对系统上的所有信息处理装置进行访问。

然而，在利用多维环、多维网格之类的拓扑结构的方式中，所有的 信息处理装置并不是一一对应地连接。因此，能想到下述问题。即，对 于从某个信息处理装置向其他信息处理装置转发数据的最短路径，在全 连接方式的情况下是一条，但是在利用多维环、多维网格之类的拓扑结 构的情况下，信息处理装置间的最短路径存在多条。因此，需要用于决 定从多条路径中采用哪条路径的路由算法。

专利文献1：日本特表2004-527176号公报

专利文献2：日本特开平08-185380号公报

专利文献3：日本特开平07-191947号公报

专利文献4：日本特开平06-266684号公报

专利文献5：日本特开平10-021208号公报

专利文献6：美国专利第6,674,720号

非专利文献1：″Age-based packet arbitration in large radix k-ary  and n-cubes″，Denis Abts and Deborah Weisser，SC07，2007

非专利文献2：″Routing and flow control in systems network  algorism″，V. Ahuja，IBM journal，1978

非专利文献3：″Flexible oblivious router algorism″，U.Par et. al.，IBM journal，1995

非专利文献4：“コンピユ一タア一キテクチヤ定量的アプロ一チ 第4版”、著者：John L.Hennessy and David A.Patterson、出版社： 株式会社 翔泳社、付録E、E-3 P22～概要、E-4 P30～トポロジ一関 連、E-5 P45～ル一テイング関連、E-6 P57～スイツチのマイクロア 一キテクチヤ関連

发明内容

本实施例的目的在于，在信息处理装置相互多维连接的信息处理系 统中缩短数据的发送等待时间。

各信息处理装置对发送数据的维度中的发送目的地和本装置的同 维度的位置进行比较，在发送目的地比较的结果是，本装置的位置是成 为数据的上述维度中的发送目的地的前1台信息处理装置的位置的情况 下，变更数据的虚拟通道。

根据本发明所公开的内容，能够在信息处理装置相互多维连接的信 息处理系统中，有效利用虚拟通道来缩短数据的发送等待时间。

附图说明

图1是用于对实施例1的信息处理系统的整体构成例进行说明的框 图。

图2是用于对图1中各信息处理装置的内部构成例进行说明的框 图。

图3是用于对由图2中的路由控制器实施的、基于维序路由方式的 维度控制方法进行说明的处理流程图。

图4是用于对由图2中的路由控制器实施的虚拟通道控制方法进行 说明的处理流程图。

图5是对图2中的路由控制器的构成例进行说明的框图。

图6是用于举例对图4示出的虚拟通道控制方法进行说明的图(之 一)。

图7是用于举例对图4示出的虚拟通道控制方法进行说明的图(之 二)。

图8是用于对通过实施虚拟通道控制方法而获得的作用效果进行说 明的图(之一)。

图9是用于对通过实施虚拟通道控制方法而获得的作用效果进行说 明的的图(之二)。

图10是用于对虚拟通道控制方法的动作流程具体地进行说明的处 理流程图。

图11是用于对能在实施例1的信息处理系统中应用的数据包的构 成例进行说明的图。

图12是用于对图2中的路由控制器所具备的交叉开关接口的构成 例进行说明的图(之一)。

图13是用于对图2中的路由控制器所具备的交叉开关接口的构成 例进行说明的图(之二)。

图14是用于对图2中的路由控制器的构成例进行说明的图。

图15是用于对图2中的信息处理部的构成例进行说明的框图。

图16是用于对用于验证应用了实施例1的情况下的效果的模拟结 果进行说明的图。

图中标号说明

4 路由控制器

5 信息处理部

41 交叉开关

42、43、44、45 各方向的交叉开关接口

48 CPU交叉开关接口

402 包头分析部

404、405 缓冲区

408 包头发送部

VC0、VC1 虚拟通道

P₁₁、P₁₂、P₂₁、P₁₂ 数据收发端口

具体实施方式

图1是实施例1中的信息处理系统的整体构成图。在图1中，信息 处理系统具有各节点N连接成2维环状的拓扑。即图1中，位于左右端 部的节点分别通过(0)、(1)、...、(5)的相同数字连接。同样，位于 上下端部的节点分别通过(10)、(11)、...、(15)的相同数字连接。其 结果，各节点连接成2维环状。

这里，每个节点N都是信息处理装置。在图1的构成例的情况下， 节点N沿着+/-x方向(图中横向)排列有6个，沿着+/-y方向(图中纵 向)排列有6个，共计包括36个节点N。另外，在图1中，右方向为 +x方向，下方向为+y方向。各节点N与在+/-x方向、+/-y方向上相互 邻接的节点N之间，通过物理通道彼此连接。各物理通道为双向通道。 这里，如图1所示，36个节点N当中，位于-x和-y方向的角的节点N₀₀(图1中左上角的节点N₀₀)的坐标为原点(0，0)。同样，位于+x和 +y方向的角的节点N₅₅(图1中右下角的节点N₅₅)的坐标为(5，5)。 同样，位于+x和-y方向的角的节点N₅₀(图1中右上角的节点N₅₀)的 坐标为(5，0)。同样，位于-x和+y方向的角的节点N₀₅(图1中左下 角的节点N₀₅)的坐标为(0，5)。即相对于位于原点的节点N而言， 在+x方向位于第n个、在+y方向位于第m个的节点N的坐标为(n， m)。例如在图1中，相对于位于原点的节点N₀₀而言，在+x方向位于 第3个、在+y方向位于第2个的节点N₃₂的坐标为如图所示的(3，2)。 另外，在图1中，各节点的坐标被标记在表示该节点的正方形的右上角 的外侧部分。

图2是用于对各节点N的内部构成例进行说明的框图。如图2所示， 节点N具备路由控制器4和信息处理部5。路由控制器4对由信息处理 部5生成的数据包、或者从邻接节点转发来的数据包进行维度控制以及 虚拟通道控制。关于维度控制以及虚拟通道控制将在后面进行说明。这 里，连接节点间的物理通道在节点N内部中被连接于路由控制器4。另 外，信息处理部5具有CPU(中央处理单元；Central Processing Unit)， 在后面将结合图15进行说明。

路由控制器4实施被称作所谓的维序路由的路由方式。下面将对维 序路由进行说明。如图1所示，设想多个信息处理装置、即节点N被多 维、在实施例1中是被2维连接的信息处理系统。所谓的维序路由，是 指在节点被多维连接的信息处理系统中，按照遵循规则的顺序使各维度 的坐标依次与发送目的地的坐标一致这样的算法。对于上述遵循规则的 顺序，例如在连接成上述2维环状的信息处理系统的情况下为x、y的 顺序。这里，设想多个信息处理装置连接成如实施例那样的2维环状的 信息处理系统，并且出发点、即信息的发送源的坐标为(0，0)、到达 点即信息的发送目的地的坐标为(2，1)的情况。在该情况下，以(0， 0)→(1，0)→(2，0)→(2，1)的顺序转发数据包。

即，首先，沿着在x坐标上配置的节点转发数据包。这里，在节点 间依次转发数据包，直到保持数据包的节点的x坐标值与数据包的发送 目的地的x坐标一致。在保持数据包的节点的x坐标值与数据包的发送 目的地的x坐标一致了的情况下，该节点向y轴方向转发数据包。然后， 沿着在y轴方向配置的节点转发数据包。这里，在节点间依次转发数据 包，直到保持数据包的节点的y坐标值与数据包的发送目的地的y坐标 一致。即、在某个维度上，在同维度上的节点间依次转发数据包，直到 保持数据包的节点的位置与发送目的地位置一致。接着，变更维度，在 变更后的维度上，在同维度上依次转发数据包，直到保持数据包的节点 的位置与同维度的发送目的地位置一致。根据该顺序，在各维度上保持 数据包的节点的位置依次与发送目的地位置一致。最终，在所有维度上， 保持该数据包的节点的位置与发送目的地位置一致。即数据包到达发送 目的地的节点。

该路由算法的优点在于，通过包含后述的日期变更线所涉及的控 制，在理论上不会引起由于数据的转发路径成为闭环结构而出现的死 锁、即成为无死锁。

另外，图2中的P₁₁、P₁₂、P₂₁、P₂₂分别表示后述的收发端口。

图3是对实施例1中的、用于进行维序路由的维度控制方法进行说 明的流程图。

图3中，在步骤S1中，在以i维度发送数据包的情况下，从邻接的 节点接收到数据包的节点，判定数据包是否已到达i维度的发送目的地。 在位于i维度的发送目的地的节点以外的节点接收到数据包的情况下， 该节点沿着与接收到数据包的维度相同的维度发送数据包。即，该情况 下，当数据包沿着x轴被转发过来时，接收到该数据包的节点发送数据 包的维度继续是x轴。

在步骤S1中，各节点从所接收到的数据包的包头读取数据包的x轴 的发送目的地坐标。另外，关于数据包的构成例，将结合图11在后面 进行说明。并且，将所读取的数据包的x轴的发送目的地坐标与本装置 的x坐标进行比较。在比较的结果是数据包的发送目的地x坐标与本装 置的x坐标一致的情况下(步骤S1的是)，数据包在当前时刻到达x轴 的发送目的地。因此，下一个维度，为了到达(i+1)维度、例如y轴 的发送目的地，将进行数据包的转发的维度变更成(i+1)维度、即y 轴(步骤S2)。另一方面，在步骤S1的判定结果为否的情况下，由于 数据包尚未到达x轴的发送目的地，因此为了到达x轴的发送目的地， 接收到数据包的节点继续将x轴维持成进行该数据包的转发的维度(步 骤S3)。

这里，维序路由的算法如上述那样具有无死锁这样的优点，另一方 面，从通信效率这样的观点考虑的话仍有研究的余地。即、在应用了维 序路由的情况下，在实际运用时，与从x轴向y轴以跨维度的方式进行 的转发相比，如上述的例所示那样在沿x轴、y轴等轴一直前进的方式 的通信被认为相当多。其结果，能够想到下述情形，即、节点间在对所 接收到的数据包进行临时保存的缓冲区的使用率上出现不均，发生数较 少的、跨轴的方式的转发会阻碍直线前进的方式的转发。在实施例1中， 采用具有无死锁这一特点的维序路由，同时使系统整体的通信效率提 高。

图4是用于对实施例1的虚拟通道控制方法进行说明的流程图。

图4中，节点在发出数据包时，判定所发出的数据包是否超过了日 期变更线(步骤S11)。这里，所谓的日期变更线，按每个维度决定，设 于各维度的规定的节点间。所谓的各维度的规定的节点间，例如在如图 1所示的信息处理系统的情况下，是指左右端的节点在(0)、(1)、(2)、...、 (5)分别相互连接的部分。而且，同样，也指上下端的节点在(10)、 (11)、(12)、...、(15)分别相互连接的部分。所谓的日期变更线，如 图1示出的信息处理系统那样，在连接成环状的信息处理系统中，在实 施上述维序路由时，为了实现无死锁而被设置。即，若转发数据包的路 径是维度被变更的机会较少的路径，则在同一维度转发数据包期间，存 在发生死锁的可能性。在如上述那样转发数据包的路径是维度被变更的 机会较少的路径的情况下，为了在同一维度转发数据包期间使产生虚拟 通道的变更而设置日期变更线。其结果，在实施维序路由的基础上，能 够实现无死锁。

这里，对虚拟通道进行说明。例如在如图1示出的信息处理系统那 样的、节点连接成环状的结构中，节点间在物理上通过1个通道连接。 在实施例1中，在各节点设置多个缓冲区，对多个缓冲区的每一个分配 虚拟通道。其结果，能够获得如下效果，即节点间通过与上述多个缓冲 区数目相同的多个虚拟通道而被连接。

对上述死锁进行说明。在如图1示出的信息处理系统那样的连接成 环状的结构中，在转发数据包时，有时特定的多个节点会成为闭环结构。 在特定的多个节点成为闭环结构的情况下，有时会在各节点所具有的一 个虚拟通道的所有缓冲区中保存有数据包，从而成为没有空置的状态。 在各节点所具有的一个虚拟通道的所有缓冲区中保存有数据包，从而没 有空置的状态下，各节点发出数据包的接收侧节点所具有的上述一个虚 拟通道的缓冲区中无空置。因此，各节点无法发出保存在上述一个虚拟 通道的缓冲区中的数据包。将这种状态称为死锁。通过上述日期变更线 的功能，在同一维度转发数据包期间，若超过日期变更线则发生虚拟通 道的变更。通过虚拟通道的变更，上述闭环结构中包含的各节点所具有 的缓冲区中、与上述无空置的缓冲区不同的虚拟通道的缓冲区被使用。 由此，若使用与无空置的缓冲区不同的虚拟通道的缓冲区，则该不同的 虚拟通道的缓冲区中有空置，节点能够向接收节点的该缓冲区的空置发 出数据包。因此上述死锁不会发生。

回到图4的说明，在S11中，当节点接收到数据包时，判断是否是 如下情况，即该节点是与日期变更线邻接的节点、且发出数据包的方向 是超过日期变更线的方向。在判断的结果为，该节点是与日期变更线邻 接的节点、且发出数据包的方向是超过日期变更线的方向的情况下，则 步骤S11的判定结果为是。在步骤S11的判定结果为是的情况下，将数 据包的虚拟通道从当前的虚拟通道变更为其他虚拟通道(步骤S12)。 例如从一个虚拟通道变更为其他虚拟通道。这里，虚拟通道的变更是通 过重写数据包所具有的包头中的虚拟通道信息VC(将结合图11在后面 进行说明)来进行的。若数据包的包头的虚拟通道信息VC被重写，则 在接收到该数据包的接收侧的节点进行接下来的动作。即，在接收侧的 节点中，将所接收到的数据包保存到接收到的数据包所具有的包头中的 虚拟通道信息VC所表示的虚拟通道的缓冲区中。

在步骤S11的判定结果为否的情况下，转移到步骤S13。在步骤S13 中，判定相对于发出数据包的维度的发送目的地坐标，本节点的同维度 的坐标是否是前一台节点的坐标。在判定的结果为，本节点的坐标是发 送目的地坐标的前一台的坐标的情况下(是)，将数据包的虚拟通道从 当前的虚拟通道变更成其他虚拟通道(步骤S14)。例如，从一个虚拟 通道变更成其他虚拟通道。

在步骤S13的判定结果为否的情况下，转移到步骤S15。在步骤S15 中，判定发出数据包的维度的发送目的地坐标是否与本节点的同维度的 坐标一致。在判定的结果为坐标一致的情况下(是)，判定本节点是否 是该数据包的最终的发送目的地(步骤S16)。在判定的结果为，本节 点是该数据包的最终的发送目的地的情况下(是)，结束图4的处理。 另一方面，在步骤S16的判定的结果为否的情况下，当数据包的虚拟通 道已经在上述步骤S11或步骤S13中被变更时，使数据包的虚拟通道回 到变更前的虚拟通道(步骤S17)。例如从上述其他虚拟通道回到一个 虚拟通道。在数据包的虚拟通道未在上述步骤S11或步骤S13中被变更 的情况下，在步骤S17中不进行任何虚拟通道的变更。

下面，结合图5～7，对结合图4进行了说明的上述虚拟通道控制方 法进行更加具体的说明。

在虚拟通道控制方法中，如上所述，各节点具有多个缓冲区。并且， 设置多个具有这种结构的收发端口。关于应用了虚拟通道控制方法的节 点N的构成，将结合图5在下面进行说明。

图5表示结合图2进行了说明的上述的各节点N的构成。但是，图 5的情况下，为了便于说明而仅仅示出路由控制器4的功能所涉及的构 成。如图5所示，路由控制器4具有交叉开关41。该交叉开关41具有 如下功能，即在具有交叉开关41的节点N发出的数据包发生了冲突的 情况下，其作为进行协调的协调部。

这里，作为结合图1、2说明的上述各节点N收发数据的端口，在 各方向具有1组数据收发端口。这里，1组数据收发端口是指，1个发 送端口和1个接收端口的组合。作为收发端口，在节点N设有+x方向 用的收发端口P₁₁、-x方向用的收发端口P₁₂、+y方向用的收发端口P₂₁、 以及-y方向用的收发端口P₂₂共计4组收发端口。另外，对于各收发端 口，设有虚拟通道的个数的量的缓冲区，该缓冲区临时保存发出的数据 包。在实施例1的情况下，虚拟通道为VC0、VC1共计2个，在节点N 共计设有4组收发端口，因此缓冲区如图5所示，设有共计8个。在图 5中，每个收发端口设置的2个缓冲区被表示为VC0、VC1。所谓发出 的数据冲突的情况，是指相对于发出数据包的各方向，发出了虚拟通道 相同的两个以上的数据包的情况。

此外，被节点N接收的数据包，按照每个被接收的方向，被保存在 2个缓冲区(VC0，VC1)当中的、设于该数据包的虚拟通道一侧的缓 冲区中。各缓冲区具有FIFO(先入先出；First In First Out)结构，在 如上所述被保存于各缓冲区的数据包当中，从最前面的数据包开始依次 被发出。这里，在上述共计8个缓冲区的最前面的数据包当中，虚拟通 道相同、且其发出的方向相互一致的多个数据包，成为上述冲突的数据 包。

图6是用于对实施了结合图4说明了的上述的虚拟通道控制方法的 情况下的数据包的动作进行说明的图。图6中，如作为数据转发方向A 而示出的那样，数据被从位于右下的节点向位于左上的节点转发。即、 图6中，数据从节点N1被依次转发至N5。但是，在图6的例子的情况 下，节点N5并不是该数据包的最终的发送目的地的节点。

在图6中，各节点所具有的2个椭圆分别表示虚拟通道VC0、VC1 的缓冲区。另外，上述2个椭圆中的、划有阴影线的一侧的椭圆表示保 存有上述数据包的一侧的缓冲区。

图6中，数据首先向左方向从节点N1被转发至N3，在数据到达维 度的发送目的地、即节点N3的位置之后，转发数据的维度被变更。然 后，在图6中，数据向上方向从节点N3被转发至N5。在图6的例子的 情况下，设定在转发数据时不会超过日期变更线。因此，在图6示出的 数据转发期间，图4的步骤S11的判定结果总是为否。

图6中，数据从节点N1被发送到N2时，接收到数据的维度的节点 N2的坐标是该维度的发送目的地的节点、即N3的前一台的坐标。因此， 图4的步骤S13的判定结果为是。这里，对于节点N2所接收的数据， 表示为SD1，在各节点N1、N2中使用虚拟通道VC0的缓冲区。因此， 在节点N2，根据S13的判定结果变更数据的虚拟通道、转发数据时所 使用的缓冲区从虚拟通道VC0的缓冲区被变更为VC1的缓冲区(步骤 S14)。其结果，数据在从节点N2被发出之后(SD2)，被保存于节点 N3的虚拟通道VC1的缓冲区中。

这里，从节点N2接收到数据的维度的节点N3的坐标，与该维度的 数据的发送目的地的坐标一致。因此，节点N3处的图4的步骤S15的 判定结果为是。另外，节点N3不是数据的最终的发送目的地的节点(步 骤S16的否)。其结果，在从节点N3向节点N4发出数据时(SD3)，转 发数据的虚拟通道从当前的VC1回到VC0(步骤S17)。即，通过通道 转换(SD1)，从VC0向VC1移动了的数据，再次回到原来的虚拟通道 VC0(SD3)。然后，数据从节点N4被向节点N5发送。从节点N4向 节点N5的数据发送在图6中表示为SD4。

接下来，结合图7，对与图6的例子不同的虚拟通道控制方法的例 子进行说明。

图7是从结合图1说明的上述节点的排列中抽出沿x轴排列的6个 节点N11～N16来进行表示的图。各节点N11～N16的x坐标分别为0～5。 为了便于说明，在图7中，设定数据包被从-x侧向+x侧转发。另外， 在图7中，各节点的上段表示虚拟通道VC0的缓冲区，下段表示虚拟 通道VC1的缓冲区。另外，在各节点内示出的“0＞3”、“0＞2”、“1＞4”， “1＞3”之类的事项，表示被保存在各节点的缓冲区中的数据包。这里， 例如“0＞3”的“＞”的左侧的数字“0”表示数据包的发送源的x坐标， 右侧的数字“3”表示数据包的发送目的地的x坐标。

另外，在图7的例子中，日期变更线设于x坐标“0”与“5”之间、 即节点N11与节点N16之间。例如对于在节点N16的VC0的缓冲区的 最上段保存的数据“4＞1”来说，发送源的x坐标是4、发送目的地的x 坐标是1。即、该数据被从节点N15向节点N12转发。这里，在实施例 1中，形成环状的连接、即圆环状的连接，转发方向为单一的方向，在 图7的例子的情况下，x轴的维度中的数据的转发方向为+x方向。因此， “4＞1”的数据包，被从位于节点N16的左侧相邻位置的、x坐标为4 的节点N15沿+x方向发送，并由节点N16接收，然后，在被从节点N16 向x坐标为0的节点N11转发之后，被从节点N11向x坐标为1的节 点N12转发。即，该情况下，由于是圆环状的连接，数据包到达x坐标 的最大值“5”的节点N16之后，被从N16直接向x坐标具有最小值“0” 的节点11发送。然后，数据包被转发至发送目的地的x坐标“1”的节 点N12。这里，在数据包从节点N16被向节点N11转发时，数据包通 过x坐标“5”与“0”之间、即日期变更线。在该情况下，图4的步骤 S11的判定结果为是，虚拟通道从当前的VC0变更成VC1。

接下来，在图7中，着眼于在节点N12下段的虚拟通道VC1的缓 冲区的最上段示出的数据包“0＞1”。对于该数据包来说，发送源的x坐 标为“0”、即是保持该数据包的节点N12的左边紧相邻的节点N11的 坐标位置。另外，数据包的发送目的地x坐标为“1”，是节点N12自身 的坐标位置。因此，数据包是从节点N11向着节点N12，向+x方向、 即图7中的右侧被发送来的数据包。在从节点N11向节点N12发送数 据包之前，在节点N11，判定为数据包的虚拟通道为VC0，相对于发出 数据包的维度、即x轴的维度的发送目的地“1”，自身的同维度的坐标 位置“0”为前1台节点的坐标(图4中步骤S13的是)。其结果，在节 点N11，虚拟通道从VC0变更成VC1(图4中的步骤S14)。然后，通 过虚拟通道VC1，该数据包被节点N12接收。按照同样的次序，在各 个节点的左侧紧相邻的节点中，数据包的虚拟通道从VC0变更成VC1， 在此基础上节点所接收到的数据包如下。即，在图7中，在节点N13 中为下段的“1＞2”、“0＞2”，在节点N14中为下段的“2＞3”、“1＞3”、“0＞3”， 在节点N15中为下段的“3＞4”、“2＞4”、“1＞4”。并且，在节点N16中 为下段的“4＞5”、“3＞5”、“2＞5”。

由此，在实施例1中，应用超过日期变更线的数据的虚拟通道从VC0 变更成VC1这一规则，即、除了图4中的步骤S11、S12之外，还应用 图4中的步骤S13、S14的规则。即，增加在如从x轴向y轴移动那样、 数据转发的维度发生变化的节点的前1台节点中变更虚拟通道这样的规 则。

下面对上述实施例1的效果进行说明。

作为实施例1的效果，能够举出与交叉开关41的握手机会和其成 立概率增大。关于这一点，结合图8进行说明。在各节点，在向其他节 点发出数据时进行以下动作。首先，对交叉开关41，从具有各方向的收 发端口的交叉开关接口42～45发出数据的发送请求。并且，若收到发送 请求的交叉开关41成为能发送的状态，则向交叉开关接口42～45给予 发送允许。通常缓冲区具有FIFO结构，仅针对各缓冲区的最前面的数 据包发出发送请求。在图8中，每个虚拟通道的缓冲区表示为VC0、 VC1。

在实施例1的情况下，将图4中的步骤S13、S14的规则追加到步 骤S11、S12的规则中而设置，因此，虚拟通道VC0、VC1间的数据包 移动的机会大幅增大。其结果，对于各方向的收发端口，数据包容易分 散在VC0、VC1两个缓冲区。其结果，如图7所示，在节点间转发的 数据包不会偏向于一方的虚拟通道的缓冲区，数据包分别被分散地保存 在VC0、VC1两个缓冲区。其结果，针对各缓冲区的最前面的数据包， 向交叉开关41发出发送请求，因此成为同时发出多个发送请求的状态。 其结果，在各交叉开关接口42～45与交叉开关41之间，握手成立的可 能性也增大。这里，所谓握手的成立是指，在某个方向的交叉开关接口 42～45向交叉开关41发出发送请求时，给予针对发送请求的发送允许。

在图8的例子中，被保存在各交叉开关接口的虚拟通道VC0、VC1 的各自的缓冲区中的数据包的虚拟通道未变更。即，保存在虚拟通道 VC0的缓冲区的数据包的虚拟通道为VC0，同样，保存在虚拟通道VC0 的缓冲区的数据包的虚拟通道为VC1。

另外，在图8的例子中，假定以下的情况。即，-x的交叉开关接口 43的虚拟通道VC0的缓冲区的最前面保存朝向+x方向的数据包，在虚 拟通道VC1的缓冲区的最前面保存朝向+y方向的数据包。同样，在-y 的交叉开关接口45的虚拟通道VC0的缓冲区的最前面保存朝向+y方向 的数据包，在虚拟通道VC1的缓冲区的最前面保存朝向+x方向的数据 包。在这种情况下，交叉开关41进行以下那样的动作。

针对交叉开关接口43的虚拟通道VC0的缓冲区的朝向+x方向的数 据包，向交叉开关41发出发送请求(S21)。同样，针对朝向+y方向的 虚拟通道VC0的缓冲区的数据包，从交叉开关接口45向交叉开关41 发出发送请求(S22)。上述S21、S22的发送请求的方向为+x、+y，彼 此不同。因此，从交叉开关接口43被发送的数据包、与从交叉开关接 口45被发送的包不冲突。因此，针对来自两个交叉开关接口43、45的 发送请求S21、S22，交叉开关41分别发出发送允许。其结果，与两个 交叉开关接口43、45的发送请求S21、S22有关的数据包均被发出。

同样，针对朝向+y方向的虚拟通道VC1的缓冲区的数据包，从交 叉开关接口43向交叉开关41发出发送请求S23。同样，针对朝向+x方 向的虚拟通道VC1的缓冲区的数据包，从交叉开关接口45向交叉开关 41发出发送请求(S24)。来自两个交叉开关接口43、45的发送请求S23、 S24的方向为+y、+x，彼此不同。因此，来自两个交叉开关接口43、45 的发送请求S23、S24不冲突。因此，针对来自两个交叉开关接口43、 45的发送请求S23、S24，交叉开关41分别发出发送允许。其结果，与 来自两个交叉开关接口43、45的发送请求S23、S24有关的数据包均被 发出。

由此，根据实施例1，2个数据包被同时发出，并行性较高。即， 根据实施例1，在各收发端口，所有的数据包有效利用2个虚拟通道 VC0、VC1来从最前面发出。其结果，使用不同的虚拟通道同时地并行 发出多个发送请求的可能性提高，数据包的发送方向不冲突的可能性增 加，数据发送的效率增加。

这里，在如图1示出的结构的信息处理系统的情况下，在虚拟通道 VC0存在同轴通信的数据包、相对地在虚拟通道VC1中，轴移动的通 信的数据包存在的频度增高。这里，所谓同轴通信是指不移动维度而被 转发的数据，所谓轴移动的通信是指移动维度而被转发的数据。其结果， 与经由各虚拟通道同时地并行发出多个来自各交叉开关接口的发送请 求的效果相结合，能够同时地从多个方向的收发端口并行发出数据包的 机会的频度增高。能够同时地从多个方向的收发端口并行发出数据包的 机会的频度增高的理由如下。即，如上所述，由于从各虚拟通道的缓冲 区同时地并行发出多个来自各交叉开关接口的发送请求，因此，与其他 发送请求不冲突的发送请求的发生频度增高。由于与其他发送请求不冲 突的发送请求能够立刻被允许并进行发送，因此能够同时地从多个方向 的收发端口并行发出数据包的机会的频度增高。

另外，在实施例1中，如图7所示，虚拟通道VC0的缓冲区的使用 率与虚拟通道VC1的缓冲区的使用率之差较小。其结果，能够立刻结 束缓冲区的使用，最终能够降低数据滞留这样的情形发生的可能性。即， 根据实施例1，由于在虚拟通道VC0、VC1的共计2个缓冲区均等地分 配数据包，因此不用增加物理上的缓冲区的量，就能够在实质上获得与 增加了虚拟通道VC0的缓冲区的量同样的效果。

而且，根据实施例1，由于能够向交叉开关41同时地发出多个发送 请求，因而当某个数据包成为了能转发的状态时，错过其转发机会的可 能性减低。因此，能够抑制交叉开关41进行协调时所用的时间的偏差。 作为一例，在图9示出的参照例中是如下的情况，即、产生了由步骤 S32表示的+y方向的同轴通信，同时产生了由步骤S31表示的从另一轴、 即+x方向向+y方向变更转发方向的轴移动的通信。在该情况下，上述 同轴通信S32和轴移动的通信S31的发送方向分别为+y，彼此一致。另 外，虚拟通道也分别为VC0，彼此一致。因此，针对S32、S31各自的 通信的发送请求彼此冲突。其结果，无法同时实施S32、S31各自的通 信，对于一方的通信来说，会失去通信机会。与此相对，根据实施例1， 如上述的图8示出的例子中所示那样，数据包被分散地保存在2个虚拟 通道的缓冲区VC0、VC1。其结果，即使是在产生了由步骤S22表示的 +y方向的同轴通信、和由步骤S23表示的从+x方向向+y方向变更转发 方向的通信，从而发送方向为+y，彼此一致的情况下，也能同时实施 S22、S23各自的通信。

即，根据实施例1，由于能够向交叉开关41同时地并行发出多个发 送请求，因而能够有效地降低失去通信机会的情形的发生频度。即，在 图8示出的实施例1的情况下，进行以下所示的动作。由步骤S22表示 的同轴通信的数据包和由步骤S23表示的来自其他轴的轴移动的通信 的数据包都分别来到与彼此不同的虚拟通道对应的缓冲区VC0、VC1 的最前面。若同轴通信的数据包和来自其他轴的轴移动的通信的数据包 都来到与不同的虚拟通道对应的缓冲区VC0、VC1的最前面，则同时 地并行发出同轴通信的发送请求和轴移动的通信的发送请求。因此，同 轴通信和轴移动的通信被同时地并行实施。

另外，在图9的参照例中，步骤S31、S32都处于+y方向的数据包 在缓冲区的最前面，并发出了针对+y方向的发送请求的状态。另一方 面，在保存有S31、S32的通信所涉及的数据包的各交叉开关接口43、 45的各自的VC0的缓冲区中，在朝向该+y方向的数据包之后，保存有 朝向+x方向的数据包。然而，由于上述朝向+x方向的数据包不在缓冲 区的最前面，因此无法向交叉开关41发出发送请求，从而无法发送。 与此相对，根据图8所示的实施例1，朝向+x方向的数据包，在各交叉 开关接口43、45中，被保存于虚拟通道的缓冲区VC1中。该虚拟通道 VC1的缓冲区与保存有朝向+y方向的数据包的虚拟通道VC0的缓冲区 不同。因此，上述朝向+x方向的数据包分别在虚拟通道VC1的缓冲区 的最前面。因此，如步骤S21、S24所示，能够同时并行地向交叉开关 41发出上述朝向+X方向的各个数据包的通信请求。

由此，根据实施例1，如图8所示，朝向+x方向的数据包和朝向+y 方向的数据包两方均来到缓冲区的最前面的可能性增加。若朝向+x方 向的数据包和朝向+y方向的数据包两方均来到缓冲区的最前面，则进 行以下动作。即，同时并行地发出朝向+x方向的数据包的发送请求(S21、 S24)和朝向+y方向的数据包的发送请求(S23、S22)。因此，如图8 所示，x轴的通信和y轴的通信被同时并行地实施。根据实施例1，通 过上述效果，并行计算机系统整体的通信效率提高。

图10是用于对本实施例的虚拟通道控制方法进行更为具体的说明 的流程图。图10中，节点发出数据包时，在步骤S31中确认数据包的 发送目的地。这里，所确认的发送目的地是发出数据包的维度中的发送 目的地。发出数据包的维度通过上述维度控制方法的实施来确定。例如 如果发出数据包的维度是x轴，则确认数据包的x坐标的发送目的地。 接下来，在步骤S32中，将所确认到的数据包的发送目的地与本节点的 位置进行比较。如果比较的结果是，本节点的位置相对于数据包的发送 目的地是前一台节点(S32是)，即当前的位置是发送目的地的前一台， 则转移到步骤S33。在步骤S33中，节点将发出数据包的虚拟通道从当 前的虚拟通道变更成其他虚拟通道。另一方面，在步骤S32的判定结果 为否的情况下，节点不对该数据包进行虚拟通道的变更(步骤S34)。 在步骤S33或者S34之后，节点向交叉开关41发送数据包。

在实现如图10等所示的虚拟通道控制方法时，能够利用数据包的 包头中保存的信息。数据包的所需要的最低限度的构成如图11所示。 即，作为包头而保存成为数据包发送目的地的节点的x坐标以及y坐标。 另外，还能采用以下方法，即：作为数据包的包头中所保存的信息，用 到发送目的地的相对坐标来取代上述的发送目的地坐标。在该方法的情 况下，将到发送目的地的相对坐标保存在包头中，每当数据包在节点间 移动时，就适当地重写该相对坐标。并且，在数据包的包头中保存有虚 拟通道信息VC(例如2比特)。在虚拟通道信息VC中，被写入有用于 识别该数据包的虚拟通道是VC0、还是VC1的信息。各节点若接收到 数据包，则参照该虚拟通道信息VC，将该包保存于虚拟通道信息VC 所表示的虚拟通道的缓冲区中。

图12是表示图2示出的路由控制器4内的构成例的框图。图12表 示设于图2示出的4个方向+x、-x、+y、-y的各方向的收发端口上的4 个交叉开关接口42～45、以及将结合图14在后面进行说明的CPU交叉 开关接口48的各自的构成例。

图12示出的交叉开关接口42～45以及CPU交叉开关接口48，分别 具有包输入部401、包头分析部402、多路分配器403、虚拟通道VC0 的缓冲区404、虚拟通道VC1的缓冲区405、多路复用器406和包输出 部411。

包输入部401被连接于包头分析部402，经收发端口，将设有该路 由控制器的节点所接收到的数据包交付给包头分析部402。在包头分析 部402中，确认所接收到的数据包的包头中保存的发送目的地x坐标、 发送目的地y坐标以及虚拟通道信息VC，分别根据确认结果执行结合 图3说明的上述维度控制方法以及结合图4说明的上述虚拟通道控制方 法。

通过包头分析部402执行虚拟通道控制方法，决定是否变更该数据 包的虚拟通道。在上述决定的结果是变更虚拟通道的情况下，包头分析 部402重写数据包的虚拟通道信息VC。在上述决定的结果是不变更虚 拟通道的情况下，包头分析部402不重写数据包的虚拟通道信息VC。 然后，包头分析部402向多路分配器发送数据包。另外，包头分析部402 在从多路复用器406向交叉开关41发出该数据包时，预先向交叉开关 41发送该数据包所涉及的发送请求408。

多路分配器403在包头分析部402的控制下，在从包头分析部402 发出的数据包的、被该节点接收到的时刻的虚拟通道信息VC所表示的 虚拟通道的缓冲区404或者405中保存该数据包。即，即使在包头分析 部402如上述那样实施虚拟通道控制方法的结果是重写了虚拟通道信息 VC的情况下，多路分配器403也将数据包保存于重写前的虚拟通道信 息VC所表示的虚拟通道的缓冲区中。

被保存在各缓冲区404、405的数据包，在包头分析部402的控制 下，依次经由多路复用器406被从该交叉开关接口向交叉开关41发送。 在数据包被从交叉开关接口向交叉开关41发送时，如上所述，预先从 该交叉开关接口的包头分析部402向交叉开关41发送针对该数据包的 发送请求408。在包头分析部402中，仅在从交叉开关41给予了发送允 许的情况下，才从缓冲区404、405取出数据包，并经多路复用器406 向交叉开关41发出。

在交叉开关41中，在由此从各交叉开关接口42～45、48发送的发 送请求发生了冲突的情况下，进行发送请求间的协调。另外，所谓发送 请求冲突的情况是指，多个发送请求所涉及的数据包的发出方向彼此一 致、且虚拟通道信息VC所表示的虚拟通道彼此一致的情况。对于针对 4组收发端口的协调顺序没有特别限定，但是可以考虑例如预先对4组 收发端口建立等级并遵循该等级的方法、加入协调的履历的方法等。

在数据包的发送请求与其他数据包的发送请求不冲突的情况下，交 叉开关41向该数据包给予发送允许。并且，交叉开关41向发出方向的 交叉开关接口发送根据该发送允许而从发送源的交叉开关接口发送过 来的数据包。另一方面，在数据包的发送请求与其他数据包的发送请求 冲突的情况下，交叉开关41如上述那样进行协调。协调的结果是，交 叉开关41向一方的数据包给予发送允许。并且，交叉开关41向发出方 向的交叉开关接口发送根据该发送允许而从发送源的交叉开关接口发 送过来的数据包。数据包被从该发出方向的交叉开关接口的包输出部 411经收发端口向节点的外部发出。

图12的例子中，交叉开关接口42～45、48的各自的各功能块401、 402、403、404、405、406、411全部通过硬件来实现。通过这样由硬件 来实现，与由软件来实现的情况相比，具有能够高速地执行数据包的处 理的优点。

图13表示了在图12示出的各交叉开关接口42～45、48的各自的构 成中，设置了包头发送部408来取代包头分析部402的例子。在图13 的例子的情况下，将包头分析部402所进行的动作，通过由设于交叉开 关接口的外部的信息处理部5执行软件来实现。其他方面与图12的情 况相同，省略重复的说明。这里，在图13的构成的情况下，在变更结 合图3说明的上述维度控制方法或者结合图4说明的上述虚拟通道控制 方法这样的情况下，能够比较容易地变更维度控制方法或者虚拟通道控 制方法的具体内容。即，在图13的构成的情况下，仅通过变更安装于 信息处理部5的软件，便能够容易地变更维度控制方法或者虚拟通道控 制方法的具体内容。其结果，能够容易地变更路由的方法。

图14是表示在各方向+x、-x、+y、-y的收发端口P₁₁、P₁₂、P₂₁、 P₂₂配设有交叉开关接口42～45的路由控制器4的构成例的框图。如图 14所示，在路由控制器4中，除了设有各方向的交叉开关接口42～45 之外，还设有上述CPU交叉开关接口48。CPU交叉开关接口48在节 点中与信息处理部5连接。在实施例1中，CPU交叉开关接口48具有 与结合图12、图13说明的上述各方向的交叉开关接口42～45相同的构 成。CPU交叉开关接口48若从信息处理部5接收到数据包，则经由图 12中的包输入部401向包分析部402交付数据包。包分析部402执行图 3的维度控制方法以及图4的虚拟通道控制方法。作为维度控制方法中 的“发出数据包的维度”，作为初始值例如设定第1维度、即x轴。另 外，作为虚拟通道控制方法中的“数据包的虚拟通道”，作为初始值例 如设定第1虚拟通道、即虚拟通道VC0。另外，交叉开关41除了接收 来自各方向的交叉开关接口42～45的发送请求之外，还接收来自CPU 交叉开关接口48的发送请求，并根据需要进行包括来自CPU交叉开关 接口48的发送请求在内的发送请求间的协调。

图15表示信息处理部5的构成例。图15中，主体部101大体上具 有通过总线200连接的CPU201、由RAM或ROM等构成的存储器部 202、光盘110用的光盘驱动器203以及硬盘驱动器(HDD)204。显示 器102、键盘103以及鼠标104也如图所示经总线200与CPU201连接， 但是它们也可以直接与CPU201连接。另外，信息处理部5的构成不局 限于图15所示的构成，可以使用各种周知的构成来取代。

在上述构成的信息处理部5中，在采用图13的构成的情况下，用 于使计算机执行上述维度控制方法以及虚拟通道控制方法的程序被安 装并由CPU201执行。其结果，如结合图13所说明的那样，能利用软 件实现维度控制方法以及虚拟通道控制方法。

下面，对通过模拟来验证了实施例1的作用效果的结果进行说明。 模拟的初始条件和设定内容如下。

●作为拓扑，以8节点×8节点的排列形成2维环状的连接。

●设置2个CPU交叉开关接口48。

●数据包的模式：所有的节点具有64个数据包，各个节点向其他节 点转发数据包。对于64个数据包的模式，在所有的节点中具有“相同 的目的地+长度”的组合模式。

●“包的长度”、“数据包的目的地”采用均匀随机数来设定。“数据 包的长度”在与1～128时钟周期相当的范围内设定。

●所有的数据包在初始状态下被保存在CPU交叉开关接口48。

●没有电缆延迟。

另外，模拟中的算法如下。

1)交叉开关41确认当前的发送状况。

2)交叉开关41确认从CPU交叉开关接口48和各方向的交叉开关 接口42～45发送的发送请求，进行对应于发送状况的公平的协调。

3)交叉开关41进行的协调的结果是，获得“发送允许”的交叉开 关接口42～45或者CPU交叉开关接口48开始发出数据包。

4)以各时间步长进行以上过程，直到所有的数据包到达所期望的 CPU交叉开关接口48。

将上述模拟的结果表示于图16中。在图16中，纵轴表示未到达数 据包数，横轴表示经过时间。实线(normal-all)表示通常的维序路由 的未到达包数。细虚线(onehop-all)表示实施了实施例1的方法的情 况下的未到达数据包数。接下来，细虚线(normal-x)表示在通常的维 序路由中存在于当前x轴的收发端口上的数据包数。粗虚线(onehop-x) 表示在实施了实施例1的方法的情况下，存在于x轴上的数据包数。单 点划线(normal-y)表示存在于通常的维序路由的y轴上的数据包数。 双点划线(onehop-y)表示在执行了实施例1的方法的情况下，y轴上 所存在的数据包数。

根据该结果能够理解以下方面。即，在系统整体中，采用实施例1 的方法时存在于x轴的数据包数的峰值最大数降低，相反，y轴的峰值 最大数增加。因此，能有效地进行维序路由，结果并行性提高，成功地 消减了10％左右的通信时间。

为了简便，在2维环状的连接的情况下进行了上述模拟，但是当然， 实施例1的技术思想与拓扑无关，都是有效的。