適用於晶片網路系統的路徑多樣性感知之容錯路由演算法和架構設計

在多核心處理器(Chip Multiprocessor, CMP)系統,為了提高資料傳輸的效率且符合系統需求,晶片內網路(Network-on-Chip, NoC)系統已被提出為一個具備設計彈性、系統可尺度化及設計可重複使用的解決方案。但隨著半導體製程的演進,晶片內網路系統易遭受到製造缺陷,使其良率隨之降低。當晶片中含有這些缺陷的路由器或連結,封包可使用的傳送路徑將會減少;進而導致系統壅塞、效能下降。因此,由容錯路由演算法來保持系統功能的正確性變得不可或缺。傳統容錯路由演算法使用區域性的錯誤位置資訊與緩衝器剩餘空間來處理錯誤的問題。然而,這些區域性資訊只在短距離傳輸上有顯著性;為了達到容錯傳輸與交通負載均衡,本篇論文提出路徑多樣性感知之路由演算法(PDA-FTR)。此演算法透過路徑數量資訊中加入錯誤位置的資訊,使得路由器可察覺到遠距離的錯誤。另外,為了同時探討錯誤與交通狀況的影響,PDA-FTR 將同時參考路徑數量與緩衝器剩餘空間的資訊,選取具有高彈性與高傳輸能力之路徑。本篇論文提出之技術相較於其他容錯路由演算法,可提升 29.0% - 132.9%的平均飽和吞吐量,並且只需 10.8%額外的硬體成本。總結本論文所提出之設計方法,可以有效分散交通負載到不同的通道上,在一個良好的效能與成本的設計平衡點上,完成容錯封包傳輸。

關鍵字

容錯路由演算法；晶片網路系統；路徑多樣性

並列摘要

To increase the efficiency of interconnections and meet data transfer requirements, network-on-chip (NoC) systems have proven to be a flexible, scalable, and reusable solution for chip multiprocessor (CMP) systems. With the increasing number of cores and the scaling of network in deep submicron (DSM) technology, the NoC systems become subject to manufacturing defects and have low production yield. Due to the fault issues, the reduction in the number of available packet routing paths may cause severe traffic congestion and performance degradation. Therefore, a fault-tolerant routing algorithm is required to maintain the correctness of system functionality and enhance effective yield. To overcome fault problems, the conventional fault-tolerant routing algorithms employ fault information and buffer occupancy (BO) information of the local regions. However, the local information only provides a limited view of network status, thus, results in heavy traffic congestion. To achieve fault-resilient packet delivery and traffic balancing, this thesis proposes a Path-Diversity-Aware Fault-Tolerant Routing (PDA-FTR) algorithm which adopts Path Diversity (PD) in path selection. In PDA-FTR, fault information is integrated into PD, therefore, routers are aware of distant faults. To jointly evaluate the effect of faults and traffic status, PDA-FTR simultaneously considers PD and BO such that packets are routed on path with high adaptiveness and great transfer capability. Compared with other fault-tolerant routing algorithms, the proposed algorithm improves the average saturation throughput by 29.0% - 132.9% compared to the existing fault-tolerant routing schemes with only 10.8% hardware overhead. In summary, the proposed routing scheme can effectively balance traffic load and accomplish fault-resilient packet transmission. Moreover, PDA-FTR achieves a good trade-off between cost and performance.