基于GPU对角稀疏矩阵向量乘法的动态划分算法

在图形处理器(GPU)上实现对角稀疏矩阵向量乘法(SpMV)可以充分利用GPU的并行计算能力,并加速矩阵向量乘法;然而,相关主流算法存在零元填充数据多、计算效率低的问题。针对上述问题,提出一种对角SpMV算法DIA-Dynamic(DIAgonal-Dynamic)。首先,设计一种全新的动态划分策略,根据矩阵的不同特征进行分块,在保证GPU高计算效率的同时大幅减少零元填充,去除冗余计算量;其次,提出一种对角稀疏矩阵存储格式BDIA(Block DIAgonal)存储分块数据,并调整数据布局,提高GPU上的访存性能;最后,基于GPU的底层进行条件分支优化,以减少分支判断,并使用动态共享内存解决向量的不规则访问问题。DIA-Dynamic与前沿Tile SpMV算法相比,平均加速比达到了1.88;与前沿BRCSD(Diagonal Compressed Storage based on Row-Blocks)-Ⅱ算法相比,平均零元填充减少了43%,平均加速比达到了1.70。实验结果表明,DIA-Dynamic能够有效提高GPU上对角SpMV的计算效率,缩短计算时间,提升程序性能。

基于高预测性的稀疏矩阵向量乘法并行计算优化

稀疏矩阵向量乘法(sparse matrix-vector multiplication,SpMV)是广泛应用于科学计算、工业仿真和智能计算等领域的重要算法,是核心的计算行为之一.在一些应用场景中,需要进行多次的SpMV迭代,以完成精确的数值模拟、线性代数求解和图分析收敛等计算要求.受限于SpMV本身的高度随机性和稀疏性所导致的数据局部性极差、缓存效率极低、计算模式非常不规则等问题,导致其计算负载成为当前高性能处理器的优化难点和研究热点.基于现代高性能超标量乱序处理器的架构特征,深入研究SpMV的各类性能瓶颈,并且提出从提升可预测性和降低程序复杂度的角度进行全面的性能优化.其核心思想是:通过构建串行访问的数据结构,提升数据访问的规律性和局部性,大幅度优化数据预取效率和缓存利用效率;通过构建规则的分支跳转条件,提升程序的分支预测准确率,有效提升程序执行效率;通过灵活运用SIMD指令集,有效提升计算资源利用率.通过对以上特性的优化,该方法可以显著缓解性能瓶颈,大幅度提升处理器资源、缓存资源和访存带宽的利用率,并且获得与主流商用计算库MKL相比平均2.6倍的加速比,相比于现有最先进算法获得平均1.3倍的加速比.

矩阵与向量在生活中的应用

在我们的日常生活中,经常会用到矩阵和向量,比如进行一次乘法运算,向量就是在矩阵中一个一个地添加数字的过程。在科学研究中,我们也经常用到矩阵,比如研究相对论的时候就需要用到一个一维的、实对称矩阵。矩阵和向量不仅在数学中有重要的地位,在现实生活中也有广泛的应用。

基于三值逻辑光学处理器实现向量矩阵乘法

向量矩阵乘法是一种应用广泛的运算,用光学方法实现向量矩阵乘法能够充分发挥光处理的并行优势,旨在提出一种新的实现向量矩阵乘法的光学方法。受到三值逻辑光学处理器结构的启发,提出用该处理器实现二进制向量矩阵乘法,这个新方法能够克服传统光学向量矩阵乘法器结构中存在的一些不足。详细说明了实现的原理和过程,并讨论了这种新方法的优点,最后展望了这种新型的光学处理器的发展前景。

一种实现平衡三进制向量矩阵乘法的光学方法

提出了一种实现平衡三进制向量矩阵乘法的光学方法。在文献[5,6]的工作基础之上,受到三值光学计算机具有处理三值信息能力的启发,继续研究三值光学向量矩阵乘法的实现,提出平衡三进制光学向量矩阵乘法的实现方法。详细说明了该方法的原理和工作步骤,并通过实验验证该方法的正确性,讨论分析了光学向量矩阵乘法的优点以及三值光学向量矩阵乘法的优势所在。

基于向量扩展多核处理器的矩阵乘法算法优化研究

在GODSON-3B八核处理器平台上,对矩阵乘法算法进行了优化和评估,针对矩阵乘法中A,B,C三个矩阵各自的访存特点,采用不同的方法对其访存行为进行优化,隐藏访存时间,使矩阵乘法性能达到122Gflops,效率为95.3%.

面向多核向量处理器的矩阵乘法向量化方法

