矩阵求逆运算的VLSI实现

矩阵运算广泛应用于各类电路计算中,矩阵运算的硬件实现能够充分发挥硬件的速度和并行性.其中矩阵求逆是矩阵运算中重要的运算.为加速矩阵求逆,研究构造出一种非常易于实现的基于心动阵列的矩阵求逆的电路结构.通过硬件描述语言Verilog建模,VCS仿真及用Design Compile进行综合,结果表明这种并行结构能快速实现矩阵求逆,且运算精度较高.     

基于批量LU分解的矩阵求逆在GPU上的有效实现

给出批量矩阵的LU分解和批量求逆算法在GPU上实现及优化方法.针对批量LU分解问题,分析Left-looking和Right-looking等常用LU分解块算法在GPU上实现时对全局内存的数据读写次数,针对GPU架构特点,选择具有较少访存数据量的Left-looking块算法.在LU分解的选主元过程,采用适合GPU架构的并行二叉树搜索算法.此外,为了降低选主元引起的行交换过程对算法性能的影响,提出Warp分组行交换和行交换延迟2个优化技术.针对LU分解后的批量求逆问题,分析矩阵求逆过程中修正方法,为了减少修正过程对全局内存的访问,在批量求逆的GPU实现中采用延迟修正的矩阵求逆块算法.同时,为了加快数据读写速度,采用更多利用寄存器和共享内存的优化方法和减少访存数据量的列交换优化方法.另外,为了避免线程的闲置和共享内存等GPU资源浪费,提出运行时动态GPU资源分配方法,相较于一次性分配的静资源分配方法性能得到明显提升.最终,在TITAN V GPU上,对10000个规模在33–190之间的随机矩阵进行测试,测试的数据类型为单精度复数、双精度复数、单精度实数和双精度实数.所实现的批量LU分解算法的浮点计算性能分别可达到约2 TFLOPS、1.2 TFLOPS、1 TFLOPS、0.67 TFLOPS,与CUBLAS中的实现相比加速比最高分别达到了约9×、8×、12×、13×,与MAGMA中的实现相比加速比分别达到了约1.2×–2.5×、1.2×–3.2×、1.1×–3×、1.1×–2.7×.批量求逆算法的浮点计算性能分别可达到约4 TFLOPS、2 TFLOPS、2.2 TFLOPS、1.2 TFLOPS,与CUBLAS中的实现相比加速比最高分别达到了约5×、4×、7×、7×,与MAGMA中的实现相比加速比分别达到了约2×–3×、2×–3×、2.8×–3.4×、1.6×–2×.     

STAP中的协方差矩阵求逆快速算法研究

研究机载雷达平台问题,空时自适应处理(STAP)是新一代机载相控阵雷达杂波抑制与目标检测的关键技术.在工程化过程中.运算量巨大是其面临的首要问题.为了改善STAP在采样矩阵维数较高情况下求逆运算的实时性能和有效提高雷达抑制杂波和抗干扰能力,提出了一种改进的Strassen矩阵求逆算法,算法结合了Strassen矩阵求逆的高效性以及采样协方差矩阵是Hermite正定阵的特点,具有运算最小,算法结构简单,便于工程实现的优点.DSP处理器的实测数据证明了方法的有效性和可行性.结果表明与目前工程中改进方法性能改善效果明显.     

下三角复矩阵求逆的ASIC设计及实现

本论文提出了一种便于ASIC实现的矩阵求逆算法,可以完成对1到16维下三角复矩阵的求逆运算,并用Verilog硬件描述语言进行实现.利用SMIC 0.13um工艺库和Synopsys公司的Design Compiler工具对代码进行了综合,并进行了低功耗优化,最后使用Modelsim工具对代码进行了仿真验证,得到的结果同C代码模拟的结果完全一致,证明本模块完全可以达到预期目的.     

矩阵三角分解分块算法的研究与实现

对稠密型线性方程组的系数矩阵进行分块LU分解,更充分地利用高速缓存,提高运算效率.对LU分解分块算法进行了研究,用VC+ +6.0对分块算法进行实现,并与标准的LU分解算法进行比较.在大矩阵情况下,分块算法比标准算法运算速度提高50%以上.     

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

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

基于LogP简化模型的矩阵求逆并行算法研究

LogP is becoming a practical parallel computation model that meets the demanding of parallel computers and parallel algorithms. So it is important to re-design parallel algorithms on the LogP model. This paper studies the parallel algorithm of computing converse matrix on the simplified LogP model, and gets the simulating results.     

