中文摘要：

为了满足系统芯片对通信带宽的要求，片上网络正逐渐取代总线成为当前多核及众核系统的主流互连方案，然而由于芯片特征尺寸的不断减小，芯片内发生故障的概率显著增加．为了提供可靠的片上通信，提出一种低成本的可重构路由算法．该算法基于无共享边界的矩形故障模型，按照故障区与网络边界的相对位置对故障区进行分类；针对不同类型的故障区定义了具体的路由器状态更新策略；重构后的片上网络可以容忍任意数目、任意分布的路由器以及链路故障．与当前容错设计方案不同，文中算法不需要增加虚拟通道来保证网络的无死锁特性，因此具有低成本、高可靠的特性．仿真实验结果表明，文中算法适用于处理器与缓存，或缓存与缓存之间的片上通信．

英文摘要：

Network-on-chip （NoC） has become an attractive structure to replace the bus to provide onchip communication for multi-core and many-core chips due to its high bandwidth and scalability. Unfortunately, modern chips are more prone to faults with the shrinking of chip feature size. To provide reliable on-chip communication, this paper proposes a low cost and reconfigurable routing algorithm. This algorithm assumes that failed routers and links are included into rectangular faulty blocks without shared boundaries, and classifies faulty blocks according to their relative position to network edges. For each type of faulty blocks, the proposed algorithm defines a way to update the status of routers. Reconfigured NoC could tolerate unbounded number of arbitrarily distributed router and link failures. Unlike existing fault-tolerant routing algorithms, the proposed keeps the network free of deadlock without adding extra virtual channels. Therefore, it is more cost efficient. Extensive simulations validated that the proposed routing algorithm is quite suitable for core-to-cache and cache to-cache NoCs.