论文部分内容阅读
并行处理系统是当今计算机科学研究的前沿。互连网络作为并行处理系统的主干,它的性质对整个网络的性能起着决定性作用。新型并行机的研制依赖于对新型互连网络的设计以及对互连网络的内在性质的研究。然而,互连网络的设计是一个多目标最优化问题,这些目标包括小的网络直径,高连通度,每个处理器(图中的顶点)与其他处理器间的低连接数,可嵌入性,可扩展性,可诊断性与容错性,易实现性,正则性和好的通信算法等等。 国际上已提出了许多种互连网络,其中超立方体以其低直径,高连通度,对称性等许多良好的性质已被用作多种并行机中处理器连接的拓扑结构。然而,超立方体并非各种性质都最优的互连网络,超立方体的有些变型还有许多比超立方体更好的性质,其中交叉立方体已经引起了国际上许多研究者的研究兴趣,它已被证明在直径、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,与超立方体和交叉立方体在比较模型下的可诊断性相同。 另外,由于这种网络同时包含了超立方体和交叉立方体作为子网络,因此它也同时具有低维超立方体和交叉立方体的性能。