平方根椭球状态定界及其并行计算

提出了一种易于脉动阵列实现的平方根椭球状态定界算法。算法将椭球形状矩阵的平方根进行递推计算,使得计算的数值稳定性得以提高。由于平方根算法具有矩阵与矩阵以及矩阵与向量的运算形式,因而适合在并行处理器上执行。为了并行计算,给出了实现此平方根算法的脉动阵列结构。计算复杂性分析显示,若系统状态维数为n,串行计算的计算复杂度至少为O(n3),而并行计算的计算复杂度降为O(n)。仿真结果验证了本方法的有效性。     

标准的微粒群优化算法的收敛性分析

利用矩阵理论对具有随机数的标准微粒群优化算法进行了收敛性分析,给出了c=d=1和c=1两个收敛性结果.     

近似最优并行算法组智能汇聚构造

作为一种高性能通用并行求解器,并行算法组(parallel algorithm portfolios, PAPs)近年来在判定、计数以及连续、离散优化等问题上取得了突出的求解效果.传统人工构造PAP的方式依赖于大量领域知识,门槛极高.为了解决这一问题,本文提出了一种基于演化优化的PAP智能汇聚自动构造方法AutoPAP.整体上, AutoPAP遵循(n+1)演化优化框架,即在每一代生成n个候选算法,并保留最优算法加入到PAP中.考虑到算法配置空间往往非常巨大且涉及混合变量,本文设计了专用变异算子以提升AutoPAP的实际性能,并证明了AutoPAP在理论上可以达到(1-1/e)近似最优构造效果.最后,本文以旅行商问题(traveling salesman problems, TSP)为例,使用AutoPAP构造得到TSP＿PAP.实验结果表明,在主流TSP测试集上, TSP＿PAP的求解效率和效果均显著好于当前TSP上公认性能最佳的求解器EAX和LKH.在128个规模1000～30000的TSP测试样例上,相比于EAX和LKH, TSP＿PAP可以将平均求解时间缩短至少45.71%,并...     

一种网上求解线性方程组的Guass-Seidel并行迭代算法

针对基于PVM的微机网络并行计算环境下,处理机的运算速度较快而处理机间的通信相对较慢的实际情况,给出了一种网上并行求解线性方程组的Guass-Se idel迭代算法。该算法将方程组的增广矩阵按行卷帘方式分布存储在各处理机中,循环传送每一次的迭代向量以减少处理间的通信次数,同时,采用计算与通信部分重叠技术,提高并行算法的效率。并用1~12台桌面PC机联成的局域网,在PVM 3.4 on W indows2000,VC 6.0并行计算平台上编程对该算法进行了数值试验,试验结果表明,该算法较传统的基于列扫描法的Guass-Se idel并行迭代算法优越。     

一类交替块Crank-Nicolson方法的差分图

利用多重图概念定义了一类交替块Ｃｒａｎｋ－Ｎｉｃｏｌｓｏｎ方法的差分图,扩充了作者关于有限差分并行计算的差分图理论。     

一种基于共享存储的并行层次兴趣匹配算法

兴趣匹配在分布式仿真中扮演着重要的角色.然而,在大规模仿真场景中,仿真实体数量大且区域变化频繁,导致兴趣匹配的计算量很大,严重影响仿真性能.另一方面,多核处理器的普及也促使从并行视角来提升兴趣匹配算法的性能.针对上述问题,提出了一种并行层次兴趣匹配算法,将订阅区域映射到一棵满二叉树中,由更新区域并行地与二叉树进行匹配,...     

基于TBB的并行Canny算法

在诸多图像边缘检测的算法中,Canny算法具有边缘检测性能良好、不易受噪声的影响、可以在噪声和边缘检测间获得很好的平衡等优点,不足之处是计算量大、实时性差。针对Canny算法存在的计算量大和实时性差等问题,提出了一种并行实现策略,即基于Threading Building Block(TBB)工具和C++语言的并行Canny算法,可以有效的缓解上述问题。通过串、并行算法执行时间的比较,证明了并行算法的优越性。     

基于视频的车辆速度自测量

在现代智能交通系统中,车辆速度是一个基本参量,如何快速精确地测量出车辆速度已经成为当今的一个研究重点。车辆速度的测量分为主动式和被动式测量,利用基于纹理的模板匹配算法,提出了一种基于视频的主动式测量车辆自身速度的方法,并利用DSP技术实现了实时测量。     

基于动态规划的序列比对的并行算法研究

针对序列比对算法进行了深入地研究,分析比较了两序列和多序列、局部和全局、渐进和迭代的序列比对算法.利用动态规划序列比对算法内在的并行性,提出了自适应的动态规划序列比对的并行策略.该策略在计算初期和计算末期采用较小的高度和宽度值使得大部分处理器参与计算,在计算中期采用较大的高度和宽度值降低处理器间的通信开销;运用上述自适应的动态规划序列比对的并行策略,提出了一种基于动态规划的序列比对的并行算法,将读入的比对序列负载均衡地分布至不同的计算结点.基于集群系统和MPI环境的实验数据及分析表明,该算法在给定进程数量的条件下,其执行时间随序列长度的增长而急剧上升;在给定序列长度的条件下,其执行时间随并行进程数量的增大而大幅减小;充分反映出该算法较好地发挥了序列比对问题的内在并行性,有效地降低了序列比对算法的时间复杂度.     

矩阵乘在通用DSP上的峰值性能模型

DSP具有能效比高的特点,可以用于通用高性能计算.矩阵乘是许多科学与计算问题的核心算法,在DSP上取得高性能具有重要的理论和现实意义.面向通用DSP,提出了矩阵乘并行算法,建立了矩阵乘峰值性能模型,根据性能模型,构建了矩阵乘性能达Tflops级DSP体系结构参数配置,对通用DSP的设计参数给出了明确的性能指标要求,包括乘加流水线数量、寄存器数目、带宽和延迟.