LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

二进制立方形递归网络的拓扑结构

二进制递归网络是一类具有良好拓扑性质和网络参数的互连网络模型.定义了一类特殊的二进制递归网络模型,即二进制立方形递归网络; 引入子网和超网的概念对其拓扑结构进行了分析研究; 证明了超立方体、扭n-立方体、广义扭立方体、交叉立方体、Mbius立方体和扭立方体连接网络都是这类特殊的二进制递归网络的具体实例.     

k元n方体网络的子网络可靠性

并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了衡量基于[k]元[n]方体网络构建的并行计算机系统的容错能力,研究了边故障模型下[k]元[n]方体网络中[k]元[(n-1)]方体子网络的可靠性。当[k(k≥3)]为奇数时,分别在固定划分模式和灵活划分模式下得出了[k]元[n]方体网络中不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间的计算公式,并通过仿真实验验证了理论结果的精确性。研究表明,当[k]为奇数的[k]元[n]方体网络中有边故障发生时,相比固定划分模式,在灵活划分模式下不同数目的[k]元[(n-1)]方体子网络保持无故障状态的平均失效时间更大。     

局部扭立方体环互连网络及其性质

优化网络的拓扑结构是互连网络研究的重要研究方向。局部扭立方体（locally twisted cube,LTQn ）是对超立方体（hypercube,Qn ）互连网络的优化变种,然而当对LTQn 升级时,需要成倍地增加网络的节点,这不利于LTQn的应用和发展。为了克服LTQn 这一缺陷,提出了一种新的互连网络拓扑结构：局部扭立方体环互连网络（locally twisted cube-connected ring interconnect network,LRN）,给出了LRN的定义及其拓扑结构,并研究了LRN的网络直径、连接度、汉密尔顿连通性、泛圈性、路由等问题,证明了LRN是一种易于升级又具有LTQn 许多优良性质的层次环互连网络（hierarchical ring interconnection networks,HRN）。     

k元n—立方体网络的死锁特征剖析

研究死锁形成几率随网络参数的变化规律 ,对于选择合适的寻径算法、改良网络设计方案都具有重要意义 .环形等多种网络都是 k元 n-立方体网络系列的拓扑同构体 .因此 ,k元 n-立方体网络死锁特征的研究结果具有一定的普遍适用性 .本文根据刻画死锁特征的死锁循环密度属性划分死锁类型 .利用死锁类型分析寻径适应性、物理通道、虚拟通道、缓冲区大小 ,消息长度以及缓冲区结构等参数对死锁形成几率的影响     

交错立方体在故障情形下的诊断度和诊断算法

基于并行系统的超级计算机一直是学术界和工业界的研究热点。作为并行系统的基础,互连网络的性质直接决定了系统的性能。交错立方体作为超立方体的变形,是一种重要的互连网络,其与超立方体相比具有低直径等优越性。利用PMC诊断模型和图论方法,研究了交错立方体在故障情形下诊断度的精确值。然后提出该情形下的诊断算法,并分析了算法的时间复杂度。进一步通过仿真实验,验证在多种故障参数下,该诊断算法的高效性优于文献算法。本文的研究能够更加精确地度量交错立方体的可靠性。     

交叉立方体内顶点不交叉路径长度的研究

Efe提出的交叉立方体（crossed cube）是超立方体（hypercube）的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论：在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径, 使得（1）最短路的长度=u和v之间的距离, （2）所有路中的最长路径长度≤u和v的距离＋4. 这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.     

超级局部扭立方体互连网络及其性质

局部扭立方体是近年来提出的超立方体的一个变型,由于它的许多优越性质(如低直径),在并行处理领域越来越受到人们的重视.然而,像超立方体一样,它也有一个缺点,即要使局部扭立方体升级,就必须成倍地增加其顶点个数.为了解决这一问题,文中将顶点个数为2的次幂的局部扭立方体推广到具有任意个顶点的互连网络,提出了超级局部扭立方体(SLTC)的定义,并证明它保持了局部扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质等方面的优良性质,从而证明了超级局部扭立方体是既保持了局部扭立方体的多种优越性质又易于升级的互连网络.     

基于Myrinet/GM的多通道通信

通信子系统对并行系统的计算效率有重要影响,大规模应用对并行平台的通信性能和可用性提出了挑战性的要求.多通道通信技术通过并行采用多路网络链路互连来提高并行系统通信性能和可用性.首先分析了多进程复用网络对通信性能的影响,然后以Myrinet/GM网络平台为基础,提出了基于网络接口层的通信链路动态选择与分配策略,设计和实现了支持多路Myrinet网络并行通信的协议层MNC.MNC支持通信进程平等,充分地利用多路Myrinet网络链路资源.在使用2路Myrinet互连的PC机群平台上,MNC进程间通信带宽相对于单链路提高了约34%,有效地提高了应用层通信性能.     

交叉立方体在两种策略下的可诊断性

互连网络可诊断性度的高低是衡量这种网络性能优劣的重要标志二交叉立方体是近年提出的一类互连网络，它有一些比超立方体更好的性质．本文用PMC模型证明了n维交叉立方体Dn在精确策略和悲观策略下分别是n-可诊断的和（2n－2）／（2n－2）一可诊断的，从而证明民在这两种策略下的可诊断性度与n维超立体的相同．另外，本文在证明Dn是n-可诊断的同时，还得到了Dn中任何两顶点之间的n条互不相交的路径，它们可作为容错远路的依据．