片上网络中基于路径多样性的交叉开关细粒度容错模块及其方法

摘要

本发明提出了一种片上网络中基于路径多样性的交叉开关细粒度容错模块及其方法，是应用于由五个输入端口、路由计算模块、交叉开关分配模块和五个输出端口所组成的路由器中；其中交叉开关细粒度容错模块包括：BIST检测单元、容错单元、额外控制单元、交叉开关。细粒度考虑交叉开关中数据分配器，内部链路以及数据选择器的不同故障情况；使用容错单元对数据分配器和内部链路的故障进行容错，且能够使得容错路径具有多样性；同时，增加一个额外的数据选择器对故障数据选择器进行容错。本发明以较小的硬件开销为代价，在交叉开关故障率大的情况下能进行正常的数据传输，提高了网络的吞吐率。

说明书

技术领域

本发明属于集成电路芯片设计的容错技术领域，特别是一种片上网络中基于路径多样性的交叉开关细粒度容错模块及其方法。

背景技术

随着集成电路技术的发展，单个芯片上会出现由数十甚至数百个处理器联合工作的超复杂电路系统。然而，基于共享总线机制的传统片上系统(System-on-Chip，SoC)的体系结构无法解决复杂多样的系统通讯需求，如互连线延迟、系统全局同步和设计效率。为解决SoC的瓶颈问题，一些研究机构借鉴计算机网络和并行计算技术，提出了互连结构——片上网络(Network-on-Chip，NoC)。NoC因其高效和可扩展的优点被广泛应用，成为一种有效的通讯架构。但是随着特征尺寸的缩减和复杂度的增加，使得芯片出现低良品率、可靠性差等问题，因此容错成为NoC设计的一个重要挑战。

路由器作为NoC通信的重要组成部分，是实现数据存储转发的关键。其中，交叉开关是路由器中的重要部件，主要负责数据的转发工作，通过仲裁逻辑实现输入与输出端口的匹配，使得存储在当前节点的输入缓冲中的数据顺利转发至下一跳节点。当交叉开关出现故障，将会导致当前节点输入缓冲中的数据无法转发至下游节点，造成数据滞留，引起端口阻塞，降低网络性能。因此，对交叉开关的容错显得尤为重要。

研究者们针对路由器中交叉开关的架构设计，提出了较多的方案。例如，Wang W F等人提出一种带buffer的交叉开关架构，主要是在交叉开关的每个输出端添加两个buffer。当buffer为空且下游的虚通道可用时，数据直接传输到下游。否则，数据将缓存在交叉开关的buffer中，当buffer变满时，数据要存在输入端口的虚通道中。该架构能够有效的增加网络的实际接收量，获得较好的性能。但是会带来较大的面积开销，且当交叉开关出现故障时，不能实现容错。RocaA等人提出了一种分布式交叉开关结构，将N×N的交叉开关解耦为N个N×1的独立子网络，并通过一个简单的仲裁器和多路选择器控制子网络。在数据传输过程中，该方案能够有效减少延迟，提高网络吞吐率。但是网络的芯片布局复杂，且无法解决交叉开关故障问题。以上两种设计方案虽然能在一定程度上降低延时，提高吞吐率，但是不能实现对交叉开关的容错。

后来，DeOrioA等人提出了ViCis的路由器架构，路由器中添加了一条旁路总线。当交叉开关出现故障时，数据可以从旁路总线传输，从而实现对交叉开关的容错。由于总线具有分时复用的特性，当出现多方向数据同时竞争总线传输时，容错效率不高。此外还有Zhang Y等人设计了一种新型的主从交叉开关路由器架构，在输入端口和交叉开关间添加了一个2×2 的小交叉开关。当主交叉开关出现故障时，动态配置2×2的小交叉开关，数据将会通过从交叉开关传输至下一跳。当交叉开关出现在故障时，只有一条容错路径。因为交叉开关主要是由数据分配器DEMUX，内部链路以及数据选择器MUX组成，这三部分故障引起的结果不同。但是DeOrioA和Zhang Y等人没有详细考虑每种故障情况，均是粗粒度的容错方案，且当交叉开关故障时，只有一条可选路径，容错路径单一，易浪费交叉开关资源。

发明内容

