CN103348640A - 中继装置 - Google Patents

Abstract

本发明提供一种中继装置。抑制从特定的发送节点发送来的信息包的传送性能(吞吐量或延迟时间)的降低，并提高NoC整体的传送性能。该中继装置，在具有信息包交换方式的分散型总线的集成电路中，用于对在节点间传送的信息包进行中继。该中继装置具有：多个缓冲器，保存附加了对发送节点进行确定的信息的信息包；分类部，其根据信息包的发送节点，将保存有信息包的多个缓冲器分类为多个组；选择部，其至少选择一个属于各组的缓冲器；和输出端口，其依次输出被选择的缓冲器中所保存的信息包。

Description

中继装置

技术领域

本发明涉及在具有分散型的总线的半导体的集成电路中，调整在总线间连接的多个中继装置间传输的多个业务(traffic)的发送调度(scheduling)的技术。特别地，本发明涉及在多个缓冲器中分散地保存有构成不同的业务的信息包(packet)时控制在缓冲器中所保存的信息包的发送的技术。

背景技术

图1(A)表示集中型的总线控制的示例。在进行集中型的总线控制的现有的集成电路中，主要在多个总线主设备(bus master)与存储器之间通过一个总线连接，由仲裁器(arbiter)调停从总线主设备向存储器的访问。然而，由于集成电路的高功能化、多核化，电路的规模增大，业务也复杂地变动着流经总线，使得基于集中型的总线控制的集成电路的设计变得困难。

另一方面，近年来，具有引入了并行计算机的连接技术、或ATM(Asynchronous Transfer Mode：异步传输模式)网等网络控制技术的分散型总线的半导体集成电路的开发正在发展。图1(B)表示分散型的总线控制的示例。具有分散型总线的半导体集成电路，构成为由多个总线连接多个中继装置。近年来，有了如下成果：通过使用如图1(B)所示的分散型总线，将大规模化的集成电路内的业务分散地传输到多个总线的片上网络(Network on Chip)。

图2是通过NoC(Network on Chip)或并行计算机、ATM网等而被利用的中继装置的基本结构的概略。在这些中继装置中，业务数据按信息包或单元(cell)的单位被分割后，发送至目的地的节点。被发送到中继装置的数据，被临时保存在缓冲器中。

此外，为了按照每个输入端口并行地发送并处理不同的信息包，而具有按照每个输入端口将多个缓冲器并列化的虚拟信道(“V信道”或者称为“VC：Virtual Channel”)。虚拟信道的实体虽然是中继装置的缓冲存储器，但可以按照每个输入端口，并且对各输入端口物理性地安装多个缓冲器，或者，通过如存在多个缓冲器那样地管理缓冲存储器上的数据，能够安装虚拟的信道。

交叉开关(crossbar switch)是决定各输入端口与输出端口的排他性连接的开关。此外，基于交叉开关的输入端口与输出端口的排他性连接由仲裁器来决定。

如此，在中继装置中，通过由仲裁器切换交叉开关的连接，将缓冲器内所保存的数据中继到目标目的地。

接着，对中继装置的输入端口与输出端口的连接的切换处理进行说明。中继装置的输入端口与输出端口通过交叉开关，分别排他性地进行连接。在此，所谓“排他性连接”定义为：当同时连接多个输入端口与多个输出端口时，对于一个输出端口，至多仅连接一个输入端口的状态。

接着，对NoC的中继装置所传输的数据的数据构造进行说明。

图3表示信息包300的传输格式的一个示例、和将信息包300分割成多个信息片(flit)的示例。

在NoC中继装置中，与一般通过并行计算机、ATM网等而被利用的中继装置不同，而要将在发送节点所生成的信息包进一步分割为被称为信息片的单位来进行中继。信息片的大小被确定为使用总线以1循环能够传输的数据尺寸。

信息包300具有：头段(head field)301、数据段302以及控制代码段303。

在头段301中，例如，记述：发送目的地(接收节点)的地址、发送源(发送节点)的地址、从信息包被发送起至到达接收节点为止的截止时刻等的信息(时间信息)。时间信息的记述方法虽然是任意的，但只要是能够在与其它信息包之间对从发送该信息包起的经过时间、或至目的地为止的截止时刻等进行比较的值即可。

在数据段302中，例如，记述：影像数据或声音数据。在控制代码段303中，例如，记述：预先确定的信息包303的结束代码。

在上述头段301的数据之中，根据接收节点的地址和发送节点的地址，来进行信息包300的中继处理和在接收侧的接收处理。

发送侧的节点，将信息包300分解为被称为信息片的小的数据单位后进行传输。1信息片是使用总线以1循环能够传输的数据，该尺寸由总线宽度的大小来决定。在将信息包300分割后的信息片之中，最初被发送的信息片，称为头信息片1104。对头信息片304，赋予了表示是信息包的开头的标志信息、以及信息包的接收节点的地址信息。

而且，在接着头信息片304的各信息片中，未保存对接收节点进行确定的地址信息。其理由是：由于接着头信息片304的信息片，会被发送到与头信息片304相同的目的地。由头信息片304来决定目的地，若确定了输出该业务的信息片的输出缓冲器，则之后接着的信息片，利用与头信息片304相同的输出缓冲器，被传输到头信息片304表示的目的地。

此外，信息包的最终的信息片被称为尾信息片306。对尾信息片306，赋予了表示该信息片是构成信息包的最后的信息片的标志信息。此外，头信息片304与尾信息片306以外的信息片，主要是传输数据的信息片，被称为数据信息片305。

接收侧的节点，若检测出控制代码段303所记述的结束代码，则根据该结束代码，从被传输的多个信息片重构为信息包。

例如，1信息包的尺寸为128字节，1信息片的尺寸为64比特。此时，1信息包分割为16信息片后被发送。然而，1信息包的尺寸以及1信息片的尺寸可能会由于应用(application)或总线宽度不同而不同，因此，应留意：上述的尺寸不过是一个示例。信息片的长度，也可以将能够记述接收节点的地址和发送节点的地址等控制数据的长度作为基准。

图4(A)是说明在NoC中，向相邻的中继装置或接收节点发送各中继装置接收到的信息包时的中继装置的一系列的处理动作的流程图。

此外，图4(B)是表示与图4(A)的信息片的发送相关的中继装置的虚拟信道的结构的图。在图4(B)所示的示例中，各中继装置分别具有两个输入端口和输出端口，而且还各具有两个用于按照每个输入端口来存储信息片的虚拟信道(VC)。

输入端口内的虚拟信道以及输出端口，通过切换交叉开关(SW)的连接来进行连接，经由输出端口来发送虚拟信道内的信息片。而且，在图4(B)中，为了简化附图，仅记载了输入端口0的虚拟信道(VC1、VC2)，而省略了输入端口1内的虚拟信道的记载。

图4(C)是按照每1循环表示从由中继装置接收到信息包起至被发送到下一个中继装置、或接收节点为止的各信息片的状态变化。

在NoC中的中继装置中，为了将被分割为信息片的信息包中继至目标目的地，针对接收到的信息片执行路由(RC：Routing Computation)、虚拟信道分配(VA：Virtual channel Allocation)、开关分配(SA：SwitchAllocation)、信息片发送(ST：Switch Traversal)的所有处理或一部分处理(例如非专利文献1)。

首先，使用图4(A)的流程图和图4(B)的中继装置的结构图，来说明NoC中的中继装置的基本动作。如图4(B)所示，将上流侧的中继装置作为“中继装置A”，将下流侧的中继装置作为“中继装置B”来进行说明。

在图4(A)的步骤401中，中继装置A判定存在有信息片的虚拟信道(VC)是否存在。若存在有信息片的虚拟信道(VC)存在，则中继装置A的处理转移至步骤402。若无存在有信息片的虚拟信道(VC)，则重复步骤401的处理，直至判定为存在有信息片为止。

在虚拟信道(VC)中存在有信息片的情况下，在步骤402中，中继装置A判定虚拟信道(VC)的开头的信息片是否是头信息片。当虚拟信道(VC)的开头信息片是头信息片时，中继装置A的处理，转移至步骤403。当虚拟信道(VC)的开头信息片不是头信息片时，中继装置A的处理，转移至步骤405。

在图4(B)的中继装置A的示例中，由于在一个虚拟信道中保存有头信息片，因此中继装置A的处理，转移至步骤403。

当虚拟信道的开头信息片是头信息片时，在步骤403中，中继装置A参照在头信息片所记载的目的地信息，执行路由处理(RC：RoutingComputation)。在路由处理中，从中继装置A选择一个接续至信息包的目的地的输出端口。

在图4(B)的中继装置A中，通过路由处理，选择与接续至“目的地”的中继装置B连接的输出端口0。

若通过路由处理选择了输出端口，则处理转移至步骤404，选择将中继装置A发送的信息包保存到相邻的中继装置B的哪个虚拟信道。

在NoC中，信息包被分割为信息片后进行中继。此外，用于中继的控制所需的基本信息仅记载在头信息片中，因此，若不同的信息包的信息片混合存在于一个虚拟信道中，则会发生信息片无法正确到达目的地的情况、或在目的地所到达的信息片无法正确恢复回原来的信息包的情况。

