K元2—立方体网络SIMD计算机图像模板匹配并行算法

模板匹配是进行虑波、边缘检测、目标识别和图像匹配的一种基本和有效的方法 .对于 N× N的图像和M× N ( M相似文献   

多核计算机上非递归并行计算矩阵乘积

提出延迟隐藏的数据预取模型,实现计算与访存的重叠操作,以达到共享二级缓存零缺失;给出基本块的概念,以简化算法的数据结构和减少存储开销;按基本块连续存储方式存储矩阵元素,从存储层次上优化算法,显著地减少页表缓冲缺失;采取非递归调度基本块的策略,充分利用多核计算机的共享二级缓存来减少访问主存的次数,并且不局限于某种特定的存储结构,实现算法缓存无关.多核计算机上的实验结果表明,给出的非递归计算矩阵乘积的线程级并行算法高效、可扩展.     

基于动态数据分布的并行Shear-Warp体绘制算法

提出了基于动态数据分布的并行Ｓｈｅａｒ－Ｗａｒｐ体绘制算法和新的动态数据分布策略,利用空闲的广播通信线路使数据重分布与绘制并行进行,提高了通信线路的利用率、避免了冗余存储,减少了资源浪费,并避免了对算法效率的影响;改进的任务分配与负载平衡策略,避免了节点机负载的不平衡和流水线作业的积压,提高了算法的效率。     

基于稀疏矩阵的并行体绘制算法

直接体绘制是三维数据可视化的重要方法。在实际应用中体数据规模庞大,如何降低计算工作量以获得更高的绘制速度是一个亟待解决的问题。文章针对该问题提出了一种运行于集群系统之上的基于稀疏矩阵的并行Splatting体绘制算法,该算法利用稀疏矩阵对体数据结构进行优化,通过实验获得了令人满意的结果。     

蔓叶线的一种并行生成算法

主要研究了著名的几何曲线——蔓叶线的一种并行生成算法,以Bresenham算法为基础,对蔓叶线的并行生成算法进行了分析和讨论。首先,从蔓叶线图像的一个已知点开始,根据递推公式逐点选择最靠近蔓叶线的像素点;然后引入并行机制生成蔓叶线的图像;最后,利用C#多线程模拟实现了该算法。模拟结果表明,这是关于蔓叶线图像的一种快速、高效的并行算法。     

一种基于投影树的并行序列挖掘算法

在许多科学和商业领域,序列模式的发现技术发挥着越来越重要的作用,然而人们对于高效的基于投影树算法的并行模式关注较少。该文首先介绍了频繁序列挖掘模式的基本概念,然后基于投影树算法,提出了分布式存储并行序列挖掘算法,并对算法的性能进行了详细的分析。     

一种基于PVM的矩阵相乘并行算法

研究了一种运行于PVM并行计算平台的矩阵相乘的并行算法。在工作站数量不为某个数的平方数时,Cannon算法在PVM环境下不能充分地利用机群系统中的资源。根据PVM并行编程环境中任务间通信的特点,文中设计了一种基于PVM的矩阵相乘并行算法,该算法根据工作站数量来确定子任务的数量,并对矩阵A进行分块,每个子任务可以计算一个分块。实验表明,该算法提高了机群并行环境中资源的利用率,提高了程序的运行效率。     

Scalable Parallel Matrix Multiplication on Distributed Memory Parallel Computers

Consider any known sequential algorithm for matrix multiplication over an arbitrary ring with time complexity O(N^α), where 2<α3. We show that such an algorithm can be parallelized on a distributed memory parallel computer (DMPC) in O(log N) time by using N^α/log N processors. Such a parallel computation is cost optimal and matches the performance of PRAM. Furthermore, our parallelization on a DMPC can be made fully scalable, that is, for all 1pN^α/log N, multiplying two N×N matrices can be performed by a DMPC with p processors in O(N^α/p) time, i.e., linear speedup and cost optimality can be achieved in the range [1..N^α/log N]. This unifies all known algorithms for matrix multiplication on DMPC, standard or non- standard, sequential or parallel. Extensions of our methods and results to other parallel systems are also presented. For instance, for all 1p N^α /log N, multiplying two N×N matrices can be performed by p processors connected by a hypercubic network in O(N^α/p+(N²/p^2/α)(log p)^2(α−1)/α) time, which implies that if p=O(N^α/(log N)^{2(α−1)/(α−2)}), linear speedup can be achieved. Such a parallelization is highly scalable. The above claims result in significant progress in scalable parallel matrix multiplication (as well as solving many other important problems) on distributed memory systems, both theoretically and practically.     

基于并行Benchmark的高性能机实用测试与评价方法

文中分析了传统基于并行基准测试程序测试方法的不足,针对目前高性能计算机处理机台数多的特点,给出了实用的测试方法,推广了传统加速比的概念,提出了一种可扩展性评价方法。使用文中给出的方法,可方便地对高性能计算机进行测试和性能评价,同时可以使用小规模的并行机测试结果预测大规模并行机的性能。最后给出了NPB在某高
性能计算机上的测试和性能评价结果。     

基于BLACS的2.5D并行矩阵乘法

并行矩阵乘法是线性代数中最重要的基本运算之一,同时也是许多科学应用的基石.随着高性能计算(HPC)向E级计算发展,并行矩阵乘法的通信开销所占比重越来越大.如何降低并行矩阵乘法的通信开销,提高并行矩阵乘的可扩展性是当前研究的热点之一.本文提出一种新型的分布式并行稠密矩阵乘算法,即2.5D版本的PUMMA(Parallel...     

并行计算稀疏矩阵乘以向量的负载平衡算法

稀疏矩阵乘以一个向量（SpM×V）的问题是许多大型应用问题的核心计算问题,文中提出了一种在并行计算机上并行计算SpMXV的负载平衡算法,计算复杂性为O（N）（N为稀疏矩阵的阶）,而目前计算此类问题的最优负载平衡算法的计算复杂性为O（N·P）（P为处理机台数）。文章最后给出了并行数值实验。     

基于复小波变换的遥感图像并行融合算法

随着遥感技术的快速发展,多源遥感图像的快速融合成为很多遥感任务的关键处理步骤。为了加速遥感图像的融合处理过程,本文首先提出了一种新的基于双树复小波变换的并行融合算法（PACWT）。算法中综合运用了数据分布、并行数据处理和负载均衡技术,以克服单机处理在计算能力和存储器空间上的限制;针对基于CWT的图像融合处理的计
计算特点,设计了一种可有效避免计算过程中数据通信的冗余划分方法。然后,从理论上分析了算法在时间和空间两方面的性能。最后,通过实验分析了算法在32-CPU的Cluster系统上的实际性能。结果表明,本文提出的算法具有良好的可扩展性,在数据量较大时可获得良好的加速比和并行效率。     

基于直径为2的摩尔图网络的并行矩阵乘算法

提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.     

求解大规模矩阵特征问题的并行算法研究

基于数据并行的重启动Arnoldi并行算法,基于使用数据并行模型的重启动Arnoldi并行算法,提出一个精化重启动Arnoldi并行算法。为了降低弱扩展性对并行性能的负面影响,该算法使用任务图模型并行计算精化向量,减少处理器进程之间的通信次数,有效地实现并行计算。在KD-50-I万亿次机上的测试结果表明,该算法具有较好的可扩展性和并行 效率。     

可重构造网孔机器上k-近邻并行算法

最近邻问题是计算几何学中的基本问题之一 ,k 近邻是最近邻的扩展 ,它在VLSI设计、数据库检索、模式匹配以及图像处理等领域有着广泛的应用背景 对于点数为N的平面点集S ,在规模为N×N的可重构造网孔机器上 ,提出了时间复杂度为O(k)的求S中所有点k 近邻的并行算法 该算法的时间复杂度已达到了该问题本身固有时间复杂度的下界     

一种非规则数据场的体绘制算法

非规则数据场的体绘制是可视化的一个热点和难点。常用直接体绘制算法有光线投射法、单元投影法、快速体绘制算法。本文吸取了上述三种算法的优点,采用体元面投影的方法来确定光线路径;同时考虑到非规则数据场的一些特性,采取三个有效的措施大大加快了投影和求交速度;在采样中用分段积分法代替等距采样,从而进一步提高了图象质量。     

基于加权矩阵的多维广义特征值并行分解算法

针对串行广义特征值分解算法实时性差的缺点, 提出基于加权矩阵的多维广义特征值分解算法. 与串行算法不同, 所提算法能够在一次迭代过程中并行地估计出多维广义特征向量. 平稳点分析表明: 当且仅当算法中状态矩阵等于所需的广义特征向量时, 算法达到收敛状态. 通过对比相邻时刻的状态矩阵模值证明了所提算法的自稳定特性. 所提算法参数选取简单, 实际实施较为容易. 数值仿真和实例应用进一步验证了算法的并行性、自稳定性和实用性.     

Parallel Mesh Algorithms for Grid Graph Shortest Paths with Application to Separation of Touching Chromosomes

The grid graph shortest path problem has many applications. In this paper, we present practical mesh algorithms using a local cost-reducing operation for various forms of the grid graph shortest path problem. The algorithms are very simple and can easily mark the vertices on shortest paths between any two vertices. The time complexity of the algorithm is proportional to the maximum length of the shortest paths with a very small multiplicative constant. Also in this paper, we discuss the application of the parallel algorithms in automatic chromosome analysis to intelligently split touching chromosomes. We identify local features useful for finding a potential path to separate touching chromosomes. We then define a distance measure based on the local features and find the best splitting path to cut touching chromosomes. The splitting algorithm only uses local information and is highly parallel.     

从大型体数据集中生成等值面的并行算法

从体数据集中生成等值面是体可视化的主要技术之一。当体数据集的数据量很大时，计算量也随之增大，单处理机的存储与计算能力难以胜任其可视化要求，基于并行与分布式计算环境设计并行可视化算法是有效的办法。本文基于工作站群机系统的ＰＶＭ环境，设计并实现了一种有效的、从大型体数据集中生成等值面的并行算法。     

基于国产YH系列并行机的并行算法设计分析与实现

基于国产 YH 并行机的并行算法的设计分析 ,实现程序高效并行。采用宏任务的并行方式 ,实现子程序级的并行 ,其并行粒度大 ,总的开销小 ,并行效果好。