一种面向非规则三维集成电路片上网络的路由方法及系统

摘要

本发明提出一种面向非规则三维集成电路片上网络的路由方法及系统，该方法包括根据所述非规则三维集成电路片上网络的拓扑结构，判断采用基于汉密尔顿路径的容错路由算法路由数据包，或基于生成树的容错路由算法路由数据包；若采用基于所述汉密尔顿路径的容错路由算法路由数据包，根据源节点与目的节点的位置确定使用按照节点编号单调上升或单调下降的顺序进行路由容错；若采用基于所述生成树的容错路由算法路由数据包，则选择生成树根节点，根据根节点，以及源节点与目的节点的位置，选择传输路径完成所述数据包的传输。

说明书

技术领域

本发明涉及集成电路的技术领域，特别涉及一种面向非规则三维集成电路 片上网络的路由方法及系统。

背景技术

三维集成技术是一种将芯片不同的器件层堆叠起来，垂直集成在一起的一 种封装技术(BanerjeeK,etal.,“3-DICs:anovelchipdesignfor improvingdeep-submicrometerinterconnectperformanceand systems-on-chipintegration,”inProceedingsoftheIEEE,Volume:89, Issue:5,2001,pp.602-633.)。这种技术可以缩短芯片内物理连线长度， 达到降低系统时延和功耗的作用。图1是一个简单的4*2*3三维芯片片上网络 (network-on-chip，NoC)的示意图，拓扑结构是常见的三维Mesh结构。图 中有3个不同器件层，24个处理单元(processingelement，PE)分别连接 各自不同的路由器节点(下称“节点”)，节点之间通过水平或者垂直方式互连。

网络拓扑是三维片上网络的一个重要架构属性，三维片上网络的规则网络 拓扑有很多种，例如三维Mesh、三维Torus，三维FoldedTorus和三维BFT (ButterflyFat-Tree)等，然而，在实际的工业界三维多处理器芯片(chip multi-processor，CMP)中，由于处理单元一般都采用异构方式设计，不同的 处理单元通常设置为不同的功能模块以满足实际应用的需求，例如，某些处理 单元可以安置处理器，其他处理单元可以嵌入二级或三级高速缓存等，因此， 三维CMP的片上网络拓扑多为不规则拓扑，具体而言，网络中每一个器件层的 结构皆不相同，且每一个节点与其上下对应的邻居节点之间的垂直链接的分布 也是非均匀的，如图2所示的典型非规则三维片上网络。

由于三维集成电路的复杂度和集成度不断提高，极大影响了片上网络的通 信效率，同时致使网络中部件的故障发生几率也相应增高，为了保障三维片上 网络的正常通信，需要引入适当的容错方法，通常，片上网络的故障分为瞬态 性故障和永久性故障，这些故障可能发生在处理单元、网络接口、路由器或者 路由器间的链路等部件中，在本发明中，我们主要关注网络中常见的永久性链 路故障，这类故障一旦发生则不能被修复，对于片上网络的通信将产生比瞬态 性链路故障更为严重的影响，需要注意的是，由于永久性故障的发生也可能导 致原本规则的网络拓扑结构具有不规则的特点，这种情形同样适用于本发明提 出的方法及系统。

国内外针对传统的二维片上网络的容错方法研究已经比较成熟，但是针对 三维片上网络，尤其是非规则拓扑结构三维片上网络(下称“非规则三维片上 网络”)的相关成果则较少，一般而言，面向存在永久性链路故障的片上网络 的容错方法通常分为以下几类：1)使用冗余部件替换失效部件；2)通过在故 障部件周围添加外围逻辑电路使数据包避开故障区域；3)使用可靠路由方法， 直接控制数据包绕过故障链接。

通常，针对大部分应用设计的片上网络规模较小、片上资源有限的现状， 如何设计低成本且高可靠性的容错方法对于保障此类三维片上网络的通信质 量至关重要，由于冗余技术和外围电路设计都需要对芯片的物理结构进行改造， 会产生一定程度的面积及功耗的开销，且电路规模越大该开销越明显，另一方 面，可靠路由方法作为一种轻量级的片上网络容错方法，不仅不会改变芯片的 结构，且能在网络发生故障时继续完成通信任务，并保证较高的通信性能，该 类方法已广泛应用于二维和三维片上网络中，但主要局限于规则的三维网络拓 扑结构。

