环、mesh嵌入RP(k)网络

作     者：刘方爱 刘志勇 张永胜 

作者机构：山东师范大学信息管理学院济南250014 国家自然科学基金委员会北京100085 

基　　金：国家自然科学基金(批准号:60373063) 山东省自然科学基金(批准号:Y2002G03) 

出 版 物：《中国科学（E辑）》 (Science in China(Series E))

年 卷 期：2004年第34卷第8期

页      码：939-950页

摘      要：基于RP(k)A连网络,首先讨论了该网络的拓扑性质,证明了RP(k)网络 是一个Hamilton图.然后,重点研究了将环和二维mesh嵌入该互连网络的算法. 构造性的证明了10*k的环可以嵌入RP(k)网络,且四个性能参数都为1.考虑到 网络的容错情况,当RP(k)网络中每个片有一个节点出现故障时,去掉故障节点 和相应的边,得到互连网络RP-1(k),该网络也是Hamilton图.然后讨论了将二 维mesh嵌入RP(k)N络的方法,定义了顺序列嵌入、迂回列嵌入和最短路径映射,并设计了嵌入算法.该嵌入算法的性能如下,若a是二维mesh最小一维的长度,按照迂回列嵌入方式,当a=1,2,3,4,5时,其延伸分别为1,2,3,3,2,拥挤度分别为1、3、4、5、3;当51O时,其延伸┍a/1O┐+2,拥挤度=max{┍Ca/10┐,6};当a=10时,四个参数都为1.研究结果表明,RP(k)网络具有简单的拓扑性质,很强的容错能 力,并且环和2-D mesh可以高效地嵌入该网络.

主 题 词：互连网络 RP(k)网络 网络嵌入 Hamilton回路 拥挤度 延伸 

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.3321/j.issn:1006-9275.2004.08.009

馆 藏 号：203134630...