Parallelization of sorting algorithms

The paper considers parallel (synchronous) array sorting algorithms obtained by parallelizing the corresponding sequential sorting algorithms. A classification of synchronous sorting algorithms, based on the sequential scheme, is proposed. A number of new efficient synchronous array sorting algorithms are developed.Translated from Kibernetika, No. 6, pp. 67–74, November–December, 1989.     

Spike train decoding without spike sorting

We propose a novel paradigm for spike train decoding, which avoids entirely spike sorting based on waveform measurements. This paradigm directly uses the spike train collected at recording electrodes from thresholding the bandpassed voltage signal. Our approach is a paradigm, not an algorithm, since it can be used with any of the current decoding algorithms, such as population vector or likelihood-based algorithms. Based on analytical results and an extensive simulation study, we show that our paradigm is comparable to, and sometimes more efficient than, the traditional approach based on well-isolated neurons and that it remains efficient even when all electrodes are severely corrupted by noise, a situation that would render spike sorting particularly difficult. Our paradigm will also save time and computational effort, both of which are crucially important for successful operation of real-time brain-machine interfaces. Indeed, in place of the lengthy spike-sorting task of the traditional approach, it involves an exact expectation EM algorithm that is fast enough that it could also be left to run during decoding to capture potential slow changes in the states of the neurons.     

Performance evaluation of iterative geometric fitting algorithms

The convergence performance of typical numerical schemes for geometric fitting for computer vision applications is compared. First, the problem and the associated KCR lower bound are stated. Then, three well-known fitting algorithms are described: FNS, HEIV, and renormalization. To these, we add a special variant of Gauss-Newton iterations. For initialization of iterations, random choice, least squares, and Taubin's method are tested. Simulation is conducted for fundamental matrix computation and ellipse fitting, which reveals different characteristics of each method.     

Performance modelling of three parallel sorting algorithms on a pipelined transputer network

The implementation of three parallel sorting algorithms, namely binary sort, odd-even transposition sort and bitonic sort, on a network of transputers is analysed in the paper. The variation in the performance of these algorithms as the number of processors and sort size are changed is investigated. Experimental results show that when up to eight transputers are used, connected as a linear pipeline configuration, all three algorithms can achieve reasonable speedup ratios. The bitonic sort, binary sort odd-even transposition sort achieve speedup ratios of 5, 4.4 and 4, respectively, when eight processors are used to sort 100,000 integers. Analytical models are derived which can be used to predict the performance of the three algorithms when a linear pipeline configuration is used. The predicted performance of the algorithms is compared with the experimental performance in order to validate the model. When the models are used to predict the performance using 16 transputers, it is found that the speedup does not significantly improve compared to the performance achieved with eight transputers. This shows that interprocessor communication has a significant effect on the algorithmic performance when a larger number of processors are used. The conclusions reinforce the fact that the binary and bitonic sorting algorithms are not well-suited to a linear pipeline configuration and that they may perform better if a different topology were used, for example a mesh or a cube connection scheme. Further, the analytical technique used for performance modelling as elaborated in the paper can be employed profitably for other multiprocessor systems as well.     

Performance evaluation of vector implementations of combinatorial algorithms

We study the performance and the use of vector computers for the solution of combinatorial optimization problems, particularly dynamic programming and shortest path problems. A general model for performance evaluation and vector implementations for the problems described above are studied. These implementations were done on a CRAY-1 vector computer and the computational results obtained show (i) the adequacy of the performance evaluation model and (ii) very important gains concerning computing times, showing that vector computers will be of great importance in the field of combinatorial optimization.     

Performance evaluation and benchmarking of six-page segmentation algorithms

Informative benchmarks are crucial for optimizing the page segmentation step of an OCR system, frequently the performance limiting step for overall OCR system performance. We show that current evaluation scores are insufficient for diagnosing specific errors in page segmentation and fail to identify some classes of serious segmentation errors altogether. This paper introduces a vectorial score that is sensitive to, and identifies, the most important classes of segmentation errors (over-, under-, and mis-segmentation) and what page components (lines, blocks, etc.) are affected. Unlike previous schemes, our evaluation method has a canonical representation of ground truth data and guarantees pixel-accurate evaluation results for arbitrary region shapes. We present the results of evaluating widely used segmentation algorithms (x-y cut, smearing, whitespace analysis, constrained text-line finding, docstrum, and Voronoi) on the UW-III database and demonstrate that the new evaluation scheme permits the identification of several specific flaws in individual segmentation methods.     

Performance evaluation of conservative algorithms in parallelsimulation languages