不同矩阵分解方法对海洋数据同化的影响*

在海洋数据同化领域,集合最优插值方法中,矩阵求逆过程所使用的奇异值分解(singular value decomposition,SVD)十分耗时。对集合最优插值中逆矩阵的求逆过程进行优化,分别使用LU分解、Choleskey分解、QR分解来替代SVD分解。首先,通过LU分解(Choleskey分解或QR分解)得到相应的三角矩阵(或正交矩阵);然后,利用分解后的矩阵来实现相关逆矩阵的计算。由于LU分解、Choleskey分解、QR分解的算法复杂度都远小于SVD分解,因此改进后的同化程序能得到大幅度的性能提升。数值结果表明,所采用的三种矩阵分解方法相比于SVD分解,都能将集合最优插值的计算效率提升至少两倍以上。值得一提的是,在四种矩阵分解中Choleskey分解使得整个同化程序的性能达到了最优。     

一般实矩阵求逆的几种算法及实用程序

对矩阵求逆的选全土元变量置换法、ＬＵ分解法、Ｈｏｕｓｅｈｏｌｄｅｒ变找法及共轭斜量法这四种算法并给实用程序,并从运算速度、运算精度和占用存储空间大小诸方面作了简单比较。     

VLSI systems for band matrix multiplication

We examine several VLSI architectures and compare these for their suitability for various forms of the band matrix multiplication problem. The following architectures are considered: chain, broadcast chain, mesh, broadcast mesh and hexagonally connected. The forms of the matrix multiplication problem that are considered are: band matrix × vector and band matrix × band matrix. Metrics to measure the utilization of resources (bandwidth and processors) are also proposed. An important feature of this paper is the inclusion of correctness proofs. These proofs are provided for selected designs and illustrate how VLSI designs may be proved correct using traditional mathematical tools.     

一种基于FBMA算法的整像素运动估计芯片的VLSI设计

给出了一种基于全搜索块匹配算法的运动估计电路的改进结构,并完成了VLSI设计.通过采用多端口匹配策略和双时钟方案,使得在提高先前帧搜索区域像素数据重复利用率的同时,将脉动阵列的计算效率提高到74.9%.采用TSMC0.25μm1P5MCMOS工艺,完成了运动估计芯片的VLSI实现,其芯片面积为3.37mm×3.37mm,最高工作频率为110MHz.综合后仿真表明在89.4MHz的频率下,该电路可以对支持MPEG4ASProfile标准的ITUR601格式视频图像(720×480@30HzNTSC或720×576@25HzPAL)进行基于整像素的实时运动估计.     

一种实时低成本压缩算法的VLSI实现

针对传统视频图像压缩算法时延长和成本高的问题,提出一种新的无损/近无损视频压缩算法。该算法由码率控制器和熵编码器组成,其中码率控制器通过对已有信息进行分析（上下文）来确定当前宏块的可用比特数,然后根据大量实验得出的高效Huffman码表,并结合位平面编码器对残差进行编码。实验结果表明,文中提出的视频图像压缩算法能够工作在300 MHz,吞吐量最差为1.3 pixel/cycle,同时仅用一块120＊720的SRAM来存储上一行像素值,因此很好地解决了时延和成本问题。     

基于禁忌搜索算法的VLSI布局

将禁忌搜索算法应用于VLSI门阵列的布局问题，建立了以总线长度和通道拥挤度的布局目标函数，用禁忌搜索算法求解目标函数的最小值，通过实验仿真，将本算法和遗传算法进行了比较，结果表明不论在解的质量和收敛速度方面，禁忌搜索算法优于遗传算法。     

利用并行方法解AX+XB=C型线性矩阵方程

提出了一种新的递推算法用于求解AX+XB=C型线性矩阵方程,这种算法可以用脉动阵列结构并行实现,该算法和结构还可求解其它几种类似的线性矩阵方程,特殊情况下求解方程的阵列结构可进一步简化.仿真结果表明,这种并行方法有较高的加速比及效率.     

A Fast Algorithm for Matrix Multiplication and Its Efficient Realization on Systolic Arrays

A new fast matrix multiplication algorithm is proposed, which, as compared to the Winograd algorithm, has a lower multiplicative complexity equal to W _M 0.437n³ multiplication operations. Based on a goal-directed transformation of its basic graph, new optimized architectures of systolic arrays are synthesized. A systolic variant of the Strassen algorithm is presented for the first time.