一个针对洗牌交换网的最优路由算法

洗牌交换网是最流行的互连网络之一 ,然而 ,它的缺点之一便是缺少最短路由算法 .最短路由算法 ,通常也称为最优路由算法 ,能保证报文在任意一对结点之间沿着最短路径传送 .针对包含 2 n个结点的洗牌交换网 ,文中给出了一个 O(n2 )时间复杂度的最短路由算法 .该算法还可以很容易地适用于立方体连接圈 (CCC) ,且所得到的算法比已有的 CCC路由算法要简单得多 .

洗牌置换与广义洗牌置换

对n为任意正整数的洗牌置换性质进行研究 ,同时对这种置换进行推广 ,提出了广义洗牌置换的定义 。

若干图的书式嵌入结果

图的书式嵌入问题是从多层印刷电路板设计,容错多处理器阵列设计等许多应用领域中抽象出来的。本文改进了[1]中提出的平面栅格,任意树,X-树的书式嵌入结果。本文还提出了较优的洗牌交换网,树网,同孔树和立方互连环的书式嵌入方法。

SEFP:一种新的固定度为4的Cayley互连网络

提出一种新的固定度为4的正则互连网络SEFPn,它是一种置换群Sn上的Cayley 图。SEFPn是基于洗牌(shuffle),交换(exchange)及翻转(flip)运算的互连网络。它直径短,其直径大约是SEPn(洗牌交换置换网络[5])的一半。我们提出了基于此网络的路由算法,并由此得到了此网络的直径估计。这种网络被证明能有效模拟其它基于置换群Sn上的Cayley 图。在要求具有限定数量的I/O端口的VLSI实现方面,此网络很具有吸引力。另外我们还讨论了此网络的一些代数性质。