随着计算机技术的发展，很多研究领域不断地交叉和融合。在微电子技术领域，一些研究者提出使用并行计算机互连网络技术解决单一芯片上多个内核的集成问题，这一技术称为片上网络(NoC)技术。NoC是片上系统(SoC)的通讯子系统，它利用互连网络解决单一芯片上的多个内核之间的通讯问题，这提高了单一芯片系统的通讯性能，也带来了互连网络中的一个关键问题，即网络死锁的问题。出于网络资源利用率和硬件成本等方面的考虑，本文提出使用死锁避免的策略，即设计无死锁的路由算法解决NoC网络中的死锁问题。 NoC网络与并行计算机互连网络之间有很多不同的地方，互连网络中的无死锁路由算法不能直接应用于NoC网络中。这首先是因为很多NoC网络(例如特定应用NoC网络)具有独特的拓扑结构，这就要求NoC网络路由算法具有更低的路由限制以保持路由的连通性。其次，由于芯片成本和功耗方面的限制，这就要求NoC网络路由算法使用更低数量的虚拟通道。NoC技术是芯片制造业发展的必然趋势，因此有必要现在开展NoC网络无死锁路由的研究，储备相关的核心技术。 针对于目前提出的一些可扩展的NoC网络结构，分别提出统一的、低虚拟通道使用和低路由限制的无死锁路由方案是本论文研究和探索的主要内容。研究工作的创新点主要体现在以下五个方面： 一是将NoC网络分为以特定应用NoC为代表的不规则拓扑结构网络和以多核处理器NoC为代表的规则拓扑结构网络。其中不规则拓扑结构网络包括非正交不规则网络和正交不规则网络(例如不规则Mesh网络)，规则拓扑结构网络包括正交网络、非正交网络和具有部分正交特征的网络(例如RDT网络)。 二是提出了基于通道类依赖图的新的无死锁路由判定定理，这一定理与Duato定理是等价的，也是无死锁路由的充要判定条件。由于通道类依赖图与网络规模无关，这一定理可以成为NoC网络无死锁路由算法设计的有力工具。 三是提出了不规则Mesh网络绕行障碍路由算法。这一算法与不规则Mesh的规模和形状无关，能够在具有不同矩形障碍区域的不规则Mesh网络中保持路由的连通性，同时算法只需要将网络中每一个物理通道分为三个虚拟通道使用。而且通过对这一算法进行扩展，本文分别提出了自适应、最短路径和耐故障的不规则Mesh网络绕行障碍路由算法。 四是提出了不规则Mesh网络组合路由算法。组合路由算法由两个子路由算法组成，并使用两个虚拟通道，即每个子路由算法分别使用一个虚拟通道。通过将部分节点设置为路由盲区，组合路由算法能够在不规则Mesh网络中保持路由的连通性。本文还提出了基于组合矩阵计算和带权无向图的优化算法，这一算法能够最小化组合路由算法的路由盲区。 五是提出了PRDT(2，1)网络二进制路由算法，这一路由算法基于二进制计算进行路由决策，其路由决策速度更快。而且当网络规模较小时，这一算法无需使用虚拟通道即可实现无死锁路由。此外，基于这一算法本文进一步提出了完全自适应的二进制路由算法。 论文的结构如下： 第1章主要描述了互连网络中死锁产生的原因和解决的策略，以及一些经典的无死锁路由理论。 第2章介绍了NoC技术的产生及其网络结构，并对NoC网络拓扑结构进行了分类。 第3章提出了基于通道类依赖图的无死锁路由充要判定定理，并对其进行了证明。 第4章研究了基于不规则Mesh网络的NoC无死锁路由算法，提出了确定性、自适应、最短路径、耐故障的绕行障碍路由算法以及组合路由算法。 第5章讨论了基于PRDT(2，1)网络的NoC无死锁路由算法，提出了确定性和自适应的二进制路由算法。第6章对研究工作进行讨论和总结。