为了避免这些，在NoC的中继装置中，在按照每个信息包从头信息片至尾信息片通过的期间，占有一个虚拟信道，而使其它信息包的信息片无法利用所占有的虚拟信道。

例如，图4(B)的中继装置A，对保存有头信息片的虚拟信道VC1，在发送信息片的中继装置B中分配一个未使用的虚拟信道(VA：Virtualchannel Allocation)。

若虚拟信道的分配(VA)结束，则中继装置A的处理转移至步骤405。

另一方面，在相邻的中继装置B中无未使用的虚拟信道时，中继装置A维持步骤404的状态，直至在中继装置B的虚拟信道能有空闲，且虚拟信道分配(VA)结束为止。

在图4(B)中，中继装置A针对保存有头信息片的虚拟信道VC1，在中继装置B中选择并分配虚拟信道VC1作为保存的缓冲器。

若输出端口的决定(RC)和在相邻的中继装置中保存信息片的虚拟信道的分配(VA)结束，则中继装置A的处理转移至步骤405，成为所保存的信息片的发送等待状态。

在步骤405中，中继装置A为了从虚拟信道发送信息片，而切换交叉开关，以将中继装置A的虚拟信道VC1分配给该输出端口(SA：SwitchAllocation)。

当相对于输出端口的个数，请求了向该输出端口的发送的虚拟信道有多个时，执行按照每个输出端口来决定允许发送信息片的虚拟信道的SW分配(SA：Switch Allocation)。

而且，NoC的中继装置，也可以在该SW分配中，根据信息包的种类(延迟保证型、尽力服务(best effort)型等)或优先度、发送时刻、到达截止时刻等信息，来调整从进行了信息包保存的虚拟信道向输出端口连接的分配量。由此，能够调整来自不同发送节点的信息包的发送调度。

若通过步骤405的SW分配(SA)，对处于信息片的发送等待状态的虚拟信道分配输出端口来连接二者，则中继装置A的处理，转移至步骤406，从被选择的输出端口发送所连接的虚拟信道内的信息片。(ST：Switch Traversal)。

如上所述，中继装置按照每个虚拟信道，通过从步骤401至步骤406进行处理，将接收到的信息片发送至目的地。

接着，使用图4(C)来说明图4(B)的中继装置A中继一个信息包时的动作。以信息包尺寸为4信息片的情况为例，说明各时刻的信息片的处理内容。

在时刻1，首先，在头信息片到达中继装置A时，中继装置A根据头信息片中被赋予的目的地信息，执行路由处理(RC)，选择接着进行发送的输出端口。

在时刻2，中继装置A执行VC分配(VA)，并决定将保存有头信息片的虚拟信道分配给与由路由处理(RC)决定的输出端口连接的中继装置B的哪个虚拟信道。

此外，在时刻2，数据信息片1到达中继装置A。由于在虚拟信道的开头存在头信息片，因此，针对数据信息片1不执行处理。

在时刻3，中继装置A执行SW分配(SW)，针对在开头保存有头信息片的虚拟信道，确定输出端口的分配。

此外，在时刻3，数据信息片2到达中继装置A。由于在虚拟信道的开头存在头信息片，因此，针对数据信息片1和数据信息片2，不执行处理。

在时刻4，中继装置A发送头信息片(ST)。此外，在发送了头信息片之后，还继续用于接着连接相同的虚拟信道和输出信道的SW分配(SW)。

此外，在时刻4，尾信息片到达中继装置A。由于在虚拟信道的开头存在数据信息片，因此，针对数据信息片2和尾信息片，不执行处理。

在时刻5，中继装置A发送数据信息片1(ST)。此外，在发送了数据信息片1之后，还继续用于接着连接相同的虚拟信道和输出信道的SW分配(SW)。由于在虚拟信道的开头存在数据信息片，因此，针对数据信息片2和尾信息片，不执行处理。

在时刻6，中继装置A发送数据信息片2(ST)。此外，在发送了数据信息片2之后，还继续用于接着连接相同的虚拟信道和输出信道的SW分配(SW)。

在时刻7，中继装置A发送尾信息片(ST)。由此，一个信息包的中继结束。

与图4(c)所示的一个信息包的中继相关的一系列处理，是其每个处理都以1循环能够结束的示例。然而，例如在VC分配(VA)中，在输出目的地的中继装置B中无虚拟信道的空闲时，直至能够空闲为止无法结束VC分配(VA)，也包括后续的信息片，在中继处理中会发生等待状态。

此外，对于SW分配(SA)，当多个虚拟信道对相同的输出端口发出发送请求时，针对各虚拟信道，会因为用于分配所请求的输出端口的发送调度而产生发送等待。

一般而言，在并行计算机或ATM中的中继装置，与NoC的中继装置相比，由于针对信息包的尺寸能够较多地确保发送缓冲器(虚拟信道)，因此由于虚拟信道的不足而引起的C分配(VA)下的延迟发生的影响小。另一方面，如何高效地将发送缓冲器(虚拟信道)内的各信息片进行发送，在其发送调度的最优化中是重点。因此，在并行计算机或ATM的中继装置中，采用了搜索发送缓冲器(虚拟信道)和输出端口的最佳组合的“Wavefront allocator”、或在中继装置的输入端口侧与输出端口侧分别重复求出最佳组合的“Parallellterative Matching”等方法(例如，非专利文献1)。

此外，考虑多个虚拟信道请求连接相同的输出端口的情况。对于这样的示例，提出了Age-Based方式(例如专利文献1)。在Age-Based方式中，为了维持发送了信息包的顺序，并且为了抑制信息包间的延迟时间的增加或离散，根据从发送起的经过时间的长度或中继的跳数来定义被称为“Age”的值。并且，先发送Age最大(或最小)的信息包。

现有技术文献

专利文献

专利文献1：美国特许第6674720号说明书

非专利文献

非专利文献1：W.DALLY，B.TOWLES，“PRINCIPLES ANDPRACTICES OF INTERCONNETION NETOWRKS”，MORGANKAUFMANN PUBLISHERS

发明概要

发明所要解决的技术问题

对此，由于在NoC中需要在集成电路上构成多个中继装置，因此与并行计算机或ATM网的中继装置相比，无法将各中继装置上能够构成的虚拟信道的个数或尺寸设置得较大。例如，一个虚拟信道的尺寸是与一个信息包相同的程度。

因此，在NoC中，在更短的延迟时间内，针对从不同的发送节点发送来的信息包，有效地分配有限的虚拟信道(VA)，以便能够在SW分配中合适地进行发送调度就变得很重要。

发明内容

本申请的非限定的例示性的实施方式，提供一种抑制从特定的发送节点发送来的信息包的传输性能(吞吐量或延迟时间)的降低、使NoC整体的传输性能提高的中继装置。

解决技术问题的技术手段

本发明的一方式的中继装置，在具有信息包交换方式的分散型总线的集成电路中，对在节点间传送的信息包进行中继，具有：多个缓冲器，保存附加了对发送节点进行确定的信息的信息包；分类部，其根据所述信息包的发送节点，将保存有信息包的所述多个缓冲器分类为多个组；选择部，其至少选择一个属于各组的缓冲器；和输出端口，其依次输出被选择的所述缓冲器中所保存的信息包。

发明效果

根据本发明一实施方式的中继装置，在不增加中继装置内的虚拟信道的尺寸或个数的情况下，针对多个信息包，区别发送节点而将由相邻的中继装置利用的虚拟信道进行均等分配，以避免基于来自相同的发送节点的信息包的占有。由此，在中继装置中，针对发送节点不同的信息包，能够维持发送调度，能够改善NoC中的传输性能(大吞吐量、低延迟)的降低。

附图说明

图1(A)是表示集中型的总线控制的示例的图，图1(B)是表示分散型的总线控制的示例的图。

图2是中继装置基本结构的概略图。

图3是表示信息包300的传输格式的一个示例、和将信息包300分割为多个信息片的示例的图。

图4(A)是说明在NoC中，将各中继装置接收到的信息包发送给相邻的中继装置或接收节点时的中继装置的一系列的处理动作的流程图，图4(B)是表示与图4(A)的信息片的发送相关的中继装置的虚拟信道的结构的图。图4(C)是表示图4(B)的中继装置A对一个信息包进行中继时的动作的图。

图5是对本申请发明人所考察的问题点的一个示例进行说明的图。

图6是说明例示的实施方式1的中继装置的动作概要的图。

图7是在例示的实施方式1中假设的分散型的总线的结构图。

图8是例示的实施方式1的中继装置1201的结构图。

图9是表示由虚拟信道信息管理部805所管理并保持的虚拟信道信息901的一个示例的图。

图10是表示中继装置801的动作步骤的流程图。

图11(A)是表示中继装置801内的虚拟信道813的情形的图，图11(B)表示在中继装置801的输入端口0中尚未接收到信息片的状态时的虚拟信道信息901的图。

图12(A)是表示在虚拟端口0保存有到达输入端口0的头信息片304的情形的图，图12(B)是表示反映了头信息片304中被赋予的发送节点以及目的地的地址、发送时刻信息之后的虚拟信道信息901的内容的图。

图13(A)是表示接着头信息片，在虚拟信道0中保存有数据信息片的情形的图，图13(B)是表示选择了中继装置801的虚拟信道815的输出端口814之后的虚拟信道信息901的图。

