应用于NoC的小规模PRDT（2，1）布线及路由问题的研究

摘要

片上网络——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 阶带环网格选取的确定。该算法具有简单、较低复杂度等特点。最后本文对算法的正确性进行说明，并且使用通道相关图技术对该算法进行了无死锁证明。