概率故障条件下k元(n-m)方体子网络的可靠性

k元n方体具有许多优良特性,已成为多处理器系统最常用的互连网络拓扑结构之一。当系统互连网络中发生故障时,系统子网络的保持能力对系统实际应用至关重要。为了精确度量k元n方体中任意规模子网络的容错能力,研究了有故障发生时k元n方体中k元(n-m)方体子网络的可靠性。当k(k≥3)为奇整数时,在概率故障条件下得出了k元n方体中存在无故障k元(n-m)方体子网络的概率的上界和下界,并给出了该可靠性的一种近似评估方法。实验结果表明,随着顶点可靠性的降低,k元(n-m)方体子网络可靠性的上下界趋于一致;当顶点可靠性较高时,利用近似评估方法得出的结果更为准确。

INS_面向k-ary n-cube的互联网模拟器

目前流行的mesh、torus和hypercube等互联网均可综合成k-ary n-cube网。为分析k-ary n-cube网的性能，必须建立它的仿真模型，而传统的通用仿真工具不适合对这种互联网的模拟。本文介绍了利用事件推进法建立的互联网模拟器INS(Interconnection Network Simulator)。与其他互联网模拟器的结果比较表明，该模拟器具有较好的应用价值。

K-ary N-cube网络中的维度气泡流控与无死锁完全自适应路由

利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列相关的特点,设计了一种称为维度气泡流控(DBFC)的新型流控策略.该流控策略建立在虚跨步(VCT)切换和信约流控机制之上,通过分析端口信约值和路由信息实现点点间的流控.在无边带karyncube网络中,如果采用DBFC流控策略,即使网络中存在环相关,设计的自适应维度气泡路由(ADBR)算法仍可实现无死锁的最短距离的路由.对于以上结论,文中提供了详细的证明.最后,通过修改模拟工具RSIM的网络模拟器———NETSIM的代码,实现了DBFC流控策略和ADBR算法.模拟结果显示,ADBR算法在性能上比常用的维序路由优越,在报文延迟上有近17.5%的降低.

k元(n-1)方体子网络可靠性的近似评估方法

多处理器系统互连网络的拓扑性质对系统功能的实现起着重要的作用。k元n方体网络的子网络可靠性是以k元n方体为拓扑结构构建的多处理器系统处理计算任务时需要考虑的一个重要因素。为了精确高效地度量概率故障条件下k元n方体中k元(n-1)方体子网络的可靠性,提出基于反向传播(BP)神经网络的k元(n-1)方体子网络可靠性的近似评估方法。首先,利用蒙特卡洛仿真方法和k元(n-1)方体子网络可靠性的已有上下界给出用于训练BP神经网络的数据集的生成方法;其次,基于生成的训练数据集构造用于评估k元(n-1)方体子网络可靠性的BP神经网络模型;最后,对BP神经网络模型得出的k元(n-1)方体子网络可靠性的近似评估结果进行了分析,并与近似计算公式和基于蒙特卡洛的评估方法的结果进行了对比。与近似计算公式相比,所提方法得出的结果更为精确;与基于蒙特卡洛的评估方法相比,所提方法的评估耗时平均减少了约59%。实验结果表明,所提方法在兼顾精度和效率方面具有一定优势。

k-ary n-cube中的移动气泡流控策略

在k-ary n-cube网络中,气泡流控是一种有效、实用的死锁避免技术,它不必依赖虚通道就能避免环网中出现的死锁问题。如果流控策略能感知到维度内缓冲区的总体使用情况,就能够更加高效地进行调度,从而提高网络性能。为了避免关键气泡机制引起的阻塞,提出了伪报文协议;结合伪报文协议,设计了移动气泡流控策略,它有效实现了维度内的全局资源感知能力。与局部气泡流控相比,路由器每条输入通道仅设置一个报文缓冲区就可以避免环网中的死锁,即最小资源需求减少了一半。网络模拟结果表明,该机制不会出现永久阻塞;在distribute、hotregion和uniform传输模式中,该机制可以有效提高网络吞吐率20%以上,并且在网络饱和后吞吐率依然维持稳定。

Hilbert k-cube的一个新上界

给出Hk(n)的一个新上界,并证明Hk(n)<n1-1/2k-1+n1-1/2k-2,其中Hk(n)为数集{1,2,…,n}中不含有Hilbert k-cube集合的最大基数.

