Abstract
This thesis explores issues related to the routing of messages in a k - aryn - cube multiprocessor interconnection network. By using a distributed algorithm that identifies paths for particular inter-processor communication flows, the capacities of the interconnecting links can be shared in a predictable manner, blocking and congestion can be reduced, and hot-spots avoided. The paths that are identified are not necessarily the shortest ones possible. The nodes in the routing fabric are autonomous - i.e. they respond to incoming messages independently and each maintains its own routing table. The thesis describes the bandwidth reservation algorithm in detail and proposes an implementation which is then simulated with a clock resolution of one cycle per unit of data communicated. The livelock and deadlock-freedom of the implementation is justified. Simulation measurements demonstrate that the set-up, communication and close-down performance of each path is as expected, that the algorithm performs correctly under various traffic models, and that the technique compares favourably with a Minimal Adaptive Routing scheme under certain conditions.