非规则流中高维数据流典型相关性分析并行计算方法

为了满足在计算资源受限的环境下高维数据流处理的实时性要求,提出一种方法——基于GPU(graphic processing unit)的非规则流中高维数据流的处理模型和具体的可行架构,并分析设计了相关的并行算法.该六层模型是将GPU处理数据的高宽带性能结合进滑动窗口中数据流的分析,进而在该框架下基于统一计算设备架构(compute unified device architecture,简称CUDA),使用数据立方模型以及降维约简技术并行分析了多条高维数据流的典型相关性.理论分析和实验结果均表明,该并行处理方法能够在线精确地识别同步滑动窗口模式下高维数据流之间的相关性.相对于纯CPU方法,该方法具有显著的速度优势,很好地满足了高维数据流的实时性需求,可以作为通用的分析方法广泛应用于数据流挖掘领域.     

非规则流中高维数据流典型相关性分析并行计算方法?

为了满足在计算资源受限的环境下高维数据流处理的实时性要求,提出一种方法——基于 GPU(graphic processing unit)的非规则流中高维数据流的处理模型和具体的可行架构,并分析设计了相关的并行算法。该六层模型是将 GPU 处理数据的高宽带性能结合进滑动窗口中数据流的分析,进而在该框架下基于统一计算设备架构(compute unified device architecture,简称CUDA),使用数据立方模型以及降维约简技术并行分析了多条高维数据流的典型相关性。理论分析和实验结果均表明,该并行处理方法能够在线精确地识别同步滑动窗口模式下高维数据流之间的相关性。相对于纯 CPU 方法,该方法具有显著的速度优势,很好地满足了高维数据流的实时性需求,可以作为通用的分析方法广泛应用于数据流挖掘领域。     

测量误差协方差矩阵的鲁棒估计

由于经典的误差协方差阵间接估计方法对于过失误差存在非常敏感,本文提出了一种基于Hampel三截尾估计的间接估计方法,在无过失误差和存在过失误差的情况下都能给出测量误差协方差矩阵可靠的估计,两个仿真实例表明了算法的鲁棒性。     

海量高维向量的并行Top-k连接查询

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.     

Horizons of Parallel Computation

This paper considers the ultimate impact of fundamental physical limitations-notably, speed of light and device size-on parallel computing machines. Although we fully expect an innovative and very gradual evolution to the limiting situation, we take here the provocative view of exploring the consequences of the accomplished attainment of the physical bounds. The main result is that scalability holds only for neighborly interconnections, such as the square mesh, of bounded-size synchronous modules, presumably of the area-universal type. We also discuss the ultimate infeasibility of latency hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs.     

并行计算模型

1.引言为提高系统性能,并行机系统设计者在体系结构上采用了多种新技术,然而目前并行软件(包括系统软件和应用软件)的研究和开发远远落后于体系结构的进步,即体系结构上的进步并未充分反映到并行软件的设计中。相比之下,串行计算和串行软件的研究是成功的,原因之一在于有一个简单而又代表了串行计算主要性能特征的计算模型(Random Ac-cess Machines,RAM)。而并行计算缺少这样一个简单、被广泛接受并在并行计算中起同等重要作用的模型。“确定少量的并行计算模型以作为程序设计语言的自然基础,并有助于高性能硬件的实现”,这一课题仍是国际公认的并行处理中具挑战性课题之一。     

Robust Optic Flow Computation

This paper formulates the optic flow problem as a set of over-determined simultaneous linear equations. It then introduces and studies two new robust optic flow methods. The first technique is based on using the Least Median of Squares (LMedS) to detect the outliers. Then, the inlier group is solved using the least square technique. The second method employs a new robust statistical method named the Least Median of Squares Orthogonal Distances (LMSOD) to identify the outliers and then uses total least squares to solve the optic flow problem. The performance of both methods are studied by experiments on synthetic and real image sequences. These methods outperform other published methods both in accuracy and robustness.     

Parallel Position Weight Matrices algorithms

Position Weight Matrices (PWMs) are broadly used in computational biology. The basic problems, Scan and MultipleScan, aim to find all the occurrences of a given PWM or a set of PWMs in long sequences. Some other PWM tasks share a common NP-hard subproblem, ScoreDistribution. The existing algorithms rely on the enumeration on a large set of scores or words, and they are mostly not suitable for parallelization. We propose a new algorithm, BucketScoreDistribution, that is both very efficient and suitable for parallelization. We bound the error induced by this algorithm. We realized a GPU prototype for Scan, MultipleScan and BucketScoreDistribution with the CUDA libraries, and report for the different problems speedups larger than 10× on several Nvidia cards.     

面向高维大数据的局部离群点并行检测算法

