片上网络——NoC(Network-on-Chip)在芯片内部用于解决多处理器片上系统内部互连问题,是未来并行系统发展的一个重要方向。片上网络技术最近几年已逐渐成为相关领域研究的热点,其中内部互连网络(Interconnection Networks)是NoC研究的重点问题之一。拓扑结构的研究是内部互连网络技术研究的重要领域之一,拓扑结构的特性对整个系统的信息传输速度、容错能力和路由算法等多方面有着重要的影响。鉴于拓扑结构的重要性,本文针对目前多处理器片上系统规模和发展状况,重点研究了小规模的PRDT(2,1)拓扑结构应用于小规模的多核片上系统的布线和路由问题。文中通过对PRDT(2,1)的网络直径和平均距离的分析,得出在相同规模的情况下PRDT(2,1)存在着比其他拓扑结构的直径和平均距离小,节点度低等优势。在小规模的片上系统中,PRDT(2,1)拓扑结构更符合要求。本课题选取具有代表性的8×8PRDT(2,1)拓扑结构作为布线研究的重点,结合当前VLSI技术水平,在满足尽量使用最短布线和尽量减少布线平面面积的前提下,8×8PRDT(2,1)拓扑结构可以完成四层布线设计,并对在实际中的关键技术给出解决方法,最终给出布线方案。本文针对4×4PRDT(2,1)结构的特殊性,结合向量路由算法,设计了一种适用于4×4PRDT(2,1)结构的具有针对性的路由算法,该算法主要是通过对源节点和目的节点的坐标差与4×4PRDT(2,1)结构的网络直径的比较,进行对1阶带环网格选取的确定。该算法具有简单、较低复杂度等特点。最后本文对算法的正确性进行说明,并且使用通道相关图技术对该算法进行了无死锁证明。