稠密矩阵乘法是大规模科学计算中许多算法的核心计算之一,文中提出一种高效的面向多核向量处理器的矩阵乘法向量化方法.提出一种按行计算的矩阵乘法向量化方法,该向量化方法的基本思想是每次同时计算C矩阵的一行元素,C矩阵第i行元素的值由k次向量乘累加完成,每次计算都是先将A矩阵第i行的第j个元素扩展为值相同的向量,再与B矩阵的第j行向量进行乘累加计算,每一次的向量乘累加计算是在各个VPE上并行进行,计算的源数据和结果数据均保存在VPE的本地寄存器上,每个计算结果涉及的乘累加计算均在同一个VPE上完成,并且A、B、C三个矩阵的数据均是按行顺序读取,访存效率高,在k循环结束时,同时完成C矩阵第i行元素值的计算.该方法能充分开发向量处理器的标量、向量协同数据加载能力,有效减少对DDR的存储带宽需求,能够避免低效的对乘数矩阵列向量数据的访问和各个VPE间的浮点归约求和计算,取得最优的内核计算性能;将处理器的一级数据缓存和阵列存储配置为SRAM访问模式,能够避免由于Cache数据不命中而导致的存储访问延迟,提高核心计算访问一级数据缓存和阵列存储的效率,采用组播DMA传输矩阵数据,能够显著提高从DDR读取矩阵数据的效率;提出依据向量处理单元VPE数量、VPE的FMAC运算单元数量、向量存储器的容量和矩阵元素的数据类型等向量处理器体系结构特点设计最优的核心子块矩阵分块参数设计方法,能够充分开发向量处理器的多核间数据并行、核内的多VPE间的向量SIMD并行、VPE内的多个FMAC单元并行、VPE内的标、向量指令级并行等多级并行性,并根据FMAC指令延迟槽进行完全循环展开,让内核始终以峰值速度运行;提出基于两级DMA双缓冲数据搬移策略,优化和平滑多级存储结构间的数据传输,使得DMA的数据搬移时间完全重叠于内核的计算时间中,让整个矩阵计算以接近内核计算的速度运行,实现最优的计算性能和效率.在MATRIX2上的实验结果表明,提出的双精度矩阵乘法的性能达到1106.88GFLOPS,效率为96.08%,核心计算的效率达到99.39%.

支持原位计算的高效三角矩阵乘法向量化方法

向量化算法映射是向量处理器的难点问题。提出一种高效的支持原位计算的三角矩阵乘法向量化方法:将L1D配置为SRAM模式,用双缓冲的乒乓方式平滑多级存储结构的数据传输,使得内核的计算与DMA数据搬移完全重叠,让内核始终以峰值速度运行,从而取得最佳的计算效率;将不规则的三角矩阵乘法计算均衡分布到各个向量处理单元,充分开发向量处理器的多级并行性;将结果矩阵保存在乘数矩阵中,实现原位计算,节省了存储空间。实验结果表明,提出的向量化方法使三角矩阵乘法性能达到1053.7GFLOPS,效率为91.47%。

光学向量矩阵乘法器的进展

经过对目前国际上研究前沿的光计算技术中处于核心地位的光学向量矩阵乘法器(OVMM)进行深入的调研,本文主要介绍了某些类型的光学向量-矩阵乘法器的结构和原理,以及国内外最新的研究进展和应用前景。并根据国内外同行在此领域已经获得的研究成果,经过综合分析,拟提出对将来光计算技术的进一步发展具建设性意义的看法。

浮点矩阵向量乘法的FPGA设计与优化

提出了一种基于IEEE-754的32 bit、64 bit浮点数格式,二叉树数据流(binary tree data flow)的矩阵向量乘法器.其在FPGA上流水线和高度并行化的高效执行.以Altera公司的EP2C70为实现设备,研究了设计的硬件规模,时钟速度,和峰值GFLOPS能力.

一套二进制向量-矩阵乘法运算的光计算系统

对计算机前沿领域的光计算进行了讨论研究,介绍了光计算的核心运算器——光学向量-矩阵乘法器的工作原理,从实验角度出发,设计出了一套性能稳定的可实现二进制向量-矩阵乘法运算的光计算系统,并分析了此套系统的光学原理和性能特点。此系统具有矩阵乘法运算、数码显示、电压输出等功能,是一套实用性很强的教学科研演示产品,对光学乘法器以及光计算的研究具有一定的指导意义。

按行及按列划分的并行矩阵向量乘法的分析

文中首先总结按行划分和按列划分的并行矩阵向量乘法在原理上的异同。然后实现基于MPI模型的按行划分以及按列划分的矩阵向量乘法的程序,并分析了程序在基本框架方面的异同。最后给出测试这两种程序的实验条件和任务,并对这两种程序在不同情况下的执行时间进行分析。

TEB:GPU上矩阵分解重构的高效SpMV存储格式

稀疏矩阵向量乘法(SpMV)是科学与工程领域中一个至关重要的计算过程,CSR(compressed sparse row)格式是最常用的稀疏矩阵存储格式之一,在图形处理器(GPU)平台上实现并行SpMV的过程中,其只存储稀疏矩阵的非零元,避免零元素填充所带来的计算冗余,节约存储空间,但存在着负载不均衡的问题,浪费了计算资源。针对上述问题,对近年来效果良好的存储格式进行了研究,提出了一种逐行分解重组存储格式——TEB(threshold-exchangeorder block)格式。该格式采用启发式阈值选择算法确定合适分割阈值,并结合基于重排序的行归并算法,对稀疏矩阵进行重构分解,使得块与块之间非零元个数尽可能得相近,其次结合CUDA(computer unified device architecture)线程技术,提出了基于TEB存储格式的子块间并行SpMV算法,能够合理分配计算资源,解决负载不均衡问题,从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性,在NVIDIA Tesla V100平台上进行实验,结果表明TEB相较于PBC(partition-block-CSR)、AMF-CSR(adaptive multi-row folding of CSR)、CSR-Scalar(compressed sparse row-scalar)和CSR5(compressed sparse row 5)存储格式,在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍;在浮点计算性能方面,平均可提高3.36、5.95、2.29和2.13倍。

