一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性,Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合,提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen),并对其特性进行了研究．证明了RHP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Q、HP(n)网络更短的直径和更小的构造开销．另外,还基于RHP(n)网络分别给出了其上的单播和广播路由算法,证明了其通信效率分别为n-1和n-1．     

双环Petersen网络直径公式及最优路由算法

双环Petersen图互联网络DLCPG(k)是双环网络与Petersen图的笛卡尔积,它具有良好的可扩展性、较短的网络直径和简单的拓扑结构等特性。通过研究其拓扑结构,得到了DLCPG(k)直径的显式公式,并给出了该网络的最优单播路由算法。     

互联网络RCP(n)的路由算法

在对互联网络RCP（Ringed Crossed cube Petersen）拓扑结构研究的基础上,利用RCP（n）网络具有正则性,良好的可扩展性,以及具有比Q_n、HP（n）、RHP（n）网络更短的直径和更小的构造开销这些特性,给出了RCP（n）的单播路由算法和广播路由算法,并证明了RCP（n）比Q_n、HP（n）、RHP（n）网络具有更好的路由性能。     

Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.     

互联网络RCP(n)的最短路算法

RCP(n)是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络.针对RCP(n)上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP(n)上任意两点间最短路的一个多项式算法,为RCP(n)上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值.     

网络容错路由算法概率分析的一种新的方法

该文提出了一种新的概率分析方法来研究在给定结点错误概率的情况下超立方体网络强容错路由算法的容错性的概率。针对文中提出的基于新的局部连通性网络容错模型的高效的强容错路由算法犤1犦,该文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达4.7%的错误结点而具有99%的概率确保找到正确结点组成的路径,而如果结点的错误概率不超过0.1%,则所有实际规模的超立方体网络能够具有99.9%的概率确保找到正确结点组成的路径。该算法的时间性能是最优的,且该算法构造的路径的长度不超过源结点和目的结点之间海明距离的两倍加上一个很小的常数。     

互联网络RCP（n）的最短路算法

RCP（n）是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络。针对RCP（n）上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP（n）上任意两点间最短路的一个多项式算法,为RCP（n）上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值。     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

A General Approach to L(h, k)-Label Interconnection Networks

Given two non-negative integers h and k,an L(h,k)-labeling of a graph G=(V,E) is a function from the set V to a set of colors,such that adjacent nodes take colors at distance at least h,and nodes at distance 2 take colors at distance at least k.The aim of the L(h,k)-labeling problem is to minimize the greatest used color.Since the decisional version of this problem is NP-complete,it is important to investigate particular classes of graphs for which the problem can be efficiently solved.It is well known that the most common interconnection topologies,such as Butterfly-like,Bene(?),CCC,Trivalent Cayley networks,are all characterized by a similar structure:they have nodes organized as a matrix and connections are divided into layers.So we naturally introduce a new class of graphs,called (1×n)-multistage graphs,containing the most common interconnection topologies,on which we study the L(h,k)-labeling.A general algorithm for L(h,k)-labeling these graphs is presented,and from this method an efficient L(2,1)-labeling for Butterfly and CCC networks is derived.Finally we describe a possible generalization of our approach.     

并行计算机互联网与包寻径算法

并行处理是计算机科学中最富有挑战性的领域之一,而并行计算机互联网和寻径算法则是这个领域中研究力量很集中的基础技术。本文介绍了几种流行的互联网结构和典型的寻径算法,并对各种网络的特性及寻径算法的性能做了分析和评述。     

LR(k)任意文法位置的断点调试方法

LR(k)文法能描述所有确定型上下文无关语言,广泛应用于各类分析器生成器中.传统的LR(k)文法断点调试方法仅支持在产生式右部末尾设置断点(后文简称尾部断点),不支持在产生式右部中间位置设置断点(后文简称中间断点),这给分析器的开发和调试带来了不便.文中提出了一种新颖的LR(k)文法断点调试方法,不但支持传统的尾部断点,还支持中间断点.该方法可显著增加可利用的断点数量,可以跟踪到更细粒度的文法成分,从而帮助用户更好地进行文法调试,降低分析器的开发难度.     

Upper bounds on the size of LR(k) parsers

It is shown that in many cases the trivial upper bound 2^{|G|k + 1} on the number of states of an LR(k) parser for a grammar G is too conservative. In particular, if G is not right-recursive, the canonical LR(k) parser for G has at most |G^k|G|·2^|G| states. Examples of grammars with large LR(k) parsers are given.     

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。     

A scheme for LR(k) parsing with error recovery part II: error recovery

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.     

双环网嵌入RP(k)网络

网络嵌入是互连网络研究的一个重要方向,通过网络嵌入可以用一种拓扑结构模拟另一种结构,高效的嵌入会提高并行程序的运行效率。构造了10*k个节点的双环网结构,基于文献[3]提出的互连网络RP（k）,提出了一种将双环网嵌入RP（k）的算法DLN-RP（k）,此算法得到的4个性能参数为拓展、负载、延伸、拥挤度分别为1,1,2,2,并证明了该结果为最优值。