On the shuffle-exchange permutation network
Douglas W. Bass, Ivan Hal Sudborough · 2002
The shuffle-exchange permutation network (SEP/sub n/) is a fixed degree Cayley graph which has been proposed as a basis for massively parallel systems. We propose a routing algorithm with an upper bound of (5/8)n/sup 2/+O(n), where n is the length of the permutation. (This improves on a (9/8)n/sup 2/ routing algorithm described earlier (Latifi and Srimani, 1996)). Thus, the diameter of SEP/sub n/ is at most (5/8) n/sup 2/+O(n). We also show that the diameter is at least n/sup 2//2-O(n). We demonstrate that SEP/sub n/ has a Hamilton cycle, for n/spl ges/3, and describe embeddings of variable-degree Cayley networks, such as bubble-sort networks, star networks and pancake networks into SEP/sub n/. Our embeddings for these networks are substantial improvement of earlier results stated in Latifi and Srimani (1996).