几种BC网络上完全二叉树的嵌入研究
并行计算在教育、科研、石油、生物、气象等相关领域发挥着日益重要的作用。多处理器互连网络(简称互连网络)在很大程度上决定了并行计算系统的性能。
因此,互连网络及其性质的研究是并行处理领域中的一个重要课题。互连网络可以表示为一个简单图,其中顶点代表处理器,边代表处理器之间的通信链路。
在互连网络的设计和分析中,图嵌入能力是衡量一个互连网络性能优劣的重要指标。给定两个图G和H,由G到H的一个嵌入定义为由G到H的一个单射。
图G和图H分别称为嵌入的客图和主图。理想的互连网络(主图)应该拥有优秀的图嵌入能力,使得拥有规则任务图(客图)的并行算法能够在该网络上高效的执行。
扩张、膨胀、拥塞和负载是衡量图嵌入性能的常用指标,图嵌入的最优性能求解问题是NP难问题。由于完全二叉树具有优越性能和广泛应用,因此将其作为客图嵌入互连网络具有十分重要的研究意义。
尽管完全二叉树到一般互连网络以最优性能嵌入的求解问题是NP难问题,但在一些特殊互连网络中以最优性能嵌入完全二叉树已经得到解决。迄今为止,关于将完全二叉树嵌入多种互连网络如网孔、星图、网格、蝶网等的研究已经取得了较多成 ...