解决矩阵链相乘处理器调度问题的一种新算法

本文介绍了矩阵链相乘处理器分配问题和离散处理器分配算法,描述了Lee Heejo等人提出的解决MCSP的处理器分配算法,提出了一种解决MCSP的时间复杂度更低的算法,使处理器能尽量被充分利用,并对三种分配算法进行了比较分析.     

并行矩阵乘的B迁移算法

本文回顾了分布式系统上的广播－移位矩阵乘算法（Ｂ－Ｓ算法）［２］和Ｃ迁移算法［５］，给出我们提出的迁移算法。Ｂ迁移算法有效地减少了通信量，在工作站机群上的应用取得了较好的结果。对比Ｂ－Ｓ算法性能提高可达到６０％，对比Ｃ迁移算法，性能提高可达到１４０％。     

基于监督学习的稀疏矩阵自动任务分配

针对稀疏矩阵与稠密向量乘运算探讨了不同的任务分配策略对性能的影响,观察到任务分配策略的选择会显著地影响稀疏矩阵的运算性能,且不存在一种固定的任务分配策略针对所有的稀疏矩阵都能获得最佳性能。为此,提出了一种基于机器学习的最优任务分配策略选择模型,其训练过程仅使用稀疏矩阵的特征来刻画输入数据集,且能够针对给定的数据集和目标平台自动地训练模型。实验结果表明,相对于默认的块分配方法,使用该模型选择的任务分配方式能够获得平均约35%的性能提升。     

一种基于Biswapped网络的并行矩阵乘算法

为了解决矩阵乘算法并行化的问题,根据Biswapped网络结构的特点,提出了一种基于Biswapped网络结构的矩阵乘并行算法.该算法采用一种新的矩阵映射方式,该算法操作简单且容易实现.理论分析和实验表明:该算法近似等效于Cannon算法.     

基于OpenMP的Winograd并行矩阵乘算法应用研究

为了提高半经典分子动力学模拟中矩阵乘法效率,通过一种稀疏矩阵分解方法化简矩阵乘法,基于OpenMP实现矩阵相乘的Winograd并行算法。该算法将Winograd算法中各部分依次采用OpenMP并行计算,降低了数据通信。在16核服务器上测试表明,该方法能够显著提高半经典分子动力学模拟中矩阵乘法效率,并行加速比能够达到9.47,并具有良好的可扩展性,为大分子体系的模拟提供了可能。     

非负矩阵分解的分层最小二乘快速算法研究

非负矩阵分解是对于代价函数近似非线性优化问题,考虑均方误差值作为代价函数,通过对分层交替非负最小二乘算法的迭代运算量进行分析,对运算耗费大的矩阵运算提出利用限制更新的方法对分层交替非负最小二乘算法进行修改,达到加速收敛的目的。通过仿真,与原倍乘更新算法、投射梯度算法比较,验证算法的有效性和稳定性和高效性。     

一种基于De Bruijn网络结构的并行矩阵乘算法

在De Bruijn网络中进行并行矩阵乘法运算,算法简单,容易实现。首先介绍了De Bruijn网络结构,然后提出了一种基于De Bruijn网络结构的矩阵乘法的并行算法,分析了它的加速比、效率等性能及可扩展性,通过与Cannon算法的比较,证明它的时间复杂度等效于Cannon算法,最后通过实验验证了这个结论的正确性。     

彩色图像的单应矩阵估计算法

图像间单应矩阵估计是图像配准与图像拼接中的核心问题,传统的估计方法是针对灰度图像的算法。本文以分层运动估计为基础提出了彩色图像的平面单应矩阵的估计算法。此算法采用色度与饱和度不变为约束条件得到彩色图像的光流方程,显著改善了亮度不变约束的不足之处;采用最优导数计算滤波器计算图像导数,提高了算法的精度与稳健性;采用尺度总体最小二乘方法代替最小二乘或总体最小二乘方法来估计模型参数,提高了算法对于图像噪声的适应性。实验结果表明,该算法稳健性好、精度高,而且可以得到稠密的匹配点。     

基于对角划分的矩阵乘并行算法

提出了一种新的基于对角划分的矩阵乘并行算法,它在以往行列划分策略的基础上,采用基于对角划分的策略。数值试验表明该算法具有较高的加速比和并行效率。     

矩阵乘协处理器上BLAS level-3运算的设计

