DPR - AN EFFICIENT DEADLOCK-FREE UNICAST ROUTING IN IRREGULAR NETWORKS

Irregular topologies have become increasingly important to the multicomputer market. The irregularity allows an easy design of scalable systems with incremental expansion capability and offers greater wiring flexibility than regular networks. This paper presents a new deadlock-free unicast routing algorithm, DPR, for irregular networks. DPR algorithm relies on the use of a spanning tree. It assigns labels only to the nodes of the network based on the parent-child relation. Generally, the routing process of DPR proceeds by visiting a sequence of (up / up cross) channels, followed by a sequence of at most three horizontal cross channels, and ends with a sequence of (down / down cross) channels. The freedom of the DPR algorithm from deadlock and livelock is proved. The DPR algorithm is compared with two previous algorithms. The results demonstrate that the communication latency obtained by the DPR algorithm is lower than the communication latency obtained by the other two algorithms.