环、mesh嵌入RP(k)网络

摘要：

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

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

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60373063;山东省自然科学基金Y2002G03

在线出版日期：2004-09-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：939-950