计算机科学 ›› 2014, Vol. 41 ›› Issue (2): 191-196.

• 网络与信息安全 • 上一篇    下一篇

混洗交换网络中最小无冲突路由分组的生成方法

张以皓,沈越泓,潘林   

  1. 解放军理工大学通信工程学院 南京210007;解放军理工大学通信工程学院 南京210007;解放军理工大学指挥信息系统学院 南京210016
  • 出版日期:2018-11-14 发布日期:2018-11-14

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

摘要: 为了解决混洗交换网络中冲突路由的分组问题,定义了路由的无冲突极大组、最小无冲突分组、特征函数及覆盖函数等概念,并基于这些概念提出了应用布尔代数计算最小无冲突分组的理论和方法。同时,为提高冲突路由分组的效率,提出了计算最小无冲突分组的近似算法。理论分析和实验表明,近似算法不仅具有良好的时间性能,而且具有较高的准确度,它为在大规模信息交换中实施分批路由策略提供了强有力的支撑。

关键词: 混洗交换网络,无冲突极大组,最小无冲突分组,特征函数,覆盖函数 中图法分类号TP393文献标识码A

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!