首先，需要说明的是，虚通道(virtualchannel，VC)和转向限制(转 向模型等)是两种主要的可以破坏片上网络通信抽象依赖环(下称“抽象环”) 的形成、从而预防死锁现象发生的关键技术。

现有的研究成果主要不足如下：

1)需要使用高成本的VC技术避免网络死锁的发生。虚通道的使用会引入 较大的面积开销和复杂的控制逻辑，不适用于对开销要求严格的电路设计。

2)即使不使用虚通道技术，而采用低成本的转向模型，或者引入新的理 论用于避免死锁，也可能带来其他的问题，例如，由于网络结构不规则，单一 的转向模型会导致其引导的路由算法出现无法执行的情形，而引入多个转向模 型则需要VC技术的支持；此外，单纯引入某些特殊路径路由数据包也存在隐 患，即在很多的非规则三维片上网络中可能无法找出符合条件的特殊路径。

3)很多现有方案的端口选择机制采用随机选择的策略，即在合法的端口 不唯一的情况下随机选择一个端口输出数据包，不能很好地绕过冲突区域，导 致网络通信性能较低。

以上三点直接导致现有的成果有三大缺陷：第一，不能保证较高的通信性 能(主要包括通信时延和吞吐率两个指标)；第二，通信的可靠性指标较低； 第三，较高的系统开销。

发明内容

针对现有技术的不足，本发明提出一种面向非规则三维集成电路片上网络 的路由方法及系统。

本发明提出一种面向非规则三维集成电路片上网络的路由方法，包括：

步骤1，根据所述非规则三维集成电路片上网络的拓扑结构，判断采用基 于汉密尔顿路径的容错路由算法路由数据包，或基于生成树的容错路由算法路 由数据包；

步骤2，若采用基于所述汉密尔顿路径的容错路由算法路由数据包，根据 源节点与目的节点的位置确定使用按照节点编号单调上升或单调下降的顺序 进行路由容错，所述数据包沿选中的汉密尔顿路径进行传输过程中，使数据包 每经过一个节点都距离目的节点更近一步；

步骤3，若采用基于所述生成树的容错路由算法路由数据包，则选择生成 树根节点，根据根节点，以及源节点与目的节点的位置，选择传输路径完成所 述数据包的传输；

步骤4，当所述数据包到达节点时，查看到达的节点的地址与所述目的节 点的地址是否相同，若相同，则所述数据包到达所述目的节点，否则循环执行 步骤2或3，直到数据包到达目的节点。

所述步骤1包括：

若所述非规则三维集成电路片上网络中存在唯一的汉密尔顿路径，则选用 所述唯一的汉密尔顿路径执行基于汉密尔顿路径的容错路由算法；若所述非规 则三维集成电路片上网络中存在多条汉密尔顿路径，则在所述多条汉密尔顿路 径中任意选择一条，执行基于汉密尔顿路径的容错路由算法；若网络中未发现 汉密尔顿路径，则采用基于生成树的容错路由算法路由数据包。

所述步骤2中将所述非规则三维集成电路片上网络中的节点按照汉密尔 顿路径上的顺序依次编号。

所述步骤3中所述根节点满足：

1)K_r位于第L层上，其中K_r为所述根节点，J为水平器件 层数，L为水平器件中的某一层水平器件；

2)设所述非规则三维集成电路片上网络的第层上有I个节点， 其中层内编号为p的当前节点p，0≤p≤I-1，设Δ_pi为当前节点p与层内除 节点p以外的第i个节点的最短跳步数，则K_r距离层内除节点p以外节点的 平均最短跳步数为N_r，N_r为：

$N_r={\min }_p\left(\frac{\underset{i=0,i\ne p}{\overset{I-1}{\Sigma }}{\Delta }_{pi}}{I-1}\right).$

所述步骤3还包括：

