HCH-立方体互连网络及其性质的研究

来源 :青岛大学 | 被引量 : 0次 | 上传用户:liongliong461
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
并行处理系统是当今计算机科学研究的前沿。互连网络作为并行处理系统的主干,它的性质对整个网络的性能起着决定性作用。新型并行机的研制依赖于对新型互连网络的设计以及对互连网络的内在性质的研究。然而,互连网络的设计是一个多目标最优化问题,这些目标包括小的网络直径,高连通度,每个处理器(图中的顶点)与其他处理器间的低连接数,可嵌入性,可扩展性,可诊断性与容错性,易实现性,正则性和好的通信算法等等。 国际上已提出了许多种互连网络,其中超立方体以其低直径,高连通度,对称性等许多良好的性质已被用作多种并行机中处理器连接的拓扑结构。然而,超立方体并非各种性质都最优的互连网络,超立方体的有些变型还有许多比超立方体更好的性质,其中交叉立方体已经引起了国际上许多研究者的研究兴趣,它已被证明在直径、Hamilton性质、模拟树和圈等方面的能力都比超立方体强。当然,交叉立方体也有一些比超立方体差的性质,如交叉立方体不像超立方体那样是边对称的。 超立方体和交叉立方体相比都既有优点也有缺点,我们希望一个网络既能具备超立方体的优点,又能具备交叉立方体的优点,使多个基本目标得到改进。针对这一问题,本文将给出在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到一种称为HCH-立方体的新型网络,并对这种网络的以下性质进行了研究:直径、最小顶点度数、顶点连通度、边连通度、圈嵌入、Hamilton连通性以及比较模型下的可诊断性。 本文首先证明了当1≤n≤3时,n维HCH-立方体互连网络的直径为n,当n≥4时,直径为[n/2]+2,即其直径仅仅比交叉立方体的直径至多大2(n维交叉立方体的直径为[(n+1)/2]),从而证明HCH-立方体的直径比超立方体小大约一半;然后证明了n维HCH-立方体互连网络的最小顶点度数和顶点连通度和边连通度为n,保持了超立方体和交叉立方体的最高连通度的优点;接下来证明了当n≥2且n≠3时,HCH_n中存在长度为l的圈(其中4≤l≤2~n),克服了超立方体在对圈的模拟能力方面的不足,并给出了求n维HCH-立方体中长度为l的圈的算法,该算法的时间复杂摘要度为O(l);本文还证明了当n之4时,HCH一立方体任意两个顶点之间存在Hamllton路径,即HCH一立方体是Hamilton连通的,而超立方体不是Hamilton连通的,这表明HCH一立方体具备了父叉立方体在Hamilton连通性方面的性质。本文还给出了在n维HCH一立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH一立方体的顶点个数;最后证明了,当n之4时,n维HCH一立方体互连网络在比较模型下的可诊断性为n,与超立方体和交叉立方体在比较模型下的可诊断性相同。 另外,由于这种网络同时包含了超立方体和交叉立方体作为子网络,因此它也同时具有低维超立方体和交叉立方体的性能。
其他文献
本文首先对当前计算机网络的安全问题进行了简单介绍,分析了在网络安全体系中引入入侵检测技术的必要性,并介绍了入侵检测的一些基础知识,详细分析了已有的各种分布式入侵检
构建分布式多层系统的三种主流组件技术分别是:COM/DCOM/COM+、CORBA和EJB。这些组件技术都是客户/服务器模式的,只能将数据移动到计算端,存在对象功能单一,网络适应性差等不
在网络技术发展日新月异的今天,移动代理技术凭借其出色的自治性和移动性,成为继CORBA、EJB、DCOM之后的新一代分布式处理的关键技术。国内外众多研究机构都在积极寻求移动代理
鉴于目前在主干网络中存在大量的IPv4设施,我们建议IPv6的部署首先从边缘接入网络开始,结合WLAN技术和移动IPv6,实现一个个移动IPv6的孤岛,逐步向纯IPv6环境过渡.在这个过渡
WWW的出现导致网站上的文本成指数级增长,因此如何自动处理这些海量联机文本成为目前重要的研究课题。自动文本分类是文本信息处理中的一个重要环节。 本文研究文本的自动
逆向工程技术是目前CAD领域研究的重点问题之一.由于逆向工程技术可以处理目前商业CAD系统难于处理的大规模测量数据造型问题,因此受到CAD系统厂家、用户的广泛重视.由于逆向
目前数据转换在功能、效率、以及支持自动转换等方面存在不足,作者对转换方法、数据转换的优先次序算法、XML与关系模式之间的自动转换算法等进行了研究.在数据清理方面,作者
现代道路运输管理是一个复杂的系统分析、管理、控制与决策过程,它需要强有力的信息支撑系统沟通各个独立的业务操作处理系统,以实现现代道路运输科学化管理所需要的综合分析
本论文讨论了几类基于Zakagi-Sugeno(T-S)模糊模型的不确定非线性动态系统的模糊控制问题,利用线性矩阵不等式(LMI)方法和Lyapunov稳定性理论,提出了几种保证闭环系统稳定的
本论文涉及的课题是“基于智能体技术的入侵检测系统体系结构的研究”,提出并深入研究了一个基于智能体技术的入侵检测系统的体系结构,构造一个比较理想的原型系统。本文陈述