一、BC互连网络及其性质(论文文献综述)
连冠勤[1](2020)在《基于网络互连的多处理机系统可诊断性能分析》文中研究指明多处理机系统中的网络结构,称为互连网络,是决定多处理机系统性能的关键因素。随着多处理机系统规模的急剧扩大,处理器和链路发生故障的情形不可避免。快速、有效的故障诊断对于系统可靠性显得尤为重要。诊断度是衡量多处理机系统的故障识别能力的关键参数,长期以来是学者们研究的热点。本文主要采用图论建模、组合网络理论分析以及系统级故障诊断理论来解析正则网络的诊断度。我们的主要研究工作具体如下。首先,提出了一种新的诊断模型——有界PMC模型,它推广了经典的具有对称性的PMC模型以及非对称的BGM模型。论文给出一步诊断度和f/(n-1)-诊断的性质和等价刻画。作为应用,确定了正则图基于有界PMC模型的诊断度,同时构造了若干f/(n-1)-可诊断的一般例子。其次,立足于研究更一般且切乎实际的诊断度——混合诊断度。本文以最近提出的两类混合诊断度,h-边容忍诊断度和点边混合故障诊断度,为研究对象,探讨了极大连通正则网络和t-可诊断网络基于PMC模型和MM*模型的h-边容忍诊断度,我们也确定了几类正则网络的混合诊断度。关于h-边容忍诊断度和点边混合故障诊断度的结果推广了已有的结果。另外,我们还研究了一般网络的非包含诊断度与经典诊断度、条件诊断度的关系,并给出了基于PMC模型和MM*模型的非包含诊断度的上下界,同时证明所给的界是紧的。最后,我们给出了取得上下界的正则网络的特征刻画。最后,对于广为研究的条件诊断度,确定了一类比BC网络范围更广的网络——超双射连接网络基于PMC模型和MM*模型的条件诊断度。先证明了超双射连接网络的2-外连通度和3-外连通度,同时也揭示这类网络的强鲁棒性。然后借助容错性分析,分别证明了超双射连接网络基于PMC模型和MM*模型的条件诊断度,其中有关MM*模型的条件诊断度的结果推广了原有的结果。
张治成[2](2020)在《十二面体-师连通圈网络及其笛卡尔乘积网络研究》文中研究说明互连网络是超级计算机的重要组成部分,在很大程度上决定着超级计算机的性能,其拓扑结构是指超大规模计算机系统中的元件(处理器)的连接模式.互连网络的结构和性质是超级计算机研究的重要课题.在设计和选择一个互连网络的拓扑结构时,Hamilton性,泛圈性,圈因子,连通度,直径等指标对分析网络性能发挥了重要作用.师海忠教授在正则图连通圈网络模型和十二面体的基础上,设计出了新的互连网络十二面体-师连通圈网络DSCC(k)和笛卡尔乘积网络DSCC(k)×Cn1×Cn2×…×Cnq,并提出如下猜想,猜想1:k次十二面体-师连通圈网络DSCC(k)是Hamilton可分解的.猜想2:笛卡尔乘积网络DSCC(k)×Cn1×Cn2×…×Cnq是 Hamilton 可分解的,特别地,当 q=1,n1=2时,DSCC(k)× K2是边不交的两个Hamilton圈的并;当q=1,n1=m时,DSCC(k)× Cm(m≥3)是边不交的两个Hamilton圈和一个完美对集的并.本文讨论了十二面体-师连通圈网络DSCC(k),笛卡尔乘积网络DSCC(k)×K2、DSCC(k)× Cm(m≥3)和DSCC(k)×Cn1×Cn2×…×Cnq在拓扑结构中的几个问题,主要结果如下:1.十二面体-师连通圈网络DSCC(k)的主要结果:根据师海忠教授设计的新网络DSCC(k),本文中(1)证明了 DSCC(k)是Hamilton可分解的,且在该结论的基础上证明了师海忠教授提出的两个一般性猜想.(2)给出了DSCC(k)的泛圈性,证明了DSCC(k)既不是泛圈的也不是偶泛圈的.(3)讨论了DSCC(k)的p-因子分解,证明了当k=0,1和k≥1时,DCC(k)中存在一定圈数的2-因子.(4)给出了DSCC(k)的一些基本性质,并作了证明.2.笛卡尔乘积网络DSCC(k)× K2和DSCC(k)× Cm(m≥3)的主要结果:根据师海忠教授构造的新网络DSCC(k)× K2和DSCC(k)× Cm(m≥3),本文中(1)证明了当k=0,1,2时,DSCC(k)× K2是Hamilton可分解的;当m=3,4,k=0,1,2 时,DSCC(k)×Cm(m≥3)是 Hamilton 可分解的.(2)证明了当k=0 时,DSCC(0)× K2 是偶泛圈的;DSCC(k)× K2是偶泛圈的;DSCC(k)× Cm(m≥3)是边偶泛圈的.(3)讨论了 DSCC(k)× K2和DSCC(k)× Cm(m≥3)的p-因子分解,证明了DSCC(k)× K2是2-因子可分解的;当k=0,m=3,4时,DSCC(k)×Cm是2-因子可分解的.(4)给出并证明了DSCC(k)× K2和DSCC(k)× Cm(m≥3)的一些基本性质.3.笛卡尔乘积网络DSCC(k)×Cn1×Cn2×…× Cnq的主要结果:根据师海忠教授设计的新网络DSCC(k)×Cn1 ×Cn2 ×Cn2×…×Cnq,本文中(1)证明了当k=0,q=2,n1=n2=2 时,DSCC(k)× Cn1 × Cn2 ×…× Cnq 是 Hamilton 可分解的.(2)给出并证明了DSCC(k)×Cn1×Cn2×…×Cnq的一些基本性质.
陈璐璐[3](2020)在《Herschel-师连通圈网络及其笛卡尔乘积网络研究》文中认为互连网络是超级计算机的重要组成部分,其拓扑结构是指超大规模计算机系统中的元件(处理器)的连接模式.实际上,互连网络的拓扑结构就是图.互连网络的结构和性质是超级计算机研究的重要课题.在设计和选择互连网络的拓扑结构时,顶点度,Hamilton性,连通度,直径等指标对分析网络性能方面发挥了重要作用.本文讨论了k次Herschel-师连通圈网络HSCC(1,k),笛卡尔乘积网络HSCC(1,k)×Cn1×Cn2×…×Cnq在拓扑结构中的几个问题,主要结果如下:1.网络HSCC(1,k)的主要结果:师海忠设计了 k次Herschel-师连通圈网络HSCC(1,k),且提出了猜想1:HSCC(1,k)是Hamilton可分解的.在本文中(1)给出了网络HSCC(1,k)的顶点数,边数,正则性,连通度;(2)证明了当k=0和k=1时猜想1成立,即HSCC(1,0),HSCC(1,1)是Hamilton可分解的;(3)研究了当k=0和k=1时,网络HSCC(1,k)的泛圈性和偶泛圈性,以及它的圈因子.2.网络HSCC(1,k)×Cn1×Cn2×…×Cnq的主要结果:师海忠设计了笛卡尔乘积网络HSCC(1,k)×Cn1×Cn2×…×Cnq,且提出猜想2:HSCC(1,k)×Cn1×Cn2×…×Cnq是Hamilton可分解的.特别地,2.1当q=1,n1=2时笛卡尔乘积网络HSCC(1,k)× K2可分解为两个边不交的Hamilton圈的并;2.2当q=1,n1=m时笛卡尔乘积网络HSCC(1,k)× Cm可分解为两个边不交的Hamiton圈和一个完美对集的并.在本文中(1)给出了这类网络的一些性质,并分别讨论了当q=1,n1=2与q=1,n1=m时,笛卡尔乘积网络HSCC(1,k)× K2 HSCC(1,k)× Cm的一些性质;(2)证明了当k=0,k=1时猜想2.1成立,以及当k=0,m=3 时猜想2.2成立;(3)研究了当 k=0,k=1 时,网络 HSCC(1,k)× K2的泛圈性,偶泛圈性和圈因子;(4)并研究了当k=0时,网络HSCC(1,0)× C3的泛圈性,偶泛圈性和圈因子.
王桂娟[4](2019)在《广义超立方体的可靠性研究》文中提出互连网络作为高性能计算网络的重要组成部分,其性能的优劣至关重要,而可靠性是衡量一个网络性能好坏的关键指标之一。广义超立方体(Generalized Hypercube,GH)是一个性能优良的互连网络拓扑结构:它具有较短的直径;它的结点可以用任意进制表示;它的连接方式和递归的结构使其易于构造。GH的拓扑结构具有一般性,其不仅包含了超立方体、网格网络、3-元n-立方体和完全图等许多的互连网络结构,而且还可以被用来设计数据中心网络,例如HyperX、BCube、FBFLY、SWCube 等。连通度、不相交路径、容错哈密顿性质以及如何删除网络中的资源以得到性能较好的网络问题是网络可靠性研究中的重要课题。然而,在用这几个指标来衡量网络的可靠性时存在许多不足:首先,用连通度来衡量一个网络的可靠性时,通常是指传统连通度。但当用传统连通度来衡量一个网络的可靠性时,某个结点的所有邻接点可以同时发生故障,而该事件在真实的运行环境中发生的概率是非常低的,因此这种情况不能很好地反映现实场景。其次,在构造容错不相交路径时,没有考虑到限制连通度,这使得构造出的不相交路径条数不够多。再次,在用容错哈密顿性质衡量一个网络的可靠性时,只考虑了单个结点和边发生故障的情形而没有将一组满足特定条件的边作为故障元素来考虑,这使得对容错哈密顿性质的研究具有一定的局限性。最后,删除网络中的一些资源可以降低网络的构造成本,然而这样一来所得到的网络难以保持其原网络的关键性质。本文针对广义超立方体中的上述可靠性问题,进行了深入研究,取得了如下的研究成果:1.研究了GH的结构连通度和子结构连通度,这些结构包括星、长度为3和4的圈、结点数为4的完全图。研究结果表明,在保证GH可靠通信的情况下,GH中可以容许的故障结点数在理想情况下几乎达到传统连通度的两倍。2.给出了在每个结点都至少有一个无故障邻接点的条件下GH的不相交路径构造算法。该算法能够在GH中构造多条不相交路径,这些不相交路径的条数大约是传统连通度下不相交路径条数的两倍,且这些路径的最大长度不超过GH的直径加2。该结论表明,在用这些不相交路径进行数据传输时,在理论上,其通信延迟至多比在传统连通度情况下的通信延迟大两跳。研究结果表明,当GH中的每个结点都有一个无故障的邻接点且GH中的故障结点数小于1-限制连通度时,GH中任意两个无故障结点之间都有一条无故障的路径。3.研究了一类GH中的故障集中包含结点、边和满足特定条件的一组边三种故障元素条件下的容错哈密顿性质。研究结果表明,要保障这类GH中存在无故障哈密顿圈和无故障哈密顿路(即不包括故障结点的哈密顿圈和路)时,与传统连通度相比,这类GH在可以容许的故障元素数量方面有了显着地提升。本文的研究结果也适用于两类重要的数据中心网络:BCube和HyperX。4.为了降低GH的构造成本,本文将GH中若干条特定的边删除后得到一个新的网络拓扑结构—交换广义超立方体(Exchanged Generalized Hypercube,EGH)。在研究了 EGH的直径、连通度以及路由等基本性质后,本文给出了 EGH的容错不相交路径构造算法和两种局部诊断算法。实验结果表明,即使EGH中的故障结点的比例达到25%,这两种诊断算法可以成功判断出结点是否发生故障的概率依然超过了90%。研究结果表明,EGH不仅降低了网络的构造成本还保持了GH的良好性能,这进一步说明了 GH具有很好的可靠性。综上所述,本文从结构连通度、不相交路径、容错哈密顿性质以及GH的变形等四个方面刻画了GH的可靠性。研究成果表明,GH在上述的四个方面都具有良好的可靠性。本文也为其他网络可靠性的研究提供了新的方法。
刘爱霞,王世英[5](2020)在《BC网络的g-超条件诊断度》文中研究说明多处理器系统的故障诊断是一个重要的研究课题。g-超条件诊断度是于2016年提出的度量系统自我故障诊断能力的一类新的参数,它是在每个非故障结点组成的分支至少包含g+1个顶点的假设下,系统G能够一次性识别的故障结点的个数。g-超条件诊断度能够更精确地度量异构环境下系统互连网络的自我故障诊断能力。文章研究了n-维双射连接(BC)网络在PMC和MM*模型下的g-超条件诊断度,给出了n-维BC网络在两种模型下g-超条件诊断度的下界。在此基础上,确定了超立方体在PMC和MM*模型下g-超条件诊断度,改进了相关结果。最后,我们给出了当1≤g≤3时,BC网络在PMC和MM*模型下的g-超条件诊断度的计算公式。
李小燕[6](2019)在《数据中心网络DCell的可靠性研究》文中进行了进一步梳理大数据时代的到来对人类社会的发展产生了深远影响。海量数据的产生推动数据处理方式的变革。在此发展态势下,云计算应运而生。云计算的模式,实际上是通过构建大型共享平台,向网络用户提供在线云服务,从而实现资源的按需分配。数据中心是云计算的核心设施,而数据中心网络是连接数据中心大规模服务器实现在线云服务的平台。因此,数据中心网络的性能决定着云计算所提供的服务质量。随着数据中心网络中服务器的大规模增加,服务器发生故障的情形是不可避免的。可靠性是保障数据中心网络正常运行的前提,也是影响云计算服务质量的重要因素。因此,可靠性的研究对衡量数据中心网络性能是至关重要的。容错能力是评估网络可靠性的重要指标。数据中心网络中故障服务器的定位、诊断、检测和修复等措施能够提高网络的可用性、可靠性和鲁棒性。DCell网络是典型的以服务器为中心的数据中心网络,具有高可拓展性、较大网络容量、较小直径和容错路由等良好性质,并且在网络通信方面能够提供较好的服务。本文基于DCell网络的拓扑结构Dm,n来研究其可靠性。首先,本文从DCell网络容错能力方面评估其可靠性能。连通度是评估网络容错能力的标志性指标,网络连通度越大,其容错能力越强。h-额外连通度是使网络不连通而最少需要删掉的结点数目,并且满足删掉这部分结点后网络中剩余的每个连通分支中结点数目都不少于h+1。h-额外连通度弥补了传统连通度的缺陷,它能够更好地评估网络的可靠性能。本文得到了Dm,n的一些容错性质,并且证明了Dm,n的h-额外连通度。其次,本文从DCell网络故障诊断能力方面研究其可靠性能。当网络中存在故障服务器又希望保证网络正常运行的情况下,就需要对故障服务器进行快速定位和检测,进而修复或更换这些故障服务器,从而提高网络的可靠性能。因此故障诊断是保障网络可靠性的重要因素。故障诊断策略通常分为精确诊断和非精确诊断这两类。g-好邻居条件诊断度和h-额外条件诊断度是基于精确诊断策略的两类不同条件下的诊断度量参数。其条件满足了网络在实际情况下发生故障的情况,并且能够使网络的故障诊断能力得到提高。非精确诊断策略又分为悲观诊断和t/k-诊断,它们都是通过牺牲少量的误诊服务器来提高网络的诊断能力。本文分别证明了Dm,n在PMC和MM*模型下基于不同策略的诊断度,g-好邻居条件诊断度和h-额外条件诊断度。本文得到Dm,n的h-额外连通度大约是其传统连通度的h+1倍。同时,本文首次得到Dm,n在PMC和MM*模型下的不同条件和策略的诊断度。本文研究结果为DCell网络的可靠性和可用性评估提供定量分析,为其在实际数据中心中的应用提供理论依据。
郭晨,彭硕,王博,肖志芳,刘华[7](2018)在《互连网络的故障诊断研究综述》文中指出互连网络作为系统内部的协同机制和主要的通信手段,是多处理器并行计算机的重要组成部分。为了进一步提高多处理器并行计算机的诊断能力,保障系统的可靠运行,在充分分析互连网络拓扑结构研究的基础上,首先指出了各种互连网络拓扑结构的继承关系、优缺点、拓扑性质、成本和连通度,进而对互连网络的各类故障诊断度进行详细阐述,在结合互连网络各类故障诊断度的基础上,以进一步提高互连网络拓扑性能和诊断能力为目标提出了互连网络故障诊断研究的3个发展方向。系统地综述了互连网络的故障诊断研究现状,重点归纳了互连网络在各类故障诊断度方面的研究成果,指出了互连网络故障诊断研究的发展趋势以及未来研究的主要方向,从而促进互连网络在多处理器并行计算机的应用和推广。
陈敬[8](2017)在《几种互连网络的故障诊断及可靠性研究》文中提出随着多处理器系统的广泛应用,系统的规模在不断扩大,一些处理器会不可避免的发生故障。因此可靠性分析与故障诊断对系统的设计和维护至关重要。互连网络是多处理器系统的拓扑结构,是影响多处理器系统性能的一个关键因素。为了选取合适的互连网络,需要研究不同互连网络的一些性质。连通度和诊断数通常被用来评估互连网络的可靠性和故障诊断能力。为了更好的研究互连网络的可靠性以及故障诊断能力,一些新的度量参数被提出:超连通度,限制连通度和额外连通度以及悲观诊断数和t/k-可诊断数。在众多互连网络中星图以及Split-Star网络因其具有小直径,对称性,可分性和高容错性等优良性质而被广泛研究。本文首先研究了星图网络Sn的可靠性。确定了当4 ≤5时星图网络的最小点边界,推导并证明了使得Sn-F中存在一个大的连通分支且剩下所有小连通分支至多含有h-1个点的子集F所满足的条件。进而证明了当3≤h4时,星图Sn网络的h-额外连通度为Kh(Sn)(h+1)n-4h+ 2(n≥7)。研究结果从理论上提高了星图的容错能力。其次探讨了 Split-Star网络的故障诊断能力。在PMC模型下确定了 Split-Star网络悲观诊断数为tp(Sn2)=4n-9。结果表明该诊断数是传统t-可诊断数的两倍,明显提高了 Split-Star网络的故障诊断能力。最后研究了 k元n立方体Qk的h-额外连通度和t/k-可诊断数之间的关系,并确定了在PMC模型下k元n立方体Qnk的h-额外连通度等于其相应的t/k-可诊断数。类似的,对BC网络来说,当k≥4,l l≤h≤-4时,有Kh(Xn)=t(n,h),其中t(n,h)=(k+l)n-1/2(k+1)(k+2)+1。该研究结果表明对于一些已知其h-额外连通度的互连网络可以直接得到其t/k-可诊断数。
周东仿[9](2017)在《交换交叉立方体上若干性质的研究》文中研究说明高性能计算机是一个可以处理海量数据和大型应用的计算机系统,它在教育、科研、石油、气象等多个领域发挥着日益重要的作用。近年来,随着高性能计算机技术应用的不断加深,系统内的处理器变得越来越多,由此引起的用于连接处理器的互连网络的规模也随之相应扩大。高性能计算机系统的性能在很大程度上取决于互连网络的性质。衡量一个互连网络性质优劣的重要标准是图的嵌入能力。作为常用的网络拓扑结构,圈和路径具有结构简单、度数小、通信代价小等优良特性,它们在并行计算等领域被大量应用。因此,互连网络中的圈和路径嵌入问题也是并行处理的一个重要课题。然而,将任意长度的圈和路径嵌入到一般互连网络中的求解问题是NP难的。互连网络的哈密顿性质可以被看作是在互连网络中圈和路径嵌入的一个特例。它在数据通信中具有重要的应用,如果在互连网络的多播路由算法中使用哈密顿圈或哈密顿路径,则能够有效地减少或避免死锁和拥塞。此外,哈密顿性质在互连网络的故障诊断中也有重要应用。因此,研究互连网络的哈密顿性质具有重要意义。随着并行计算机系统规模的不断扩大,系统中处理器或处理器间通信链路不可避免地会出现故障,这就带来了系统在可靠性和可使用性方面的问题。解决这一问题的方法就是容错技术,而故障诊断是进行容错处理的关键步骤。故障诊断就是识别出发生故障的处理器或通信链路,它可以在不增加系统额外硬件成本和维护开销的情况下,达到提高系统可靠性和可用性的目的。因此,研究互连网络的故障诊断是一个具有重要意义的课题。交换交叉立方体网络(Exchanged Crossed Cube,简称为ECQ网络)是一种性能优良的互连网络,如具有较好的路由性能(低直径)、较少网络链路数、高扩展性等,并能够支持超大规模的互连网络。研究ECQ网络的可嵌入性、容错性和可诊断性,可以为其应用于高性能计算等领域提供理论依据。因此,该研究具有重要的理论与应用价值。本文研究内容分为以下三个部分:1.我们证明了ECQ网络具有很好的哈密顿性质,主要结论如下:(1)证明了当s≥2和t≥3时,ECQ(s,t)中任意两个不同顶点之间不仅存在哈密顿路径,而且存在比哈密顿路径长度少1的路径。(2)给出了ECQ(s,t)上任意两个不同顶点之间一条哈密顿路径的构造算法,并分析了算法的时间复杂度。(3)在(2)的基础上,我们还给出了ECQ(s,t)上哈密顿圈的构造算法,并分析了算法的时间复杂度。(4)我们证明了对于任意的整数s≥2,t≥3和s≤t,ECQ(s,t)是(s-2)-哈密顿连通的和(s-1)-哈密顿的。2.我们研究了ECQ网络的可嵌入性问题,给出了如下研究结果:(1)对于任意的整数s≥2和t≥3,证明了在ECQ(s,t)中包含长度从4到2s+t+1的圈(除ECQ(2,3)和ECQ(3,3)中不包含长度为9的圈外)。(2)证明了对于任意的整数3≤s≤t E Q s t,中任两个不同顶点之间都存在长度为l的路径,其中[s+1/2]+[t+1/2]+ 5≤l≤2s+t-1 + 5 ≤ l ≤ 2s+t+1-1。注意:ECQ(s,t)的直径是[s+1/2]+[t+1/2]+2。(3)证明了对于任意的整数s ≥ 3和t ≥ 4,ECQ(s,t)中任两个不同顶点之间都存在长度为l的路径,其中「s+]+「t+]+ 4 ≤ ≤ 2s+t+1-1。3.我们研究了ECQ网络的可诊断性,得出了如下结论:对于任意的整数1 ≤ s ≤ t,证明了ECQ(s,t)在悲观策略下基于PMC模型和MM*模型的诊断度都为2s。综上所述,在相同维度下,尽管ECQ网络仅有交叉立方体网络中约一半的边数,但它依然很好地保持了交叉立方体网络所拥有的哈密顿性质、圈嵌入能力和路径嵌入能力;ECQ网络除了比交换超立方体网络拥有较小的通信传输延迟外,其诊断能力依然与相同条件下交换超立方体网络的诊断能力一样。
刘钊[10](2016)在《几种BC网络上完全二叉树的嵌入研究》文中研究说明并行计算在教育、科研、石油、生物、气象等相关领域发挥着日益重要的作用。多处理器互连网络(简称互连网络)在很大程度上决定了并行计算系统的性能。因此,互连网络及其性质的研究是并行处理领域中的一个重要课题。互连网络可以表示为一个简单图,其中顶点代表处理器,边代表处理器之间的通信链路。在互连网络的设计和分析中,图嵌入能力是衡量一个互连网络性能优劣的重要指标。给定两个图G和H,由G到H的一个嵌入定义为由G到H的一个单射。图G和图H分别称为嵌入的客图和主图。理想的互连网络(主图)应该拥有优秀的图嵌入能力,使得拥有规则任务图(客图)的并行算法能够在该网络上高效的执行。扩张、膨胀、拥塞和负载是衡量图嵌入性能的常用指标,图嵌入的最优性能求解问题是NP难问题。由于完全二叉树具有优越性能和广泛应用,因此将其作为客图嵌入互连网络具有十分重要的研究意义。尽管完全二叉树到一般互连网络以最优性能嵌入的求解问题是NP难问题,但在一些特殊互连网络中以最优性能嵌入完全二叉树已经得到解决。迄今为止,关于将完全二叉树嵌入多种互连网络如网孔、星图、网格、蝶网等的研究已经取得了较多成果。超立方体作为一种常用的互连网络得到了众多研究者的青睐,其具有许多优越性质比如低直径、高连通性、对称性、递归构造性等。然而,完全二叉树不能以最优性能嵌入超立方体,却能以最优性能嵌入某些超立方体变型,如交叉立方体和折叠立方体。超立方体及其若干变型均具有一一对应连接和可递归构造性质,研究者依据这两个性质将它们归结为一类互连网络——BC网络。然而,关于将完全二叉树嵌入BC网络的研究成果相对较少。本文中,我们主要研究几种BC网络——莫比乌斯立方体、奇偶立方体和局部扭立方体上完全二叉树的嵌入问题。我们证明了完全二叉树能以最优性能嵌入莫比乌斯立方体和奇偶立方体,以及以较优性能嵌入和容错嵌入局部扭立方体。具体包括以下内容:1.n维莫比乌斯立方体(Mn)上完全二叉树的嵌入与交叉立方体不同的是,Mn是由两个不同构的子莫比乌斯立方体组成(n≥5)。因此,在Mn上嵌入完全二叉树将面对更复杂的情形。我们研究了Mn上完全二叉树以最优性能嵌入的问题,取得了如下研究结果:(1)证明了莫比乌斯立方体中满足的一个重要性质——由不相交子立方体构成的立方体对同构于子莫比乌斯立方体。(2)基于Mn上存在同构立方体对的性质,提出了一种对Mn上的完全二叉树嵌入进行类型划分的构造方法。(3)证明了完全二叉树能以扩张1、负载1、拥塞1和膨胀趋近于1嵌入Mn。2.n维奇偶立方体(PQn)上完全二叉树的嵌入与Mn上完全二叉树的嵌入方法不同,我们给出了PQn上完全二叉树以最优性能嵌入的证明方法。进一步,我们还设计了相应的嵌入算法和模拟实验,取得了如下研究结果:(1)证明了完全二叉树能以扩张1、负载1、拥塞1和膨胀趋近于1嵌入PQn。(2)给出了时间复杂度为O(Nlog N)的完全二叉树嵌入算法,其中N为PQn的顶点个数,并给出了算法的正确性证明。(3)设计了在PQn上嵌入完全二叉树的模拟实验。3.n维局部扭立方体(LT Qn)上完全二叉树的容错嵌入随着互连网络规模的不断增大,处理器和通信链路将不可避免地出现故障。因此,我们有必要去评估互连网络的容错嵌入能力。我们研究了LTQn上完全二叉树的嵌入以及容错嵌入问题,取得了如下研究结果:(1)证明了以任意顶点为根的完全二叉树能以扩张2、负载1、拥塞1和膨胀1嵌入LTQn。(2)证明了当LTQn上的任意一个顶点发生故障时,LTQn上嵌入的完全二叉树能以扩张2和拥塞2动态重建。(3)证明了当LTQn上的任意两个顶点发生故障时,LTQn上嵌入的完全二叉树能以扩张3和拥塞3动态重建。(4)证明了当LTQn上的故障顶点数超过两个时,在给定的限制条件下LTQn上嵌入的完全二叉树能以扩张3和拥塞3动态重建。
二、BC互连网络及其性质(论文开题报告)
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、BC互连网络及其性质(论文提纲范文)
(1)基于网络互连的多处理机系统可诊断性能分析(论文提纲范文)
中文摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景与意义 |
1.2 系统级故障诊断的研究现状 |
1.2.1 基于PMC模型的诊断度研究现状 |
1.2.2 基于MM~*模型的诊断度研究现状 |
1.3 论文框架 |
1.4 本文创新之处 |
第2章 基础知识 |
2.1 图与网络的基本概念和记号 |
2.2 系统级故障诊断模型 |
2.2.1 基于测试的诊断模型 |
2.2.2 基于比较的诊断模型 |
2.3 限制性诊断度及其判定 |
2.3.1 f/s-诊断度 |
2.3.2 h-边容忍诊断度 |
2.3.3 非包含诊断度 |
2.3.4 条件诊断度 |
2.3.5 h-额外条件诊断度 |
2.4 若干常见的正则网络及性质 |
2.4.1 基于阿贝尔群的网络拓扑 |
2.4.2 基于置换群的网络拓扑 |
第3章 有界PMC模型的诊断度刻画 |
3.1 预备知识 |
3.2 基于(f_1,f_2)-BPMC模型的一步诊断度 |
3.3 基于(f_1,f_2)-BPMC模型的f_1/(n-1)-诊断度 |
第4章 正则网络的混合诊断度 |
4.1 正则网络的h-边容忍诊断度 |
4.1.1 极大连通的正则网络的h-边容忍诊断度 |
4.1.2 t-可诊断网络的h-边容忍诊断度 |
4.2 点边故障的混合故障诊断度 |
4.2.1 基于PMC模型的点边混合故障诊断度 |
4.2.2 基于MM*模型的点边混合故障诊断度 |
第5章 正则网络的非包含诊断度 |
5.1 一般网络非包含诊断度的刻画 |
5.2 非包含诊断度达到最小的正则网络 |
5.3 非包含诊断度达到最大的正则网络 |
第6章 超双射连接网络的条件诊断度 |
6.1 超双射连接网络的容错性质 |
6.2 H_n(m)基于PMC模型的条件诊断度 |
6.3 H_n(m)基于MM*模型的条件诊断度 |
第7章 研究工作总结与展望 |
7.1 研究工作总结 |
7.2 研究工作展望 |
参考文献 |
攻读学位期间承担的科研任务与主要成果 |
致谢 |
个人简历 |
(2)十二面体-师连通圈网络及其笛卡尔乘积网络研究(论文提纲范文)
摘要 |
Abstract |
第1章 绪论 |
1.1 研究背景 |
1.2 本文的主要工作 |
第2章 基本知识 |
2.1 图论的有关术语及重要定义 |
2.2 十二面体-师连通圈网络的概念 |
2.3 笛卡尔乘积网络DSCC(k)×K_2的概念 |
2.4 笛卡尔乘积网络DSCC(k)×C_m的概念 |
2.5 笛卡尔乘积网络DSCC(k)×C_(n_1)×C_(n_2)×…×C_(n_q)的概念 |
第3章 十二面体-师连通圈网络DSCC(k)及其性质 |
3.1 DSCC(k)的Hamilton分解 |
3.2 DSCC(k)的泛圈性 |
3.3 DSCC(k)的p-因子分解 |
3.4 DSCC(k)的基本性质 |
第4章 笛卡尔乘积网络DSCC(k) ×K_2及其性质 |
4.1 DSCC(k)×K_2的Hamilton分解 |
4.2 DSCC(k)×K_2的泛圈性 |
4.3 DSCC(k)×K_2的p-因子分解 |
4.4 DSCC(k)×K_2的基本性质 |
第5章 笛卡尔乘积网络DSCC(k)×C_m及其性质 |
5.1 DSCC(k)×C_m的Hamilton分解 |
5.2 DSCC(k)×C_m的泛圈性 |
5.3 DSCC(k)×C_m的p-因子分解 |
5.4 DSCC(k)×C_m的基本性质 |
第6章 笛卡尔乘积网络DSCC(k)×C_(n_1)×C_(n_2)×…×C_(n_q)及其性质 |
6.1 DSCC(k)×C_(n_1)×C_(n_2)×…×C_(n_q)的Hamilton分解 |
6.2 DSCC(k)×C_(n_1)×C_(n_2)×…×C_(n_q)的基本性质 |
结束语 |
参考文献 |
致谢 |
个人简历、在学期间发表的学术论文及研究成果 |
(3)Herschel-师连通圈网络及其笛卡尔乘积网络研究(论文提纲范文)
摘要 |
abstract |
第1章 绪论 |
1.1 研究背景 |
1.2 本文的主要工作 |
第2章 基本知识 |
2.1 图论的有关术语及重要定义 |
2.2 k次Herschel -师连通圈网络HSCC(1,k)的概念 |
2.3 乘积图的概念 |
第3章 k次Herschel-师连通圈网络HSCC(1,k)及其性质 |
3.1 HSCC(1,k)的基本性质 |
3.2 HSCC(1,k)的泛圈性 |
3.3 HSCC(1,k)的圈因子 |
第4章 笛卡尔乘积网络HSCC(1,k)×K_2及其性质 |
4.1 HSCC(1,k)×K_2及其性质 |
4.2 HSCC(1,k)×K_2的Hamilton分解 |
4.3 HSCC(1,k)×K_2的泛圈性 |
4.4 HSCC(1,k)×K_2的圈因子 |
第5章 笛卡尔乘积网络HSCC(1,k)×C_m及其性质 |
5.1 HSCC(1,k)×C_m基本性质 |
5.2 HSCC(1,k)×C_m的Hamilton分解 |
5.3 HSCC(1,k)×C_m的泛圈性 |
5.4 HSCC(1,k)×C_m的圈因子 |
第6章 HSCC(1,k)×C_(n_1) C_(n_2)×...×C_(n_q)及其性质 |
6.1 HSCC(1,k)×C_(n_1)×C_(n_2)×...×C_(n_q)基本性质 |
第7章 结束语 |
参考文献 |
致谢 |
在学期间发表的学术论文及研究成果 |
(4)广义超立方体的可靠性研究(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 研究背景和意义 |
1.2 国内外研究现状 |
1.2.1 连通度 |
1.2.2 不相交路径 |
1.2.3 哈密顿性质 |
1.2.4 诊断 |
1.2.5 网络变形结构 |
1.3 研究内容 |
1.4 本文组织结构 |
第二章 相关知识 |
2.1 基本概念和符号表示 |
2.2 广义超立方体的定义及其基本性质 |
2.3 本章小结 |
第三章 结构连通度 |
3.1 广义超立方体的1—额外连通度 |
3.2 H-结构连通度和H-子结构连通度 |
3.2.1 κ(G,H)和κ~s(G,H) |
3.2.2 κ(G,K_(1,1))和κ~s(G,K_(1,1)) |
3.2.3 κ(G,K_(1,M))和κ~s(G,K_(1,M)) |
3.2.4 κ(G,C_3)和κ~s(G,C_3) |
3.2.5 κ(G,K_4)和κ~s(G,K_4) |
3.2.6 κ(G,C_4)和λ~s(G,C_4) |
3.3 容错性能分析 |
3.4 本章小结 |
第四章 1-限制连通度下的不相交路径 |
4.1 基于相邻结点的不相交路径 |
4.1.1 第一种不相交路径 |
4.1.2 第二种不相交路径 |
4.1.3 路径的不相交性 |
4.2 基于不相邻结点的不相交路径 |
4.2.1 基础路径 |
4.2.2 第一种构造路径的方法 |
4.2.3 第二种构造路径的方法 |
4.2.4 第三种构造路径的方法 |
4.2.5 第四种构造路径的方法 |
4.2.6 不相邻结点间的不相交路径 |
4.3 模拟实验 |
4.3.1 相邻结点 |
4.3.2 不相邻结点 |
4.4 本章小结 |
第五章 容错哈密顿性质和容错哈密顿连通性 |
5.1 BCube的定义及性质 |
5.2 BC_(n,k)的容错哈密顿性质和哈密顿连通性 |
5.3 交换机发生故障情形下BC_(n,k)的容错哈密顿性质 |
5.4 性能分析 |
5.4.1 故障交换机的数量 |
5.4.2 故障元素的数量 |
5.5 本章小结 |
第六章 广义超立方体的变形 |
6.1 交换广义超立方体 |
6.1.1 交换广义超立方体的定义 |
6.1.2 交换广义超立方体的性质 |
6.2 路由算法 |
6.3 不相交路径 |
6.3.1 第一种不相交路径 |
6.3.2 第二种不相交路径 |
6.3.3 第三种不相交路径 |
6.3.4 第四种不相交路径 |
6.3.5 EGH中任意两点之间的不相交路径 |
6.4 交换广义超立方体中的局部诊断 |
6.4.1 在PMC模型下的局部诊断 |
6.4.2 在MM模型下的局部诊断 |
6.4.3 模拟实验 |
6.5 构造成本 |
6.6 本章小结 |
第七章 总结与展望 |
7.1 总结 |
7.2 展望 |
参考文献 |
攻读博士学位期间发表的论文和参与的科研项目 |
致谢 |
(5)BC网络的g-超条件诊断度(论文提纲范文)
0 引言 |
1 术语和记号 |
2 BC网络在PMC和MM*模型下的g-超条件诊断度的下界 |
3 g较小时,BC网络在PMC和MM*模型下的g-超条件诊断度 |
4 结论 |
(6)数据中心网络DCell的可靠性研究(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 引言 |
1.2 数据中心网络研究现状 |
1.3 网络可靠性研究现状 |
1.4 研究意义 |
1.5 研究内容 |
1.6 文章组织结构 |
第二章 相关知识 |
2.1 基本概念和符号表示 |
2.2 PMC模型和MM~*模型 |
2.3 数据中心网络DCell及其基本性质 |
2.4 本章小结 |
第三章 DCell网络的h-额外连通度 |
3.1 预备知识 |
3.2 容错性质 |
3.3 h-额外连通度 |
3.4 本章小结 |
第四章 DCell网络基于不同策略的诊断度 |
4.1 预备知识 |
4.2 在PMC和MM~*模型下基于精确策略的诊断度 |
4.3 在PMC模型下基于悲观策略的诊断度 |
4.4 在PMC模型下基于t/k-策略的诊断度及诊断算法 |
4.5 在MM*模型下基于t/k-策略的诊断度及诊断算法 |
4.6 本章小结 |
第五章 DCell网络的g-好邻居条件诊断度 |
5.1 预备知识 |
5.2 在PMC模型下的g-好邻居条件诊断度 |
5.3 在MM~*模型下的g-好邻居条件诊断度 |
5.4 本章小结 |
第六章 DCell网络的h-额外条件诊断度 |
6.1 预备知识 |
6.2 在PMC模型下的h-额外条件诊断度 |
6.3 在MM~*模型下的h-额外条件诊断度 |
6.4 本章小结 |
第七章 总结与展望 |
7.1 总结 |
7.2 展望 |
参考文献 |
攻读博士学位期间发表的论文和参与的科研项目 |
致谢 |
(7)互连网络的故障诊断研究综述(论文提纲范文)
1 引言 |
2 互连网络拓扑结构研究 |
2.1 线性阵列和树形结构 |
2.2 超立方网络 |
2.3 扭立方网络 |
2.4 折叠超立方网络 |
2.5 交叉立方网络 |
2.6 莫比乌斯立方网络 |
2.7 平衡立方网络 |
2.8 增广立方网络 |
2.9 交换超立方网络 |
2.1 0 超立方网络二次变种拓扑结构 |
3 互连网络的故障诊断与诊断度研究 |
3.1 互连网络的精确故障诊断与诊断度研究 |
3.2 互连网络的非精确故障诊断与非精确诊断度研究 |
3.3 互连网络的条件故障诊断与条件诊断度研究 |
3.4 互连网络的顺序故障诊断与顺序诊断度研究 |
4 互连网络的故障诊断研究展望 |
4.1 互连网络的拓扑结构研究 |
4.2 互连网络的非精确故障诊断研究 |
4.3 互连网络的顺序故障诊断研究 |
5 总结 |
(8)几种互连网络的故障诊断及可靠性研究(论文提纲范文)
摘要 |
ABSTRACT |
符号对照表 |
缩略语对照表 |
第一章 绪论 |
1.1 多处理器系统可靠性的研究背景和意义 |
1.2 多处理器系统故障诊断的研究背景和意义 |
1.3 主要工作及论文结构 |
第二章 预备知识 |
2.1 图的概念及基本定义 |
2.2 额外连通度的相关概念 |
2.3 PMC模型下的悲观诊断数和t/k-可诊断数 |
2.4 本文研究的互连网络 |
2.4.1 星图S_n |
2.4.2 Split-Star网络 |
2.4.3 BC网络 |
2.5 本章小结 |
第三章 确定星图网络S_n的最小点边界及h-额外连通度 |
3.1 星图网络S_n最小点边界 |
3.2 星图网络的h-额外连通度 |
3.3 本章小结 |
第四章 研究Split-Star网络在PMC模型下的悲观诊断数 |
4.1 Split-Star网络S_n~2邻点集下界的确定 |
4.2 Split-Star网络的悲观诊断数 |
4.3 本章小结 |
第五章 给出k元n立方体Q_n~k的额外连通度和t/k-可诊断数之间的关系 |
5.1 k元n立方体Q_n~k网络及其相关性质 |
5.2 PMC模型下的t/k-可诊断数和h-额外连通度 |
5.3 在PMC模型下k元n立方体Q_n~k的t/k-可诊断数 |
5.4 PMC模型下的t/k-诊断算法 |
5.5 本章小结 |
第六章 结论与展望 |
6.1 主要相关结论 |
6.2 展望 |
参考文献 |
致谢 |
作者简介 |
(9)交换交叉立方体上若干性质的研究(论文提纲范文)
摘要 |
abstract |
第一章 绪论 |
1.1 研究背景 |
1.1.1 高性能计算 |
1.1.2 互连网络 |
1.2 研究意义 |
1.3 国内外研究现状 |
1.4 研究内容 |
1.5 本文组织结构 |
第二章 相关知识 |
2.1 图论基本概念和符号表示 |
2.2 超立方体及其变型 |
2.2.1 超立方体 |
2.2.2 超立方体的几种主要变型 |
2.3 ECQ网络及其基本性质 |
2.3.1 ECQ网络的定义 |
2.3.2 ECQ网络的基本性质 |
2.4 本章小结 |
第三章 ECQ网络上的哈密顿性质 |
3.1 引言 |
3.2 ECQ网络上的哈密顿性质 |
3.3 ECQ网络上哈密顿路径和哈密顿圈的构造算法 |
3.4 ECQ网络上的容错哈密顿性质 |
3.5 模拟实验 |
3.6 本章小结 |
第四章 ECQ网络中圈与路径的嵌入 |
4.1 圈嵌入 |
4.1.1 圈嵌入概述 |
4.1.2 ECQ网络中圈的嵌入 |
4.1.3 模拟实验 |
4.2 路径嵌入 |
4.2.1 路径嵌入概述 |
4.2.2 预备知识 |
4.2.3 ECQ网络中路径的嵌入 |
4.3 本章小结 |
第五章 ECQ网络的可诊断性 |
5.1 故障诊断概述 |
5.2 ECQ网络的可诊断性 |
5.3 本章小结 |
第六章 总结与展望 |
6.1 总结 |
6.2 展望 |
参考文献 |
攻读博士学位期间发表的论文和参与的科研项目 |
附录A |
致谢 |
(10)几种BC网络上完全二叉树的嵌入研究(论文提纲范文)
摘要 |
Abstract |
第一章 绪论 |
1.1 研究背景 |
1.2 互连网络研究概述 |
1.3 完全二叉树嵌入研究概述 |
1.3.1 图嵌入概述 |
1.3.2 完全二叉树嵌入的研究现状 |
1.4 研究内容 |
1.5 文章组织结构 |
第二章 相关知识 |
2.1 图论基本概念和符号表示 |
2.2 超立方体及其变型 |
2.2.1 超立方体 |
2.2.2 超立方体的几种主要变型 |
2.3 BC网络的定义与性质 |
2.3.1 BC网络的定义 |
2.3.2 BC网络的相关性质 |
2.4 本章小结 |
第三章 完全二叉树在莫比乌斯立方体上的嵌入 |
3.1 引言 |
3.2 莫比乌斯立方体的定义 |
3.3 辅助引理 |
3.4 完全二叉树在莫比乌斯立方体上的嵌入 |
3.5 本章小结 |
第四章 完全二叉树在奇偶立方体上的嵌入 |
4.1 引言 |
4.2 奇偶立方体的定义与性质 |
4.3 完全二叉树在奇偶立方体上的嵌入 |
4.4 奇偶立方体上完全二叉树的嵌入算法 |
4.4.1 算法描述 |
4.4.2 算法分析 |
4.5 模拟实验 |
4.6 本章小结 |
第五章 完全二叉树在局部扭立方体上的嵌入及容错嵌入 |
5.1 引言 |
5.2 局部扭立方体的定义 |
5.3 辅助引理 |
5.4 完全二叉树在局部扭立方体上的嵌入 |
5.5 完全二叉树在局部扭立方体上的容错嵌入 |
5.6 本章小结 |
第六章 总结与展望 |
6.1 总结 |
6.2 展望 |
参考文献 |
攻读博士学位期间发表的论文和参与的科研项目 |
致谢 |
四、BC互连网络及其性质(论文参考文献)
- [1]基于网络互连的多处理机系统可诊断性能分析[D]. 连冠勤. 福建师范大学, 2020(12)
- [2]十二面体-师连通圈网络及其笛卡尔乘积网络研究[D]. 张治成. 西北师范大学, 2020(01)
- [3]Herschel-师连通圈网络及其笛卡尔乘积网络研究[D]. 陈璐璐. 西北师范大学, 2020(01)
- [4]广义超立方体的可靠性研究[D]. 王桂娟. 苏州大学, 2019(06)
- [5]BC网络的g-超条件诊断度[J]. 刘爱霞,王世英. 山西大学学报(自然科学版), 2020(02)
- [6]数据中心网络DCell的可靠性研究[D]. 李小燕. 苏州大学, 2019(04)
- [7]互连网络的故障诊断研究综述[J]. 郭晨,彭硕,王博,肖志芳,刘华. 计算机科学与探索, 2018(10)
- [8]几种互连网络的故障诊断及可靠性研究[D]. 陈敬. 西安电子科技大学, 2017(06)
- [9]交换交叉立方体上若干性质的研究[D]. 周东仿. 苏州大学, 2017(06)
- [10]几种BC网络上完全二叉树的嵌入研究[D]. 刘钊. 苏州大学, 2016(08)