本发明是为了避免上述现有研究存在的不足之处，提供了一种片上网络中基于路径多样性的交叉开关细粒度容错模块及其方法，以期能详细考虑交叉开关中数据分配器DEMUX，内部链路以及数据选择器MUX这三部分的故障情况，从而能针对每个部分的故障进行容错，并且容错路径具有多样性，此外在交叉开关故障率大的情况下能实现正常的数据传输，提高网络吞吐率，保证网络的整体性能。

本发明解决技术问题所采用的技术方案是：

本发明一种片上网络中基于路径多样性的交叉开关细粒度容错模块，是应用于由五个输入端口、路由计算模块、交叉开关分配模块和五个输出端口所组成的路由器中；其特点是，所述交叉开关细粒度容错模块包括：BIST检测单元、容错单元、额外控制单元、交叉开关；

所述交叉开关是由数据分配器DEMUX、数据选择器MUX和内部链路组成；

所述额外控制单元包括：额外数据选择器EMUX；

所述容错单元的输出端即为所述交叉开关的输入端；

所述路由计算模块根据输入端口所接收的数据包，计算所述数据包在所述交叉开关中的目的输出端口；

所述BIST检测单元用于检测所述数据分配器DEMUX、内部链路和数据选择器MUX的故障情况，若检测到发生故障，则将发生故障的相应部件置为“1”，从而形成故障信息表，交叉开关分配模块读取故障信息表中的故障信息进行路径配置；

所述交叉开关分配模块根据所述目的输出端口为所述数据包在所述交叉开关内分配传输路径并发送给所述容错单元；

所述容错单元根据所述交叉开关分配模块发送的传输路径，获得数据包的输入端口，从而在所述容错单元内部为所述数据包分配相应的容错传输路径，使得所述数据包能通过所述容错传输路径达到所述交叉开关的输入端；

本发明所述的片上网络中基于路径多样性的交叉开关细粒度容错模块的特点也在于，

所述交叉开关分配模块是按如下方式分配传输路径：

所述交叉开关分配模块根据数据分配器DEMUX和内部链路所产生的故障信息，为所述 数据包在所述交叉开关内分配无故障的数据分配器DEMUX和内部链路；

所述交叉开关分配模块根据数据选择器MUX产生的故障信息，选择所述数据包是否通过所述额外数据选择器EMUX进行传输，仅当传输路径上的数据选择器MUX产生故障，则利用所述额外数据选择器EMUX传输至目的输出端口。

本发明一种片上网络中基于路径多样性的交叉开关细粒度容错方法的特点是应用于由输入端口、路由计算模块、交叉开关分配模块、交叉开关细粒度容错模块和输出端口所组成的路由器中；所述交叉开关细粒度容错模块包括：BIST检测单元、容错单元、额外控制单元、交叉开关；所述交叉开关是由数据分配器DEMUX、数据选择器MUX和内部链路组成；所述交叉开关细粒度容错方法是按如下步骤进行：

步骤1、所述路由计算模块根据所述输入端口所接收的数据包，计算所述数据包在所述交叉开关细粒度容错模块中的目的输出端口；

步骤2、所述BIST检测单元检测所述数据分配器DEMUX、内部链路和数据选择器MUX的故障情况，若检测到发生故障，则将发生故障的相应部件置为“1”，从而形成故障信息表，交叉开关分配模块读取故障信息表中的故障信息进行路径配置；

步骤3、所述交叉开关分配模块根据所述目的输出端口为所述数据包在所述交叉开关内分配传输路径并发送给所述容错单元；

步骤4、所述容错单元根据所述交叉开关分配模块发送的传输路径，获得数据包的输入端口，从而在所述容错单元内部为所述数据包分配相应的容错传输路径，使得所述数据包能通过所述容错传输路径达到所述交叉开关的输入端；

步骤5、所述交叉开关分配模块根据所述容错传输路径和传输路径控制所述数据包经过所述交叉开关细粒度容错模块到达所述输出端口，从而完成数据包在所述路由器中的传输。

本发明所述的片上网络中基于路径多样性的交叉开关细粒度容错方法的特点也在于，

所述步骤3是按如下过程进行：

步骤3.1、所述交叉开关分配模块根据数据分配器DEMUX和内部链路所产生的故障信息，为所述数据包在所述交叉开关内分配无故障的数据分配器DEMUX和内部链路；

步骤3.2、所述交叉开关分配模块根据数据选择器MUX产生的故障信息，选择所述数据包是否通过所述额外数据选择器EMUX进行传输，仅当传输路径上的数据选择器MUX产生故障，则利用所述额外数据选择器EMUX传输至目的输出端口，从而获得数据包在所述交叉开关中的传输路径。

