最近几年,大规模多处理器系统在计算领域起到了越来越重要的作用。为了解决大型的应用问题必须要求多处理器系统中的每个处理器协同工作。这就要求在处理器之间需要进行数据交换,即在整个系统中的每个节点需要发送和接受数据。因此,通信的效率对整个多处理器系统的性能起着至关重要的作用。同时,随着处理单元的增多,系统部件出错的可能性也随之增加。容错是指在部件失效的情况下网络运作的能力,然而容错技术的实现往往是以巨大的性能降低为代价,所以设计具有容错能力的高性能通信技术是一个极具挑战性的问题。路由是其中的一种通信方式,即把数据从一个源节点发送到一个目的节点的一种通信过程。为了保证多处理器系统的高性能和高可靠性,必须设计具有良好容错能力的路由算法。网格拓扑结构是多处理器系统中很流行的一种互连网络结构。它具有很多优点,如拓扑形状简单、直观,很适合进行大规模集成;另外它具有良好的可扩展性。故许多商用和试验的多处理器系统都采用网格拓扑结构。本文就是在网格结构的多处理器系统上研究其容错路由。我们首先介绍了多处理器中容错路由算法研究意义和作用,并介绍了容错路由研究的主要内容和相关的基础知识。在介绍基于网格的新的容错算法之前,我们介绍了容错路由研究领域里一些著名算法。基于这些算法,分析它们存在的不足,我们设计了两个新型的基于网格结构的容错路由算法。第一个算法是基于二维网格的自适应和最小容错路由算法。我们提出了二维网格中存在最小通路的一个充分必要条件。通过在网格中建立最小通路区(RMP)来,该算法能确保路由路径的最优性,以最大程度的提高通信效率。该算法在我们采用的故障模型下,如果存在最小通路区,则路由的路径具有最优性。另外,我们通过引入扩展安全级,对我们的算法进行了完善和改正,增加了算法的灵活性和速度。第二个算法是基于三维网格的完全自适应和最小容错路由算法,我们将二维网格中的充要条件扩展到三维网格中,找到了一个三维网格最小路由的充要条件,并在此基础上提出了一个新型的路由算法,该算法在存在最小路径的情形下能确保路由路径的最优性。