BLAS level 3运算的计算复杂度较高,其往往成为应用的性能瓶颈。采用线性阵列结构的矩阵乘协处理器可实现高性能、高效的矩阵乘运算。在矩阵乘协处理器上高效实现BLAS level 3运算,对大规模科学与工程仿真应用的计算加速至关重要。以矩阵乘为核心运算,结合线性阵列的结构特点,提出了矩阵乘协处理器上BLAS level 3运算的设计,并构建了相应的性能分析模型。实验结果表明,矩阵乘协处理器上SYMM、SYRK和TRMM运算的计算效率分别达到了99%,98%和80%,与SW26010和NVIDIA V100 GPU上矩阵运算的计算效率相比,最高提升了31%。     

基于采样和MIMD结构的背包问题并行算法

背包问题属于著名的NP完全问题,在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上,本文提出了一种基于采样和MIMD结构的背包问题并行求解算法,并给出了算法性能的理论分析和在IBMP690超级计算机上的实验结果。实验结果表明,当背包实例的维数n≥40时,本算法的并行效率可达60％以上。因此,本并行算法具有较好的可扩展性,能应用于各种MIMD结构的并行机上有效地求解背包问题。     

MIMD computing in the USA—1984

This paper is a survey of proposed and existing multi-instruction stream computers (MIMD) in the U.S.A., carried out in the summer of 1984. A broad classification of MIMD computers is proposed, and the computers are discussed in this framework. Brief details are given of the architecture and performance (when known) of each machine, together with references to the principal published papers.     

A parallel FFT on an MIMD machine

In this paper we present a parallelization of the Cooley- Tukey FFT algorithm that is implemented on a shared-memory MIMD (non-vector) machine that was built in the Dept. of Computer Science, Tel Aviv University. A parallel algorithm is presented for one dimension Fourier transform with performance analysis. For a large array of complex numbers to be transformed, an almost linear speed-up is demonstrated. This algorithm can be executed by any number of processors, but generally the number is much less than the length of the input data.     

A parallel Ada system on an experimental multiprocessor

This paper describes the development of a parallel Ada system on an experimental MIMD multiprocessor. The system enables a single unmodified Ada program, with a number of tasks, to execute in parallel on different processors. Allocation and migration strategies are controlled by mechanisms in the run-time system, and are thus transparent to the Ada programmer. The parallel Ada system is based on a validated portable front-end compiler. Implementation issues related to the multiprocessor environment are pointed out, and solutions to these issues are suggested. The experimental multiprocessor environment, consisting of both hardware and software, is described. Applicable resource allocation strategies in, and feasible experiments with, the Ada system are discussed. The complete experimental system provides unique possibilities to experiment with, and monitor the effects of, design decisions at different levels in a multiprocessor environment.     

分布式存储环境下矩阵转置并行算法研究

本文针对基于消息传递机制的分布式高性能计算中经常遇到的矩阵转置问题,在分析环状算法的基础上,提出了一种新的蝶形并送算法。     

利用遗传算法求解线程分配问题

文章讨论了软件实现的多线程DSM系统中的线程分配问题,提出了一种新颖的基于遗传算法的动态分配方法,试算结果表明,该方法收敛稳定,求解性能良好.     

基于MPI的中国教育网最短路并行算法

针对传统的Floyd算法难以解决中国教育网的平均最短路径长度计算问题,在对网络进行度分析的基础上,设计了一种宽度优先搜索(BFS)并行算法,该算法可有效地避免对出度为0的节点进行搜索,采用VC编写基于MPI(MessagePassingInterface)的并行程序,通过20台电脑连网计算分析,该方法取得了令人满意的结果。     

Parallel Logic Programming for Problem Solving

We present a new model for parallel evaluation of logic programs. This model can exploit the main sources of parallelism that the language of logic expresses: Independent AND parallelism and OR parallelism, together with a secondary source emerging as a consequence of the Independent AND Parallelism: the producer/consumer parallelism. The efficiency is derived from the use of ordered structures for managing the information generated throughout the search process. The model is suitable for evaluating programs with a high degree of non-determinism because it never generates two processes for solving the same subgoal and hence it can exploit the same real parallelism generating a lower number of processes than other models. As an application example, we consider the Job Shop Scheduling problem. We report experimental results showing that logic programs can be designed that exhibit parallelism, and that the use of heuristic information translates into speedup in obtaining answers.     

并行遗传算法的研究

在分析了解决组合优化问题所遇到的困难的基础上,引入遗传算法。进而提出基本遗传算法在解决数量级很大的组合优化问题上的缺陷,并详细介绍了遗传算法的三种并行模型。最后给出改进的并行遗传算法模型。