图14(A)是表示在虚拟信道0中接着头信息片304、数据信息片305，保存了尾信息片306的情形的图，图14(B)是表示确定了中继装置801输出信道815之后的虚拟信道信息901的图。

图15(A)是表示从图14(A)起进行了1循环时间的中继装置801的虚拟信道815的情形的图，图15(B)表示从头信息片至数据信息片被发送的状态下的虚拟信道信息901的情形的图。

图16(A)表示从中继装置803至尾信息片被发送时的各虚拟信道813的情形的图，图16(B)是表示尾信息片1106被发送之后的虚拟信道信息901的图。

图17是表示在图10的步骤1007中，输出信道选择部809对虚拟信道813分配输出信道815的输出信道的虚拟信道分配处理的流程图。

图18(A)是表示在中继装置801中，同时接收到多个信息包时的虚拟信道813的情形的图，图18(B)是表示虚拟信道813处于图18(A)的状态时的虚拟信道信息901的内容的图。

图19是表示中继装置801的虚拟信道813的内容为图18(B)时的、发送节点分类部807对虚拟信道进行分类后的结果的示例的图。

图20(A)及(B)是说明在图10的步骤1008中，虚拟信道选择部810和开关切换部811对于选择了输出端口和输出信道的虚拟信道813进行向输出端口的连接、并分配信息片的发送定时的开关分配处理的图。

图21是表示时间信息以及基于时间信息的优先度的比较基准的示例的图。

图22(A)以及(B)是表示从中继装置R9看到的各种目的地的定义、以及能与该定义相当的目的地的具体例的图。

图23(A)及(B)是表示将多个发送接收节点处理作为一个组时的被分组的网格型NoC的示例的图。

图24是表示将属于相同的本地总线的多个总线主设备处理作为一个组的示例的图。

图25是对例示的实施方式2中的中继装置的动作进行说明的图。

图26是对例示的实施方式2中的中继装置的结构进行说明的图。

图27是对例示的实施方式2中的中继装置的动作进行说明的流程图。

图28是说明在NoC上的中继装置801中，表示信息包的传输的拥挤状况的指标的一个示例的图。

图29是对输出信道分配量决定部2402的动作的一个示例进行说明的图。

图30(A)是表示网格型拓扑的结构例的图，图30(B)是表示圆环面型拓扑的结构例的图，图30(C)是表示阶层型拓扑的结构例的图。

图31是对在存储器总线中利用本发明的一方式的中继装置的示例进行说明的图。

图32是对在多核处理器(multi-core processor)上利用本发明的一方式的中继装置的示例进行说明的图。

具体实施方式

以下，说明本申请发明人考察的问题点。之后，参照附图，来说明本发明的示例的实施方式的中继装置。

图5是对本申请发明人考察的问题点的一个示例进行说明的图。

图5表示：主设备(master)A和主设备B经由NoC上的中继装置A和中继装置B而与公共的存储器连接，且主设备A和主设备B分别向存储器发送信息包的情形。

中继装置A与中继装置B，分别各具有2个输入端口以及输出端口，且各输入端口具有4个虚拟信道(VC)。

在从中继装置A内的8个虚拟信道向中继装置B发送信息包时，中继装置A能够利用的中继装置B的虚拟信道的个数为4个。所以，中继装置A的8个虚拟信道无法同时确保中继装置B的虚拟信道。因此，不区别信息包的发送节点，而根据信息包到达中继装置A的顺序或到达目的地的节点为止的截止时刻的顺序、赋予信息包的优先度的顺序等，来选择相邻的中继装置的虚拟信道。其结果是，从相同发送节点输出的信息包，会发生将中继装置B内的虚拟信道全部占有的状况。

例如，如图5所示，若在中继装置A的虚拟信道当中，仅对保存主设备A的信息包的虚拟信道，分配中继装置B的虚拟信道，则中继装置B的虚拟信道不足。中继装置A，无法发送来自主设备B的信息包，针对作为不同发送节点的主设备A和主设备B的信息包，无法进行基于开关分配(SA)的发送调度。其结果是，针对各发送节点维持恰当的传送性能的传送变得困难。

因此，在中继装置A中，为了恰当地进行基于SW分配(SA)的调度，需要按照发送节点不同的每个信息包来分配1个以上的虚拟信道(VC)。

利用并行计算机或ATM的一般的网络通信是尽力服务型通信，允许延迟。此外，针对发送缓冲器(虚拟信道)的尺寸的限制，也比半导体的情况小。即使连续发送指向相同目的地发送的信息包，也会由于从中继装置内的虚拟信道相同的发送节点发送来的信息包，而难以发生全部被占有的状况。此外，即使由从相同发送节点接收到的信息包占有了中继装置的虚拟信道，也会由于与占有状态持续的时间相比，在并行计算机或ATM中能够允许的信息包的延迟时间更长，而对传送性能的影响小。

另一方面，NoC中的通信的多数，大多需要实时处理性，且不允许延迟等，针对延迟的限制较大。并且，由于在半导体电路上安装中继装置，因此对虚拟信道的个数或尺寸的限制较大，容易发生中继装置内的虚拟信道的不足。其结果是，直至不足的虚拟信道被开放为止的延迟时间会对传送性能产生很大的影响。

本申请发明人，鉴于上述问题点，完成本申请发明。

本发明的一方式的概要如下。

本发明的一方式的中继装置，在具有信息包交换方式的分散型总线的集成电路中，对在节点间所传送的信息包进行中继，具有：多个缓冲器，保存附加了对发送节点进行确定的信息的信息包；分类部，其根据所述信息包的发送节点，将保存有信息包的所述多个缓冲器分类为多个组；选择部，其至少选择一个属于各组的缓冲器；和输出端口，其依次输出被选择的所述缓冲器中所保存的信息包。

在某一方式中，在所述信息包中附加有时间信息，当有2个以上缓冲器属于被分类的组时，所述选择部根据各缓冲器中所保存的所述信息包的时间信息，将2个以上缓冲器当中的一个选择作为优先位次最高的缓冲器，当仅有1个缓冲器属于被分类的组时，所述选择部选择所述缓冲器作为优先位次最高的缓冲器。

在某一方式中，所述输出端口，以根据各信息包的时间信息而确定的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

在某一方式中，所述时间信息是信息包应到达发送目的地的节点的截止时刻，所述输出端口按照所述截止时刻的由近至远的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

在某一方式中，所述时间信息是信息包从发送源的节点被发送的发送时刻，所述输出端口按照所述发送时刻由早至晚的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

在某一方式中，所述中继装置还具有：测定部，其按照每个发送节点，来测定对信息包的传输的拥挤状况的程度进行表示的指标，所述拥挤状况越严重，越测定为较大指标；和决定部，其决定输出量，以使越是所述指标较大的发送节点，越从所述输出端口输出更多的信息包。

在某一方式中，所述测定部，对由所述分类部分类出的缓冲器的个数进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

在某一方式中，所述测定部，对信息包到达本中继装置起至传出的通过时间进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

在某一方式中，所述测定部，对总线的利用频带进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

在某一方式中，所述发送节点是一个总线主设备、或者多个总线主设备的集合体，所述分类部根据所述一个总线主设备、所述多个总线主设备的集合体、或者所述信息包在传送路径上通过了的一个或多个中继装置，将所述多个缓冲器分类为所述多个组。

在某一方式中，所述分类部根据所述信息包在传送路径上通过了的中继装置，将保存有信息包的所述多个缓冲器分类为多个组。

在某一方式中，存在多个发送节点、并且各发送节点被预先分类为属于多个组的任一个，所述分类部根据发送了所述信息包的发送节点所属的组，将保存有信息包的所述多个缓冲器分类为多个组。

(实施方式1)

图6是说明本实施方式的中继装置的动作的概要的图。主设备A和主设备B，经由NoC上的中继装置A和中继装置B而与公共的存储器连接。表示出主设备A和主设备B分别向存储器发送信息包的情形。

中继装置A和中继装置B，分别各具有两个输入端口和输出端口，各输入端口中各具有4个虚拟信道(VC)。

本实施方式的中继装置，在进行虚拟信道的分配(VA)时，参照由分配完毕的虚拟信道发送的信息包的发送节点。然后，当从多个发送节点接收信息包(信息片)时，对保存有从各发送节点发送来的信息包(信息片)的虚拟信道，分配相邻的中继装置的至少一个虚拟信道(VA)。换言之，对各发送源分配1个以上中继装置的虚拟信道(VA)，以使从某个发送节点发送来的信息包不占有相邻的中继装置的虚拟信道，并且使所有的发送节点的信息包能够维持发送调度。

例如，在图6中，本发明的一方式的中继装置A，分别确定在中继装置B中被分配了虚拟信道的信息包的发送节点，针对保存有从主设备A和主设备B发送来的各信息包的虚拟信道，进行虚拟信道的分配，以使被分配的中继装置B的虚拟信道的个数成为相同。中继装置A，针对保存有来自主设备A和主设备B的信息包的虚拟信道分配一个以上中继装置B的虚拟信道。由此，能够基于交叉开关的切换(SA)进行发送调度，从而能够维持与每个主设备的请求相符的频带控制。

图7是本实施方式中假设的分散型的总线的结构图。