在始终为入向，始终为出向、先入向再出向这三种传输方向中选择传输路 径完成数据包的传输。数据包在确定根节点的生成树上进行传输过程中，使数 据包每经过一个节点都距离目的节点更近一步。

还包括：若所述步骤2或者所述步骤3中的下一跳节点不唯一，则根据 DP-3D机制，获得当前节点每个合法端口的流量感应情况，选择流量最少的合 法端口输出，降低消息碰撞的几率，避开热点区域。

本发明还提出一种面向非规则三维集成电路片上网络的路由系统，包括：

判断模块，用于根据所述非规则三维集成电路片上网络的拓扑结构，判断 采用基于汉密尔顿路径的容错路由算法路由数据包，或基于生成树的容错路由 算法路由数据包；

汉密尔顿路径算法模块，用于若采用基于所述汉密尔顿路径的容错路由算 法路由数据包，根据源节点与目的节点的位置确定使用按照节点编号单调上升 或单调下降的顺序进行路由容错，所述数据包沿选中的汉密尔顿路径进行传输 过程中，使数据包每经过一个节点都距离目的节点更近一步；

生成树算法模块，用于若采用基于所述生成树的容错路由算法路由数据包， 则选择生成树根节点，根据根节点，以及源节点与目的节点的位置，选择传输 路径完成所述数据包的传输；

到达目的节点模块，用于当所述数据包到达节点时，查看到达的节点的地 址与所述目的节点的地址是否相同，若相同，则所述数据包到达所述目的节点， 否则循环执行所述汉密尔顿路径算法模块或所述生成树算法模块，直到数据包 到达目的节点。

所述判断模块包括：

若所述非规则三维集成电路片上网络中存在唯一的汉密尔顿路径，则选用 所述唯一的汉密尔顿路径执行基于汉密尔顿路径的容错路由算法；若所述非规 则三维集成电路片上网络中存在多条汉密尔顿路径，则在所述多条汉密尔顿路 径中任意选择一条，执行基于汉密尔顿路径的容错路由算法；若网络中未发现 汉密尔顿路径，则采用基于生成树的容错路由算法路由数据包。

所述汉密尔顿路径算法模块中将所述非规则三维集成电路片上网络中的 节点按照汉密尔顿路径上的顺序依次编号。

所述生成树算法模块中所述根节点满足：

1)K_r位于第L层上，其中K_r为所述根节点，J为水平器件 层数，L为水平器件中的某一层水平器件；

2)设所述非规则三维集成电路片上网络的第层上有I个节点， 其中层内编号为p的当前节点p，0≤p≤I-1，设Δ_pi为当前节点p与层内除 节点p以外的第i个节点的最短跳步数，则K_r距离层内除节点p以外节点的 平均最短跳步数为N_r，N_r为：

$N_r={\min }_p\left(\frac{\underset{i=0,i\ne p}{\overset{I-1}{\Sigma }}{\Delta }_{pi}}{I-1}\right).$

所述生成树算法模块还包括：

在始终为入向，始终为出向、先入向再出向这三种传输方向中选择传输路 径完成数据包的传输。数据包在确定根节点的生成树上进行传输过程中，使数 据包每经过一个节点都距离目的节点更近一步。

还包括：若所述汉密尔顿路径算法模块或者所述生成树算法模块中的下一 跳节点不唯一，则根据DP-3D机制，获得当前节点每个合法端口的流量感应情 况，选择流量最少的合法端口输出，降低消息碰撞的几率，避开热点区域。

由以上方案可知，本发明的优点在于：

第一点，本发明可以在容错的基础上提高三维集成电路片上网络的通信性 能，包括降低平均通信时延和提高网络吞吐量。这一点主要是因为基于汉密尔 顿路径或者生成树的最短路径优先算法和拓展至三维场景的端口选择机制，可 以避开热点区域，减小数据包发生冲突的几率。本发明的路由自适应度较高， 可以根据片上网络的实际故障发生状况加以判断，选择冲突最小的合法输出端 口；