Parallel discrete event simulation with conservative synchronization algorithms has been used as a high performance alternative to sequential simulation. In this paper, we examine the performance of a set of parallel conservative algorithms that have been implemented in the Maisie parallel simulation language. The algorithms include the asynchronous null message algorithm, the synchronous conditional event algorithm, and a new hybrid algorithm called Accelerated Null Message that combines features from the preceding algorithms. The performance of the algorithms is compared using the Ideal Simulation Protocol. This protocol provides a tight lower bound on the execution time of a simulation model on a given architecture and serves as a useful base to compare the synchronization overheads of the different algorithms. The performance of the algorithms is compared as a function of various model characteristics that include model connectivity, computation granularity, load balance, and lookahead     

A synthesis of several sorting algorithms

Summary We synthesise versions of six well known sorting algorithms from a common specification using program transformation techniques. On the way to the sorting algorithms we synthesise three algorithms for generating permutations thus building up a family tree for the sorts exposing certain relationships between them.     

基于CUDA的多信道锋电位实时分类方法

为提高多信道神经元锋电位分类任务的计算效率,满足其在实时场景下的应用需求,提出基于统一计算设备架构(compute unified device architecture,CUDA)的掩蔽高斯混合模型的并行化实现和优化方案。利用高维锋电位数据的稀疏特性和高斯混合模型的强抗干扰性以及良好并行性,借助GPU图形处理器,对特征掩蔽高斯混合模型(Masked Gaussian mixture model,Masked GMM)进行并行实现,进行针对性优化。实验结果表明,在32信道的锋电位数据集上,与原有的CPU串行实现相比,该方案分类速度提高了170倍左右,达到了实时计算,为高维信道锋电位实时分类提供了可行的解决方案。     

Performance evaluation of object detection algorithms for video surveillance

In this paper, we propose novel methods to evaluate the performance of object detection algorithms in video sequences. This procedure allows us to highlight characteristics (e.g., region splitting or merging) which are specific of the method being used. The proposed framework compares the output of the algorithm with the ground truth and measures the differences according to objective metrics. In this way it is possible to perform a fair comparison among different methods, evaluating their strengths and weaknesses and allowing the user to perform a reliable choice of the best method for a specific application. We apply this methodology to segmentation algorithms recently proposed and describe their performance. These methods were evaluated in order to assess how well they can detect moving regions in an outdoor scene in fixed-camera situations.     

蓝牙Ad hoc网络形成算法的性能评价

评价一个蓝牙Adhoc网络形成算法的优劣可以用不同方法和性能指标来衡量。文中首先介绍了蓝牙Adhoc网络的拓扑结构,然后讨论了评价蓝牙Adhoc网络形成算法的主要手段和性能指标,对目前主要的蓝牙Adhoc网络形成协议的性能进行了总结和比较。此外,还对树型散射网形成(Tree Scattemet Formation,TSF)协议的部分性能指标进行了仿真,给出了相应的性能仿真曲线。最后总结现有网络形成协议存在的问题,分析业界关注的重点及今后可能的研究方向。     

Performance evaluation of smoothing algorithms for transmittingprerecorded variable-bit-rate video

The transfer of prerecorded, compressed variable-bit-rate video requires multimedia services to support large fluctuations in bandwidth requirements on multiple time scales. Bandwidth smoothing techniques can reduce the burstiness of a variable-bit-rate stream by transmitting data at a series of fixed rates, simplifying the allocation of resources in video servers and the communication network. This paper compares the transmission schedules generated by the various smoothing algorithms, based on a collection of metrics that relate directly to the server, network, and client resources necessary for the transmission, transport, and playback of prerecorded video. Using MPEG-1 and MJPEG video data and a range of client buffer sizes, we investigate the interplay between the performance metrics and the smoothing algorithms. The results highlight the unique strengths and weaknesses of each bandwidth smoothing algorithm, as well as the characteristics of a diverse set of video clips     

Performance evaluation of some clustering algorithms and validity indices

In this article, we evaluate the performance of three clustering algorithms, hard K-Means, single linkage, and a simulated annealing (SA) based technique, in conjunction with four cluster validity indices, namely Davies-Bouldin index, Dunn's index, Calinski-Harabasz index, and a recently developed index I. Based on a relation between the index I and the Dunn's index, a lower bound of the value of the former is theoretically estimated in order to get unique hard K-partition when the data set has distinct substructures. The effectiveness of the different validity indices and clustering methods in automatically evolving the appropriate number of clusters is demonstrated experimentally for both artificial and real-life data sets with the number of clusters varying from two to ten. Once the appropriate number of clusters is determined, the SA-based clustering technique is used for proper partitioning of the data into the said number of clusters.     

Optimal filtering for spike sorting of multi-site electrode recordings

