一种基于GPU的L1最小化问题快速求解方法

摘要

一种基于GPU的L1最小化问题快速求解方法，在NVIDIA的Maxwell架构GPU设备上，采用CUDA并行计算模型，利用GPU新特征及内核合并和优化技术，提供了一种L1最小化问题快速求解方法。该求解方法中不仅包含了自适应优化的矢量运算、非转置矩阵矢量乘和转置矩阵矢量乘的设计，而且能够仅通过简单的CUDA线程分配设置不同，实现单个或并发多个L1最小化问题的并行求解。实验结果表明，本发明提出的求解方法是有效的，而且具有极高的并行度和适应性。与现有的并行求解方法相比，性能大幅度提高。

主权项

一种基于GPU的L1最小化问题快速求解方法，其特征在于，基于快速迭代收缩阈值算法，在NVIDIA的Maxwell架构GPU设备上，采用CUDA并行计算模型，并行加速求解L1最小化问题；设计了自适应优化的矢量运算、非转置矩阵矢量乘和转置矩阵矢量乘，并通过合理的CUDA线程分配实现了单个L1最小化问题并行求解器和并发多个L1最小化问题的并行求解器；所述求解方法的具体步骤如下：1)根据数据字典的维度和GPU设备的计算资源设置，完成线程束分配设置和线程分配设置；2)采用32字节对齐填充的方式，保存数据字典至0开始索引的按行存储的矩阵中；传输数据字典和矢量从主机端到GPU设备端；3)同时在主机端上，异步计算FISTA的输入参数；4)根据需要求解的L1最小化问题的个数，如果仅求解单个L1最小化问题，在GPU设备端上启发调用单个L1最小化问题并行求解器的设置；如果求解并发多个L1最小化问题，在GPU设备端上启发调用并发多个L1最小化问题的并行求解器的设置；5)在GPU设备端上，使用自适应优化的非转置矩阵矢量乘并行设计，实现FISTA中的非转置矩阵矢量乘；6)在GPU设备端上，使用自适应优化的转置矩阵矢量乘并行设计，实现FISTA中的转置矩阵矢量乘；7)在GPU设备端上，融合剩余的矢量操作，使用流式并行设计，融合方式计算FISTA中剩余的矢量操作；8)同时在主机端上，异步计算标量值；9)如果达到收敛条件，停止迭代，传输稀疏表示从GPU设备端到主机端，否则返回步骤5)，继续迭代。