高晓慧，李 晶，谢秀梅

(1.太原科技大学应用科学学院，太原 030024；2.大同市广灵一中，山西 大同 037500)

1 背景介绍

直连网络是一种常见的网络拓扑结构，已经广泛应用于多处理器系统，多计算机系统以及集群系统中。随着并行计算机互连网络和VLSI技术的迅速发展，系统中的并行处理机越来越多，仍采用传统的网络互连结构已不能满足需求。于是人们对并行计算机互连网络拓扑结构进行了大量的研究[1-4]，并对其中的一些拓扑结构已研制出了相应的商用和研究用的并行计算机系统。网络是一种完全对称的直连网络拓扑结构，它具有很多优秀的网络特性[5]，如规则对称性，路径多样性以及良好的扩展性。因此它广泛应用于许多商用系统中，例如，2004年底评出的全球超级计算机TOP100中排名首位的IBM BlueGene/L就采用网络；而另一家通信设备制造商，Avici公司在其推出的世界上第一台太比特路由器中也采用网络作为其交换网络拓扑。

图嵌入是将一个客图映射到一个主图中的一项技术，是评价一个网络性能的重要指标。 因此，对采用结构的多处理器系统进行嵌入研究是非常必要的。许多应用如结构仿真和处理器分配都可以用图嵌入来建模。在并行处理系统中，由于路和圈的结构均被用于模拟线性数组，所以在图嵌入问题中经常会选择路和圈来作为客图[6]。图的容错性是指当网络中出现故障时，该网络仍然具有的一些好的性质。二维网络是二维网络的扩展，它比网络具有更好的性能，近十几年来人们对网络的容错嵌入进行了大量的研究。……