星形图上最小无死锁受限条件及无死锁路径算法

针对是形图中台能产生死锁的问题,对星形图上无无线锁的路径算法进行了研究,得到了星形图上的两类最小无死锁受限条件,并给出了一个满足该两类最小无死锁受限条件的无死锁路径算法。同时还证明了文献中提出的两个死锁受限条件分别只是该文所提出的两类最小无死锁受限条件的一个特例。     

Routing Function and Deadlock Avoidance in a Star Graph Interconnection Network

In this paper the properties of paths in a star graph are investigated through the analysis of the corresponding star transposition tree. The general algebraic expression for all shortest paths between any two nodes (routing function) is found, and it is shown that every shortest path consists of a number of subpaths which can be combined in an arbitrary order or even mutually nested. Further, due to the known routing function the deadlock problem is solved using the method of virtual channels. A minimal deterministic routing algorithm is developed which recognizes the structure of the path by extracting subpaths and allows optimal adaptive management of virtual channels. Finally, based on the sufficient number of virtual channels, the minimal fully adaptive routing algorithm is suggested which offers an opportunity to reroute the message a number of times, while maintaining the shortest path between two nodes.     

n Star虫蚀寻径网络中的一种广播算法

文章介绍了一种采用虫蚀寻径机制的ｎＳｔａｒ互连网络结构,讨论了在该结构上传送消息的广播算法,并对这一算法加以分析。     

Embedding Meshes on the Star Graph

We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n-degree star graph can efficiently simulate an n-dimensional mesh.     

Improved Routing and Sorting on Multibutterflies

This paper shows that an N -node AKS network (as described by Paterson) can be embedded in a ( 3N / 2 ) -node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly networks) with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting and finding the median of n log n items on an n -input multibutterfly in O ( log n ) time, a work-efficient deterministic algorithm for finding the median of n log ² n log log n items on an n -input multibutterfly in O (log n log log n ) time, and a three-dimensional VLSI layout for the n -input AKS network with volume O(n ^3/2 ) . While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks. We also present a separate, and more practical, deterministic algorithm for routing h -relations on an n -input multibutterfly in O(h + log n) time. Previously, only algorithms for solving h one-to-one routing problems were known. Finally, we show that a twinbutterfly, whose individual splitters do not exhibit expansion, can emulate a bounded-degree multibutterfly with (α,β) -expansion, for any α⋅β < 1/4 . Received July 23, 1997; revised May 18, 1998.     

A Parallel Algorithm for Lagrange Interpolation on the Star Graph

This paper introduces a new parallel algorithm for computing an N(=n!)-point Lagrange interpolation on an n-star (n>2). The proposed algorithm exploits several communication techniques on stars in a novel way, which can be adapted for computing similar functions. It is optimal and consists of three phases: initialization, main, and final. While there is no computation in the initialization phase, the main phase is composed of n!/2 steps, each consisting of four multiplications, four subtractions, and one communication operation and an additional step including one division and one multiplication. The final phase is carried out in (n−1) subphases each with O(log n) steps where each step takes three communications and one addition. Results from a cost-performance comparative analysis reveal that for practical network sizes the new algorithm on the star exhibits superior performance over those proposed for common interconnection networks.     

Introspective Sorting and Selection Algorithms

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N²). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ(N log N) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.     

On Probabilistic Networks for Selection, Merging, and Sorting

We study comparator networks for selection, merging, and sorting that output the correct result with high probability, given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n,k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of on the size of networks of success probability in , where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size . We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in , where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least and nearly logarithmic depth. Received January 22, 1996, and in final form February 14, 1997.     

基于对应比较图的Fabric排序机制优化

针对HLF (Hyperledger Fabric)区块链系统在排序阶段中存在的缺陷,提出了一种基于对应比较图的图排序优化方案.利用对应比较图具有相关不变性质的图合并过程以及其算法运行时间短的特点,设计了一种基于交易重要度的拓扑算法,旨在减少由于默认的顺序排序而导致的序列化冲突问题.通过实验与分析,表明该方案有效解决了原始方案的序列化冲突问题,减少了系统中无效事务的比例,提升了系统交易效率,节省了大量的计算与存储资源.     

Optimal Deterministic Sorting and Routing on Grids and Tori with Diagonals

We present deterministic sorting and routing algorithms for grids and tori with additional diagonal connections. For large loads ( ), where each processor has at most h data packets in the beginning and in the end, the sorting problem can be solved in optimal hn/6+o(n) and hn/12+o(n) steps for grids and tori with diagonals, respectively. For smaller loads, we present a new concentration technique that yields very fast algorithms for h<12 . For a load of 1, the previously most studied case, sorting only takes 1.2n+o(n) steps and routing only 1.1n+o(n) steps. For tori, we can present optimal algorithms for all loads . The above algorithms all use a constant-size memory for all processors and never copy or split packets, a property that the corresponding lower bounds make use of. If packets may be copied, 1—1 sorting can be done in only 2n/3+o(n) on a torus with diagonals. Generally gaining a speedup of 3 by only doubling the number of communication links compared with a grid without diagonals, our work suggests building grids and tori with diagonals. Received August 18, 1997; revised December 28, 1997.     

