Computer Science ›› 2014, Vol. 41 ›› Issue (2): 191-196.

Previous Articles     Next Articles

Method of Computing Least No Conflict Routing Groupings in Shuffle-exchange Networks

ZHANG Yi-hao,SHEN Yue-hong and PAN Lin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: In order to resolve the problem of how to separate conflict routings in shuffle-exchange networks,the concepts of the maximal no conflict routing group,the least no conflict routing groupings,eigenfunction and covering function were defined.Based on these concepts,the theory and method of computing the least no conflict routing groupings by boolean algebra were proposed.In addition,an algorithm of approximately computing the least no conflict routing groupings was put forward to improve the efficiency of batch routing.Results of theoretical analysis and experiments show that the time efficiency and accuracy of the algorithm are excellent.It provides strong supports for carrying out batch routing policy in process of massive information exchange.

Key words: Shuffle-exchange network,Maximal no conflict routing group,Least no conflict routing groupings,Eigenfunction,Covering function

[1] Stone H S.Parallel Processing with the Perfect shuffle[J].IEEE Transactions on Computers,1971,C-20(2):153-161
[2] Goke L R,Lipovski G J.Banyan networks for partitioning multiprocessing systems[C]∥Proc Fist Annual Computer Architecture Conf.1973:21-28
[3] Wu C,Feng T.On a Distributed processor communication architecture[C]∥Proc Compcon Fall.1980:599-605
[4] Akbar S,Reza S N,Hamid Sarbazi A.The Shuffle-ExchangeMesh Topology for 3D NoCs[C]∥The International Symposiumon Parallel Architectures,Algorithms,and Networks.IEEE,2008,23:275-280
[5] Chou W Y,Chen R B,Chen Chiu-yuan.All-to-All Personalized Exchange Algorithms in Generalized Shuffle-exchange Networks[C]∥Eighth International Conference on Networks.2009:185-190
[6] Muller O,Baghdadi A,Jezequel M.From parallelism levels to amulti-asip architecture for turbo decoding[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systems,2009,7(1):92-102
[7] Ding N,Ma H L,Tan G Z.The Parallelization Design of Chaotic Encryption System Based on Mulitlevel Shuffle-Exchange Network[C]∥Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing.2009:698-671
[8] Lawrire D H.Access and alignment of data in an array proces-sor[J].IEEE Transactions on Computers,1975,C-24(12):1145-1155
[9] Clonan T J.Topological equivalence of optical crossover net-works and modified data manipulator networks[J].Appl.Opt.,1989,28(13):94-98
[10] Raghavendra C S,Varma A.Rearrangeability of the 5-StageShuffle-Exchange Network for N=8[A]∥Proceedings of 1986International Conference on Parallel Proceeding[C].University Park,USA,1987:119-122
[11] 戴浩,沈孝钧.在7级混洗交换网络中实现16×16的可重排性[J].电子学报,2007,35(10):1875-1885
[12] 葛方斌,张涛,宋金玉,等.3n-1级混洗交换网络的重排性研究[J].通信学报,2011,32(10):10-18
[13] 李挥,何伟,伊鹏,等.排序集线器多级互连交换结构的多路径自路由模型[J].电子学报,2008,36(1):1-8
[14] Linial N,Tarsi M.Interpolation between bases and the shuffle exchange network[J].European J Combin,1989,10(1):29-39
[15] Ge F B,Zhao M,Zhang T,et al.A new policy to solve routing conflict in shuffle-exchange network[J].Science China Information Sciences,2011,54(7):1512-1523
[16] Raghavendra C S.On the Rearrangeability Conjecture of(2log2N-1)-stage Shuffle- Exchange Network[A]∥IEEE Computer Society Technical Committee on Computer Architecture Newsletter[C].1994-95:10-12

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!