在本实施方式中，以经由多个中继装置(R)连接了作为发送节点的多个总线主设备(BM)与作为接收节点的多个存储器(M)的结构(多段连接网，MIN：Multistage Interconnection Network)为例进行说明。各中继装置设为2输入2输出。

在图7中，表示出8个总线主设备(BM0～BM7)、12个中继装置(R0～R11)、8个存储器(M0～7)通过总线被连接的电路的情形。图7的最左边所示的3位数字，表示总线主设备(发送节点)的地址。此外，图7的最右边所示的3位数字表示存储器(目的地节点)的地址。

12个中继装置，每4个为一组地分为3个组。3个组是与8个总线主设备连接的组(R0、R1、R2、R3)、与8个存储器连接的组(R8、R9、R10、R11)、以及连结与总线主设备或存储器连接的中继装置的组(R4、R5、R6、R7)。

构成多级连接网的各中继装置，具有2输入2输出的交叉开关。在各中继装置中，能够通过切换交叉开关，变更输入端口与输出端口的连接的组合，来变更信息包的传送路径。而且，从一个中继装置向输出端口不同的传送路径，能够同时发送信息片。

在多级连接网中，通过各中继装置上的开关的切换，在所有总线主设备与所有存储器之间，必然能够构筑一个以上的传送路径。

一般而言，为了通过交叉开关来连接N个总线主设备和M个存储器的全部，开关需要N×M个。而且，随着总线主设备或存储器的个数增加，开关的个数会急剧增加。相对于此，在多级连接网(MIN)中，具有以下特征：通过阶段性地连接输入输出端口个数少的交叉开关，能够仅通过小的开关来切换总线主设备与存储器之间的连接。

而且，在本实施方式中，虽然举例说明了多级连接网，但这仅是一个示例。即便集成电路的结构是其它拓扑，也能够应用上述的技术。此外，在本实施方式中，从总线主设备向存储器的数据传送，设为是通过信息包交换方式经由多个中继装置来进行的，以此进行说明。

此外，在各中继装置中，发送来的信息片，通过开关的切换而被发送至与目标的路径接续的中继装置、或目的地的节点。

而且，在图7中，虽然假设了从总线主设备向存储器发送信息片的示例，但这仅是一个示例。信息片的目的地不局限于存储器。信息片的目的地，例如，可以是其它总线主设备，也可以是用于与周边设备连接的输入输出接口。

图8是本实施方式的中继装置1201的结构图。

中继装置801具有：输入缓冲器802；开关803；输出缓冲器804；虚拟信道信息管理部805；输出端口选择部806；发送节点分类部807；时间信息比较部808；输出信道选择部809；虚拟信道选择部810；和开关切换部811。

以下，对各结构要素的功能进行说明。

输入端口812，接收从相邻的中继装置、或发送节点(例如图7的BM0～BM7)发送来的信息片。

输入缓冲器802是存储从在输入端口侧相邻的中继装置801a(或发送节点)发送来的信息片的缓冲器。

构成输入缓冲器802的临时缓冲器，可以按照中继装置801的每个输入设置一个，或者也可以按照每个输入而设置多个虚拟信道813以使能够按照不同的每个信息包利用单个信道来进行发送调度控制。在本实施方式中，如图8所示，按照每个输入缓冲器812，各具有4个虚拟信道813。

交叉开关803，是对中继装置801的输入端口812与输出端口814的排他性连接进行切换的开关。

输出缓冲器804，是向与后述的输出端口814连接的中继装置组801b发送信息片时所利用的临时缓冲器。

在输出缓冲器804中，还设置有多个输出信道815。输出信道815，仅设置了与输出端口814连接的中继装置801b的输入缓冲器内的虚拟信道相同的个数，且与相邻的中继装置组801b的虚拟信道确定为一对一的对应关系。

输出端口814从中继装置801向相邻的中继装置801b、或接收节点发送信息片。

从中继装置801发送的信息片被存储于与在发送中利用的输出信道所对应的输出端口814连接的中继装置801b的虚拟信道中。即，中继装置801，通过选择在信息片的发送中利用的输出信道815能够在输出端口814所连接的中继装置801b中指定保存发送来的信息片的虚拟信道。

虚拟信道信息管理部805，管理与各虚拟信道813所保存的信息片相关的信息。虚拟信道信息管理部805所管理的信息的内容的细节，在后面使用图9来进行说明。

若向输入缓冲器814发送了新的头信息片，则输出端口选择部806根据头信息片所记述的目的地信息，来选择接续至接着进行传输的中继装置801b的输出端口。

发送节点分类部807，根据各虚拟信道内所保存的信息包的发送节点的不同，进行虚拟信道的分组。

时间信息比较部808，比较基于对各虚拟信道813所保存的信息包中被赋予的时间信息的优先度，按优先度从高至低的顺序对虚拟信道赋予分配虚拟信道的顺序。

在本实施方式中，信息包中被赋予的时间信息，设为是信息包到达目的地节点的截止时刻。此外，基于时间信息的优先度，设为信息包到达目的地为止的截止时间越是最短的信息包、优先度越高。

输出信道选择部809，根据各虚拟信道813内所保存的信息片之中的、由发送节点分类部807进行的每个发送节点的分类结果和由时间信息比较部808进行的信息包的截止时刻的比较结果，来选择输出缓冲器804中的未分配的输出信道815。

虚拟信道选择部810，按照每个输入端口812，从多个虚拟信道813当中，选择一个发送信息片的虚拟信道813的候补。

开关切换部811，通过切换交叉开关803的连接，来决定由虚拟信道选择部810所选择的虚拟信道与各输出端口814之间的排他性连接，并切换交叉开关803的连接。

而且，在本申请说明书中，将在虚拟信道中保存中继装置801接收到的信息片的处理所涉及的输入端口812、输入缓冲器802、虚拟信道813的集合统一定义为输入部。此外，将从中继装置801输出在虚拟信道中所保存的信息片的处理所涉及的交叉开关803、虚拟信道选择部810、开关切换部811、输出缓冲器804、输出信道815、输出端口814的集合统一定义为输出部。

图9是由虚拟信道信息管理部805管理并保持的虚拟信道信息901的一个示例。

虚拟信道信息901，为了区别各虚拟信道，而分配了输入端口和虚拟信道的识别号码，进而，若在虚拟信道中保存了信息包，则要管理：用于确定信息包的发送节点的地址信息、用于确定信息包的目的地的地址信息、信息包到达目的地为止的截止时间等在信息包的发送调度中所利用的时间信息、用于使信息包到达目的地的输出端口的号码、输出信道的号码。而且，时间信息可以不是截止时间，例如，也可以是信息包的发送时刻。

此外，输出信道号码，对从输出端口发送来的信息包进行保存，与作为接收节点的中继装置的虚拟信道的号码对应。

在本实施方式中，虽然对在输出端口814具有输出信道815的中继装置801的示例进行说明，但在不具有输出信道815的中继装置中，要记录在相邻的中继装置801b中利用的虚拟信道的号码，以作为虚拟信道信息901的输出信道号码。

接着，使用图10的流程图和图11至图18来说明各中继装置801的动作与虚拟信道信息901的关系。而且，在图11至图18中，对与图8、图9相同的结构赋予相同符号，并省略说明。

若NoC的电路启动，则中继装置801经由输入端口812成为来自相邻的中继装置801a、或发送节点的信息片的接收等待状态。由此开始图10所示的处理。

图11(A)表示中继装置801内的虚拟信道813的情形。此外，图11(B)表示在中继装置801的输入端口0中尚未接收到信息片的状态时的虚拟信道信息901。

以下，在本说明书中，仅对与输入端口0相关的虚拟信道信息901进行例示。

在图11中，由于未接收到信息片，因此虚拟信道处于未使用状态。

在图10的步骤1001中，判断中继装置801的输入端口812是否接收到信息片。

在接收到信息片时，处理进入步骤1002，在未接收到信息片时，处理进入步骤1003。在接收到信息片时，处理进入步骤1002，在未接收到信息片时，处理进入步骤1003。

在步骤1002中，输入端口812，将接收到的信息片保存到虚拟信道813中。而且，保存有信息片的虚拟信道813，通过相邻的中继装置801a或发送节点来预先决定。

在步骤1003中，输入缓冲器802判断在各虚拟信道813内是否存在信息片。当存在信息片时，处理进入步骤1004，当不存在信息片时，处理返回步骤1001。

在步骤1004中，中继装置801的虚拟信道813，判定在虚拟信道813的开头所保存的信息片是否是头信息片304。当虚拟信道813的开头信息片是头信息片时，处理进入步骤1005，当不是头信息片时，处理进入步骤1008。

图12(A)表示从图11(A)经过1循环时间，在虚拟信道0中保存有到达输入端口0的头信息片304的情形。

头信息片304若到达虚拟信道813，则虚拟信道信息管理部805，在图10的步骤1005中，在虚拟信道信息901中记录在中继装置801的发送调度中用于决定信息包的发送顺序的信息。所谓用于决定信息包的发送顺序的信息，例如，是在头信息片304中所记载的发送节点发送源和接收节点目的地的节点的各个地址，信息包整体到达目的地的节点为止的截止时刻。

