【摘 要】
:
随着并行与分布式系统的发展,并行计算机中处理器数量大量增加,处理器之间的互连网络的性质显得越来越重要。同时,在具有大量处理器的系统中,处理器发生故障的情形变得不可避
论文部分内容阅读
随着并行与分布式系统的发展,并行计算机中处理器数量大量增加,处理器之间的互连网络的性质显得越来越重要。同时,在具有大量处理器的系统中,处理器发生故障的情形变得不可避免,系统必须在有故障处理器的情况下继续工作。因此,对互连网络通信性能和容错通信方面的研究成为了并行与分布式系统领域重要的研究课题。超立方体是一种著名的互连网络,具有直径小,结点度数低等优点。随着对超立方体的研究的深入,研究者们提出了多种超立方体的变型,这些变型普遍具有直径大约是超立方体的一半的优点。BC互连网络是一大类超立方体变型,包含了超立方体和大部分已知的超立方体变型。BC互连网络的提出为超立方体及其变型的研究提供了便利。本文主要工作如下:第一部分研究BC互连网络上的容错通信。首先,证明了n维BC互连网络的故障直径的上界为n+「log(|F_n|+1)」。其次,给出了BC互连网络上的一种容错单播和广播算法。并且证明本文所提出的算法在故障结点数小于2n-2且故障结点的分布满足每一个结点至少有一个非故障邻结点的条件时,单播算法在最坏情况下能以时间复杂度O(nlogn)生成长度至多为n+「log(|F_n|+1)」+3的无故障路径;而广播算法在最坏情况下能以时间复杂度O(NlogN)获得以任意非故障结点为根的可靠生成树,并且该生成树的最大高度为n+「log(|F_n|+1)」+3。最后,通过JAVA程序相对算法的性能进行了评估。本文的第二部分主要研究BC互连网络的直径。文献中已经证明n维BC互连网络的直径的上界为n,而所有已知的BC互连网络的直径的下界为「(n+1)/2」。在本文中,提出了一种直径为「n/3」+3的BC互连网络(n≥14),从而改进了BC互连网络的直径的下界。
其他文献
目标跟踪是一门综合了计算机技术、自动化控制技术、图像处理技术、人工智能等多个研究方向的综合技术。目标跟踪在许多领域都有着广泛的应用,如智能监控、交通监视、商场监
随着人类社会日益网络化,现实网络系统变得越来越复杂甚至难以预测,然而人们对网络的安全性和稳定性提出的要求却越来越高。因此,对复杂网络的稳定性研究已成为人们普遍关注的热
随着国民经济的快速增长和社会的进步,银行、电力、交通以及军事设施等领域对安全防范报警系统的需求与日俱增,对智能视频监控技术的应用及发展提出了更高的要求。行人检测与
随着中国城市化的发展和土木工程技术的进步,城市中各种民用工程建设发展很快。而对这些桥梁、大坝、隧道等建筑物以及电力电缆等方面的健康状态的监测,根据关键部件的特征信
生物模型可以模拟系统行为,预测系统未知的行为和特性,从而测试生物学家提出的假设,进行一些实验条件无法达到或非常耗时耗力的模拟实验,它们与生物实验相辅相承,使得生物系统的研
IEEE 802.11 DCF协议以其简易性与健壮性成为目前主流的无线Ad hoc 网络的MAC协议,其基本思想是载波侦听与冲突避免。同时,DCF协议也提供了两种数据包传输机制:二次握手机制(又被
P2P网络具有良好的开放性与扩展性,同样也具有极大的动态性和差异性。正是这样的特性,使得将P2P技术引入VoIP这类对网络环境要求较高的应用带来系统整体性能提升的同时,用户
科学技术推动世界的发展,科技的力量正影响着我们生活、学习和工作。矿产资源管理信息化作为矿产资源管理工作与现代信息技术的结合点,对促进高效管理、科学决策、依法行政,进
基于特征造型技术的三维CAD系统目前已广泛应用于产品设计。随着三维建模技术的发展,CAD系统中包含越来越多的几何特征。含有丰富特征的CAD模型被广泛应用于产品发展的各个阶
cDNA微阵列和寡核苷酸芯片等高通量检测技术的成熟应用,产生了大量的基因表达数据,其中包括静态数据和时序数据。基因表达时序数据反映了生物基因在时间进程上的特性,对其进