当前局部离群点并行检测算法在实现时,没有消除局部离群点中存在的冗余数据,存在k值不稳定、局部可达密度低、检测时间长的问题,严重影响数据的正常使用,于是提出面向高维大数据的局部离群点并行检测算法。根据信息熵原理采用E-PCA算法提取高维大数据的特征,并消除冗余特征,实现高维大数据的降维处理,提高算法的检测精度;为了在较短的时间内完成局部离群点的并行检测,结合Hadoop分布式平台中的Mapreduce分布框架和传统的离群点检测算法,在高维大数据中完成局部离群点的并行检测。仿真结果表明,所提算法的k值适中、局部可达密度高和检测时间短。     

Fast Computation of the Bezout and Dixon Resultant Matrices

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon–Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas requireO (n³) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses onlyO (n²) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas requireO (m⁴n⁴) additions and multiplications to calculate all the entries of the Dixon–Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses onlyO (m²n³) additions and multiplications.     

Krylov子空间方法及其并行计算

Krylov子空间方法在提高大型科学和工程计算效率上起着重要作用。本文阐述了Krylov子空间方．法产生的背景、Krylov子空间方法的分类,在此基础上,研完了分布式并行计算环境下Krylov子空间方法的并行计算方法,给出了Krylov子空间方法的并行化策略。     

Robust Latent Factor Analysis for Precise Representation of High-Dimensional and Sparse Data

High-dimensional and sparse(HiDS)matrices commonly arise in various industrial applications,e.g.,recommender systems(RSs),social networks,and wireless sensor networks.Since they contain rich information,how to accurately represent them is of great significance.A latent factor(LF)model is one of the most popular and successful ways to address this issue.Current LF models mostly adopt L2-norm-oriented Loss to represent an HiDS matrix,i.e.,they sum the errors between observed data and predicted ones with L2-norm.Yet L2-norm is sensitive to outlier data.Unfortunately,outlier data usually exist in such matrices.For example,an HiDS matrix from RSs commonly contains many outlier ratings due to some heedless/malicious users.To address this issue,this work proposes a smooth L1-norm-oriented latent factor(SL-LF)model.Its main idea is to adopt smooth L1-norm rather than L2-norm to form its Loss,making it have both strong robustness and high accuracy in predicting the missing data of an HiDS matrix.Experimental results on eight HiDS matrices generated by industrial applications verify that the proposed SL-LF model not only is robust to the outlier data but also has significantly higher prediction accuracy than state-of-the-art models when they are used to predict the missing data of HiDS matrices.     

多核计算机上的并行计算

研究了多核计算机上0penMP＋Vc＋＋编程模式的并行程序,并在双核和四核计算机上分别使用传统算法和并行算法计算数列求和、矩阵乘积及矩阵Cholesky分解。试验表明,传统串行程序只能利用多核计算机的一个核资源,而采用OpenMP程序的并行效率很高。     

并行计算模型对比分析

随着集群式系统的发展,并行计算模型在估计和评价系统的性能、引导集群的体系结构以及指导并行算法和程序的设计等方面都显得越来越重要。对于目前已有的并行计算模型的设计思想和原理的了解和分析,非常有利于新的模型的设计与研究。本文首先介绍了目前比较常见的5种并行计算模型,接着在同步性、通信方式和参数等3个方面分析比较了它们的异同和优缺点,最后得出结论,指出了下一代并行计算模型的发展趋势是与具体应用相关的并行计算模型。     

Robust Input Covariance Constraint Control for Uncertain Polytopic Systems

In this paper, the robust input covariance constraint (ICC) control problem with polytopic uncertainty is solved using convex optimization with linear matrix inequality (LMI) approach. The ICC control problem is an optimal control problem that optimizes the output performance subjected to multiple constraints on the input covariance matrices. This control problem has significant practical implications when hard constraints need to be satisfied on control actuators. The contribution of this paper is the characterization of the control synthesis LMIs used to solve the robust ICC control problem for polytopic uncertain systems. Both continuous‐ and discrete‐time systems are considered. Parameter‐dependent and independent Lyapunov functions have been used for robust ICC controller synthesis. Numerical design examples are presented to illustrate the effectiveness of the proposed approach.     

Parallel Biomolecular Computation: Models and Simulations