On Classification of k-Dimension Paths in n-Cube

The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as (n - k + 1)×n matrix of characters from the same alphabet. A classification of the paths is founded on numerical invariant as special partition. The partition consists of n parts, which correspond to columns of the matrix.

K元2-立方体网络SIMD计算机图像模板匹配并行算法

模板匹配是进行虑波、边缘检测、目标识别和图像匹配的一种基本和有效的方法 .对于 N× N的图像和M× N ( M<N )的模板 ,周期性模板匹配算法在单处理机上用传统的算法实现需要 O( N2 M2 )时间 .显然模板匹配和大多数图像处理及计算机视觉一样是计算密集型问题 ,应采用并行处理方法实现 .该文以 L S MPP并行阵列计算机的应用为研究背景 ,较详细地讨论了模板匹配算法在具有受限局部寄存器的 L S MPP计算机上的并行实现问题 ,提出了一种适用于 K元 2 -立方体网络结构的 SIMD计算机的图像模板匹配并行算法 ,并在 L S MPP计算机上得到了很好的应用 .该算法对于 N× N的图像和 M× N的模板 ,其通信复杂性和计算复杂性都是 O( M2 ) ,分析表明该算法是最优的 .

基于共享策略的k-支配轮廓体的求解算法

现有的k支-配轮廓算法虽然可以对给定的高维数据集计算出不同k(k≤d)值对应的k-支配轮廓,但是,由于不能共享计算结果,会导致很多冗余操作.提出k-支配轮廓体的概念,即所有的k(k≤d)值对应的k-支配轮廓的集合,在此基础上,提出两种基于共享策略的k-支配轮廓体算法——由下到上算法(BTA)和由上到下算法(TBA).理论分析和实验验证表明,所提算法可有效的减少冗余操作.

k-方体图邻点可区别全色数(英文)

本文证明 k-方体图 (k≥ 2 )的邻点可区别的全色数为 k+2 .

k-元n-立方体网络局部通信模式下的性能模型

大规模并行计算机互连网络的设计对并行应用程序的执行效率有重要影响,k-元n-立方体是广泛使用的拓扑结构.局部通信是并行应用的主要通信模式之一,研究局部通信模式下互连网络的性能有重要意义,已有分析模型缺乏对这方面的充分研究.引入局部通信率和局部通信区域半径组成的二元参数,刻画k-元n-立方体网络节点间通信的空间局部性.利用排队论对网络建模,研究延迟和吞吐量随负载的变化规律,比较局部性参数对网络性能的影响强度,针对长、短消息情况分别进行详细讨论.最后采用改进的网络模拟器,验证分析模型具有较高的准确性.为具有局部通信性质的大规模并行应用,提供了一种有效预测延迟和吞吐量的方法.

交换交叉立方网络在PMC模型下的(t,k)-诊断度研究

交换交叉立方网络是新型互连网络拓扑结构研究的最新成果之一,它同时继承了交换超立方网络和交叉立方网络在网络直径、连接边、成本等方面优点,表现出更高的性价比,有望成为多处理器并行计算机的一种更加优化的组织形式。然而,目前,交换交叉立方网络尚未正式引入多处理器并行计算机。影响交换交叉立方网络应用和推广的主要原因之一是其可靠性研究尚不系统,其中以诊断度为代表的运行可靠性的研究最为迫切。基于此,以交换交叉立方网络为研究对象,在得到交换交叉立方网络相关拓扑性质的基础上,通过理论推导和仿真实验证明的方式,首次得出了交换交叉立方网络ECQ(s,t)在PMC模型下的(t,k)-诊断度,进一步补充完善了交换交叉立方网络的可靠性指标,为后续的应用和推广提供了有力的技术支撑。

k-ary n立方体中的测地泛圈

文中用归纳假设法证明了结论:当n≥2,k≥3,u和v是Qkn中任意2个顶点,由对称性,不妨设u=(0,0,…,0),v=(d1,d2,…,dn),这里0≤di≤k/2,(i=1,…,n),记d=d1+d2+…+dn≤1,N=kn,则对于每个偶数l适合2d+2≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.若有i和j满足1≤i≤j≤n,使得di≥1且dj≥1,或有且dj=k/2且dj=0,j≠i,1≤j≤n,则又有l=2d;当n≥2,k≥3是奇数,u和v是Qkn中任意2个顶点,由对称性,不妨设u=(0,0,…,0),v=(d1,d2,…,dn),这里0≤di≤k/2,,(i=1,…,n),记d=d1+d2+…+dn≥1,N=kn,r=max{di},则对于每个奇数l适合2d+k-2r≤l≤N,则Qkn中有过u和v长为l的圈C,且C上u和v的距离为d.

