OE+IOE: A novel turn model based fault tolerant routing scheme for networks-on-chip

Network-on-chip (NoC) communication architectures are increasingly being used today to interconnect cores on chip multiprocessors (CMPs). Permanent faults in NoCs due to fabrication challenges in ultra deep submicron (UDSM) technology nodes and due to wearout have led to an increased emphasis on fault tolerant design techniques. To ensure fault tolerant communication in NoCs, several fault tolerant routing algorithms have been proposed in recent years with the goal of routing flits around faults. A majority of these algorithms are based on the turn model approach due to its simplicity and inherent freedom from deadlock. However, existing turn model based fault tolerant routing algorithms are either too restrictive in the choice of paths that flits can traverse, or are tailored to work efficiently only on very specific fault distribution patterns. In this paper, we propose a novel low overhead fault tolerant routing scheme that combines the odd-even (OE) and inverted odd-even (IOE) turn models to achieve much better fault tolerance than traditional turn model based schemes. The proposed scheme uses replication opportunistically to optimize the balance between energy overhead and arrival rate. Our experimental results indicate that the proposed OE+IOE routing scheme provides better fault tolerance than existing turn model, N-random walk, and dual virtual channel based routing schemes that have been proposed in literature.