几种互连网络上图嵌入的研究

发布时间：2017-04-30 08:54

  本文关键词：几种互连网络上图嵌入的研究，，由笔耕文化传播整理发布。

【摘要】：高性能并行计算机是一个国家综合科技实力的体现,在银行、科研、教育、辅助设计、医药、石油、气象、信息安全等相关领域发挥着日益重要的作用。并行计算机中处理器连接的方式(互连网络)对于并行计算机的性能至关重要。一个互连网络可以用一个图G=(V(G),E(G))来表示,其中V(G)代表顶点集合,而E(G)代表边集。在并行处理领域,研究互连网络及其性质是一个非常重要的课题。交替群图、WK-递归图和局部扭立方体是常用的互连网络结构,它们具有许多优越的性质,因而受到研究者的广泛关注。可嵌入性是互连网络的一个重要性质,图嵌入在并行算法的移植等方面具有重要应用。图嵌入问题的描述如下:给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1每个顶点到G2每个顶点的一个单射,以及G1每条边到G2某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的图嵌入能力,从而能够使客图上的并行算法在其上高效地迁移并运行。路径和网格是并行计算中的两种通用的互连网络结构,许多并行算法都是基于路径和网格设计的。研究如何嵌入不同种类的路径和网格到主图中是一个重要的研究方向。本文研究交替群图、WK-递归图和局部扭立方体三种互连网络上的图嵌入问题,本文研究的两类主要的客图为:不相交路径和网格。具体研究内容如下:1.交替群图上一对一顶点不相交路径覆盖的嵌入问题。本文证明了交替群图具有良好的路径嵌入性质:在n-维交替群图(AGn)中,对于任意的整数n≥3,任意两个不同的顶点μ和ν之间可以嵌入m条顶点不相交路径,且这些路径可以覆盖AGn的所有顶点,这里1≤m≤2n-4。因为AGn的顶点度为2n-4,所以μ和ν之间最多可以嵌入2n-4条顶点不相交路径。该嵌入的扩张和膨胀都为1,也就是在扩张和膨胀这两个参数上该嵌入是最优的。2.WK-递归图上一对一顶点不相交路径覆盖的嵌入问题。本文证明了WK-递归图具有良好的路径嵌入性质:在d基t级WK-递归图(K(d,t))中,对于任意的整数d≥4和t≥1,任意两个不同的顶点μ和ν之间可以嵌入m条顶点不相交路径,且这些路径可以覆盖K(d,t)的所有顶点,这里1≤m≤d-1。因为K(d,t)的连通度为d-1,所以μ和ν之间最多可以嵌入d-1条顶点不相交路径。该嵌入的扩张和膨胀都为1,也就是在扩张和膨胀这两个参数上该嵌入是最优的。3.局部扭立方体上3D网格的嵌入问题。本文证明了局部扭立方体具有良好的网格嵌入性。在n-维局部扭立方体(LTQn)中,本文得到两个主要的结果如下:(1)对于任意的整数n≥4,大小为2×2×2n-3的2个顶点不相交的3D网格可以扩展1和膨胀2嵌入LTQn中。(2)对于任意的整数n≥6,大小为4×2×2n-5的4个顶点不相交的3D网格可以扩展1和膨胀4嵌入LTQn中。上述结果在扩张方面是最优的,因为其扩张都为1。
【关键词】：并行计算 互连网络 图嵌入 不相交路径 网格
【学位授予单位】：苏州大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP338.6
【目录】：

• 摘要4-6
• Abstract6-10
• 第一章 绪论10-16
• 1.1 研究背景10-12
• 1.2 研究内容12-13
• 1.3 研究意义13-14
• 1.4 文章组织结构14-16
• 第二章 相关知识16-26
• 2.1 图论基本概念和符号表示16-19
• 2.2 互连网络19-20
• 2.3 图嵌入问题20-25
• 2.4 本章小结25-26
• 第三章 交替群图上一对一顶点不相交路径覆盖的嵌入26-59
• 3.1 交替群图的定义26-27
• 3.2 交替群图上性质的研究27-28
• 3.3 交替群图上一对一顶点不相交路径覆盖的嵌入28-58
• 3.4 本章小结58-59
• 第四章 WK-递归图上一对一顶点不相交路径覆盖的嵌入59-82
• 4.1 WK-递归图的定义59-60
• 4.2 WK-递归图上性质的研究60-61
• 4.3 WK-递归图上一对一顶点不相交路径覆盖的嵌入61-81
• 4.4 本章小结81-82
• 第五章 局部扭立方体上3D网格的嵌入82-96
• 5.1 局部扭立方体介绍82-85
• 5.2 相关定义和符号表示85-86
• 5.3 嵌入2个顶点不相交的2 × 2 × 2n?3网格至n-维局部扭立方体86-90
• 5.4 嵌入4个顶点不相交的4 × 2 × 2n?5网格至n-维局部扭立方体90-95
• 5.5 本章小结95-96
• 第六章 总结与展望96-98
• 6.1 总结96-97
• 6.2 展望97-98
• 参考文献98-111
• 攻读博士学位期间发表的论文和参与的科研项目111-113
• 致谢113-115

【参考文献】

中国期刊全文数据库 前1条

1 刘敏;刘红美;;PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS[J];Acta Mathematica Scientia;2013年01期

  本文关键词：几种互连网络上图嵌入的研究，由笔耕文化传播整理发布。

本文编号：336514