A testbed for evaluation of fault-tolerant routing in multiprocessor interconnection networks

This paper presents a comprehensive evaluation testbed for interconnection networks and routing algorithms using real applications. The testbed is fle xible enough to implement any network topology and fault-tolerant routing a lgorithm, and allows the system architect to study the cost versus performa nce trade-offs for a range of network parameters. We illustrate its use wit h one fault-tolerant algorithm and analyze the performance of four shared m emory applications with different fault conditions. We also show how the te stbed can be used to drive future research in fault-tolerant routing algori thms and architectures by proposing and evaluating novel architectural enha ncements to the network router, called path selection heuristics (PSH). We propose three such schemes and the Least Recently Used (LRU) PSH is shown t o give the best performance in the presence of faults.