第二点，本发明可以利用汉密尔顿路径或者生成树这两个图论概念的自身 特点，消除片上网络中形成抽象环的可能性，在不使用昂贵VC技术的情形下 就能够避免三维场景下的通信死锁发生。从实现成本的角度出发，本发明中的 低开销三维集成电路片上网络的容错路由算法具备较强的工程技术意义；

第三点，本发明可以保证较高的通信可靠性。网络可靠性的一个重要指标 就是在给定的时间内，能够由源节点路由至目的节点的数据包的数量占据这段 时间内注入到网络中数据包总数量的比例。若该比例较高，则对应的路由设计 方法的可靠性就越高。本发明可以使数据包尽可能短时间内路由至目的节点， 在设定的时间内保证通信的可靠性。

附图说明

图1是一个典型的4*2*3三维Mesh片上网络的示意图；

图2是一个典型的非规则三维片上网络的示意图；

图3是非规则三维片上网络中的汉密尔顿路径示意图；

图4是非规则三维片上网络中的生成树示意图；

图5是基于汉密尔顿路径的路由算法示例图；

图6是基于生成树的路由算法示例图。

具体实施方式

首先，简要介绍一下本发明的技术背景，即在路由算法中引入的两个图论 概念——汉密尔顿路径和生成树。

概念1：给定图G，若存在一条路径，经过图中每一个顶点恰好一次，这 条路径则称之为图G的一条汉密尔顿路径(EbrahimiM,DaneshtalabM, PlosilaJ.“Fault-tolerantroutingalgorithmfor3DNoCusing hamiltonianpathstrategy,”inProceedingsofDesign,Automation& TestinEuropeConference&Exhibition.LosAlamitos:IEEEComputer SocietyPress,2013,pp.1601-1604.)。

由概念1可知，汉密尔顿路径是图论中的一个基本概念，在规则的三维 Mesh结构中，必然存在多条汉密尔顿路径，将所有节点按照编号升序或降序 排列恰好经过一次，如图3所示，为一个不规则三维片上网络，其中所有双向 箭头组成的路径表示的是该网络的一条汉密尔顿路径，基于这条路径路由数据 包的优势在于能够避免出现数据传输抽象回路，不需要使用高成本的虚通道 (VC)技术。

需要注意的是，由于汉密尔顿路径自身的特点，图3中的节点编号规则与 图2不同，需要根据路径按顺序编号，图2中的非规则网络则不存在汉密尔顿 路径，这也说明并不是所有的非规则三维片上网络都存在汉密尔顿路径，同时， 每一个不规则网络也可能存在不唯一的汉密尔顿路径(不同的汉密尔顿路径会 使节点编号发生相应变化)。

另一方面，基于汉密尔顿路径的路由算法的本质是有条件的“最短”路径 算法，但并非必须严格沿汉密尔顿路径路由，只要不违背“严格按节点编号升 序或降序传输”的前提，则选择其他的非汉密尔顿路径也并不会引入数据传输 抽象回路，依然可以避免死锁，例如，节点6是源节点，节点10是目的节点， 则选择的路径是6→7→10，而非6→7→8→9→10，不过，如果最短路径上发 生永久性链接故障，则需要选择其他的合法路径，例如，链接7-10出现故障， 则节点7处的数据包可以选择链接7-8，按照7→8→9→10的顺序继续按照节 点编号升序路由，这种操作也提高了路由算法的可靠性。

概念2：给定图G，若存在一个所有顶点均由边连接在一起，且不存在回 路的树，则该树叫做图G的一个生成树(MatsutaniH,BogdanP,Marculescu R,etal.“Acaseforwireless3DNoCsforCMPs,”inProceedingsof the18thAsiaandSouthPacificDesignAutomationConference.Los Alamitos:IEEEComputerSocietyPress,2013,pp.23-28.)。

同样作为一个图论的概念，生成树本身没有方向性，为了保留尽可能多的 边以保障网络通信路径的数量，生成树路由算法需要引入传输方向来消除网络 中的抽象传输回路，这里，本发明引入两个传输方向：入向(In)和出向(Out)， 从而在不产生回路的基础上，在生成树中保留更多的边(链路)，提高网络的 通信可靠性。In和Out都是相对于生成树根节点而言的，与三维网络的其他 七个方向，即东(East)、南(South)、西(West)、北(North)、上(Up)、 下(Down)和本地(Local)不同，In和Out两个方向将以上七个方向做了抽 象化处理，如图4所示(以图2中的网络为例)，若选择节点12作为生成树的 根节点，则实线箭头表示的就是传输方向为In的路径，而虚线箭头表示的传 输方向为Out的路径。