与已有技术相比，本发明效果体现在：

1、本发明通过设计交叉开关细粒度容错模块，能有效容忍交叉开关中数据分配器 DEMUX，内部链路以及数据选择器MUX的故障，并且得到的容错路径具有多样性，此外在交叉开关故障率大的情况下能进行正常的数据传输，提高了网络的吞吐量，保证了网络的整体性能。本发明首先使用BIST检测单元详细检测交叉开关中这三部分的故障信息；再利用容错单元对数据分配器和内部链路的故障进行容错，且能够使得容错路径具有多样性；同时，增加了一个额外的数据选择器对故障数据选择器进行容错。

2、本发明通过采用BIST检测的方法，可以得到交叉开关中所有数据分配器DEMUX，内部链路以及数据选择器MUX的详细故障情况，在本发明中，检测到的故障为永久性故障，不可恢复，在存储故障信息时，将检测到的故障部分置为“1”。通过一张故障信息表可以存储数据分配器DEMUX和内部链路的所有故障信息，以便交叉开关分配单元使用这些信息进行交叉开关的路径配置。故障信息表的使用能够节省存储空间，且在查找时快速方便。

3、本发明通过在交叉开关前面添加容错单元，使得在交叉开关出现数据分配器DEMUX故障或内部链路故障时，数据包能通过容错单元传输至交叉开关的其他输入端，最终到达目的端口，且这种设计能够得到多条的容错路径。相比前人设计的交叉开关容错架构中容错路径单一，在故障率大时，容错效果不佳等不足之处，本发明均有很大的改善，尤其是在故障率大时，保证了网络的吞吐率不会骤降。

4、本发明通过在交叉开关的输出端添加一个额外控制单元，使得交叉开关的数据选择器MUX出现故障能有效容错，避免了有些研究中一旦发现数据选择器MUX故障就放弃该数据选择器MUX对应的输出端口，导致数据传输失败且浪费资源。本发明只增加很小的面积开销，使得在数据选择器MUX均故障时也能够通过额外的数据选择器传输数据，提高了网络的吞吐率。

5、本发明通过设计一个交叉开关分配模块，能够控制数据包在一个时钟周期内从整个交叉开关细粒度容错模块中传输出去，相比前人设计的交叉开关旁路架构，平均延时有所降低且吞吐率提高了不少。此外在配置容错单元的输出端时，设计了一种改进的轮询仲裁机制，提高了分配效率，并通过有限状态机从多条容错路径中选择一条最佳路径进行数据传输，保证了数据的正常传输。整体的交叉开关分配模块逻辑结构清晰简单，开销增加不多，但是有效的控制了整个交叉开关细粒度容错模块的运转。

附图说明

图1是本发明的整体路由器架构图；

图2是本发明中交叉开关数据分配器和内部链路的故障信息图；

图3是本发明中交叉开关W输出端对应的有限状态机图；

图4是本发明额外控制模块的工作原理图：

图5是本发明中容错单元输出端配置图。

具体实施方式

本实施例中，一种片上网络中基于路径多样性的交叉开关细粒度容错模块，是应用于由五个输入端口、路由计算模块、交叉开关分配模块和五个输出端口所组成的路由器中，如图1所示，可以看出交叉开关细粒度容错模块包括：BIST检测单元、容错单元、额外控制单元、交叉开关；

交叉开关是由数据分配器DEMUX、数据选择器MUX和内部链路组成，分别连接包括东E、西W、南S、北N以及本地L五个基本输入输出端口；

额外控制单元包括：额外数据选择器EMUX，该EMUX是一个五输入一输出的数据选择器，它是通过BIST控制器来控制选通状态，当五个MUX均故障时采用轮询仲裁机制依次响应请求；

容错单元有5个数据分配器DEMUX和5个数据选择器MUX，每个数据分配器DEMUX用5条内部链路分别连接东E、西W、南S、北N以及本地L 5个方向的数据选择器MUX，数据可以通过容错单元到达交叉开关的其他输入端口，最后到达目的地，实现对数据分配器DEMUX和内部链路的容错；其中容错单元的输出端即为交叉开关的输入端；

路由计算模块根据输入端口所接收的数据包，计算数据包在交叉开关中的目的输出端口；