此外，图12(B)表示头信息片304中被赋予的发送节点以及目的地的地址、反映了发送时刻信息后的虚拟信道信息901的内容。其中，在虚拟信道信息901中记录：作为信息包的发送节点的BM2的地址010(图7)、作为目的地的存储器5的地址101(图7)、和信息包到达目的地为止的截止时刻90(循环)。

图13(A)表示从图12(A)进一步经过1循环时间，接续于头信息片，在虚拟信道0中保存了数据信息片的情形。

中继装置801的输出端口选择部806，在图10的步骤1006中，参照在步骤1005中被更新的虚拟信道信息901来确定信息包的目的地，并选择用于向目的地发送信息包的输出端口814。

在此，说明使用图7所示的多级连接网来选择输出端口814的方法的一个示例。在图7所示的多级连接网中，对各存储器以3位二进制数分配了地址，对各信息包的头信息片以3位二进制数赋予了成为目的地的存储器的地址。

实施方式1的输出端口选择部806，在头信息片中被赋予的3位地址之中，从左边读取与中继装置的级数相同位的数字。然后，若该值为0，则在图12中选择输出端口0，若值为1，则在图12中选择输出端口1。

例如，考虑从总线主设备BM2(地址：010)向存储器5(地址：101)发送数据的情况。按照存储器5的地址所记载的3位数字，首先，中继装置R1向右下的中继装置R7发送信息片。接着，中继装置R7向右上的中继装置R10发送信息片。最后，中继装置R10向右下的存储器5发送信息片。由此，从总线主设备BM5向存储器2传送信息片。

而且，作为由输出端口选择部806进行的输出端口的选择方法，若是根据分散总线的拓扑而恰当地将信息片发送至目的地的方法，则也可以是上述以外的方法。

图13(B)表示出选择了中继装置801的虚拟信道815的输出端口814之后的虚拟信道信息901。可知选择了输出端口0。由此，中继装置801能够将虚拟信道0当中的信息包发送至指向作为目的地的存储器5的输出端口0。

图14(A)表示从图13(A)经过1循环时间，在虚拟信道0中接续于头信息片304、数据信息片305，保存了数据信息片306的情形。

中继装置801，在图10的步骤1007中，发送节点分类部807、时间信息比较部808、和输出信道选择部809，参照虚拟信道信息管理部805，并将虚拟信道中所保存的信息包分类为基于发送节点之不同的组，进而按照每个被分类的组来确定保存有信息包到达目的地为止的截止时间最短的信息包的虚拟信道。而且，在所确定的虚拟信道之中，若输出信道为未设定的信道，则对该虚拟信道分配输出信道。

如前面的图13(A)所示，在中继装置801中，虽然选择了输出端口0，但输出信道存在未选择的虚拟信道。此外，在输出端口0中存在未使用的输出缓冲器0。因此，输出信道选择部809，针对输入端口0的虚拟信道0，分配输出端口0的输出信道0。

图14(B)表示出决定了中继装置801输出信道815之后的虚拟信道信息901。在虚拟信道信息901中，选定对虚拟信道0所选择的输出信道号码0。

在此，虽然为了简化说明，而以在刚启动后的中继装置801中到达一个信息包的情况为例进行了说明，但对于在多个信息包刚到达中继装置801之后对各虚拟信道813分配输出信道814的处理，将使用图17在后面详细进行说明。

图15(A)表示出从图14(A)经过1循环时间后的中继装置801的虚拟信道815的情形。

在图10的步骤1008中，中继装置801的虚拟信道选择部810，按照每个输入端口812，从输出信道分配完毕的虚拟信道之中选择一个虚拟信道。

而且，中继装置801的开关切换部811，通过虚拟信道选择部810，来判定：在按照每个输入端口812而选择出的一个虚拟信道之间，输出端口是否有竞争。如果，输出端口为竞争的虚拟信道，则从其中选择一个虚拟信道。

由此，按照每个输出端口814选择发送信息片的虚拟信道813，基于该结果，开关切换部811切换交叉开关803的连接，以使包含所选择的虚拟信道813的输入端口812与输出端口814连接。

若切换了交叉开关，则在步骤1009中，虚拟信道选择部810和开关切换部811所选择的虚拟信道813分别发送信息片。

图15(B)表示出从头信息片至数据信息片被发送的状态下的虚拟信道信息901的情形。尾信息片尚未发送。

图16(A)表示从中继装置803至尾信息片被发送时的各虚拟信道813的情形。

在图10的步骤1010中，虚拟信道814，在发送信息片时，判定所发送的信息片是否为构成信息包的最后的信息片。

在图10的步骤1011中，当所发送的信息片是构成信息包的最后的信息片时，开放至此确保的虚拟信道，以使其它信息包能够利用该虚拟信道。虚拟信道信息管理部805，对与发送了尾信息片的虚拟信道814相关的信息进行初始化。

图16(B)表示出发送了尾信息片1106后的虚拟信道信息901。通过从输入端口0的虚拟信道0中发送了尾信息片，从而虚拟信道信息管理部805，对与输入端口0的虚拟信道0相关的信息进行初始化。

以上，通过重复从步骤1001至步骤1011的处理，中继装置801将信息包向目的地进行中继处理。

图17是表示在图10的步骤1007中，输出信道选择部809对虚拟信道813分配输出信道815的输出信道的处理(虚拟信道分配：Virtualchannel Allocation)的流程图。

此外，图18(A)表示在中继装置801中，多个信息包同时到达时的虚拟信道813的情形。在中继装置801中，不仅会发生构成相同信息包的信息片连续达到的情况，而且还会发生构成不同信息包的信息片混合到达的情况。此外，图18(B)表示出虚拟信道813处于图18(A)的状态时的虚拟信道信息901的内容。

根据图18(A)及图18(B)，在中继装置801所设置的输入端口0的虚拟信道1中，从发送节点010向目的地000的信息包已到达。然后，保存1个构成截止时刻为140以内的信息包的头信息片和数据信息片，设定了输出端口0。输出信道未设定。

另一方面，在输入端口0的虚拟信道2中，从发送节点010向目的地000发送的信息包已到达。然后，保存1个构成截止时刻为105循环的信息包的数据信息片，设定了输出端口0和输出信道0。

另一方面，在输入端口1的虚拟信道0中，从发送节点111向目的地010发送的信息包已到达。然后，保存一个构成截止时刻为125循环的信息包的头信息片和数据信息片，设定了输出端口0。

在输入端口1的虚拟信道1中，从发送节点110向目的地011发送的信息包已到达。保存构成截止时刻为130循环的信息包的头信息片，设定了输出端口0。

在输入端口1的虚拟信道2中，从发送节点111向目的地010发送的信息包已到达。保存构成截止时刻为118循环的信息包的头信息片，设定了输出端口0。

以下，以中继装置801的虚拟信道处于图18的状态时为例，使用图17来说明针对虚拟信道的输出信道的分配的细节。

在步骤1701中，输出信道选择部809，选择输出端口，并且，判断输出信道是否存在未选择的虚拟信道813。若输出端口被选择、且输出信道不存在未选择的虚拟信道813，则返回步骤1701。若输出端口被选择、且输出信道存在未选择的虚拟信道813，则处理转移至步骤1702。

在步骤1702中，虚拟信道813判定在输出端口814中是否存在空闲的输出信道815。若输出信道815中无空闲，则返回步骤1702。若在输出信道815中有空闲，则处理转移至步骤1703。

在步骤1703中，发送节点分类部807，根据信息包的发送节点的不同，将输出信道未选择的虚拟信道进行分组。

图19表示中继装置801的虚拟信道813的内容为图18(B)时的发送节点分类部807将虚拟信道分类后的结果的示例。也就是说图19表示基于发送节点的不同的虚拟信道的分组。

如图18(B)所示，在虚拟信道815中，保存有从3种发送节点(地址为010、110、111)到达的信息片。即，虚拟信道，根据发送节点，也就是说根据发送源的地址被分类为3组。对发送节点的地址为010的组，分类输入端口0的虚拟信道1，对发送节点的地址为110的组，分类输入端口1的虚拟信道1，对发送节点的地址为111的组，分类输入端口1的虚拟信道0和虚拟信道3。

而且，图19的最下段所示的“设定完毕的输出信道数”，表示出直至输出信道号码的设定为止已结束的虚拟信道数。在图18(B)的示例中，设定了虚拟信道号码2的虚拟信道直至输出信道号码为止，其它虚拟信道未设定输出信道号码。因此，若按照发送源的每个地址进行分类，则仅地址“010”的发送源栏记载为“1”，其它成为“0”。

接着，在步骤1704中，时间信息比较部808，参照在虚拟信道信息901中所记录的截止时刻，并按照由发送节点的地址的不同所分类出的各组的每个虚拟信道，将保存截止时刻最接近的信息包的虚拟信道选择为优先位次1。此时，已经分配完毕的虚拟信道从优先位次的设定对象中被除外。

在图19中，在发送节点的地址为010的组中，选择输入端口0的虚拟信道1，在发送节点的地址为110的组中，选择输入端口1的虚拟信道1，在发送节点的地址为111的组中，选择输入端口1的虚拟信道0。

通过该步骤S1704的处理，输出信道选择部809，能够对所有发送节点分配一个以上输出信道。而且，当对于某一发送节点而言，对所有虚拟信道本来就分配有输出信道时，该发送节点从基于上述处理的优先位次的确定中被除外。

