基于FPGA的KLT特征点多层次归并排序

KLT算法已在多个领域得到成功的应用,其中特征点的排序是用来选择好的特征点跟踪的关键。针对传统排序算法计算耗时、实时性差的缺点,提出一种可并行的多层次归并排序算法并在FPGA中实现了其并行计算,同时分析了其周期精确的计算时间。结果表明该归并排序算法可以[O(N)]的时间复杂度完成特征点的排序,能够满足高清分辨率的图像/视频数据中KLT特征点排序的实时性要求。     

A novel artificial neural network for sorting

An artificial neural network (ANN) is employed for sorting a sequence of real elements in monotonic (descending or ascending) order. Although inspired by harmony theory (HT), whereby the same construction as for the HT ANN is followed, the proposed ANN differs in the mode of operation, namely the obliteration of the consensus (harmony) function, the circumvention of simulated annealing as a means of settling to a solution, the simplification of the activation updating of the nodes of the upper layer, the clamping of the nodes of the lower layer, the gradual shrinking of the ANN and the use of an automatic termination criterion. The creation of the sorted sequence is progressive, whereby at most as many network updates are required as there are elements in the sequence. Ties between elements are resolved by simultaneous activation of the corresponding nodes. Finally, the min and max problems are solved in a single network update.     

面向属性网络的可重叠多向谱社区检测算法

谱社区检测算法多基于结构对网络进行划分,往往受限于划分数量且难以控制重叠程度。设计了面向属性网络的谱社区检测算法,可将属性网络划分为任意数量的可重叠社区并有效发现离群点。具体地,首先,从结构和属性两方面综合考虑,基于加权模块度设计了最大化到节点向量化的分区映射方法;其次,给出簇中心向量的初始选择策略,并将其融合在面向属性网络的重叠度和离群度制约中,实现重叠社区的发现;再次,设计节点分配策略,计算节点与簇中心向量的内积,将节点分配给具有最高内积的社区;最后,结合节点隶属情况,高效地在属性网络中检测出结构紧密、可重叠和具有离群点的社区。此外,将本文算法应用于现实世界的多个网络,验证了本文算法的有效性和效率。     

A time-optimal distributed sorting algorithm on a line network

We have achieved a strict lower time bound of n−1 for distributed sorting on a line network, where n is the number of processes. The lower time bound has traditionally been considered to be n because it is proved based on the number of disjoint comparison-exchange operations in parallel sorting on a linear array. Our result has overthrown the traditional common belief.     

A graph-based Lamarckian-Baldwinian hybrid for the sorting network problem

A hybrid genetic algorithm (GA) is proposed for the optimal sorting network problem. Based on a graph-theoretical viewpoint, we devised a solution repair heuristic which incorporates a strong local optimization. We also propose a new encoding scheme which combines the characteristics of Lamarckian and Baldwinian GAs. Using a single-CPU PC, we obtained results comparable to previous results obtained with supercomputers.     

Height-balanced multiway trees

A typical class of structures to organize ordered files is multiway trees, among which the most widely used is the perfectly balanced B-tree. In this paper we present the new family of BMT multiway trees, which are kept balanced in height, similarly to the classical binary height balanced trees used in central memory. The height of a BMT, that is the maximum search length for a key, is shown to be a logarithmic function of the number of keys in the worst case. Updating a BMT by key insertion is studied, and a technique to keep the tree balanced is presented. A comparison between the performance of BMTs and B-trees leads to the conclusion that the two structures are roughly comparable as to search length for a key, while BMTs require less memory space than B-trees for small node sizes. The real difference between BMTs and B-tree is in rebalancing operation, which requires a work proportional to the node size in the BMTs and to the tree height in the B-tree.     

Single-exception sorting networks and the computational complexity of optimal sorting network verification

Asorting network is a combinational circuit for sorting constructed from comparison-swap units. The depth of such a circuit is a measure of its running time. It is known that sorting-network verification is computationally intractable. However, it is reasonable to hypothesize that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the verification of shallow sorting networks is also computationally intractable. Firstly, a method for constructing asymptotically optimalsingle-exception sorting networks is demonstrated. These are networks which sort all zero-one inputs except one. More specifically, their depth isD(n-1)+2log(n-1)+2, whereD(n) is the minimum depth of ann-input sorting network. It follows that the verification problem for sorting networks of depth 2D(n)+6logn+O(1) is Co-NP complete. Given the current state of knowledge aboutD(n) for largen, this indicates that the complexity of verification for shallow sorting networks is as great as for deep networks.This research was supported by NSF Grant CCR-8801659.     

