Fault tolerance of adaptive routing algorithms in multicomputers

An evaluation of the effectiveness of adaptive routing techniques in tolerating failures is presented. It is shown that adaptive routing techniques yield gracefully degradable systems for the workloads considered. For medium to large communication granularity and the workloads considered in this study, if adaptive-routing is used, it is shown that the problem completion time does not increase drastically due to failures. When node failures were considered, it was observed that the mismatch of problem communication structure with the physical communication structure did not result in significant loss of performance. Since adaptive routing techniques are warranted for performance reasons, it is argued that making use of this adaptive routing hardware to tolerate failures is a favorable option