Narrow Results

We propose a deadlock-free routing scheme in irregular networks using prefix routing. Prefix routing is a special type of routing with a compact routing table associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labeling in an irregular network is done through constructing a spanning tree. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel (shortcut) between two branches of the tree between two phases. We show that the proposed routing scheme is deadlock- and livelock-free. We also compare prefix routing with the existing up*/down* routing which has been widely used in irregular networks. Possible extensions are also discussed.

Hierarchical interconnection networks with n-dimensional hypercube clusters can strike a balance between wide application suitability, size scalability as well as reliability. Cluster communications support for such networks must therefore be reliable and efficient without incurring large overheads. This paper proposes a reliable and cost-effective intra-cluster communications strategy for such a class of interconnection networks. The routing algorithm can tolerate up to (n - 1) component faults in the cluster and generates routes that are cycle-free and livelock-free. The message is guaranteed to be optimally (respectively, sub-optimally) delivered within a maximum of n (respectively, 2n - 1) hops. The message overhead incurred is one of the lowest reported for the specified fault tolerance level – with only a single n-bit routing vector accompanying the message to be communicated. Finally, routing hardware support may be simply achieved with standard components, facilitating integration with the host network.