光学向量-矩阵乘法器教学演示实验

为了在光计算教学中提供让学生更易于形象理解光的并行计算能力和实现方式的教学环境,基于向量-矩阵乘法的基本原理,采用LED阵列、光敏管阵列、柱面透镜、薄透镜等简易的基础光学元件搭建了4×4的光学向量-矩阵乘法器教学演示实验.该演示实验展示了并行光计算系统的基本功能实现和构成要素,有助于学生对光计算有初步的形象认识和了解,认知本课程的目的和意义,有利于激发学生对课程学习的兴趣.

稀疏矩阵向量乘法的并行计算

本文研究大型稀疏矩阵向量乘法的并行化措施。主要包括高效的存储方法,核心代码用汇编语言编写,循环展开,宏任务和微任务方式,重排序和分块技术。根据实际问题的需要,分别给出了一般稀疏矩阵和对称正定带状矩阵向量乘法内核子程序,ELLPACK,ITPAKC及LINPACK等库和许多应用程序可直接调用它们。

光学向量矩阵乘法实验研究

旨在对光学向量矩阵乘法进行实验研究。针对Goodman向量矩阵乘法器原理光路模型中存在的结构庞大、可实现的运算规模有限、制作成本较高等问题,提出了一种用液晶阵列实现向量矩阵乘法的方法。该方法具有易于微型化、可完成大规模的二进制向量矩阵乘法运算、制作成本较低的优点。对该方法的原理进行详细地说明;并利用本课题组开发完成的三值逻辑光处理器作为实现该方法的核心器件,完成了实验。实验结果表明该方法具有正确性和巨大的并行处理优势。

光学向量矩阵乘法研究

向量矩阵乘法运算是数值计算中基本的运算,广泛应用于线性方程组求解、图像处理、数字信号处理、人工智能等多个领域。目前向量矩阵乘法的实现方法有很多种,其中用光学方式实现向量矩阵乘法的方法因其所特有的并行性和乘法性质,在解决这类二维信息处理问题时独具优势而受到研究者们的青睐。对光学向量矩阵乘法的研究进行了深入的分析和总结,综述国内外各种光学矩阵乘法实现的理论和方法,并阐述作者研究的基于三值光学逻辑处理器的实现方法,该方法具有结构简单、易于微型化、计算精度高等优点。

稀疏矩阵向量乘法在申威众核架构上的性能优化

计算机数值模拟是现代科学和技术发展的重要触发力量.在数值模拟中,求解大规模稀疏线性方程组是非常重要的一个环节.迭代求解过程中稀疏矩阵向量乘法是耗时最长的计算核心之一,存在严重的数据局部性差、写冲突、负载不均衡等问题.因此,稀疏矩阵向量乘法已经成为了当前性能优化的难点和研究热点.本文面向国产众核处理器架构,以申威26010国产众核处理器为平台,针对稀疏矩阵向量乘法,在线程级和指令级并行层面上进行细粒度的并行算法设计和优化实现.其核心思想是,将众核架构设计精巧的矩阵分层分块技术用于矩阵存储、访问和任务调度,在保证右端向量数据复用的同时有效实现了负载均衡,避免了申威26010上因频繁缓存判断和细粒度访问导致的潜在性能问题.通过对SuiteSparse矩阵集合中的2710个算例的测试,该算法可以获得与主核上的串行算法相比11.7倍的平均加速和55倍的最高加速.

多位二进制向量矩阵乘法的研究和实现

随着人类对计算机性能的需求不断增加,出现了大规模、超大规模计算机系统,但是随之而来的通讯代价和能耗代价也提出了很多严峻的挑战,各种非电子计算机方法因此被广泛关注。本文以三值光计算机为实现平台,探讨如何利用一位二进制向量矩阵乘法的实现方法解决多位二进制向量矩阵乘法。

一种基于闪存的温度补偿型向量矩阵乘法器

基于XMC 65 nm浮栅工艺,设计了一种基于闪存的存算一体向量矩阵乘法器。进行模拟计算的闪存单元工作在线性区,采用两个闪存单元以差分的方式存储一个权重,提高了计算线性度,减小了权重的温度系数分布。设计了电流减法与缓冲电路,精确得到了乘累加的计算结果,并通过负阻并联型闪存负载实现了良好的温度补偿。模拟计算的精度为4位。仿真结果表明,各权重的计算结果为:在-40℃~85℃范围内,温度系数小于0.1%/℃;在85℃~130℃范围内,温度系数小于0.25%/℃。