|Authors||F. O. Sem-Jacobsen, T. Skeie, O. Lysne and J. Duato|
|Title||Dynamic Fault Tolerance in Fat-Trees|
|Afilliation||Communication Systems, Communication Systems|
|Publication Type||Journal Article|
|Year of Publication||2011|
|Journal||IEEE Transactions on Computers|
Fat-trees are a very common communication architecture in current large-scale parallel computers. The probability of failure increases with the number of components. We present a routing method for deterministically and adaptively routed fat trees, applicable to both distributed and source routing, that is able to handle several concurrent faults and that transparently returns to the original routing strategy once the faulty components have recovered. The method is local and dynamic, completely masking the fault from the rest of the system. It only requires a small extra functionality in the switches to handle misrouting around a fault. The method guarantees connectedness and deadlock and livelock freedom for up to radix/2 -1 arbitrary simultaneous faults. Our simulation experiments show a graceful degradation of performance as faults are added. Furthermore, they demonstrate that for most fault combinations, our method will even be able to handle significantly more faults beyond the radix/2-1 limit with high probability.