In this paper, we propose a deadlock-free routing algorithm for wormhole routed n-dimensional hypercubes (n-cube). Previous researches have focused on designing deadlock-free routing algorithms for an n-cube based on the Hamilton-path labeling. However, the labeling method widely employed in the literature is called the Gray-Code labeling. The Gray-Code labeling is a fixed approach and provides only one way to achieve routing. In contrast to this traditional way, a distributed Hamilton-path labeling algorithm is proposed in this paper to provide up ot 2~2n-2n! ways of labeling. In addition, the propsed Hamilton-path labeling process can be completed for an n-cube in O(n) parallel steps. Finally, a heuristic algorithm to obtain an efficient way of labeling ofr our approach according to different system traffic distributions is also given. Therefore, the system performance can be imporved significantly with such heuristic approach.
展开▼