BIST检测单元用于检测数据分配器DEMUX、内部链路和数据选择器MUX的故障情况，若检测到发生故障，则将发生故障的相应部件置为“1”。由于数据分配器DEMUX故障的结果同其相连接的四条内部链路故障的结果一样，均使得数据被阻塞在输入端口，故将DEMUX和内部链路的故障信息存储在一张故障信息表中，如图2所示，为某一交叉开关DEMUX和内部链路的故障信息。表中的每一行表示从某一输入到五个方向输出的链路故障情况，每一列表示五个方向输入到某一输出的链路故障情况。其中“1”表示交叉开关的某一输入到一个输出的内部链路故障，无法传数据；“0”表示该内部链路完好，可以传数据。在交叉开关中从某一方向输入到该方向对应的输出之间没有链路，无法传数据，为了便于存储故障信息，假设该通路对应了一条内部链路，并将其永久置为“1”，一直不可用，故表的斜对角线上均为“1”。例如S输入对应的一整行，除了到S输出这条链路以外，到其他四个方向的链路均完好。而L输入到其他五个方向输出的链路均故障。从图2中可以得出，当故障信息表某一输入对应的一行中存在一个“0”，表示该输入连接的DEMUX完好，且“0”对应的链路还可以继续传数据。当出现五个“1”，表示连接该输入的DEMUX故障，或者是DEMUX连接的内部链路均故障，都会使得该输入端口无法传数据至下一跳，从而形成完整的数据分配器DEMUX和内部链路的故障信息表，交叉开关分配模块读取故障信息表中的故障信息进行路 径配置；

交叉开关分配模块根据目的输出端口为数据包在交叉开关内分配传输路径，具体方法是交叉开关分配模块根据数据分配器DEMUX和内部链路所产生的故障信息，为数据包在交叉开关内分配无故障的数据分配器DEMUX和内部链路，并发送给容错单元；

此外交叉开关分配模块根据数据选择器MUX产生的故障信息，选择数据包是否通过额外数据选择器EMUX进行传输，仅当传输路径上的数据选择器MUX产生故障，则利用额外数据选择器EMUX传输至目的输出端口。

容错单元根据交叉开关分配模块发送的传输路径，获得数据包的输入端口，从而在容错单元内部为数据包分配相应的容错传输路径，使得数据包能通过容错传输路径达到交叉开关的输入端；

本实施例中，一种片上网络中基于路径多样性的交叉开关细粒度容错方法，也是应用于由输入端口、路由计算模块、交叉开关分配模块、交叉开关细粒度容错模块和输出端口所组成的路由器中；交叉开关细粒度容错模块包括：BIST检测单元、容错单元、额外控制单元、交叉开关；交叉开关是由数据分配器DEMUX、数据选择器MUX和内部链路组成；交叉开关细粒度容错方法是按如下步骤进行：

步骤1、路由计算模块根据输入端口所接收的数据包，计算数据包在交叉开关细粒度容错模块中的目的输出端口；

步骤2、BIST检测单元检测数据分配器DEMUX、内部链路和数据选择器MUX的故障情况，若检测到发生故障，则将发生故障的相应部件置为“1”，从而形成故障信息表，交叉开关分配模块读取故障信息表中的故障信息进行路径配置；

步骤3、交叉开关分配模块根据目的输出端口为数据包在交叉开关内分配传输路径以及在容错单元中分配容错路径，此时的交叉开关分配模块要经历两个阶段：第一阶段配置交叉开关，主要解决交叉开关输入输出的匹配问题；当出现交叉开关故障时，需要重新分配传输路径并将配置信息发送给容错单元，接着进行交叉开关分配的第二阶段，解决容错单元的输入输出匹配问题；