单向k-元n-立方体网络

单向k-元n-立方体是指具有单向边的k-元n-立方体互连网络拓扑。当网络包含的顶点数目较大时,比起传统的双向k-元n-立方体,单向k-元n-立方体对通信硬件复杂性的要求更低一些。提出了k-元n-立方体的一个定向,使得定向后的单向k-元n-立方体UQkn有一些良好的性质。证明了UQkn是正则的,极大弧连通的,具有迭代结构的且UQkn的直径是小的。此外,提出了一个简单的多项式时间路由算法。

基于比较模型的扩展立方体网络的(t,k)-诊断度研究

针对扩展立方体网络故障诊断问题,提出一种基于比较模型的(t,k)-故障诊断方法。首先,通过图论的方法研究n维扩展立方体网络(nAQ)的重要性质,根据这些性质设计了一个基于比较模型的算法来寻找该扩展立方体网络的最大非故障组件。然后,利用所得的最大非故障组件来确定该网络系统的(t,k)-故障诊断度。最后,提出并证明了n维扩展立方体网络是(t,2n-1)-可诊断的。结果表明,n维扩展立方体网络的(t,2n-1)-诊断度2^(n-1)(2n-2)lb(2n-3)/(2n-3)~2远大于其条件诊断度(6n-17)及传统故障诊断度(2n-1)。

k-方体图的Smarandachely邻点全染色

研究了k-方体图Qk(V,E)的Smarandachely邻点全染色,证明了关于图的Smarandachely邻点全染色猜想于k-方体图成立,r-正则图G(V,E)的Smarandachely邻点全色数sχat(G)=Δ(G)+2,其中sχat(G)表示G(V,E)的Smarandachely邻点全色数。

条件故障下k-元n-立方体的强Menger边连通度

为了更好地度量网络的容错性,运用数学归纳法和反证法,讨论了条件故障下k-元n-立方体的强Menger边连通度问题。证明了当k≥4,n≥2时,k-元n-立方体是(6n-8)-条件边故障容错强Menger边连通的;当k=3,n≥2时,3-元n-立方体是(4n-6)-条件边故障容错强Menger边连通的。最后举了一个反例证明该结论是最优的。通过对这个问题的讨论和证明,可以补充Qiao等关于超立方体(2-元n-立方体)的条件容错强Menger边连通度的结果,同时进一步改进了翟登鑫对这个问题的研究结果。

关于路的k-方图的邻点可区别-边全染色和第一类弱全染色

给出了路的k-方图的邻点可区别-边全染色数和第一类弱全染色数。

边故障k元n立方体中经过匹配的指定二不交路覆盖

对边故障k元n立方体网络中经过匹配的指定二不交路覆盖的存在性问题进行了探讨。设Q_(n)^(k)是一个k元n立方体网络,其中n≥4、k≥4是偶数,M是Q_(n)^(k)的匹配,F是Q_(n)^(k)的故障边集。若(u,u′)和(v,v′)是Q_(n)^(k)中任意2条不相邻的边,满足{u,v}∩V(M)=Ф和(u′,v′)∈M,则当M+F≤2n-7时,在Q_(n)^(k)-F中存在2条顶点不相交的路Pu,u′和Pv,v′,经过匹配M且V(Pu,u′)∪V(Pv,v′)=V(Q_(n)^(k))。

基于红黑树与K-D树的LiDAR数据组织管理

LiDAR点云是由海量的激光离散脚点组成的三维点集,在平面以及垂直方向上均分布有数量不均的离散点。LiDAR点云离散点相互之间缺乏空间拓扑关系,所以建立适当的数据组织结构对LiDAR点云进行组织是对LiDAR点云进行处理的基础。根据LiDAR点云的数据结构特点,利用红黑树与K-D树建立一种"非空"规则立方体格网和K-D树相结合的双层次数据结构,用于LiDAR点云的组织管理,从而降低结构冗余和提高索引效率。