A PARTIALLY NETWORK RECONFIGURATION MECHANISM ON TWO- DIMENSIONAL MESH AND TORUS WITH FAULTS

摘要

Fault tolerance becomes a crucial factor in designing on-chip packet networks for modern complex chip multiprocessors whose topologies usually are two dimensional mesh or torus. In this paper, we propose a reconfiguration mechanism for deadlock-free routing on two dimensional mesh and torus topologies that include faulty links. Irregularity of the topology by the faults introduces difficulties in guaranteeing both connectivity and deadlock freedom of routing algorithms. To provide both properties, the proposed reconfiguration mechanism uses a spanning-tree based routing. To maintain the performance, it uses the regularity of two-dimensional mesh and torus, and the path set is similar to that with no faults whose paths are well-distributed. Evaluation results show that the reconfiguration mechanism on a faulty network achieves high throughput close to that of the west-first turn model without no faults.