引入In和Out两个传输方向后，数据包路由同样具备单向性特点，从而 可以避免网络死锁，具体而言，若目的节点可以通过In方向或者Out方向直 达，则直接按照该方式路由即可；否则，则按照先In方向再Out方向路由(网 络中不允许发生180°转向以避免出现抽象回路)，依然也可以防止死锁发生。 例如，在图4所示的网络中，源节点为节点2，目的节点为节点5，则2→1→ 0→5或者2→1→4→5皆是可行的传输路径；若源节点位置不变，目的节点换 成节点6，则路径2→1→8→11→12→13→6或者2→1→0→5→12→13→6都 是可选的路径，需要注意的是，先按照In方向再按照Out方向路由数据包并 不是一定要经过根节点，比如，源节点依然为节点2，目的节点为节点10，则 数据包的传输路径是2→1→8→11→10，同时，网络中的永久性链接故障一旦 出现，则会对具体的路径规划有所影响。例如，若链接1-4出现故障，则源节 点为节点2，目的节点为节点5的传输路径仍有2→1→0→5可选择。

需要注意的是，若网络中存在多个生成树(即有多个根节点)且每个生成 树都同时用以指导网络的路由选择，则需要相应数量的虚通道支持，因此，本 发明只涉及单个生成树的路由算法设计，根节点确定后，网络生成树的结构也 随之确定。

在上文中介绍的基于汉密尔顿路径的路由算法和生成树路由算法，都可以 在不使用虚通道机制的前提下避免网络死锁，同时将数据包路由至目的节点， 这里，本发明给出假设1，用于保证非规则网络中容错路由算法的可执行性和 通信的可靠性。

假设1：无论网络中任何位置发生永久性链接故障，都不会出现不可达的 节点。

基于汉密尔顿路径的路由算法和生成树路由算法两者本质不同，具有各自 的特点，相对而言，前者比后者对网络的结构要求更加严格，如前文所说，并 不是每一个非规则三维片上网络都存在汉密尔顿路径，此外，由于汉密尔顿路 径可以按照节点编号直接进行单调的升序或降序路由，因此其最大跳步数可以 通过源节点和目的节点的编号相减得出，设跳步数为N，源节点的编号为N_S， 目的节点的编号为N_D，则N≤|N_D–N_S|，而生成树算法的路由跳步数与生 成树根节点的位置选择相关度很高，不同的根节点位置会极大影响这一网络核 心指标，因此，生成树路由算法相对于基于汉密尔顿路径的路由算法，将给系 统性能带来一定的不确定性，需要设计相应的技术方案尽可能使其性能稳定并 得以提升。

设非规则三维片上网络的节点数为K(网络中的节点编号即为0～K-1)，网 络中水平器件层数目为J(网络中各层编号按照自底向上为0～J-1)。

由于汉密尔顿路径一旦确定，节点按照路径顺序编号(本发明按自底向上 的器件层顺序对节点采用升序编号0～K-1)，网络中的节点间相互可达路径也 就确定下来，相对于生成树路由算法具有更高的性能稳定性，在不规则三维网 络中没有汉密尔顿路径的情况下，则须执行生成树容错路由算法，节点的编号 规则较为简单，即自第0层至第J-1层，只须在每层按行序编号，仅作为节点 标志即可(可参考图2中的网络节点编号)。

生成树容错路由算法的核心在于其根节点位置的选取方法，这里介绍该位 置的具体量化选取思路，从公平性角度考虑，根节点与每个节点的跳步数需要 尽可能小，这样能够避免远端的节点经过较多跳步数到达目的节点，因此，设 编号为K_r的节点为网络生成树的根节点，本发明选择K_r需要满足以下两个约 束条件：

1)K_r位于第L层上，其中

