OTIS网络结构的并行矩阵乘算法

提出基于光交换互连系统(OTIS)网络结构的矩阵乘并行算法,分析它的时间复杂性.采用一种新映射策略来处理一般OTIS网络结构上的矩阵映射,即矩阵映射策略是根据基图中的哈密尔顿路径来分配处理器的.通过OTIS网络的拓扑结构模拟实验,结果表明,OTIS网络矩阵乘算法的性能优于Cannon算法,更加优于O(n3)串行矩阵乘算法.     

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

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

一种矩阵相乘的并行算法实现与性能评测

用传统的串行算法进行矩阵相乘运算会受到矩阵规模、单机的CPU主频、内存大小和存储器空间等方面的限制.而使用并行算法是解决上述限制的最有效途径.为此,在集群计算环境下,使用SPMD计算模型和基于MPI消息传递技术设计实现了矩阵相乘的并行算法.实验表明,此并行算法在一定矩阵规模下具有较好的加速比和并行效率.     

Vandermonde矩阵求逆的并行算法及其复杂度

分析Ｖａｎｄｅｒｍｏｎｄｅ矩阵的一种求逆递推式,利用卷积技术研究递推式求解的并行计算方法,给出了并行算法的实现方案,该算法的时间复杂度为Ｏ（ｌｏｇ２ｎ＾２）。     

DS-CDMA盲多用户检测算法性能实验研究

针对CDMA下行链路仅知道目标用户自身扩频码这一情形,通过仿真实验对恒模、最小输出能量、递归最小二乘、Kalman滤波以及基于独立分量分析这几种线性和非线性盲多用户检测算法的误码率和信干比进行了性能比较和讨论.实验证明,基于独立分量分析的盲多用户检测算法具有较好的性能.为对算法工程实现提供具体的参考,本文对各算法的计算复杂度进行了分析.     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

基于OpenMP的对称矩阵:LDLT分解并行算法实现

分析对称矩阵LDLT分解过程的并行结构,给出对称矩阵LDLT分解的并行算法,然后考虑粗粒度组合后的负载平衡,提出基于OpenMP的对称矩阵LDLT分解并行算法的实现方案,并对该方案的并行计算性能进行数值实验.实验表明,基于OpenMP的对称矩阵LDLT分解并行算法在多核处理器系统中能够显著地提高算法性能.     

一种基于特征值分解的信道估计算法

信道估计是OFDM系统中的一项关键技术.传统的LMMSE算法涉及到自相关矩阵的逆运算,算法复杂度较高,时间开销较大.本文提出的算法首先对信道频率响应的自相关矩阵进行降维,再进行特征值分解,避免了求解逆矩阵,算法复杂度较低.仿真实验对信噪比、均方误差、误码率性能进行了分析,结果表明提出的算法在保证了系统良好性能的基础上,有效地降低了运算的复杂度.     

块三对角M矩阵的并行判定方法

根据朱旭的矩阵计算定理,提出了判断块三对角矩阵是否为M矩阵的并行算法.该算法在求解过程中,通过合理安排处理机的任务,尽量减少了通信的次数及时间,并且可以根据中间结果及时得到判断,使算法获得了较好的加速度.     

新的求解大规模线性最小二乘问题的随机算法

目的针对传统的求解线性最小二乘问题方法的计算、存储复杂度大,不适于大规模问题的缺点,提出新的随机算法近似求解大规模线性最小二乘问题。方法通过随机采样对超大规模线性最小二乘问题的系数矩阵进行约减,利用快速Walsh-Hadamard对问题进行变换来保留原问题的重要信息,再用QR分解算法求解约减问题,得到原问题的近似解。结果该方法有效降低了问题的求解复杂度和存储复杂度。结论数值实验表明新算法和相关算法相比求解精度可接受,但大大减少求解时间且在同等计算平台下可处理更大规模的问题。     

矩阵相乘并行算法的MPI实现

介绍行列划分算法和矩阵相乘并行算法MPI程序,给出基于矩阵相乘并行算法的MPI实现,分析和讨论处理器数目、复杂性、矩阵划分、B子块传递、死锁避免和矩阵数据的获取等问题。     

MapReduce based computation of the diffusion method in recommender systems

