随着半导体工艺的不断发展，单个芯片上集成的晶体管数量将越来越多。届时，它们将被组合成上千个各自独立又相互通信的处理单元。为了充分利用它们的处理能力，需要高效的通信结构来完成它们之间的通信。传统的连接这些处理单元的总线结构在功耗、延迟、同步、线路可靠性以及带宽等方面很难适应新的需要。为了满足片上系统的通信需要，研究者提出了片上网络(Network-on-Chip，NoC)的通信架构，并从多个方面阐述了以片上网络代替总线通信结构的必要性。片上网络与通用的计算机网络一样，也采用分层的体系结构。片上网络的设计包括拓扑结构、路由算法、交换技术、流控制策略等方面。但是，由于片上网络是在单个芯片上实现的微型网络，所以它的设计有区别于通用计算机网络的独特的地方。因为片上网络结构需要与同一个芯片上的计算单元竞争空间，所以，片上网络所占的面积必须尽可能小。同时也需要尽量减少它的功耗开销。研究者对适用于片上网络的各种拓扑结构进行了广泛的研究。网格(Mesh)结构由于具有结构简单、容易实现、可扩展性好等方面的优势得到最多的关注。在交换技术方面，虫孔(Wormhole)交换技术由于需要较少的缓存空间，并且数据包延迟较小，所以适合在片上网络中应用。本论文主要研究采用网格结构和虫孔交换技术的片上网络的路由算法相关问题。　　 本文具体内容分为三大部分：第一部分为第一章和第二章，主要内容为绪论和相关研究；第二部分为第三章到第五章，主要介绍关于路由算法的三个研究成果；第三部分为第六章、第七章以及结语部分，介绍了两种流控制策略和论文总结。　　 本文的主要研究成果如下：首先，提出了一种为特定应用计算路由的算法(RABC)。RABC方法通过打破信道依赖图中所有的圈来确保得到的路由算法不会形成死锁。由它得到的路由算法具有较高的自适应度，且性能不依赖于它打破这些圈的顺序。同时RABC算法的计算复杂度仪为O(n)。　　 其次，提出了一种减少路由表查询次数的方法(RQRT)。在基于表格实现的路由中，为了降低数据包延迟，从而提高系统性能，需要对路由表的查询方法进行改进。由于网格结构比较规则，从而为其生成的路由表也有一定的规律可循。RQRT方法充分利用网格拓扑结构路由表的规律特性，减少了50％的路由表查询次数，极大地提高了系统的性能。　　 第三，提出了ANoP选择策略。当路由算法计算出多个输出端口时就需要选择策略从中选择一个恰当的输出端口。ANoP选择策略能公平地选择所有由路由算法计算出的输出端口，使流量在网络中均匀分布，从而能够充分利用网络资源，提高系统性能。　　 第四，提出了注入水平流控制策略(ILFC)。在该流控制策略中，源节点发送数据的速率被划分成若干个水平(Injection Level)。然后源节点在发送数据的时候根据网络的状态自动选择最大且不会使网络发生拥塞的注入率水平。模拟结果表明，应用了IJFC流控制后，片上网络就会运行在比较平稳的状态，不再发生拥塞。　　 第五，提出了四分之一负载门限(QLT)流控制策略。通过记录网络的状态，我们发现，为了避免片上网络进入一种恶性拥塞状态，网络的负荷存在着一个门限值(具体为路由器缓存空间的四分之一)。当网络的负载低于该门限值时，网络中就不会出现拥塞。反之，当网络的负荷超过该门限值时，网络中就会出现严重的拥塞。而且该门限值规律在网络的局部范围内仍然起作用。根据这个发现，我们设计了QLT流控制策略。它基本思想是记录路由器被占用的缓冲区的总和，如果它超过了指定门限值，则认为该路由器所在的路径已经发生拥塞了，应该推迟向该路径发送数据。否则认为该路径没有发生拥塞，可以继续发送数据。