矩阵求逆算法在Cell上的并行

本文分析和介绍了如何在Cell上实现矩阵求逆的并行算法,从而提高矩阵求逆的运算速度,提到的矩阵求逆并行算法对于其他的多核并行处理器具有通用性。     

一种新的概念格并行构造算法

概念格作为形式概念分析理论中的核心数据结构,在数据挖掘和知识发现、人工智能、信息检索、粗糙集[1]等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。提出了一种基于闭包系统划分的概念格并行构造算法——Para_Prun算法,它将概念集合看作初始闭包系统,引入了子闭包系统的有效性判断,迭代生成相互独立的多个子闭包系统,然后在每个子闭包系统中独立生成概念,有效地提高了概念的求解速度。最后用实验证明了算法的正确性和有效性。     

Ramsey数R（3,28）新下界的并行计算*

寻找有效的参数集,构造素数阶循环图,用并行算法获得二色Ramsey数R（3,q）的新下界:R（3,28）≥164。     

四正则图的纵横嵌入优化并行算法*

纵横嵌入术已为超大规模集成电路（VLSI）的平面设计提供了较完备的理论体系,在EREW PRAM(ExclusiveRread and ExclusiveWrite Parallel Random Access Machine)并行计算模型上,使用O((m+n)/ logn)个处理器,时间复杂度为O(logn),对四正则图的纵横嵌入图优化,使图中边的总折数达到最少且所占面积最小。     

混合SPMD模拟退火算法及其应用

模拟退火算法由于有很好的数学特性－以概率1收敛于全局最优值,再加上其算法本身与特定的问题无关,因此被广泛地用于各种组合优化问题。但是,模拟退火算法又具有收敛速度慢,执行时间长,算法性能与初始值有关及参数敏感等特点,使得它在不少应用中成为一种低效甚至是不可行的算法。文中提出一种混合SPMD模拟退火算法,在克服经典模拟退火算法内在串行性的同时,进一步和下山法结合起来,并综合多种优化方法,在一定的处理机规模内取得了可扩展和并行效果,显著提高了算法的收敛速度,克服了算法性能对初始值和参数选择的过分依赖,在提高算法性能的同时,方便了算法的使用。该算法已在一个机群系统THNPSC－1上得以实现,并在材料科学的一个定量电子晶体学研究问题中得到应用,降低了该问题的求解时间,提高了求解质量。     

一类Toeplitz三对角方程组的一种分布式并行算法

文中提出一类Toeplitz三对角方程组的一种分布式并行算法。该算法以系数矩阵的分解为基础,充分利用了系数矩阵结构的特殊性,算法因并行化而引入的冗余计算量非常少,算法的通信机制简单,通信量仅与处理 机台数p有关,与方程组规模n无关,算法具有很高的并行效率,理论分析和数值试验表明,其加速比Sp(n)→p(n→ ∞）,此为线性加速比的理想情况。文中给出了算法在分布存储多计算机系统上的数值试验结果。     

起节点上并行算法设计策略的研究

本文分析了超节点这一新型体系结构上的算法设计方法,并具体讨论了超节点上的数据分配和任务划分,最后举出一个实例－－高斯消去法的分块算法,提出了如何在现有共享算法和分布算法的基础上,开发超节点上的并行算法。     

网格结构上图象小波变换的并行算法

为提高大图象小波变换的速度,本文设计了一种网格结构上图象小波变换的并行算法,其特点是负载平衡,且通信只在少数几个处理机间进行,通信量小,因而算法效率高。     

不同数据分配方式下并行系统的可扩展性

本文以高斯消去法为例,从理论和实验上给出了一般可扩展性分析步骤,分析了不同数据分配策略对并行算法和机器组合体可扩展性的影响。这对算法可扩展性分析的推广是很有意义的。     

多线程的多特征粒子滤波跟踪并行算法

多特征粒子滤波较传统粒子滤波跟踪精度高,其运算量大,跟踪实时性差．文中结合多特征粒子滤波的算法特点,提出了基于多线程的多特征并行模型,在算法实施上采用多线程与多特征进行匹配,并分析了该模型的并行效率以及各特征间通讯机制的协调性．实验结果表明：该并行算法提高了多特征粒子滤波两倍以上的效率．