基于最小传输延迟的单向Hamming网设计

《基于最小传输延迟的单向Hamming网设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第25卷第5期2016年10月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．25，No．5Oct．2016基于最小传输延迟的单向Hamming网设计柴国荣，文艳艳，宗胜亮，苑春(兰州大学管理学院，甘肃兰州730000)摘要：Hamming网日(m，n)作为超立方网的推广，优良的性质使其成为并行处理和计算系统的首选拓扑结构。本文利用分层方法，对单向Hamming网进行最小直径(定向直径)设计，以保证低干扰的同时，降低其传输延迟，一方法如下：当n=3时，首先根据d(Ⅳ(2，3))=3得到3≤d(胃(3，3))s4，进而得到4曼d(Ⅳ(4，

2、3))s5，最后将H(m，3)按照日(4，3)分层，每一层日(m，3)按照H(4，3)方式进行定向设计；当n≥4时，每一层按照H(2，n)的方式进行定向。最后验证，按照这种方式设计的Hamming网，可有效降低信息传输延迟。关键词：网络理论；Hamming网；定向直径；传输延迟中图分类号：17224．33；0224文章标识码：A文章编号：1(107．3221(2016)05—0132—05doi：10．12005／orms．2016．0172DesignofOne-waySystemAboutHammingNetworkBasedontheMinimumTransmissionDe

3、layCHAIGuo—rong，WENYan—yan，ZONGSheng—liang，YUANChun(SchoolofManagement，LanzhouUniversity，Lanzhou730000，China)Abstract：Asanextensionofthehypercube，HammingnetworkH(m，n)becomesthepreferredtopologyofapar—allelprocessingandcomputingsystembecauseofexcellentnaturthe．Inordertoensurethelowdisturbanceof

4、theinformationaswellasthereductionoftransmissiondelay，wedesigntheone-wayHammingnetworkfromtheviewoftheminimumdiameter(theorienteddiameter)withtheuseofhierarchicalmethod．Themethodofdesig—ningHammingnetworkisasfollows．Whenn=3，ithasgot3曼d(H(3，3))≤4accordingtod(日(2，3))=3，andthen．4冬d(H(4，3))冬5．Thel

5、aststageistodelaminate日(m，3)accordingtoH(4，3)．Whenn≥4，eachlayerorientatedinthewayofH(2，n)．Finally，wevalidatethatHammingnetworkdesignedinthiswaycanreduceinformationtransmissiondelay．Keywords：networktheory；Hamminggraph；theorienteddiameter；transmissiondelay0引言随着科学技术的飞速发展，需要利用计算机处理的数据规模越来越大。更进一步，由

6、于通信、商业、军事等行业竞争的Et益加剧，建造大规模的超级计算机系统进行海量数据的交换和处理势在必行(1997年Columbia大学的Sullivan和同事设计了第一台超立方体并行计算机CHOPP，现在也有很多基于超立方网的超级计算机投入商业运行：Cahech的Comesic，Intel的iPSC和ConnectionMachines)。这种背景要求人们设计既有效可靠、又方便经济的网络，构造简单和性质良好的网络不仅有很高的通信效率，而且有很强的应用性(改进的Hamming网可以有效地对R&D项目实施中止决策)，这对于网络设计者提出了严峻的挑战。在网络设计时，双向网由于一条边上两组信

7、息同时在传输，容易造成信息干扰，为此可将网络设计成单向的。目前广泛应用的单向网络如：单向环形网、DEBruj‘in单向多级网、DEBRujin网¨o、Kautz旧。等。收稿日期：2014—10-27基金项目：国家自然科学基金资助项目(71072070，71472079)作者简介：柴国荣(1976一)，男，甘肃会宁人，博士，教授，主要研究方向：项目管理、集成优化、合作创新。文艳艳(1987-)。女，山东济南人，博士生，主要研究方向：集成优化、公共决策与公共项目管理。宗胜