计算机互连双环网络的最优设计

《计算机互连双环网络的最优设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中　国　科　学　　　(E　辑)第29卷　第3期SCIENCEINCHINA(SeriesE)1999年6月3计算机互连双环网络的最优设计徐俊明(中国科学技术大学数学系,合肥230026)摘要　　双环网络G(N;r,s)有N个结点0,1,2,⋯,N-1,并从每个结点i发出两条有向边i→i+r(modN)和i→i+s(modN),其中1≤r≠s

2、能在r=1时达到的双环网络无限族.同时指出Esqué等人结果中的一个错误.关键词　　计算机互连网络　最优设计　双环网络　循环有向图　直径众所周知,计算机互连网络或通讯系统的拓扑结构可以用有向图G来模拟,其中G的顶点表示处理机或开关元件,G的有向边表示单向通讯连线.网络的有效性的一个重要参数是信息的传输延迟,它可以用图的直径来度量.双环网络具有对称性、简单性和可扩性,因而被广泛用于计算机互连网络或通讯系统的拓扑结构中.双环网络的图论模型是指这样一个有向图G(N;r,s),它的每个顶点记为0,1,2,

3、⋯,N-1,并从每个顶点i发出两条有向边i→i+r(modN)和i→i+s(modN),其中r和s是两个自然数,而且1≤r≠s

4、d(N;r,s),并记d1(N)=min{d(N;1,s):1d(N),则d(N)不可能在r=1时达到.我们称这样的N为奇异的.若存在s使得d(N;1,s)=d1(N),则称G(N;1,s)是优的.若存在r和s使得d(N;r,s)=d(N),则称G(N;r,s)是最优的.设m是一个正实数,[m]表示不小于m的最小整数.[1]早在1974年,Wong和Coppersmith就证明了d1(N)≥

5、[3N]-2.(2)并且提出研究下述组合问题:对每个N≥4,确定d1(N)的精确值,并且构造出优的G(N;1,s).由于问题的困难性和应用的局限性,这个问题的研究一直没有得到足够的重视.随着计算机的广泛应用和大规模集成电路以及光缆技术的出现,这个问题才得到广泛深入的研1998208214收稿,1999201222收修改稿3国家自然科学基金资助项目(批准号:19671057)和国家博士点基金及中国科学院基金资助项目©1995-2004TsinghuaTongfangOpticalDiscCo.,Lt

6、d.Allrightsreserved.第3期徐俊明:计算机互连双环网络的最优设计273[2～8]究.直到1987年,人们才陆续构造出16个优的双环网络无限族.但这16个无限族不能[7]包含50以内的所有自然数.突破性进展是在1993年.李乔等人提出一个系统的构造方法,并且根据这个方法列表展示出102个优的双环网络无限族,其中包含已知的16个和所有的自然数N,4≤N≤300.[6]1987年,Fiol等人证明了(2)式中的下界对于一般的双环网络G(N;r,s)仍然成立,即d(N)≥[3N]-2.(

7、3)同时,他们通过计算机搜索后发现,奇异的N确实存在,它的最小值是450.事实上d1(450)=36,并且G(450;1,59)是优的.然而,d(450;2,185)=[3·450]-2=35.由(3)式知G(450;2,185)是最优的.对N≥4,记lb(N)=[3N]-2.G(N;r,s)称为紧优的,如果d(N;r,s)=lb(N).易知,若G(N;r,s)是紧优的,则它一定是最优的.反之不真.李乔等人在文献[7]中所展示的102个优的双环网络无限族中,有69个是紧优的.紧优的G(N;r,s)

8、称为奇异的,如果N是奇异的.由上面的说明知,G(450;2,185)是奇异紧优的.Esqué等人在文献[3]的结尾断言找到一个奇异紧优双环网络无限族{G(N(e);r(e),2s(e)):e∈Z},其中N(e)=2700e+2220e+450,r(e)=30e+2,s(e)=420e+185,Z是非负整数无限集.令Z′={157k+136:k∈Z},则Z′