基于两次优先级排序的虚拟网络映射算法

为解决现有的虚拟网络映射算法忽略网络本身属性,仅按照请求到达的顺序分配资源而导致物理资源利用率低的问题,利用时间窗模型,提出了基于两次优先级排序的虚拟网络映射算法。在第一次排序中,粗化虚拟网络请求的同时根据业务类型、属性参数计算请求优先级,初步确定窗口中虚拟网络映射顺序;在第二次排序中,综合考虑链路带宽资源需求和节点途径跳数,通过链路权重来确定优先级,计算最佳映射路径。仿真结果表明,该算法降低了虚拟网络请求的平均等待时间,提高了请求接受率及收益开销比。     

基于双ibutterfly网络的插入排序算法

为实现密码算法硬件实现过程中序列插入排序的高效性，对序列排序特点和当前最为有效的GRP插入排序算法进行分析，基于ibutterfly网络的插入排序实现效率的评估策略，针对GRP算法存在的潜在缺陷，给出GRP算法的改进算法及其硬件实现。利用Matlab对改进算法的实现效率进行验证，基于Design Complier综合工具对其硬件电路进行性能评估，评估结果表明，在硬件面积增加8?2％的基础上，该方案能够有效提升GRP算法的灵活高效性，验证了改进方案的合理性。     

Optimum multiway search trees

Summary The construction of optimum multiway search trees for n keys, n key weights and n+1 gap weights, is investigated. A new general optimality principle is presented, which can be tuned for specific applications. Moreover we consider the affects of three additional constraints, namely height, structural and node search restrictions, which lead to a number of new construction algorithms. In particular we concentrate on the construction of optimum t-ary search trees with linear and binary search within their nodes for which we obtain O(n ³ t) and O(n ³log₂ t) time algorithms, respectively. Whether these algorithms are or are not optimal remains an important open problem, even in the binary case.     

Analysis and design of an analog sorting network

An analog sorting neural network is presented. First, existing order representations are discussed and a generalized order representation is introduced. The sorting problem is then formulated as the assignment problem. Based on the assignment problem formulation, the neural network architecture is described. Design principles and an op-amp based circuit realization of the analog neural network are delineated. Three illustrative examples are also discussed to demonstrate the capability and performance of the analog neural network. The proposed analog neural network is shown to be capable of monotonic and bitonic sorting and suitable for hardware implementation.     

Designing a multiway synchronization protocol

A multiway synchronization protocol makes it possible for several processes to synchronize in an environment where communication is asynchronous. We present the design of such a protocol. The design methodology is based on formulating the behaviour of the entities as transition systems. This admits a correctness proof: we show that the protocol is correct relatively an ‘ideal’ non-distributed algorithm, in the sense that the protocol and the ideal algorithm cannot be separated by any amount of testing. The proof method is based on cs-equivalence.     

A new parallel sorting approach with sorting memory module

A new approach to accelerating parallel sorting processes is introduced in this paper. This approach involves the design of a new type of memory chip with sorting functions. This type of sorting memory chip is feasible with today's VLSI techniques. A memory module organizing several sorting memory chips associated with additional ECL or TTL control logic circuits is also presented. Using the sorting memory modules in a shared memory parallel processor machine, parallel sorting algorithms such as the column sort method can reduce the row access time significantly and avoid data collisions in the interconnection network. Experimental simulation results on the practical speedup achieved and the memory utilization for the proposed approach are described.     

多路计时系统设计

本文介绍了一个多路计时系统的设计方案,给出硬件电路,重点阐述了高精密计时系统的设计方法。并说明了系统采用可(编程芯片的设计技术。     

A framework for evaluating pairwise and multiway synchrony among stimulus-driven neurons

Several authors have previously discussed the use of log-linear models, often called maximum entropy models, for analyzing spike train data to detect synchrony. The usual log-linear modeling techniques, however, do not allow time-varying firing rates that typically appear in stimulus-driven (or action-driven) neurons, nor do they incorporate non-Poisson history effects or covariate effects. We generalize the usual approach, combining point-process regression models of individual neuron activity with log-linear models of multiway synchronous interaction. The methods are illustrated with results found in spike trains recorded simultaneously from primary visual cortex. We then assess the amount of data needed to reliably detect multiway spiking.