Migration of Tasks in Interconnection Networks Based on the Star Graph

The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the optimal set of codes which can collectively recognize a set of distinct substars is derived. It is shown that using only (n − 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n ≤ 9. When relinquishment of tasks is considered, task migration could potentially improve the utilization of network resources by reducing/eliminating the fragmentation caused as a result of task deallocation. A deadlock-free procedure is presented to migrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via disjoint paths; (ii) the adjacency among the mapped nodes is preserved. The procedure can be made distributed with a slight modification. The work can be extended to other hierarchical networks based on permutation group.     

Conditional Fault Diameter of Star Graph Networks

It is well known that star graphs are strongly resilient like thencubes in the sense that they are optimally fault tolerant and the fault diameter is increased only by one in the presence of maximum number of allowable faults. We investigate star graphs under the conditions offorbidden faulty sets, where all the neighbors of any node cannot be faulty simultaneously; we show that under these conditions star graphs can tolerate upto (2n− 5) faulty nodes and the fault diameter is increased only by 2 in the worst case in presence of maximum number of faults. Thus, star graphs enjoy the similar property of strong resilience under forbidden faulty sets like then-cubes. We have developed algorithms to trace the vertex disjoint paths under different conditions.     

Graph Characterization by Counting Sink Star Subgraphs

In this paper, we study the polynomial coefficients of the reduced Bartholdi zeta function for characterizing simple unweighted graphs and demonstrate how to use these coefficients for clustering graphs. The polynomial coefficients of the reduced Bartholdi zeta function are invariant to vertex order permutations and also carry information about counting the sink star subgraphs in a symmetric digraph of G. We also investigate the advantages of the reduced Bartholdi coefficients over other spectral methods such as the Ihara zeta function and Laplacian spectra. Experimental results indicate that the proposed method is more effective than the other spectral approaches, and compared to the Ihara zeta function, it has less sensitivity to structural noises such as omitting an edge.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

基于图神经网络的智能路由机制

现有基于人工智能的路由方案泛化能力较差,难以适应动态的网络拓扑变化。提出基于深度强化学习的智能路由机制SmartRoute。通过实时感知网络中流量分布状态,动态调整路由策略,并结合图神经网络的拓扑信息感知能力和深度强化学习的自我训练能力,提升网络路由策略的智能性。实验结果表明,与DRL-TE、TIDE等方案相比,SmartRoute最多节省9.6%的端到端时延,且具有更好的鲁棒性。     

星图互联网络上的并行路径算法

为了提高星图互联网络中任意两个结点之间传输大量数据信息的效率以及当星图网络中出现结点故障或链路故障的情况下保证数据信息的正常传输,从群论的角度出发,重点采用循环置换的相关性质,给出了一种新的寻找星图互联网络中任意两点之间的所有并行路径的方法。由于在寻找的过程中,该方法将条件细化成不同的情况讨论,从而保证了在每种情况下给出的所有并行路径的长度构成的集合的上界都是最短的,同时也保证了该算法的有效性和最优性。     

基于图的特征选择算法

针对数据挖掘与模式识别领域中的高维数据处理问题,通过分析样本类间距离与类内距离,给出一种基于图理论的特征排序框架。根据该框架,提出使用类内-类间和K近邻相似度定义的2种快速特征选择算法,能避免复杂度较高的广义特征分解过程。实验结果表明,该算法具有较高的分类精度。     

基于图排序和最大信息增益的领域实体抽取方法

领域知识图谱在各行各业中都发挥着重要作用,领域实体的获取则是构建领域知识图谱的重要基础。数据标注、编写抽取规则等现有的实体抽取方法往往需要较多的人工参与工作。提出一种基于图排序的实体抽取方法和基于最大信息增益的实体扩展方法来构建领域实体集,通过实体识别获得候选实体,基于维基百科的背景信息计算候选实体间的相关度构建实体图,并利用基于置信度传播的图排序算法筛选领域核心实体。在DBpedia中根据最大信息增益来平衡类与领域核心实体相关性及类的抽象程度两个因素以生成实体扩展的共性类。在此基础上,通过SKOS体系中的“Is subject of”关系获得共性类的实例实体,并根据基于字符串相似和结构相关度的方法对扩展实例实体进一步筛选,最终获得全面、准确的领域实体集。以数据结构课程为例构建该课程领域实体集,得到1 115个实体。实验结果表明,在领域数据集上,领域实体抽取F1值达到0.67,能够在较少人工参与的条件下有效获得领域实体,有助于领域知识图谱的构建。     

直接选择排序可视化设计与实现

针对学生在学习数据结构抽象的排序算法时难以理解的问题,采用目前应用最多的java面向对象开发语言,并使用MYECLIPS集成开发环境进行开发,实现了直接选择排序的可视化。形象、清晰、直观地展现了排序的动态过程,可以很好地激发学生的学习兴趣,提高教学成果。