2)设非规则网络的第层上有I个节点，层内编号为p，0≤p≤I-1 (编号的作用范围只限于本层，仅为方便说明，与网络节点编号无关)。设 Δ_pi为当前节点p与本层其他节点(除节点p以外一共I-1个节点中的第i个) 的最短跳步数，则K_r距离层内其他节点的平均最短跳步数为N_r为：

$N_r={\min }_p\left(\frac{\underset{i=0,i\ne p}{\overset{I-1}{\Sigma }}{\Delta }_{pi}}{I-1}\right)---\left(1\right)$

若满足公式(1)的第层内节点不唯一，则在其中任意选择一个即 可。

应注意到，生成树根节点周边的数据流量通常较大，易导致该区域温度升 高，并影响物理部件的正常功能执行。本发明假设芯片散热装置在芯片的底层 之下(即第0层下方)，因此当三维芯片的器件层数是偶数时，本发明在第 层中，而非第层中选择生成树根节点，以利于芯片整体热量的 及时消散。

另一方面，动态规划(dynamicprogramming，DP)选择机制(MakT,Cheung PYK,LamKP,etal.“Adaptiveroutinginnetwork-on-chipsusinga dynamic-programmingnetwork,”IEEETransactionsonIndustrial Electronics,2011,58(8),pp.3701-3716.)，是一个面向传统二维网络的 低开销、高效率的端口选择机制，DP机制没有根据当前节点临近区域的流量 情况，而是根据实时的由源节点至目的节点的路径规划更新情况，在备选方案 中选择最优的传输路径。由于DP机制在二维网络中已经获得了较好的实验效 果，本发明将该机制拓展至三维空间中，记为DP-3D端口选择机制，以获得较 高的通信性能，DP-3D机制与容错路由算法结合在一起，就组成了本发明提出 的完整自适应可靠路由方法。

本发明的具体步骤为：

步骤100：根据非规则三维片上网络的结构判断其是否存在汉密尔顿路径；

步骤200：根据步骤100的判断结构，进行下一步操作。若网络中存在汉 密尔顿路径且唯一，则选用该路径执行基于汉密尔顿路径的容错路由算法；若 网络中存在汉密尔顿路径且不唯一，则需要在这些路径中任意选择一条，再执 行基于汉密尔顿路径的容错路由算法；若网络中不存在汉密尔顿路径，则采用 基于生成树的容错路由算法路由数据包；

步骤201：若三维片上网络采用基于汉密尔顿路径的容错路由算法路由数 据包，首先根据源节点S和目的节点D的位置确定是使用按照节点编号的单调 上升还是下降的顺序进行容错路由，此顺序一旦选定，则不可更改。数据包在 网络中沿选中的汉密尔顿路径传输的过程中，应尽可能保证数据包每经过一个 节点都距离目的节点更近一步；

步骤202：若三维片上网络采用基于生成树的容错路由算法路由数据包， 首先应选择出合适的生成树根节点R，再根据根节点R，以及源节点S和目的 节点D的位置，在始终为In，始终为Out和先In再Out这三种传输方向中选 择合适的传输路径完成数据包的路由过程。数据包在确定根节点的生成树上传 输的过程中，应尽可能保证数据包每经过一个节点都距离目的节点更近一步；

步骤300：若步骤201或者202中的可选下一跳节点不唯一，则根据DP-3D 机制，获得当前节点每个合法端口的流量感应情况，选择流量最少的合法端口 输出，降低消息碰撞的几率，避开热点区域；

步骤400：数据包到达下一个节点后，先比较节点地址，如果该节点是目 的节点D，则到达目的节点，否则，依据网络负载的不同，再次执行步骤201 或者202中的内容，以及步骤300中的相关操作，得出下一跳节点的位置；

步骤500：重复执行步骤400中的内容，直至数据包到达目的节点D。

举例而言，依然以图3中的不规则网络为例进行说明。很显然，在该网络 中存在不止一条的汉密尔顿路径，以图3中所示的路径为例进行说明。设源节 点为节点2，目的节点为节点17，如图5所示。由于链接6-13故障，因此无 法使用“最短”路径2→3→4→5→6→13→14→17进行路由，转而采用另一条 “最短”路径2→3→8→9→10→11→16→17。本例采用的是按节点编号进行 单调升序路由，反之亦同理。

