稀疏表示算法在 GPU 的优化.doc

精品论文稀疏表示算法在 GPU 的优化赵广銮，张洪刚北京邮电大学信息与通信工程学院，北京 100876摘要： 介绍稀疏表示的背景、应用范围和 GPU 并行计算的发展。结合对当前稀疏表示的主流 算法分析，以及对 GPGPU 平台 CUDA 编程模型的理解，实现稀疏表示算法在并行性上的优 化处理，并通过实验与 CPU 上的稀疏表示算法进行对比探讨。 关键词：稀疏表示；图形处理器；统一计算设备架构中图分类号： TP391Optimization of Sparse RepresentationAlgorithm on GPUZHAO GuangLuan, ZHANG HongGangInformation an Communication Engineering School, Beijing University of Posts andTelecommunications, Beijing 100876Abstract:Introduce the background of sparse representation, eld of application and the development of General-purpose computing on GPU. With the analysis to popular sparse representation algorithms and the comprehension of Compute Unied Device Architecture, an optimization of Sparse Representation is proposed. Furthermore, an experiment between a GPU implement and a CPU one will be held to nd out the performances of two platform. Key words: Sparse Representation;GPU;CUDA0 引言稀疏表示，又称为压缩感知1 ，是近年来关于图像识别、计算机视觉、数值计算等领域的 研究热点。由于稀疏表示应用广泛，较难计算，因此不断有学者针对求解稀疏问题提出特定的 算法。尽管如此，现有算法没有充分考虑算法并行性问题，在并行环境中不能合理利用多计算 核心的资源。另一方面，在 CPU 多核化、服务器集群化的背景之下，并行计算领域越来越受到重视。 简单的单线程任务已经无法充分利用多核 CPU 带来的优势。如何尽可能利用多核 CPU、服 务器集群的性能，已成为软件工程师必须考虑的问题。多台机器协作运行，到一台多 CPU 机 器的运作，再到近年的多核 CPU，并行计算的应用已从军事、大型科学计算等领域逐渐走到 大众生活，大型科技公司纷纷提出自己的并行框架，并行计算受到更多人的关注。作者简介： 赵广銮（1987-），男，硕士研究生，主要研究方向：图像识别、数值计算。E-mail: zhaoguangluan 通信作者：张洪刚（1974-），男，副教授，博士生导师，主要研究方向：图像处理与图像识别、视频检索与过滤以及计算机视觉。 E-mail: zhhg- 6 -1 稀疏表示稀疏表示 (Sparse Representation)，又称为压缩感知 (Compressive Sensing)，它意欲用尽 可能少的非 0 系数表示信号的主要信息，从而简化信号处理问题的求解过程。在信号处理方 面，稀疏表示的一个重要应用是压缩采样。与传统的基于频域采样模型不同，稀疏表示的核心 思想是将共享各信号间的共性，然后用极少量信息（稀疏向量）表示他们的差异，理论上不再 受奈奎斯特准则限制。稀疏表示吸收了传统压缩理论的优点，然后克服其不足，现在逐渐成为 一个重要的基础研究领域。由于稀疏表示的本质是凸优化问题2 ，因此可以直接使用解决一般凸工具如内点法来解 决。但事实表明，由于稀疏问题的特殊性，普通的算法并不能高效地进行对其求解。因此，人 们针对和利用稀疏问题的特殊性，提出了许多特定的算法3 。这些算法能较有效率地解决稀疏 问题，也推动了稀疏表示在实际问题中的应用。1.1 稀疏表示求解形式稀疏表示的原始模型为：xmin |x|0 s.t. Ax = b(1)其中 b Rn 为待处理信号，A Rn×m 为基函数字典，x Rm 为稀疏表示求解结果，|x|0 << m。|x|0 为 x 的稀疏度，它表示向量 x 中非 0 的个数。由于 |x|0 在数学上被证明是非凸的，其最小化问题是 NP-hard 问题，在计算机上求解非常困难4 。为了能实际求解稀疏表示，可以把 |x|0 近似为 |x|1 ，其中 |x|1 为 x 中所有元素的绝对值之和，因此稀疏表示的一般表达式为：xmin |x|1 s.t. Ax = b(2)1.2 求解算法求解稀疏问题可以使用拉格朗日乘子法 (Augmented Lagrange Multiplier, ALM) 进行求 解。对于稀疏表示，其增广拉格朗日函数为： 2L (x, ) = x1 + , Ax b + 2 Ax b(3)其中 > 0 为拉格朗日乘子。增广拉格朗日乘子法每次迭代都会减少 L (x, )，从而使得原问 题的目标值下降，得到的新的 xk 后可以更新乘子 k ，然后迭代求解 xk+1 和 k+1 ，最终 xk+1 将会收敛到原问题的最优解，迭代步数越多，则收敛精度越高。另外，ALM 问题还能求解稀疏表示的对偶问题：2 2min bT y xT (z AT y) +y,x,zz AT y2 s.t. z B1 (4)对于上述问题，可以使用下面的三步算法进行求解：1 k+1A kkz = P (AT y + x /)yk+1 = (AAT )1 (Azk+1 (Axk b)/)xk+1 = xk (zk+1 AT yk+1 )(5)该算法又称为 DALM5 。对于 A Rn×m ，DALM 在 n m 的情况比原 ALM 算法更有效率。2 GPU 并行计算图形处理器 (Graphics Processing Unit, GPU) 的起源来自于对分担计算机图形学任务的 要求。在大型 3D 渲染任务中，CPU 需要对计算机图形建模作大量相似性运算，这部分工作 会占用了 CPU 大量时间，而耽误了其他逻辑处理。GPU 的核心技术和硬件设计能迅速处理 图形方面的任务，如光线处理、纹理渲染和 3D 建模等。有了 GPU 的出现，CPU 就能专心在 任务调度、逻辑处理等方面，而把图形处理与渲染任务交给了 GPU 实现。在现代三维技术迅 速发展的背景下，图形显卡和 GPU 也被日益重视，GPU 的发展速度在近几年甚至超越了半 导体的黄金定理摩尔定律。2.1 GPU 通用计算与 CPU 相比，GPU 有其独特的优点：核心数非常多，并行性高，基于流处理。而这些优 点也就是现代并行计算科学所需要的，因此使用 GPU 在并行计算是未来的一大发展方向。近 年来，随着 GPU 的发展和并行计算的普及，GPU 通用计算 (General-purpose computing on GPU, GPGPU) 倍受重视。在一个通用的跨语言及平台的编程结构、底层图形库 OpenGL(Open Graphics Library)中，人们尝试着编写通用计算的程序。初期的 GPGPU 通过三组基本概念（数组 纹理，计 算核函数 着色器，运算 渲染），完成了在 GPU 上进行数值计算的任务。实验证明，相同性价比的 CPU 和 GPU 同时执行一个并行度高的任务，GPU 的执行效率远远高于 CPU。但这种 GPU 编程方法存在不少问题，如编写程序非常麻烦、接口函数不够丰富、欠缺错误处 理机制、不容易调试程序等，难以用其编写工业级的计算应用。2.2 统一计算设备架构NVidia 公司率先推出了从硬件层到应用层一体化的解决方案，称为统一计算设备架 构6 (Compute Unied Device Architecture, CUDA)。NVidia 新推出的显卡系列等均支持 CUDA，且 CUDA 计算能力 (CUDA Compute Capability) 不断提高，适应更多的应用环境。 目前，CUDA 已经得到了广泛的认可，在消费市场、科研界和金融界均有不少高质量的 应用。CUDA 为海量数据的复杂、实时计算提供了高效便利的计算平台。GPGPU 是未来并行计算的主流方向，而 CUDA 则是 GPGPU 领域的领衔者。3 稀疏表示的并行优化稀疏表示算法在串行上已有较高的速度，但应用在并行处理上仍有提升的空间。本章将探 讨如何在 GPU 并行平台上对稀疏表示算法进行优化。3.1 传统 DALM 的问题在应用 DALM 算法解决稀疏问题时，主要步骤包括矩阵 -向量相乘、向量的基本操作（加 法、尺寸变换、软阈值等）和向量的求模。其中前两种是并行性较高的操作，而后一种即求模 实际在并行处理上的本质是数组的归并操作，一般并行处理器上的归并操作由如下图所示：图 1: GPU 归并操作示意图 可以看到，在归并操作中，每次循环时需要计算的处理器减半，但由于最后需要传送到CPU 上进行判断，其余的处理器只能以空闲状态等待同步，这无疑是对计算资源的浪费。 在原有的 DALM 算法中，需要对迭代结果 xk+1 进行求模，判断循环是否结束，有可能会出现上述浪费资源的情况。3.2 CUDA 中 CPU 与 GPU 的协作关系在 CUDA 框架的编程理念中，CPU 作为逻辑处理、流程调度的工作单元，而 GPU 则是 为主要的计算承担者。而 CUDA 采用的是异步工作模式，CPU 和 GPU 是并行工作的。若 CPU 在调用 GPU 处理的数据时，例如发生显存与主存通信拷贝，开发者必须考虑两 者的同步问题，一般的处理方法是调用 cudaThreadSynchronize 函数使得 CPU 与 GPU 达到 同步。在常规算法上，一般逻辑调度的工作较少，CPU 占用率较低，多数时间在于 GPU 的 数据处理及线程间同步与通信上。3.3 延迟 CPU 同步判断前面讲到，由于归并操作中的同步操作下多数计算核心必须空闲等待，造成 GPU 计算资 源的浪费。事实上，在精度要求高、迭代次数较多的情况下，每次迭代所产生的浪费不容忽 视，而且是不必要的。由算法描述得知，判断循环结束的条件并不影响下一步迭代的运行，即 下一个循环的其他运算不必等待向量的求模操作完成。因此，在实现上利用 CPU 延迟判断可 以更有效利用其他资源。具体做法是将算法的同步操作减低至当前有计算的核心数，即其他计算核心在计算结束后 即时释放，继续执行下一步迭代的运算，如下图所示：图 2: 应用 CPU 延迟判断后的 GPU 归并操作示意图 从图中可以看出，如果当前归并操作结束并通知 CPU 作收敛判断时，下一步的迭代运算已经进行了一部分。可以分如下两种情况讨论：1. 如果 CPU 判断后认为迭代应该继续，则已 经进行的操作是有效的，并且继续运行；2. 如果 CPU 判断后认为迭代可以终止，则超前进行 的操作是多余的，运行结束。由于执行一次算法时只会出现一次情况 2，大部分都是出现情况1，因此超前的运算能更充分的利用 GPU 计算资源，并行性更高。需要说明的一点，为了保 证超前的运算有不能破坏结果 xk+1 的存储，超前计算部分只能包含更新 x 以前的运算。4 实验对比根据上述的优化处理，可以在 GPU 上实现了优化后的 DALM 算法，并跟 CPU 上的DALM 进行对比。下面将根据两个平台上的实现进行仿真实验，比较两者的速度。 实验基于如下计算环境：处理器为酷睿 I5 双核处理器，主频为 2.4GHz，内存为 4G 的DDR3(频率 1066MHz)，显卡为 Nvidia GeForce GT 335M，显存为 1GB，拥有 72 个 CUDA 处理器核心，核心频率为 1088MHz，操作系统为 Windows 7 64bit，使用 Visual Studio 2010 及 Nvidia CUDA 5.0 作为开发与运行平台。以下实验数据基于 50 次程序运行的平均统计。表 1: CUDA 下人脸识别中的结果对比（单位：ms）稀疏度 (p/m)矩阵尺寸DALM(CPU)DALM(GPU)0.1300 × 90010581600 × 1800588158900 × 270013472361200 × 360023613190.2300 × 900216122600 × 1800846238900 × 270020313561200 × 36003510481从上表我们可以看到，GPU 的计算速度比 CPU 要快不少，而且随着矩阵规模及稀疏度的增加变得尤其明显，稀疏表示算法在并行平台上有优异的表现。5 总结稀疏表示是一门日益重要的基础学科，其应用范围非常广泛，也存在求解难度。通过增广 拉格朗日乘子法可以求解稀疏表示的原问题和对偶问题。本文通过结合稀疏表示与 CUDA 并 行平台的研究，提出了稀疏表示在并行平台上的改进优化，通过 CPU 延迟判断，令多核心计 算单元的并行带宽得到更充分的利用，进一步提高稀疏表示算法在并行平台上的速度。参考文献（References）1 D. Donoho. Compressed sensing J. IEEE Trans Inform Theory, 2006, 52(4):1289-1306.2 He R, Zheng WS, Hu BG, et al. Two-Stage Nonnegative Sparse Representation for Large- Scale Face Recognition J. Neural Networks and Learning Systems, IEEE Transactions on,2012, 24(1):35-46.3 A. Adler, M. Elad, Y. Hel-Or. Probabilistic Subspace Clustering Via Sparse RepresentationsJ. Signal Processing Letters, IEEE, 2012, 20(1):63-66.4 GeneH. Golub, C.F.V. Loan. 矩阵计算（第三版）M，北京：人民邮电出版社，2011.5 Yang JF, Zhang Y. Alternating Direction Algorithms for L1 Problems in Compressive Sens- ing J. SIAM Journal on Scientic Computing, 2009, 33(1):250-278.6 Nvidia. Nvidia CUDA programming guideOL. 2012.