This paper is concerned with the development of techniques for massively parallel computation at the molecular scale, which we refer to as molecular parallelism. While this may at first appear to be purely science fiction, Adleman [Ad1] has already employed molecular parallelism in the solution of the Hamiltonian path problem, and successfully tested his techniques in a lab experiment on DNA for a small graph. Lipton [L] showed that finding the satisfying inputs to a Boolean expression of size n can be done in O(n) lab steps using DNA of length O(n log n) base pairs. This recent work by Adleman and Lipton in molecular parallelism considered only the solution of NP search problems, and provided no way of quickly executing lengthy computations by purely molecular means; the number of lab steps depended linearly on the size of the simulated expression. See [Re3] for further recent work on molecular parallelism and see [Re4] for an extensive survey of molecular parallelism. Our goal is to execute lengthy computations quickly by the use of molecular parallelism. We wish to execute these biomolecular computations using short DNA strands by more or less conventional biotechnology engineering techniques within a small number of lab steps. This paper describes techniques for achieving this goal, in the context of well defined abstract models of biomolecular computation. Although our results are of theoretical consequence only, due to the large amount of molecular parallelism (i.e., large test tube volume) required , we believe that our theoretical models and results may be a basis for more practical later work, just as was done in the area of parallel computing. We propose two abstract models of biomolecular computation. The first, the Parallel Associative Memory (PAM) model, is a very high-level model which includes a Parallel Associative Matching (PA-Match) operation, that appears to improve the power of molecular parallelism beyond the operations previously considered by Lipton [L]. We give some simulations of conventional sequential and parallel computational models by our PAM model. Each of the simulations use strings of length O(s) over an alphabet of size O(s) (which correspond to DNA of length O(s log s) base pairs). Using O(s log s) PAM operations that are not PA-Match (or O(s) operations assuming a ligation operation) and t PA-Match operations, we can: 1. simulate a nondeterministic Turing Machine computation with space bound s and time bound 2 ^O(s) , with t = O(s) , 2. simulate a CREW PRAM with time bound D, with M memory cells, and processor bound P, where here s = O( log (PM)) and t = O(D+s), 3. find the satisfying inputs to a Boolean circuit constructible in s space with n inputs, unbounded fan-out, and depth D, where here t = O(D+s). We also propose a Recombinant DNA (RDNA) model which is a low-level model that allows operations that are abstractions of very well understood recombinant DNA operations and provides a representation, which we call the complex , for the relevant structural properties of DNA. The PA-Match operation for lengthy strings of length s cannot be feasibly implemented by recombinant DNA techniques directly by a single step of complementary pairing in DNA; nevertheless we show this Matching operation can be simulated in the RDNA model with O(s) slowdown by multiple steps of complementary pairing of substrings of length 2 (corresponding to logarithmic length DNA subsequences). Each of the other operations of the PAM model can be executed in our RDNA model, without slowdown. We further show that, with a further O(s)/ log (1/ε) slowdown, the simulations can be done correctly with probability 1/2 even if certain recombinant DNA operations (e.g., Separation) can error with a probability ε. We also observe efficient simulations can be done by PRAMs and thus Turing Machines of our molecular models. Received December 30, 1995; revised December 30, 1996, and January 22, 1998.     

On the Computation of Elementary Divisors of Integer Matrices

We describe a “semi-modular" algorithm which computes for a given integer matrix A of known rank and a given prime p the multiplicities of p in the factorizations of the elementary divisors ofA . Here “semi-modular" means that we apply operations to the integer matrix A but the operations are driven by considering only reductions of row vectors modulo p.     

基于鲁棒协方差矩阵估计的盲信道识别方法

为了提高基于二阶协方差矩阵的盲信道识别方法在脉冲噪声环境下的性能,以α稳定分布过程为脉冲噪声模型,利用m-估计的方法得到该脉冲噪声信道下接收信号协方差矩阵的鲁棒估计,再利用噪声子空间的方法实现信道的盲识别.仿真结果表明,该方法在脉冲噪声环境下的性能要明显优于传统的基于二阶统计协方差矩阵的盲信道识别方法的性能.     

改进协方差矩阵的智能车视觉目标跟踪方法

智能车辆视觉目标具有非线性、噪声分布非高斯性的典型特点，现有算法难以实时估计目标的状态。针对识别物体复杂且多变，很难用完全的特征来描述待识别目标及其背景的不断变化，提出了一种用于融合颜色特征及SURF（Speed-Up Robust Features）特征的协方差矩阵来改进粒子滤波算法，从而提升视觉目标跟踪的实时性，满足智能车辆的要求。首先，对采集的图像进行预处理来获取感兴趣区域。接着，通过融合颜色特征及SURF特征构造范围感兴趣区域（Region Of Interest，ROI）的目标特征协方差矩阵，建立目标状态预测模型及状态观测模型，用于改进粒子滤波算法粒子重采样过程，实现对目标的精确跟踪。最后，将该方法与Mean-shift算法和颜色属性（CN）算法进行对比。实验结果表明，在智能车视觉跟踪过程中对光环境瞬时变化、目标物体存在短时遮挡以及目标物体姿态改变时，该算法在满足智能车辆对实时性要求的前提下，有效提升算法的精确度及鲁棒性。