A new routing algorithm for the shuffle-exchange permutation network

被引：1
作者：
Chen B. [1 ,2 ]
Xiao W. [3 ]
Du N. [4 ]
机构：
[1] College of Mathematics and System Science, Xinjiang University
[2] Department of Computer Science, Zhangzhou Teacher's College
[3] Department of Computer Science, South China University of Technology
[4] Department of Mathematics, Xiamen University
来源：
Journal of Systems Science and Complexity | 2006年 / 19卷 / 4期
关键词：
Cayley graph; Fixed degree; Routing; Shuffle-exchange permutation network;
D O I：
10.1007/s11424-006-0586-2
中图分类号：
学科分类号：
摘要：
In this paper, a new routing algorithm is given for the shuffle-exchange permutation network (SEP n ). The length of the path between any two nodes given by our algorithm is not more than 11/16n 2+O(n), i.e., the diameter of SEP n is at most 11/16n 2+O(n). This improves on a 1/8(9n 2-22n+24) routing algorithm described earlier by S. Latifi and P. K. Srimani. We also show that the diameter of SEP n is more than 1/2n 2. © Springer Science + Business Media, Inc. 2006.
引用
收藏
页码：586 / 591
页数：5
相关论文
共 8 条
  • [1] Akers S.B., Krishnamurthy B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, pp. 555-566, (1989)
  • [2] Lakshmivarahan S., Jwo J.S., Dhall S.K., Symmetry in interconnection networks based on Cayley graphs of permutations: A survey, Parallel Comput., 19, pp. 361-407, (1993)
  • [3] Huang J.P., Lakshmivarahan S., Dhall S.K., Analysis of interconnection networks based on simple Cayley coset graphs, Proc. IEEE Symp. Parallel and Distributed Processing, pp. 150-157, (1993)
  • [4] Yuntao S., Zifeng H., Jianping S., A parallel fast fourier transform algorithm on the star interconnection networks, Journal of Computer Research and Development, 39, 5, pp. 625-630, (2002)
  • [5] Fen L.W., Lakshmivarahan S., Dhall S.K., Routing in a class of Cayley graphs of semidirect products of finite groups, Journal of Parallel and Distributed Computing, 60, pp. 539-565, (2000)
  • [6] Guihai C., Lau F.C.M., Qing G., Li X., An optimal routing algorithm for shuffle-exchange networks, Chinese Journal of Computers (in Chinese), 24, 1, pp. 25-31, (2001)
  • [7] Latifi S., Srimani P.K., SEP: A fixed degree regular network for massively parallel systems, The Journal of Supercomputing, 12, pp. 277-291, (1998)
  • [8] Leland W.E., Solomon M.H., Dense trivalent graphs for processor interconnection, IEEE Transactions on Computers, 31, 3, pp. 219-222, (1982)
1