如图6所示，是当不规则网络中不存在汉密尔顿路径时执行生成树容错路 由算法的示例。由于按照网络生成树根节点需要满足的约束条件，只有节点8 和节点11满足要求，因此节点12不能再作为网络生成树的根节点。这里设节 点11为根节点。当链接11-12发生永久性故障时，路径2→1→8→16→15→ 17和2→1→8→7→15→17依然皆可使用，由于数据包经过节点8时合法的输 出端口不唯一，需要根据端口选择机制DP-3D进行实时判断，假设最后选择了 2→1→8→7→15→17为数据传输路径，分别经历了2个In方向(链接1-2和 1-8)和随后的3个Out方向(链接7-8，7-15和15-17)的传输。

本发明还提出一种面向非规则三维集成电路片上网络的路由系统，包括：

判断模块，用于根据所述非规则三维集成电路片上网络的拓扑结构，判断 采用基于汉密尔顿路径的容错路由算法路由数据包，或基于生成树的容错路由 算法路由数据包；

汉密尔顿路径算法模块，用于若采用基于所述汉密尔顿路径的容错路由算 法路由数据包，根据源节点与目的节点的位置确定使用按照节点编号单调上升 或单调下降的顺序进行路由容错，所述数据包沿选中的汉密尔顿路径进行传输 过程中，使数据包每经过一个节点都距离目的节点更近一步；

生成树算法模块，用于若采用基于所述生成树的容错路由算法路由数据包， 则选择生成树根节点，根据根节点，以及源节点与目的节点的位置，选择传输 路径完成所述数据包的传输；

到达目的节点模块，用于当所述数据包到达节点时，查看到达的节点的地 址与所述目的节点的地址是否相同，若相同，则所述数据包到达所述目的节点， 否则循环执行所述汉密尔顿路径算法模块或所述生成树算法模块，直到数据包 到达目的节点。

所述判断模块包括：

若所述非规则三维集成电路片上网络中存在唯一的汉密尔顿路径，则选用 所述唯一的汉密尔顿路径执行基于汉密尔顿路径的容错路由算法；若所述非规 则三维集成电路片上网络中存在多条汉密尔顿路径，则在所述多条汉密尔顿路 径中任意选择一条，执行基于汉密尔顿路径的容错路由算法；若网络中未发现 汉密尔顿路径，则采用基于生成树的容错路由算法路由数据包。

所述汉密尔顿路径算法模块中将所述非规则三维集成电路片上网络中的 节点按照汉密尔顿路径上的顺序依次编号。

所述生成树算法模块中所述根节点满足：

1)K_r位于第L层上，其中K_r为所述根节点，J为水平器件 层数，L为水平器件中的某一层水平器件；

2)设所述非规则三维集成电路片上网络的第层上有I个节点， 其中层内编号为p的当前节点p，0≤p≤I-1，设Δ_pi为当前节点p与层内除 节点p以外的第i个节点的最短跳步数，则K_r距离层内除节点p以外节点的 平均最短跳步数为N_r，N_r为：

$N_r={\min }_p\left(\frac{\underset{i=0,i\ne p}{\overset{I-1}{\Sigma }}{\Delta }_{pi}}{I-1}\right).$

所述生成树算法模块还包括：

在始终为入向，始终为出向、先入向再出向这三种传输方向中选择传输路 径完成数据包的传输。数据包在确定根节点的生成树上进行传输过程中，使数 据包每经过一个节点都距离目的节点更近一步。

还包括：若所述汉密尔顿路径算法模块或者所述生成树算法模块中的下一 跳节点不唯一，则根据DP-3D机制，获得当前节点每个合法端口的流量感应情 况，选择流量最少的合法端口输出，降低消息碰撞的几率，避开热点区域。

以上对本发明的具体实施例进行了描述和说明，这些实施例应被认为其只 是示例性的，并不用于对本发明进行限制，本发明应根据所附的权利要求进行 解释。