We derive an optimal linear filter, to reduce the distortions of the peak amplitudes of action potentials in extracellular multitrode recordings, which are due to background activity and overlapping spikes. This filter is being learned very efficiently from the raw recordings in an unsupervised manner and responds to the average waveform with an impulse of minimal width. The average waveform does not have to be known in advance, but is learned together with the optimal filter. The peak amplitude of a filtered waveform is a more reliable estimate for the amplitude of an action potential than the peak of the biphasic waveform and can improve the accuracy of the event detection and clustering procedures. We demonstrate a spike-sorting application, in which events are detected using the Mahalanobis distance in the N-dimensional space of filtered recordings as a distance measure, and the event amplitudes of the filtered recordings are clustered to assign events to individual units. This method is fast and robust, and we show its performance by applying it to real tetrode recordings of spontaneous activity in the visual cortex of an anaesthetized cat and to realistic artificial data derived therefrom.     

Average time behavior of distributive sorting algorithms

In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX ₁, ...,X _n drawn from a densityf onR ¹. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n ² is nonincreasing andg is independent off), the following is shown:

1. Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
2. Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .

No additional restrictions are put onf.     

Performance evaluation of artificial intelligence algorithms for virtual network embedding

Network virtualization is not only regarded as a promising technology to create an ecosystem for cloud computing applications, but also considered a promising technology for the future Internet. One of the most important issues in network virtualization is the virtual network embedding (VNE) problem, which deals with the embedding of virtual network (VN) requests in an underlying physical (substrate network) infrastructure. When both the node and link constraints are considered, the VN embedding problem is NP-hard, even in an offline situation. Some Artificial Intelligence (AI) techniques have been applied to the VNE algorithm design and displayed their abilities. This paper aims to compare the computational effectiveness and efficiency of different AI techniques for handling the cost-aware VNE problem. We first propose two kinds of VNE algorithms, based on Ant Colony Optimization and genetic algorithm. Then we carry out extensive simulations to compare the proposed VNE algorithms with the existing AI-based VNE algorithms in terms of the VN Acceptance Ratio, the long-term revenue of the service provider, and the VN embedding cost.     

A computer environment for beginners’ learning of sorting algorithms: Design and pilot evaluation

This paper presents the design, features and pilot evaluation study of a web-based environment -the SORTING environment- for the learning of sorting algorithms by secondary level education students. The design of this environment is based on modeling methodology, taking into account modern constructivist and social theories of learning while at the same time acknowledging the role of hands-on experience, the significance of students’ expressing their previous knowledge, the importance of interlinked multiple representation systems (MRS) and the role of constructive feedback on student learning. Although SORTING supports student learning of typical sorting algorithms such as Bubble-sort, Quick-sort and Selection-sort, it can also be adapted to integrate more sorting algorithms. The analysis of the data emerging from the pilot evaluation study of SORTING has shown that students used all the representation systems (RS) provided and found them attractive and easy to use. On the whole, student interactions within SORTING helped them to become aware of both the intuitive and the typical sorting procedures used, to conceptualize them, to overcome learning difficulties, to correct themselves and to make connections between different representations of the sorting algorithms used.     

Distributed sorting algorithms for multi-channel broadcast networks

A multi-channel broadcast network is a distributed computation model in which p independent processors communicate over a set of p shared broadcast channels. Computation proceeds in synchronous cycles, during each of which the processors first write and read the channels, then perform local computations. Performance is measured in terms of the number of cycles used in the computation, where each bit to be transmitted is assumed to require a separate cycle. In this paper we investigate the problem of sorting p bit strings of uniform length m, each string initially located at a different processor in the broadcast network. We develop an efficient sorting method that first reduces the length of the strings without affecting their relative order, then proceeds using only the shorter strings. A sequence of three successively improved algorithms based on this approach is presented, the best of which runs in O(m + p log p) cycles. By showing a lower bound of Ω(m) cycles, we prove that the algorithm is optimal for sufficiently large m. Our results improve by a factor of log p the solution of the multiple identification problem presented by Landau, Yung and Galil (1985).     

Parallel sorting algorithms for tightly coupled multiprocessors

We present three parallel sorting algorithms suitable for implementation on tightly coupled multiprocessors and compare their performance on the Denelcor HEP. Two of the algorithms implemented—parallel Shellsort and quickmerge—are new. Shellsort is amenable to parallelization; however, since Shellsort has higher complexity than quicksort, parallel Shellsort is inferior to parallel quicksort. A second new parallel algorithm, called quickmerge, is based upon both quicksort and mergesort. Our implementation of quickmerge achieves significantly higher speedup than occur implementation of parallel quicksort.