接着在步骤1705中，判断是否存在设定完毕的输出信道数为0的发送节点的信息包。当存在时，处理进入步骤S1706，当不存在时，处理进入步骤S1707。

若存在未设定输出信道的发送节点的地址，则转移至步骤1706，若不存在未设定输出信道的发送节点的地址，则步骤转移至步骤1707。

在图19的示例中，在发送节点的地址为010的组中，由于已经对发送节点的地址相同的输入端口0的虚拟信道2分配了输出信道，因此，设定完毕的输出信道数为1。在发送节点的地址为110和111的组中，在发送节点的地址相同的虚拟信道中不存在分配了输出信道的虚拟信道，因此，设定完毕的输出信道数为0。因而，在图19的示例中，由于存在输出信道未设定的发送节点的地址(110、111)，因此，转移至步骤1706。

接着，在步骤1706中，输出信道选择部809，在输出信道未设定的发送节点的虚拟信道中，选择一个截止时间最接近的虚拟信道，换言之，选择一个优先度最高的虚拟信道。

在图19的示例中，在输出信道未设定的组(110、111)中，选择截止时间最接近的输入端口1的虚拟信道0。

当对于所有的发送节点，存在一个以上分配了输出信道的虚拟信道时，在步骤1707中，输出信道选择部809，在所有的组中，对截止时刻最接近的虚拟信道分配输出信道。

如上所述，通过重复步骤1701至步骤1707，中继装置801，能够对所有发送节点分配一个以上输出信道，并且从截止时间接近的虚拟信道优先分配输出信道。

图20(A)及(B)，是说明在图10的步骤1008中，虚拟信道810和开关切换部811对于选择了输出端口和输出信道的虚拟信道813进行向输出端口的连接、且分配信息片的发送定时的处理(开关分配：SwitchAllocation)的图。

图20(A)是说明其动作的一个示例的流程图。此外，图20(B)是说明对虚拟信道选择完毕的虚拟信道，输出端口的连接所决定的动作的流程的图。

在步骤2001中，虚拟信道选择部810，按照每个输入端口，选择一个设定有输出信道的虚拟信道。

例如，在图20(B)的示例中，在输入端口0和输入端口1中分别各具有4个虚拟信道，在输入端口0中，处于对虚拟信道0和3设定了输出信道的状态。此外，在输入端口1中，处于对虚拟信道0、1和2设定了输出信道的状态。

虚拟信道选择部810，在各个输入端口中，从呈输出信道设定完毕的虚拟信道之中，选择一个虚拟信道。在图20(B)中，虚拟信道选择部810对于输入端口0选择虚拟信道0，对于输入端口1选择虚拟信道1。

接着，在步骤2002中，开关切换部811，按照每个输出端口，在输入端口侧所选择的虚拟信道中，从输出端口的设定竞争的信道中选择一个虚拟信道。

在图20(B)中，例如，在输入端口0所选择的虚拟信道以及在输入端口1所选择的虚拟信道都设定为输出端口0时，开关切换部811选择两个虚拟信道的一个。

而且，针对开关分配，也可以是上述说明以外的方法。

例如，若选择图20(A)步骤2001中的每个输入端口的虚拟信道，则在步骤2002中每个输出端口的虚拟信道的选择中，按照每1循环，通过轮叫调度(round robin)按照顺序选择多个虚拟信道的方法，或也可以概率上随机地进行选择。如此在每1循环中变更了发送信息片的虚拟信道的情况下，能够以信息片单位交织(interleave)发送源不同的信息包，从而从表面上看将多个信息包并列地进行输出。

这样，本实施方式的中继装置801，通过区别信息包的发送节点，并对从不同的发送节点发送来的信息包分配在NoC的中继装置中所限定的虚拟信道，发送节点相同的信息包占有中继装置801的虚拟信道，避免在发送节点不同的信息包之间无法进行发送定时的调度的状况，抑制降低传送性能(吞吐量、延迟时间、抖动(jitter))。

在本实施方式中，在时间信息比较部808中，根据信息包中被赋予的截止时刻来进行了输出信道的分配。然而，即使截止时间以外，也可以以与信息包的中继相关的时间信息为基准，来定义输出信道的分配的优先位次。

图21表示时间信息，以及基于时间信息的优先度的比较基准的示例。

作为时间信息，例如，可以使用从发送信息包起的经过时间。

为了作为时间信息来管理发送时刻，需要仅能表达半导体系统正在动作的期间的位数。因此，在半导体系统长时间进行动作时，时间信息的位数变大。

相对于此，在使用从发送信息包起的经过时间作为时间信息的情况下，只要仅表达从信息包被发送至被接收为止所需的时间的位数即可，因此，能够将时间信息的位数抑制得较小。若作为时间信息处理的值的位数较小，则由于能够缩小时间信息比较部808中的时间信息的比较电路，因此对半导体系统的资源削减是有效的。

此外，即使使用发送时刻，也能够通过使用由年月日时分秒表达的发送时刻的一部分(例如，M位的发送时刻，从较小位起使用n位的值(n：M＞n的整数))，而缩小作为时间信息进行处理的位数。作为n位的值，例如，能够使用仅表达从信息包被发送至被接收为止所需的时间的位数。

此外，作为时间信息，可以使用信息包到达接收节点为止的截止时刻，从截止时刻接近的信息包起按顺序分配输出信道。

一般而言，根据总线主设备的种类或处理的内容，直至信息包到达接收节点为止能够允许的延迟时间会不同。因此，在从发送节点发送了多个直至截止时刻为止的时间较长的信息包之后，若假设发送直至截止时刻为止的时间较短的的信息包的状况，则在中继装置中，与从发送时刻早的信息包起按顺序分配输出信道来发送信息包相比，从直至截止时刻为止的残留时间较短的信息包起分配输出信道来发送信息包的方式，能够针对更多的信息包，遵守可允许的延迟时间。

此外，作为时间信息，也可以代替截止时刻而采用直至截止时刻为止的剩余时间。

在本实施方式中，以在发送节点分类部807中，将发送节点的区别作为发送节点的地址为例进行了说明。然而，发送节点的区别的定义，不局限于发送节点的地址。

例如，作为发送节点，也可以指定中继装置。图22(A)及(B)表示出从中继装置R9观察的各种目的地的定义，以及能与该定义相当的目的地的具体例。例如，在图22(A)的结构中，能够将可成为信息包的发送节点的在传送路径上通过途中的中继装置定义为发送节点。

若对于图22(A)的中继装置R9，设为发送节点为总线主设备，则对于中继装置R9而言的发送节点，从总线主设备0至总线主设备7为止的8个成为对象。另一方面，若发送节点设为从该中继装置观察时为两个之前的中继装置，则对于中继装置R9而言的发送节点，可成为4个中继装置R0～R3。而且，若将目的地的定义设为一个之前的中继装置，则2个中继装置R4以及R5成为发送节点。

此外，在图22(A)中，作为第n级的中继装置区别一个之前已通过的中继装置的方法，能够通过信息包中被赋予的发送源的地址之中从右起第(n+1)位的数值来进行区别。

例如，图22(A)的中继装置R9是第1级的中继装置。因此，参照接收到的信息包的发送源的地址，若从右起第二位的数值为0，则判定为通过了中继装置R4的信息包。此外，若从右起第二位的数值为1，则判定为通过了中继装置R5的信息包。如此，能够分别区别信息包一个之前已通过的中继装置。

此外，作为第n级中继装置判定两个之前已通过的中继装置的方法，能够通过信息包中被赋予的发送源的地址之中从右起第(n+1)位和第(n+2)位的数值来进行区别。

例如，参照图22(A)的第1级的中继装置R9中接收到的信息包的发送源的地址。然后，若从右起第二位和第三位的数值为00，则判定为通过了中继装置R0的信息包。此外，若从右起第二位和第三位的数值为01，则判定为通过了中继装置R1的信息包。此外，若从右起第二位和第三位的数值为10，则判定为通过了中继装置R2的信息包。此外，若从右起第二位和第三位的数值为10，则判定为通过了中继装置R2的信息包。此外，若右起第二位和第三位的数值为11，则判定为通过了中继装置R3的信息包。通过这样的步骤，能够分别区别信息包两个之前已通过的中继装置。

如此，通过将发送节点的定义设为传送路径上的途中的中继装置，与实际上将发送信息包的总线主设备设为发送节点的情况相比，能够削减在发送节点分类部807分类的组的个数，能够减轻在虚拟信道间的发送节点的比较处理。

此外，为了削减在发送节点分类部807进行分类的组的个数，也可以将每多个发送节点统一为一个组，将它们处理作为一个发送源。

例如，图23(A)表示网格型的NoC中的总线主设备的地址。此外，图23(B)表示基于地址(X，Y)的第一位的值的总线主设备的分组。

以下，以图23(A)所示的网格型的NoC为例，对将多个发送接收节点处理为一个组的方法进行说明。

在图23(A)中，表示由赋予了(00，00)等地址的多个总线主设备、和多个中继装置(R)构成的网格型NoC。