当数据包请求交叉开关传输时，查询故障信息表，交叉开关分配模块根据数据分配器DEMUX和内部链路所产生的故障信息，重新为数据包在交叉开关内分配无故障的数据分配器DEMUX和内部链路；具体操作如下，首先查询故障信息表中目的输出端口对应的某一列，从中找到为“0”的一项或几项，得到多条容错路径，利用有限状态机从中选择一条最佳的容错路径来传输数据，图3是有限状态机选择容错路径的原理图，举例说明W输出端口对应的状态机，该状态机共有五个状态S＝{S0，S1，S2，S3，S4}，其中S0表示连接交叉开关中E 输入和W输出的内部链路无故障。依此类推，S1，S2，S3，S4分别表示连接S，W，N，L四个方向的输入到W输出的内部链路无故障。状态转化条件Q＝q0q1q2q3q4，它的值来自故障信息表对应W输出端口的列向量，其中q0，q1，q2，q3，q4分别是S0，S1，S2，S3，S4的转化条件。例如在S0状态时，当q0＝0时，表示E输入到W输出的链路完好，可以传输数据，不会转到下一个状态；当q0＝1时，表示E输入到W输出的链路故障，无法传输数据，会转到下一个状态S1，其余状态转化同理。利用交叉开关分配第一阶段的轮询仲裁器输出信号Gnt＝g0g1g2g3g4来确定起始状态。假设交叉开关分配第一阶段的轮询仲裁器输出信号Gnt＝00001时，表示W输出允许从L输入方向的数据传输，状态机的起始状态为S4，由图3读出Q＝00111，在S4状态下，q4＝1表示交叉开关中连接L输入和W输出的链路故障，故转向状态S0，此时q0＝0，即E输入到W输出的链路可用。最终本地的数据会经过容错单元的E输出端口到达交叉开关的E输入，并从交叉开关中连接E输入和W输出的链路传输出去；

接着交叉开关分配模块根据数据选择器MUX产生的故障信息，选择数据包是否通过额外数据选择器EMUX进行传输，仅当传输路径上的数据选择器MUX产生故障，则利用额外数据选择器EMUX传输至目的输出端口，此时数据包要发送请求输出信号给EMUX，等待EMUX返回授权信号再进行传输；图4是交叉开关输出端的额外控制单元图，主要由一个额外数据选择器EMUX和轮询仲裁器组成。其中M_fault_info共五位，分别表示交叉开关中五个数据选择器MUX的故障情况，“1”表示故障，“0”表示完好。图中的BIST controller可以从BIST中读取M_fault_info，并根据得到的信息来控制EMUX的选通状态。当M_fault_info中某一位为“1”，其对应的MUX故障，此时启动EMUX，使得本来要从故障MUX传到下一跳的数据发送请求给EMUX，EMUX响应请求，数据最终经过EMUX到达下一跳。当有五个方向的数据请求EMUX输出时，采用轮询仲裁器依次响应请求。当M_fault_info每一位均为“0”时，EMC模块被禁用，从而获得数据包在所述交叉开关中的传输路径；

步骤4、容错单元根据交叉开关分配模块发送的传输路径，获得数据包的输入端口，从而在容错单元内部为数据包分配相应的容错传输路径，使得数据包能通过容错传输路径达到交叉开关的输入端；因为交叉开关中可能存在数据分配器DEMUX故障和内部链路故障，使得数据包无法通过交叉开关分配第一阶段已经匹配好的输入输出传到下一跳。本发明提出的容错单元能够有效解决这个问题，根据数据要到达的输出端，重新配置容错单元，得出多条容错路径。此时，可能会有多个方向的数据请求容错单元某一输出，要在每个输出端进行P:1的仲裁，采用改进的轮询仲裁器，根据DEMUX和内部链路的故障信息DML_fault_info响应请求，每一个输出端均有一个仲裁逻辑，在图5中是以Output_E为例，其中BIST Controller读取故障信息表中的DML_fault_info，并将这些信息传到改进的轮询仲裁器中，Input_req请 求信号有五位，分别代表E，S，W，N，L五个方向，其中“1”表示有请求，“0”表示无请求。改进的轮询仲裁器的工作原理是：当Input_req信号中E输入有请求，该请求的数据要经过交叉开关的E输入传到下一跳，且经过的交叉开关数据分配器DEMUX和内部链路均完好，此时优先响应E输入的请求，再依次响应其他方向的请求。若不满足上述条件，则轮询响应来自所有方向的Input_req信号。

步骤5、交叉开关分配模块根据容错传输路径和传输路径控制数据包经过交叉开关细粒度容错模块到达输出端口，从而完成数据包在路由器中的传输。

综上所述，本方法的细粒度考虑交叉开关中数据分配器，内部链路以及数据选择器的不同故障情况；使用容错单元对数据分配器和内部链路的故障进行容错，且能够使得容错路径具有多样性；同时，增加一个额外的数据选择器对故障数据选择器进行容错，从而以较小的硬件开销为代价，在交叉开关故障率大的情况下能进行正常的数据传输，提高了网络的吞吐率。