Route restrictions for deadlock free routing with increased bandwidth in a multi-stage cross point packet switch

摘要

A method and apparatus for establishing deadlock free routing in a bi- directional, multi-stage, inter-connected, cross-point based packet switch, particularly, though not exclusively employed within a high speed packet network of a massively parallel processing system. Specifically, a group of sets of restricted routes traversing a source, intermediate and destination switch chip are determined by establishing a number of route restrictions from each source switch in the network and determining a number of routes restricted between each source- destination pair of switch chips therein, such that the standard deviation for the number of routes left unrestricted between all source- destination pairs of switch chips for the packet network is minimized. The group of sets of restrictions is created by analyzing a first portion of the network to determine deadlock free route restrictions that comply with the established per switch restrictions and the determined source- destination pair restrictions therefore and then incrementally adding each remaining switch chip for the network and repeating the analysis. Any number of sets from the resultant group of sets of route restrictions may be implemented within the network in accordance with determined link usage and intermediate switch chip usage balancing techniques.