在图23(A)的NoC中，16个总线主设备以纵横各4列格子状被配置，且通过中继装置连接。在图23(A)中，各总线主设备的地址，将图23的横向设为X轴，将纵向设为Y轴，分别以2位二进制数定义X轴方向和Y轴方向的号码。

在此，若以各总线主设备的地址的X和Y的值的从左起第一位的值来区别总线主设备，则如图23(B)所示，能够将16个总线主设备分别分类为地址为(0，0)、(0，1)、(1，0)、(1，1)的四个组。

然后，若关注属于某个组的中继装置，则只要针对保存有从自身所属的组内发送来的信息包和从各个其它三个组发送来的信息包的虚拟信道，选择保存截止时刻最接近的信息包的虚拟信道作为优先位次1即可。

而且，将多个发送接收节点统一为一个组的方法，例如，也可以采用各发送接收节点的地址的X坐标和Y坐标分别从左起第二位的值。

此外，也可以与NoC的拓扑的形式、或各总线主设备的地址的决定方法相符地进行变更。

在被作为发送节点的中继装置中已有信息包到达的情况下，该中继装置只要再次根据图21(B)的任一个定义来设定发送节点，并发送信息包即可。

此外，为了削减由发送节点分类部807分类的组的个数，也可以根据集成电路内的拓扑或总线的种类的不同，将多个发送节点统一成一个组，并将它们处理作为一个发送源。也就是说，虽然微观上存在多个发送节点，但宏观上观察这些多个发送节点，能够以整体处理作为一个发送节点。

图24表示将多个总线主设备(总线主设备组)的集合体看作一个发送节点来处理的集成电路100的结构。

图24的集成电路100由在较宽范围进行高速连结的基干总线101和在较近距离进行低速连结的本地总线102a～102c这两种总线构成。基干总线101和本地总线102a～102c由中继装置103a～103c连接。该中继装置具有在传送频带不同的总线之间能够传送数据的性能。具有这样性能的中继装置也可以被专用设置。

在图24的示例中，将属于本地总线A的总线主设备的集合(总线主设备组)处理作为发送节点A，将属于本地总线B的总线主设备组处理作为发送节点B，将属于本地总线C的总线主设备组处理作为发送节点C。而且，本地总线内的中继装置，将各总线主设备作为各发送节点来进行动作。

一般而言，通过总线的布线或动作频率的限制，不容易通过高速总线来连接集成电路上的所有总线主设备。因此，如图24所示，通过利用本地总线汇集来自多个总线主设备的发送数据，并传送至最接近的基干总线，从而在电路设计中能够减少总线的布线或动作频率的限制。

如此，在多个总线主设备间的连接，通过不同的本地总线被划分的情况下，在基干总线上的中继装置中，为了削减在发送节点分类部807分类的组的个数，也可以将属于相同本地总线的总线主设备的集合进行统一，处理作为一个发送节点。

作为识别总线主设备属于哪个本地总线的方法，考虑有多个。例如，如下：

(1)各中继装置在发送节点分类部807中保持对能够识别发送源的总线主设备的发送节点地址与该总线主设备所属的本地总线的对应关系进行了定义的表格，以对接收到的信息包的发送节点地址和表格的内容进行比较。由此，各中继装置，能够识别该信息包是从哪个本地总线发送来的信息包。

(2)在信息包的头段301中，预先赋予确定本地总线的信息，发送节点分类部807，接收信息包的中继装置参照头段301。由此，能够识别该信息包是从哪个本地总线发送来的信息包。

在图24中，与公共的本地总线连接的多个总线主设备，被看作一个发送节点。而且，不需要以本地总线单位来规定发送节点，例如，能够根据拓扑或总线的种类的不同来规定发送节点。

更具体而言，可以将多个本地总线统一为一个而作为一个发送节点。例如，当相对于属于本地总线C的总线主设备数，属于本地总线A和本地总线B的总线主设备分别较少、且发送量也较少时，将属于本地总线A和本地总线B的总线主设备进行统一而处理作为一个发送节点。通过减少属于各发送节点的总线主设备数之差，能够减少发送量之差。

(实施方式2)

在实施方式1中，在安装上存在对虚拟信道数或尺寸的限制的半导体电路上的中继装置中，设为：中继装置区别要发送的信息包的发送节点，对各个发送节点的信息包分配1个以上作为相邻的接收节点的中继装置的虚拟信道。由此，维持了针对从不同的发送节点到达的多个信息包能够进行发送调度的状态，并提高了该传送效率(吞吐量或传送延迟)。

在本实施方式中，当按照每个发送节点，信息包的发送效率不同时，中继装置，根据来自各个发送节点的信息包的拥挤状况来调整在作为相邻的接收节点的中继装置中虚拟信道的分配数，针对拥挤的信息包，通过优先分配相邻的中继装置的虚拟信道而使NoC的传送效率提高。

作为由于发送节点的不同而使作为中继装置内的信息包的拥挤状况不同的情况，例如，在图5的示例中，来自主设备A的信息包的发送间隔比主设备B的发送间隔短，来自主设备A的信息包的传输比主设备B的信息包的传输更拥挤，在中继装置A中，会发生保存有从各个主设备发送来的信息包的虚拟信道的个数为4个和2个这样的状况。

若针对中继装置自身的虚拟信道，如图6所示，公平地进行在中继装置B中保存所发送的信息包的虚拟信道的分配，则来自拥挤较大的主设备A的信息包的传输，在至中继装置A为止的路径上容易占有虚拟信道，即使其它发送节点(例如主设备C)在之后想要发送信息包，也由于在路径上没有虚拟信道的空闲，易于产生无法立即进行发送的问题。

图25是对本实施方式的中继装置的动作进行说明的图。

图25的结构，由于与图6相同，因此省略说明。

实施方式2的中继装置A，对各发送节点的信息包，最少分配1个中继装置B的虚拟信道，以使能够维持发送调度，进而，根据中继装置A的虚拟信道的利用数与中继装置B的虚拟信道利用数的关系，对拥挤较大的发送节点的信息包优先分配中继装置B的虚拟信道。

图25的中继装置A，例如，对来自主设备A的信息包和来自主设备B的信息包，首先，各分配1个中继装置B的虚拟信道，进而，决定针对来自各主设备的信息包的中继装置B的虚拟信道的分配量，以使中继装置A利用的虚拟信道的个数与在中继装置B利用的虚拟信道的差分接近于均等。

在图25的示例中，首先，分别对来自主设备A的信息包、来自主设备B的信息包各分配1个中继装置B的虚拟信道，进而，由于来自主设备A的信息包和来自主设备B的信息包在中继装置A中利用的虚拟信道数的比率为4比1，因此，对来自主设备A的信息包优先将中继装置B的虚拟信道分配多个(3个)，以使在中继装置B中利用数也接近于4比1。

图26是对本实施方式中的中继装置的结构进行说明的图。

针对与实施方式1相同的结构，赋予相同符号而省略说明。

发送负荷测定部2401，按照每个发送节点，测定信息包的传输(业务)的负荷、或表示拥挤状况的值(指标)。输出信道分配决定部2402，根据由发送节点的不同而被区别的信息包的发送负荷，来决定接受节点的中继装置801b的虚拟信道的分配量。

图27是说明本实施方式中的中继装置的动作的流程图。针对与图10相同的处理，赋予相同符号，并省略说明。

在步骤1704中，当对中继装置801中所保存的信息包的所有发送节点，分配了一个以上输出信道815的情况下，在步骤2501中，中继装置801的发送负荷测定部2401，按照每个发送节点，测定信息包的传输的拥挤状况。

图28是说明在NoC上的中继装置801中，表示信息包的传输的拥挤状况的指标的一个示例的图。

作为表示在发送节点所区别的信息包的传输的拥挤状况的指标，可列举：(1)虚拟信道的利用数、(2)从信息包到达中继装置起至发送出的通过时间、(3)总线的利用频带(使用频带、设计频带)等。

在以下的说明中，作为表示在发送节点所区别的信息包的传输的拥挤状况的指标，以(1)虚拟信道的利用数为例进行说明。

在步骤2502中，输出信道分配量决定部2402，在中继装置801的虚拟信道中，对按照每个发送节点进行区别而得到的输出信道呈未设定的虚拟信道数、和按照每个发送节点区别而得到的设定完毕的输出信道(与中继装置801b的虚拟信道对应)数进行比较，以该差分为基础来决定分配的优先位次。

图29是对输出信道分配量决定部2402的动作的一个示例进行说明的图。

在图29中，在中继装置A中，输出信道呈未选择的虚拟信道有4个，其发送节点是地址为010、110、111这三种。然后，发送节点的地址为010的信息包设为1个，发送节点的地址为110的信息包设为1个，发送节点的地址为111的信息包设为2个。已经对发送节点分配了1个输出信道。

输出信道分配量决定部2402，区别发送节点而根据输出信道呈未设定的虚拟信道的利用数求出输出信道利用数的差分，将它设为针对该发送节点的输出信道的剩余分配量。

在图29中，针对发送节点的地址为010的信息包的输出信道的剩余分配量是0，针对发送节点的地址为110的信息包的输出信道的剩余分配量是0，针对发送节点的地址为111的信息包的输出信道的剩余分配量为1。

在步骤2503中，输出信道选择部809，若输出信道的剩余分配量为1以上的信息包，则转移至步骤2504。当输出信道的剩余分配量全部为0，且正在进行输出信道的分配时，转移至步骤1706。

