Rule-Based Routing for Fault-Tolerant Parallel Computers

Routing has an important influence on the performance of interconnection networks in parallel computers. Besides simple oblivious schemes like xy-routing for 2D grids there exist a lot of sophisticated adaptive and fault-tolerant routing algorithms which could however not be implemented so far, because there are no fast hardware routers which are able to support them. In this paper such a flexible and programmable router design is proposed which is based on a rulebased representation of routing algorithms. By making use of the ARON method a fast and efficient hardware rule interpreter can be implemented. The basic principle of rule-based routers is discussed taking typical adaptive routing algorithms as examples. The structure of a prototype is also presented. The influence of increased routing decision time by the rule interpreter is studied by means of simulations.