并行无存储冲突的邻接矩阵算法

邻接矩阵算法在科学计算与信息处理方面有着极为重要的应用,是图论的基础研究之一。针对目前邻接矩阵算法多是基于串行,或并行SIMD模型而无法解决存储冲突的问题,提出一种基于SIMD-EREW共享存储模型的并行邻接矩阵算法。算法使用O(p)个并行处理单元,在O(n2/p)的时间内完成对n个数据点邻接矩阵的计算。将提出算法与现有算法进行的性能对比分析表明:本算法明显改进了现有文献的研究结果,是一种并行无存储冲突的邻接矩阵算法。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

无存储器中冲突的并行快速排序算法

本文在一个ＥＲＥＷ ＰＲＡＭｅｘｃｌｕｓｉｖｅ ｒｅａｄ ｅｘｃｌｕｓｉｖｅ ｗｒｉｔｅ ｐａｒａｌｌｅｄ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍａｃｈｉｎｅ）上提出一个并行快速排序算法，这个算法用Ｋ个处理器可将Ｎ个项目在平均Ｏ（ｎ／ｋ＋ｌｏｇｎ）ｌｏｇｎ）时间内排序，所以平均来说算法的时间和处理器数量的乘积对任何ｋ≤ｎ／ｌｏｇｎ是Ｏ（ｎｌｏｇｎ）。     

基于邻接矩阵存储结构的二元关系的自反闭包运算

关系的应用非常广泛.在数学领域对关系的研究主要集中在关系的性质上,很少有人研究关系的存储结构和算法.本文主要论述了二元关系的邻接矩阵存储结构和在此结构之上的关系的创建和自反闭包运算.并利用C语言实现了该算法.最后分析了算法的复杂性.     

面向多兴趣区域图像处理应用的高效无冲突并行访问存储模型

针对不规则数据访问模式图像处理应用提出了一种通用的高效无冲突并行访问存储模型.在主存储器与处理器之间构建了一种多体存储结构,并将大部分的不规则数据访问模式归类为对图像中多个局部矩形兴趣区域内的任意位置固定大小矩形数据块的无冲突并行访问.为了提高访问效率,只将兴趣区域内的数据缓存在多体存储器中,且不同兴趣区域的重叠数据可以重用.多体存储器的寻址机制是基于提出的地址映射表结构进行动态寻址,而不是采用传统的固定寻址函数,既保证了对任意数据读写操作的编址一致性,又提高了数据重用性.每处理一个新兴趣区域就对地址映射表内容进行一次更新,提出的双表结构与数据块动态调度机制保证了更新过程与计算过程的并行执行.基于提出的存储模型构建了硬件体系结构,并在FPGA上实现,测试结果表明,与直接访问主存储器相比在访存速度上提高了几倍到上百倍.     

无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

基于邻接矩阵的FP-tree构造算法

提出了一种基于邻接矩阵的FP-tree构造方法。首先通过扫描数据库建立2-项集支持数的邻接矩阵,通过邻接矩阵对项进行过滤和新方式排序,然后再利用邻接矩阵构造FP-tree,使得FP-tree的分支、节点数和深度大幅度地减少,从而使存储空间减少、遍历时间缩短。最后使用标准数据集进行验证测试并和其他算法的比较,实验结果表明,该算法在保证结果的同时有效地提高频繁项集挖掘的效率。     

并行无冲突存储器的存储模式

本文着重讨论在怎样的存储模式下,并行存储器能最有效地实现二维方阵的无冲突访问,且使调整网络NW_1和NW_2较易实现;同时对任意阶方阵的存储模式进行了研究,给出一个重要的构造定理;最后利用4阶方阵构造一个由16个存储体组成,能实现并行无冲突访问的存储模式及调整网络,使其没有存储单元冗余、实现方便等优点。     

并行存储反应调度算法研究

文章提出了一种并行存储反应调度算法,它是基于存储访问建模的和基于规则的存储自动优化算法。这种算法使用E_IS_PPM和Last_N_Successor算法对存储访问建模,然后对存储访问模式进行分类,并确立了存储优化的规则集。最后,在MPI基础上实现了调度算法。     

由邻接矩阵求解可达矩阵的一种改进简便算法

传统的由邻接矩阵求解可达矩阵的算法计算量很大，不适合手动计算，也没有提出相应的适合计算机的算法。这篇文章引入转移矩阵的概念．并在此基础上加以改进，形成一套完整的可行的求解可迭矩阵的方法。有效地减少了计算量。     

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

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.     

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

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

Parallel Complexity of Matrix Multiplication1

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm; namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)–(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided.     

一般稀疏矩阵相乘的混合并行算法

稀疏矩阵相乘广泛应用于科学和工程计算中,是科学计算中的一种常用的基本运算,其面临着数据量大,非零值分布不规则,负载难均衡,计算结果矩阵的列指数无规则分布等问题.通过矩阵分块,优化数据传输,负载均衡,改良并行快速排序方法来解决上述问题,提高了计算效率.在多线程下计算速度比商业软件Intel MKL(Intel math kernel library)平均提高56％.同时,还通过MPI+OpenMP进行混合并行优化,在共享存储系统上两者有类似的计算速度.     

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

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

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

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

基于Ray-casting算法的并行存储系统

Ray—casting算法是一种高质量的直接体绘制算法,但绘制速度过慢,因此设计基于Ray—casting算法的硬件专用体系结构已成为研究的热点。而存储系统又是制约整个体系结构的瓶颈部件,其性能的优劣直接影响整个系统的运行速度。该文针对直接体绘制中的Ray—casting算法设计了无访存冲突的八体低位交叉并行存储系统VOXMEM提高吞吐率,并提出相应的体素存储分配策略和地址计算方法。该并行存储系统采用基于页模式的SDRAM实现,并通过仿真实验获得了令人满意的结果。