而且，在步骤2504中，若存在剩余分配量为1以上的发送节点，则输出信道选择部809，对其中优先度最高的信息包分配输出信道。

在图29的示例中，由于发送节点的地址111的剩余分配量为1，因此，对其中最接近截止时间的、在输入端口1的虚拟信道0中所保存的信息包分配输出信道。

以上，通过进行图26的结构和图27的动作，实施方式2的中继装置，当按照每个发送节点而信息包的发送率不同时，针对在发送节点所区别的信息包的传输中呈拥挤的传输，通过优先分配相邻的中继装置的虚拟信道而缓和了拥挤的增加，因此，会提高NoC的传送效率。

以上，对本发明例示的实施方式进行了说明。

在实施方式1及2中，虽然以集成电路的拓扑为多级连接网的情况为例进行了说明，但本发明例示的中继装置并不局限于在多级连接网中的利用。例如，如图30(A)所示，也可以格子状排列中继装置来构成网格型拓扑。此外，如图30(B)所示，也可以在上下左右构成以环状连接中继装置的圆环型拓扑。而且，如图30(C)所示，也可以构成分层地连接总线的分层型拓扑等。若是经由分散型的总线来连接多个总线主设备的拓扑，则能够同样应用上述中继装置。

图31是说明在存储器中利用本发明的一方式的中继装置的示例的图。

在图31中，表示出利用分散型的总线使手机或PDA(Personal DigitalAssistants)、电子书阅读器等便携终端、或TV、录像机、摄像机、监视摄像头等使用的半导体电路上的总线主设备(CPU、DSP、传送处理部、图像处理部等)与多个存储器连接的利用例。

在同时利用多个影像或音乐等的再现、记录、变压器代码、书籍或照片、在地图上的阅览或编辑、游戏的播放等多个应用程序或服务的情况下，从各总线主设备向存储器的访问会增加。当从各总线主设备进行访问的存储器的个数仅一个时，访问会集中于一处。为了解决访问集中，需要扩大存储器侧的输入输出的传送频带，从而成本会增加。

作为避免集中访问该存储器的方法，根据应用程序或服务等的种类将总线主设备利用的存储器进行物理划分，并通过分散型的总线使这些总线主设备与存储器连接，能够避免集中访问存储器。

然而，例如在图31中，当某一总线主设备为了保存影像数据而对存储器A以高速率发送了数据信息包时，若单纯地维持各中继装置发送来的数据信息包的顺序而直接进行中继，则传送路径上的虚拟信道全部被以存储器A为目的地的信息包占有的频度增加。其结果是，难以向其它存储器传输数据，会发生其它应用程序或服务的性能降低或处理时间的增加。

相对于此，在使用本发明例示的中继装置的情况下，在各中继装置的虚拟信道中，由于对目的地不同的信息包均等地分配虚拟信道，能避免因向特定的存储器的信息包而引起的虚拟信道的占有，从而提高半导体电路上的所有应用程序或服务的性能、或缩短处理时间。

而且，上述存储器，可以是易失性的DRAM，也可以是非易失性的闪存。也可以是易失性存储器以及非易失性存储器混合存在。

图32是对在多核处理器(multi-core processor)上利用本发明例示的中继装置的示例进行说明的图。

在图32中，为了提高CPU或GPU、DSP等的核心处理器的处理能力，是以网格状排列多个核心处理器，通过分散总线将它们连接的多核处理器。

在多核处理器中，在各核心处理器间进行了通信，例如，在各核心处理器中，具有存储有运算处理所需要的数据的高速存储器，在核心处理器间处理彼此的高速存储器的信息，能够共享，由此能够提高性能。

然而，在多核处理器上发生的核心处理器间的通信，各个配置或距离(中继点数)、通信频度是不同的。因此，若单纯地维持数据信息包的顺序而直接进行中继，则会产生虚拟信道全部被以特定的核心处理器为目的地的信息包占有而使信息包数据难以传输的中继装置，引起多核处理器的性能的降低、或处理时间的增加。

相对于此，在使用本发明例示的中继装置的情况下，在各中继装置的虚拟信道中，由于对目的地不同的信息包均等地分配虚拟信道，因而能避免因指向特定的核心处理器的信息包而占有了虚拟信道的中继装置的产生，从而提高各核心处理器的性能、或缩短处理时间。

上述的中继装置能够通过硬件或软件来实现。例如，图8所示的各结构要素，能够作为硬件电路被安装。或者，也可以作为设计工具内的处理来安装这些中继装置的各结构要素的动作，通过将各种动作条件作为参数来赋予，从而执行模拟后进行实际的电路设计。通过将中继装置的一个或多个结构要素安装作为设计工具，从而能通过计算程序等来进行总线的频带设计，而不需要由模拟或基于模拟的总线频带的逐次渐进(cut and try)进行的设计和验证，具有能够使开发工数缩短的这一优异效果。

产业上的可利用性

本发明的一实施方式的中继装置，在具有分散型的总线的集成电路中，通过有效地进行针对发送信息包的在各中继装置上的虚拟信道的分配顺序的调度而不增加安装时限制较大的虚拟信道，能够提高NoC整体的传送性能(吞吐量、传送延迟、抖动)。因此，例如，当使用分散总线在一个SoC(System on Chip)上对多个介质处理用的DSP或进行高速文件传送的CPU等进行集成化时，在实现安装所需的资源的省资源化和处理的低延迟化双方上是有用的。

此外，对于基于资源的省资源化和处理的低延迟化的集成电路整体的省电化也是有用的。

附图标记的说明：

300-信息包，

301-头段，

302-数据段，

303-控制代码段，

304-头信息片，

305-数据信息片，

307-尾信息片，

801、801a、801b-中继装置，

802-输入缓冲器，

803-交叉开关，

804-输出缓冲器，

805-虚拟信道信息管理部，

806-输出端口选择部，

807-发送节点分类部，

808-时间信息比较部，

809-输出信道选择部，

810-虚拟信道选择部，

811-开关切换部，

812-输入端口，

813-虚拟信道，

814-输出端口，

815-输出信道，

901-虚拟信道信息，

2401-发送负荷测定部，

2402-输出信道分配量决定部。

Claims (12)

1.一种中继装置，在具有信息包交换方式的分散型总线的集成电路中，对在节点间传送的信息包进行中继，具有：

多个缓冲器，保存附加了对发送节点进行确定的信息的信息包；

分类部，其根据所述信息包的发送节点，将保存有信息包的所述多个缓冲器分类为多个组；

选择部，其至少选择一个属于各组的缓冲器；和

输出端口，其依次输出被选择的所述缓冲器中所保存的信息包。

2.根据权利要求1所述的中继装置，其特征在于，

在所述信息包中附加有时间信息，

当有2个以上缓冲器属于被分类的组时，所述选择部根据各缓冲器中所保存的所述信息包的时间信息，将2个以上缓冲器当中的一个选择作为优先位次最高的缓冲器，

当仅有1个缓冲器属于被分类的组时，所述选择部选择所述缓冲器作为优先位次最高的缓冲器。

3.根据权利要求2所述的中继装置，其特征在于，

所述输出端口，以根据各信息包的时间信息而确定的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

4.根据权利要求3所述的中继装置，其特征在于，

所述时间信息是信息包应到达发送目的地的节点的截止时刻，

所述输出端口按照所述截止时刻的由近至远的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

5.根据权利要求3所述的中继装置，其特征在于，

所述时间信息是信息包从发送源的节点被发送的发送时刻，

所述输出端口按照所述发送时刻由早至晚的顺序，输出各组的所述优先位次最高的缓冲器中所保存的各信息包。

6.根据权利要求1所述中继装置，其特征在于，

还具有：

测定部，其按照每个发送节点，来测定对信息包的传输的拥挤状况的程度进行表示的指标，所述拥挤状况越严重，越测定为较大指标；和

决定部，其决定输出量，以使越是所述指标较大的发送节点，越从所述输出端口输出更多的信息包。

7.根据权利要求6所述的中继装置，其特征在于，

所述测定部，对由所述分类部分类出的缓冲器的个数进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

8.根据权利要求6所述的中继装置，其特征在于，

所述测定部，对信息包从到达本中继装置起至传出为止的通过时间进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

9.根据权利要求6所述的中继装置，其特征在于，

所述测定部，对总线的利用频带进行测定，以作为对所述信息包的传输的拥挤状况进行表示的指标。

10.根据权利要求1所述的中继装置，其特征在于，

所述发送节点是一个总线主设备、或者多个总线主设备的集合体，

所述分类部根据所述一个总线主设备、所述多个总线主设备的集合体、或者所述信息包在传送路径上通过了的一个或多个中继装置，将所述多个缓冲器分类为所述多个组。

11.根据权利要求10所述的中继装置，其特征在于，

所述分类部根据所述信息包在传送路径上通过了的中继装置，将保存有信息包的所述多个缓冲器分类为多个组。

12.根据权利要求10所述的中继装置，其特征在于，

存在多个发送节点，并且各发送节点被预先分类为属于多个组中任一个，

所述分类部根据发送了所述信息包的发送节点所属的组，将保存有信息包的所述多个缓冲器分类为多个组。

Images