半导体技术的发展和应用需求推动着处理器设计进入“多核”甚至“众核”时代。在“多核”以及“众核”环境下，传统总线或点对点通信结构面临着性能、功耗和可扩展性等方面的不足。针对这些局限，研究者们借鉴计算机通信网络的思想提出了一种新的片上通信结构—片上网络（Network-on-Chip，NoC）。随着处理器核数的不断增加，由生产缺陷、工艺偏差和芯片老化等引发的硬故障导致NoC出现故障的概率也在相应提高。另外，网络拥塞导致数据的传输延时显著增加，NoC整体性能急剧下降。因此，本文以容错路由和拥塞路由为对象，研究2Dmesh结构片上网络中无死锁容错路由算法和拥塞感知自适应路由算法。路由算法主要采用虚通道技术和无虚通道转向模型来避免死锁。　　本研究主要内容包括：⑴在分析单故障NoC结构特点的基础上，本文提出了一种适用于容错的奇偶（Fault-Tolerant Odd-Even，FTOE）转向模型，以弥补现有转向模型应用于无虚通道容错路由算法中存在故障周围负载不均衡和丢包的问题。同时基于该转向模型本文设计了一种可重构的无虚通道容错路由（Reconfigurable and Fault-Tolerant Routing， RFTR）算法。RFTR算法可以容忍任意位置的单链路故障或者单节点故障，并且均衡了故障周围的负载，缩短了部分数据包的绕行路径。⑵面向多节点故障的无虚通道容错路由算法通常采用故障模型将多节点故障容错问题转换为故障区域绕行问题，从而简化了算法的复杂度。然而，现有多节点故障无虚通道容错路由算法都存在故障区域周围负载不均衡和长绕行路径的问题；并且由于数据包垂直进入故障区域边界而引入被禁止的转向，造成网络死锁。为了解决上述问题，本文将FTOE转向模型与提前预测相结合，设计了一种面向多节点故障的负载均衡无虚通道容错路由（Load-Balancing and Fault-Tolerant routing，LBFT）算法。LBFT算法只需要存储少量的故障信息就能预测故障区域的位置并且提前绕过它，这样数据包就不会垂直进入故障区域边界，避免了网络死锁。更重要的是，LBFT算法可以容忍任意位置、任意数量的节点故障，并且均衡了故障区域周围的负载，缩短了部分数据包的绕行路径。⑶无虚通道容错路由算法通常采用转向模型来避免死锁，而转向模型禁止了一些转向，降低了算法的自适应性。为了采用最少数量虚通道，同时又使得容错路由算法具有更大的自适应性，本文将double-Y结构应用于片上网络中，该网络Y方向采用两条虚通道，X方向采用一条虚通道。然而，应用于 double-Y网络的现有转向模型由于其自身的限制，容错路由算法只能容忍单链路故障或者单节点故障。随着故障的不断增加，越来越多的数据包被丢弃。因此，本文提出了一种新的转向模型 NMad-y，该转向模型将现有转向模型中被禁止的转向变为可转，大大提高了转向模型的自适应性。本文还提出了一种新的故障信息分发机制，该机制可以分发2-hop之内邻接链路的故障信息。最后基于NMad-y转向模型和2-hop之内链路的故障信息，本文设计了一种自适应容错路由（Adaptive and Fault-Tolerant Routing，AFTR）算法。该算法可在不丢失网络性能的前提下提高网络的可靠性，实现了数据包97.43％的到达率，并且可以容忍任意位置、任意数量的链路故障和节点故障。⑷非本地自适应路由算法通常采用本地和远端链路的拥塞信息选择输出路径，从而大大促进网络性能。现有的非本地自适应路由算法都采用专用的拥塞信息传播网络或者将拥塞信息嵌入到数据包包头中传播。经过拥塞信息的传播，网络中的每个节点都知道远端链路的状态。然而，这些拥塞传播机制要么引入额外的硬件开销，要么使得拥塞信息传播不及时，进而造成更大的拥塞。为了解决上述问题，提出了一种基于消息的拥塞信息传播机制，该机制采用两种专用的消息传播拥塞信息，这样既没有引入额外的硬件开销，也使得拥塞信息传播更及时。最后文设计了一种高效的非本地自适应路由（Efficient and Non-local Adaptive Routing，ENAR）算法。ENAR算法根据被传播的拥塞信息选择输出路径，能有效避免网络拥塞。由于该算法只考虑位于源节点和目标节点之间最小象限内的链路状态，且每个方向只比较相同数量的链路状态，因此消除了冗余信息。