片上网络由于其高度的可扩展性和灵活性,成为了片上系统最核心的组件,能够为核与核之间提供高速且可靠的通信。片上网络的研究主要从拓扑结构、交换技术和路由算法这三方面,路由算法为消息选择合适的传输路径,是影响系统性能的关键因素。因此,对片上网络的路由算法进行研究具有非常重要的意义。本文对mesh网络的路由算法中存在的问题进行了深入的分析,并展开了一系列的研究,主要成果包括:·本文针对现有的二维mesh网络的路由算法存在的不能均衡使用虚拟通道的问题,提出了一种基于新的虚拟网络划分模式的路由算法。不同于传统的虚拟网络划分模式,新的虚拟网络划分模式为不同的虚拟网络可分配相同的虚拟通道,从而减少了对虚拟通道的需求。通过设置禁止转弯和特殊转弯来避免死锁,这种约束是轻量级的,不会对算法的自适应性产生影响。通过仿真实验,结果证明了路由算法的有效性。·随着片上集成的核数的增加,二维mesh网络表现出了较长的连线和较高的功耗等不足,针对这个问题,展开了对全连接的三维堆叠mesh网络的路由算法的研究。本文对基于重复转弯概念的各种路由算法的路由压进行分析和探索,找到了具有最小路由压的路由算法,从理论上保证了得到的路由算法具有使网络负载均衡的能力。本文对提出的路由算法进行了严格的无死锁证明。实验表明提出的路由算法对比于其他的不使用虚拟通道的路由算法在性能上具有优势,与理论的分析相符。·针对硅穿孔（TSV）技术存在制造复杂性和面积开销等方面的问题,本文以二维mesh网络中的虚拟网络模式作为启发点,提出了适用于两层之间只使用部分垂直连接（PVCs）的三维mesh网络的虚拟网络模式,并基于此设计了相应的高性能路由算法。基于新的虚拟网络模式,两个虚拟网络可以分配一些公共的虚拟通道,这与Linder和Harden提出的原始的虚拟网络模式完全不同。并且,任何的消息都能够在多个虚拟网络中路由。通过仿真实验证明了提出的算法与已有的两种算法相比,能够提供较高的吞吐量和较低的平均延迟。