The performance of existing diffusion-based algorithms in recommender systems is still limited by the processing ability of a single computer .In order to conduct the diffusion computation on large data sets, a parallel implementation of the classic diffusion method on the MapReduce framework is proposed.At first, the diffusion computation is transformed from a summation format to a cascade matrix multiplication format , and then , a parallel matrix multiplication algorithm based on dynamic vector is proposed to reduce the CPU and I/O cost on the MapReduce framework , which can also be applied to other parallel matrix multiplication scenarios .Then, block partitioning is used to further improve the performance , while the order of matrix multiplication is also taken into consideration . Experiments on different kinds of data sets have verified the efficiency of the proposed method .     

基于OpenMP矩阵相乘并行算法的设计

目的设计并实现一种基于数据划分的矩阵乘法的并行算法,将划分的数据交给多个线程同时执行,充分挖掘计算机的性能。方法根据OpenMP并行编程的基本风格,并在Visual Studio2005上搭建能够实现并行编程的环境平台。结果并行算法所花费的时间较非并行算法短。结论通过与非并行矩阵乘法性能进行比较,验证该算法可以有效地利用多核处理器的优势。     

Root-MUSIC，PM，MUSIC算法的比较

对测向算法（DOA）中的2种降低运算量的算法,即求根的MUSIC算法（Root-MUSIC）和传播算子算法（PM）,与多重信号分集算法（MUSIC）进行比较,并对两者降低运算量的作用进行了有效性分析和验证.Root-MUSIC算法通过求根降低运算量,PM通过矩阵乘法代替矩阵分解降低运算量.仿真结果表明,在阵元数较少时Root-MUSIC是最有效的算法,否则PM算法更为有效.     

PC机群上FOX乘法的并行实现

分析了并行计算技术和机群系统的特点,提出了PC机群上FOX乘法并行实现的算法原理,并提出了改进算法.数值结果表明改进的算法收到较好的效果.     

快速可扩展的矩阵幂运算并行算法及其应用

提出了一种LARPBS模型上改进的矩阵幂运算并行算法，将它应用于矩阵的逆运算和矩阵的LU分解，分析了它们的可扩展性和复杂性．通过分析可以看出，这些算法是目前成本最优的并行算法。     

空间调制信号的QRD-M检测算法及其改进

针对空间调制(spatial modulation,SM)系统中最优检测算法,即最大似然(maximum likelihood,ML)算法存在的高复杂度问题,提出了基于QRD-M(QR-decomposition with M-algorithm,QRD-M)算法的空间调制信号检测算法.该算法运用M算法树搜索策略,每层只计算最优的M个分支,其性能近似最优且运算量较低,有利于硬件实现.但随着发收天线数增多,传统QRD-M算法的检测性能会下降并需要较长的算法执行时间.因此,采用并行检测的思想,提出了PQRD-M(parallel QRD-M,PQRD-M)检测算法.该算法在各个分支上分别独立地进行搜索,提高了执行效率.对所提出的算法进行了复杂度分析,并在不同天线数目和不同保留节点数下对其误码性能进行了仿真,结果表明,相比于QRD-M算法,PQRD-M算法以增加一定的计算量为代价,能显著地改善空间调制信号检测性能,同时还能节约硬件资源.     

基于增强蚁群优化算法与排序的 MIMO 检测算法

基于最大似然比的多输入多输出(multiple input multiple output,MIMO)检测算法的计算复杂度随着天线阵的规模呈指数级增加,提出一种计算复杂度较优的MIMO检测算法.采用基于对数似然比的排序QR分解技术将信道矩阵分解为正交矩阵与上三角矩阵,相应地修改信号的发射顺序,降低错误判断引起的错误传播效应;为传统人工蚁群优化算法的信息素更新策略引入负信息素概念,有效地控制系统的拥塞;根据优化路径的距离积累了信息素.该方法设计了基于负信息素的信息素更新策略,增加MIMO系统的拥塞控制能力,考虑信道的衰落本性,基于路径的距离积累信息素.为了测试该算法的性能,进行了多组对比实验,结果表明,误码率性能优于其他智能优化算法,且对于64×64等大规模天线阵,该算法的计算复杂度随天线规模增长较小.     

多处理机中矩阵乘法的算法研究

从矩阵乘法的顺序代码、并行代码中分析了其通信时间开销和计算性时间复杂性,提出了使用直接法、子矩阵和递归算法;为提高效率,还提出了将通信安排在计算过程中间进行的算法,使得计算获得最大的重合。解决了多处理机系统中因处理器间的通信速度相对滞后所产生的负面影响问题,给数值计算带来很大的方便。