（信号与信息处理专业论文）基于gpu加速的信号mp稀疏分解.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 信号稀疏分解以其简洁、稀疏、灵活的优良特性成功的应用到信号处理的 诸多方面中，成为信号处理研究的热点之一。匹配追踪算法实现简单、便于理 解，在稀疏分解诸算法中算法复杂度最低，是信号稀疏分解中运用最广泛的算 法。但即使这样，基于m p 的信号稀疏分解依然面临分解速度慢、算法复杂度 高、计算耗时长的问题。 与c p u 相比，g p u 对大量数据的处理能力更加出色。g p u 的存储器带宽 也较c p u 更有优势。g p u 为大量数据的运算提供了新的解决方案，特别是 c u d a 的提出，使g p u 有向通用计算机发展的趋势。 针对c p u 实现信号m p 稀疏分解出现的问题，本文采用n v i d i a 公司发 布的统一运算设备架构c u d a 来进行信号稀疏分解的g p u 加速，提高信号稀 疏分解的运算速度。 首先本文介绍了一维信号稀疏分解的基本原理，特别是基于m p 的信号稀 疏分解算法思想。接着阐述了n v i d i a 公司的g p u 产品c u d a ，并从硬件和 软件两方面介绍了c u d a 编程模型、存储器模型、软件体系、执行模式等。 然后针对基于m p 的信号稀疏分解分解速度慢的缺点，对其采用g p u 进 行加速来实现。在实现的过程中，本文提出了符合硬件特性的内积运算并行方 案及改进方案。与c u d a 库函数中的内积运算函数进行比较，内积并行方案 的运算效率更出色。该方案成功应用到基于m p 的信号稀疏分解中的原子能量 运算、信号或其残差与冗余字典中原子的内积运算中。基于c u d a 平台，本 文对局部运算中冗余字典生成并行实现，提高了字典中原子的生成速度。实验 表明，与c p u 串行运算相比，在待分解信号长度为8 19 2 时，g p u 实现基于 m p 的信号稀疏分解，加速比可达3 7 10 倍。 最后针对g p u 实现基于m p 的信号稀疏分解存在冗余字典过大的问题， 对基于f f t 的信号m p 稀疏分解算法采用g p u 进行加速。在实现过程中，本 文对冗余子字典、快速傅里叶变换及其反变换等局部运算进行g p u 并行实现。 同时本文提出的内积并行运算方案成功运用于字典中原子的能量计算中。实验 表明，在待分解信号长度为16 3 8 4 时，g p u 加速基于f f t 的信号m p 稀疏分 解的速度是c p u 串行实现的1 2 2 9 倍。 关键词：稀疏分解；匹配追踪；f f t ；g p u ；c u d a 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t s i g n a ls p a r s ed e c o m p o s i t i o nh a sb e e ns u c c e s s f u l l ya p p l i e di nm a n yf i e l d s w i t hi t ss i m p l e ，s p a r s e ，n e x i b l ec h a r a c t e r i s t i c s s os i g n a ls p a r s ed e c o m p o s i t i o n b e c o m e so n eo fh o ts p o t si ns i g n a lp r o c e s s i n gr e s e a r c h c o m p a r e dw i t ho t h e r s p a r s ed e c o m p o s i t i o na l g o r i t h m s ，m a t c h i n gp u r s u i ti s e a s i e rt ou n d e r s t a n da n d r e a l i z ew h i c hm a k i n gi tw i d e l yu s e di ns p a r s ed e c o m p o s i t i o n b u tt h e r ea r es t 订1 s o m ep r o b l e m sf o rm pa l g o r i t h m ， s u c ha s h u g ea l g o r i t h mc o m p l e x i t ya n d c o m p u t a t i o n a lc o s t c o m p a r e dw i t hc p u ， g p uh a st h es t r o n g e ra b i l i t yi n p r o c e s s i n gl a r g e a m o u n t so fd a t aa n dm u c hw i d e rm e m o r yb a n d w i d t h i tp r o v i d e sas o l u t i o nf o rt h e 1 a r g ea m o u n t so fd a t ac o m p u t a t i o n w i t ht h ep r o p o s e dc u d a ，g p uh a sd e v e l o p e d f r o mg r a p h i cp r o c e s s i n gu n i tt og e n e r a lp u r p o s eu n i t t h i st h e s i sc o n c e n t r a t e so nt h em a t c h i n gp u r s u i ta l g o r i t h mb a s e do nc p u w e c a r r yo u tf u r t h e rr e s e a r c hf o rm a t c h i n gp u r s u i ta l g o r i t h mb a s e do ng p ut o i m p r o v es p a r s ed e c o m p o s i t i o nr a t e f i r s t l y ； t h i s t h e s i si n t r o d u c e st h eb a s i c p r i n c i p l e o f s i g n a l ss p a r s e d e c o m p o s i t i o n ，e s p e c i a l l y t h ep r i n c i p l e f b r s p a r s ed e c o m p o s i t i o nb a s e d o n m a t c h i n gp u r s u i t t h e nt h i st h e s i si n t r o d u c e sg p uo fn v i d i ac o r p o r a t i o n ， e s p e c i a l l yp a r a l l e lc o m p u t i n gf e a t u r e sw i t hc u d a ，i n c l u d i n gc u d ap r o g r a m m i n g m o d e l ，c u d as o f t w a r es y s t e m ，c u d am e m o r ym o d e l ，c u d ae x e c u t i o nm o d e s a n ds oo n p a y i n ga t t e n t i o n 。t ot h es l o wr a t eo fs p a r s ed e c o m p o s i t i o n ，g p ui su s e dt o a c c e l e r a t ea n dr e a l i z e i nt h ep r o c e s so fr e a l i z a t i o n ， i n n e rp r o d u c tp a r a l l e l c o m p u t i n gs 0 1 u t i o n sm e e t i n gt h eh a r d w a r ef i e a t u r e sh a v eb e e np r o p o s e d 。c o m p a r e d w i t ht h ei n n e rp r o d u c tc u d a1 i b r a r yf u n c t i o n s ，t h es 0 1 u t i o n si nt h i st h e s i sa r e m o r ee f j f i c i e n t t h e nc u d ap l a t f o mi su s e dt og e n e r a t eo v e r - c o m p l e t ed i c t i o n a r y o fa t o m s a n dt h ep r o p o s e di n n e rp r o d u c tp a r a l l e ls c h e m ei ss u c c e s s f u l l ya p p l i e d t ot h ea t o m i ce n e r g yo p e r a t i o n sa n di n s i d ea c c u m u l a t e dc o n l p u t a t i o no fs i g n a l so r i t sr e s i d u a ls i g n a l sw i t ha t o m s n om a t t e ri ti s1 0 c a ld a t ap a r a l l e lc o m p u t i n g ，o rt h e o v e r a l ls i g n a lm p b a s e ds p a r s ed e c o m p o s i t i o n ，t h eo p e r a t i o ne m c i e n c yo fg p ui s m u c hh i g h e rt h a nt h a to fc p u w h e nt h el e n g t ho fs i g n a li s819 2 ，t h es p e e d u po f g p ui s3 7 1 0 a f t e rt h er e a l i z a t i o no fs i g n a lm p b a s e ds p a r s ed e c o m p o s i t i o no ng p u ， 西南交通大学硕士研究生学位论文第1 i i 页 t h e f ei so n ep r o b l e m ：r e d u n d a n td i c t i o n a r yi st o ob i g s i g n a lm p b a s e ds p a r s e d e c o m p o s i t i o nu s i n gf f to ng p uh a sb e e ni m p l e m e n t e d i nt h ep r o c e s s i n g ， o p e r a t i o n so ng e n e r a t i n go v e r c o m p l e t es o nd i c t i o n a r y ，f a s tf o u r i e rt r a n s f b n na n d i n v e r s ef a s tf o u r i e rt r a n s f o mh a v eb e e ni m p l e m e n t e di np a r a l l e l 。a n dt h ep a r a l l e l s c h e m ea l s oh a sb e e n 印p l i e ds u c c e s s f u l l yt oa t o m i ce n e r g yc a l c u l a t i o n w h e nt h e 1 e n g t ho fs i g n a li s 16 38 4 ，t h es p e e d u po fg p ui s12 2 9 k e yw o r d s ：s p a r s ed e c o m p o s i t i o n ；m a t c h i n gp u r s u i t ( m p ) ；f a s tf o u r i e rt r a n s f o r m ； g p u ；c u d a 西南交通大学硕士研究生学位论文第】页 第1 章绪论 1 1 论文研究背景及意义 传统的信号表示理论中，最常用的处理方式是正交线性变换，例如离散余 弦变换、傅里叶变换、小波变换等。对于某些信号，正交线性变换有良好的表 示效果和物理意义，能够解决这些信号的表示问题。但是，自然界是多姿多彩 的，在工程应用中，我们很少遇到单一的理想信号，更多的时候必须面对交织、 杂糅在一起的不同类型的信号混合体。对于这些混合信号，单一的正交基变换 无法进行有效地表达，这是正交基变换无法逃避的局限【l 】。近年来，学者在信 号表示方面的研究有了新的思路。新的理论是：基函数由过完备冗余字典代替， 过完备冗余字典由冗余函数所构造，从过完备冗余字典中自适应的找出少数的 几个符合待分解信号的结构特性的原子，通过这几个原子的最优线性组合，来 逼近原始信号，由此获得信号最简洁的表达。这就是信号的稀疏表示( s p a r s e r e p r e s e n t a t i o n ) 【1 1 。信号稀疏分解的思想首先由m a l l a t 和z h a n g 在小波分析的 基础上提出，他们随后引入了匹配追踪( m a t c h i n gp u r s u i t ，m p ) 算法来实现信号 稀疏分解。信号稀疏分解提出之后引起了人们的广泛关注，成为调和分析和信 号处理领域中的研究热点【2 - 6 1 ，成功的应用于信号去噪【1 1 、信息编码【7 1 、识别【8 】 和压缩9 1 中。 信号的稀疏表示拥有巨大的研究价值和广阔的发展前景。基于m p 的信号 稀疏分解算法的计算复杂度相对其他稀疏分解算法是最小的，但依然十分繁 重。计算复杂度高、运算时间长，是阻碍其产业化推广的关键因素。 中央处理器c p u 在控制单元、运算单元、存储器控制单元中寻求一种平 衡，以求完成复杂的逻辑运算。而图形处理器( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) 是一种高度并行的流处理器，在图形和数据运算上表现出强大的处理能力。相 比c p u ，它使用更多的晶体管作为执行单元，因此其拥有更强大的浮点计算能 力和存储器带宽。在模式识别、图像处理、视频压缩、物理模拟、信号处理、 电磁仿真等很多领域中，人们将大量的串行运算以并行的方式转化成流处理模 式，通过可编程的g p u ，进行加速实现。通常g p u 相比c p u 在运算速度上可 以获得一个甚至几个数量级的加速比。 基于m p 的信号稀疏分解面临的主要问题是生成冗余字典速度慢，内积运 算耗时。而这两大问题，在运算上都符合g p u 的数据并行性。g p u 的并行运 西南交通大学硕士研究生学位论文第2 页 算特性可以为处理这两类问题提供解决方案。利用g p u 强大的并行计算能力， 使用可编程c u d a 进行运算加速，对稀疏分解算法进行快速实现，可以极大 的提高信号稀疏分解的速度。因此基于g p u 加速的信号m p 稀疏分解对理论 研究和工程应用都有现实的意义。 1 2 国内外研究现状 1 2 1 稀疏分解研究现状 19 9 3 年，m a l l a t 和z h a n g 首次提出基于超完备冗余字典( o v e c o m p l e t e d i c t i o n a r y ，也称原子库) 的信号稀疏分解思想【。通过信号在超完备冗余字典上 面的分解，自适应的选取合适的基来线性表示信号，从而获得信号的简洁表达。 在文献【1 】中，作者强调了冗余字典的构成应符合信号本身固有特性，并说明了 超完备冗余字典对信号表示的必要性。 信号稀疏分解思想提出以后，科研工作者沿着几个方向推动信号稀疏分解 的发展：寻找最佳匹配原子的搜索算法【lo 。1 4 】，超完备冗余字典的构造算法 【1 5 艺3 1 ，信号稀疏分解在在实际信号处理中的应用等。 在寻找最佳原子的搜索算法上，o m p 算法( o r t h o g o n a lm a t c h i n gp u r s u i t ，正 交匹配追踪) 瞄4 】是在m p 算法基础上由p a t i 等人在1 9 9 3 年提出的稀疏分解改进 算法。此算法比m p 算法多了一道工序，即对所选原子首先利用格拉姆施密 特正交化方法进行正交化处理。此算法典型特点是迭代有限次后，收敛速度更 快【2 5 2 6 1 。1 9 9 9 年，d d o n o h o 领导的斯坦福小组创造性的提出了基追踪( b a s i s p u r s u i t ) 【2 7 渤1 算法，b p 算法实质上是使用优化方法思想求解模约束的欠定问 题。该算法性能优于m p 算法，但缺点也比较明显，计算量巨大，令人无法承 受。目前此算法还只限于较短信号的理论研究。文献【3 0 】中基于b p 算法进行 改进，提出了核基追踪算法( k e r n e lb a s i sp u r s u i t ，k b p ) 。该算法把核函数和适 应度选择问题有机的运用到基追踪算法中，扩展了基追踪算法的应用范围，此 算法因而运用到高维空间中。2 0 0 6 年，d d o n o h o 等人又提出了分段匹配追踪 ( s t a g e w i s eo r t h o g o n a lm a t c h i n gp u r s u i t ，s t o m p ) 算法。该算法是对o m p 算法 的改进，在牺牲一定稀疏分解的精度前提下，换取运算速度的提高。但无论是 o m p 算法还是s t o m p 算法，在g r a m s c h m i d t 正交化中都增加了大量的运算 量。 在降低算法复杂度方面，基于信号m p 稀疏分解和智能计算的方法相结合， 是一个异军突起的方向。使用智能计算算法后，信号m p 稀疏分解的速度更快， 西南交通大学硕士研究生学位论文第3 页 计算复杂度急剧下降。典型的算法有：遗传算法【3 1 ，3 2 1 ( g a ) 、蚁群算法【33 1 、粒 子群优化算法【3 4 1 、量子遗传算法35 1 、人工鱼群算法【3 6 】等。2 0 0 5 年m a r c of d u a r t e 等人在m p 算法的基础上提出了树形匹配追踪( t r e em a t c h i n gp u r s u i t ， t m p ) 算法【3 7 】，该算法迭代中递减原子的搜寻范围，通过用分层的树状模型表 示冗余字典，进而提高运算效率。s h a n ef c o t t e r 等人进一步改进，提出了树 形正交匹配追踪( t r e e - b a s e do r t h o g o n a lm a t c h i n gp u r s u i t ，t b o m p ) 算法【蹦j 。 k a r a b u l u t ，g z 等人提出正交匹配追踪算法【3 9 1 ( f t b o m p ) 算法，该算法也采用 树型搜索策略。文献 4 0 也是树形追踪算法的相关文献，对冗余字典进行树型 模型集合划分，减小冗余字典的原子总数，提高运算效率。 上述方法均属于弱匹配追踪【4 1 1 ( w e a km a t c h i n gp u r s u i t ，w m p ) ，它们在很 大程度上以牺牲算法精度为代价降低算法复杂度，实质上是用次优解代替全局 最优。文献 4 2 】在w m p 基础上将其与m p 算法有机结合，提出了多原子匹配 追踪算法( m a m p ) ，提高了分解速度，且重构信号的质量也得到了较大的提高。 文献【4 3 基于c u d a 运算平台，对基于f f t 的图像m p 稀疏分解快速算法 进行g p u 并行实现，极大的提高了图像稀疏分解的速度。 基于m p 的信号稀疏分解算法需要处理的关键问题是冗余字典形成速度 慢、内积运算耗时。文献 4 4 和文献 4 5 】中对超完备冗余字典进行集合划分， 形成冗余子字典，子字典中不存在形状相同的一类原子。通过平移冗余子字典 中的原子，实行互相关运算取代单独的一个原子和信号残差的内积运算。然后 在互相关运算上做文章，用线性卷积实现互相关运算，再用快速傅里叶变换 ( f a s tf o u r i e rt r a n s f o m ，f f t ) 实现线性卷积，在重构信号精度基本不变的情况 下此快速算法加快了信号m p 稀疏分解的实现，提高了稀疏分解的运算速度。 但此算法在待分解信号长度较短时，使用第一类算法，分解速度较基于m p 的 信号稀疏分解有明显提高，但如果信号较长时，鉴于计算机的硬件局限，不得 不使用稀疏分解第二类算法时，此算法对信号稀疏分解速度的提高影响有限。 1 2 2g p u 高性能运算特性 19 9 9 年，n v i d i a 公司提出了图形处理器( g r a p h i cp r o c e s s i n gu n i t ，g p u ) 。 g p u 问世后，其性能每年倍翻，发展速度大大超过了摩尔定律。随着g p u 性 能的扩展和提高，其应用扩展到计算密集型的科学计算上，成为了通用计算的 一个有效平台【46 4 7 1 。一个新的研究领域被开辟出来，即基于g p u 的通用计算 ( g e n e r a l p u r p o s ec o m p u t a t i o no ng r a p h i c sp r o c e s s i n gu n i t s ，g p g p u ) 【4 8 】。相比 c p u 的数据运算，g p u 的优势非常明显。其拥有更多执行单元a l u ，浮点计 算能力上是同时期主流c p u 性能的10 倍左右。如图1 1 所示【4 9 1 。 西南交通大学硕士研究生学位论文第4 页 篁 兮 u o 芝 j 囊耳j u n a p rj 她m ”vm 叠y 2 0 0 32 0 0 4 2 0 0 5 2 0 0 82 0 0 7 j u 立 2 0 0 8 图1 1c p u 和g p u 峰值浮点计算能力对比图 g p u 不仅在浮点计算能力上有明显优势，在显存带宽上也较c p u 出色。 g t 2 0 0g p u 的显存带宽为1 4 0 g b s ，达到了同时期主流c p u 最高内存带宽的 5 倍左右，如图1 2 所示【4 9 1 。 8 0 b _ # d - ，浊h g 毒知 6 0 4 0 2 0 o c ； u l t r l 7 n ， 。 歹 一。，e o t te e rn o r t h w d 一_ _ - - 2 0 0 善2 a 0 42 0 口52 0 0 62 0 0 7 图1 2c p u 和g p u 带宽对比图 具有代表性的g p u 产品有n v i d i a 公司推出的统一计算设备架构 ( c o m p u t eu n i n e dd e v i c ea r c h i t e c t u r e ，c u d a ) 模型【4 9 1 ，a m d 公司推出的b r o o k 蓬考【5 0 】 j 口 o c u d a 是一种新的计算架构。它作为一个完整的g p u 通用计算的解决方 案，通过编程，可以对硬件进行直接访问。采用c u d a 来管理g p u 上的硬件 资源，使g p u 作为一个“协处理器”( c o p r o c e s s o r ) ，为大规模的数据并行计算 应用提供了有力条件。c u d a 语言提供了大量的并行运算的指令，使用类c 语 言作为编程工具。使开发人员上手快，易于接受。为开发人员使用g p u 进行 效率更高的大规模数据运算提供了切实可行的解决方案【5 。 西南交通大学硕士研究生学位论文第5 页 1 3 本文的章节安排 针对信号稀疏分解计算量大，计算时间长的问题，本文对基于m p 的信号 稀疏分解算法和基于f f t 的信号m p 稀疏分解快速算法中数据进行并行性分 析。并利用g p u 的加速特性，在n v i d i a 公司的c u d a 架构平台上实现基于 m p 的信号稀疏分解和基于f f t 的信号m p 稀疏分解，提高信号稀疏分解的运 算速度。 具体章节安排如下： 第一章主要介绍课题的研究背景和意义，包括稀疏分解的由来及其发展出 来的各种算法，所存在的问题等。然后介绍了g p u 的发展现状，g p u 相对c p u 的运算优势，重点提及n v i d i a 公司的统一设备运算架构c u d a 。 第二章首先介绍信号稀疏分解中匹配追踪的基本概念，然后阐述了超完备 不相干级联冗余字典，特别是g a b o r 字典的一些特性。最后粗略的论述了信号 稀疏分解的一种快速算法：基于f f t 的信号m p 稀疏分解算法。接着介绍g p u 的相关知识。主要从硬件和软件两方面阐述了c u d a 统一设备运算架构，包 括编程模型、软件体系、存储器模型、执行模式等。 第三章主要利用c u d a 平台，对基于m p 的信号稀疏分解进行g p u 加速。 首先对基于m p 的稀疏分解中的数据并行性做分析，提出了针对局部数据并行 运算的k e r n e l 函数，进而对整体稀疏分解流程进行设计。针对冗余字典生成和 耗时的内积运算，本文提出符合硬件特性的并行方案，并对该方案不断进行优 化和改进。然后通过实验验证字典生成、字典中原子能量运算的加速效应。最 后，使用g p u 加速整体的信号m p 稀疏分解，在重建信号质量相差无几的情 况下，测试其加速比。实验结果表明，在信号长度为8 19 2 的情况下，使用g p u 实现运算速度是c p u 实现速度的3 7 10 倍。如果待分解信号更长，g p u 运算 的加速效应会更明显。 第四章主要利用c u d a 平台，对基于f f t 的信号m p 稀疏分解进行g p u 加速。同基于m p 的信号稀疏分解g p u 实现一样，先分析基于f f t 的信号m p 稀疏分解中数据运算的并行性，设计局部数据并行运算的k e r n e l 函数，进而提 出整体稀疏分解算法的流程。然后本文对冗余子字典生成、f f t 运算进行串行 和并行速度测试，验证g p u 实现的加速效应。最后，利用g p u 实现整体的基 于f f t 的信号m p 稀疏分解算法，并与c p u 实现进行运算效率比较。实验结 果表明，在信号长度为16 3 8 4 时，g p u 的并行处理优势发挥出来，运算速度是 c p u 的l2 2 9 倍。如果待分解信号更长，则g p u 运算的加速效果会更好。 西南交通大学硕士研究生学位论文第6 页 第2 章信号m p 稀疏分解和c u d a 运算平台 匹配追踪算法在信号稀疏分解中应用最广，算法复杂度最低。本章主要介 绍基于m p 的信号稀疏分解方法及信号质量评价标准。然后介绍了本文所使用 的超完备冗余字典。最后粗略的介绍了基于f f t 的信号m p 稀疏分解快速算法。 不同公司设计的通用计算g p u 产品不同。本文使用n i v d i a 公司提供的 c u d a 运算平台，并从硬件和软件两个方面对其展开说明。这是因为c u d a 开发语言以c 语言为基础，是c 语言的扩展，易于开发。c u d a 编程模型易 于编程实现。 2 1 信号m p 稀疏分解算法 2 1 1 信号m p 稀疏分解算法思想 设待研究信号厂的长度为，与其相对应的超完备冗余字典为d = 毋) 旧， 其中字典中原子g ，与信号厂拥有相同的长度。原子岛满足i | 毋i l = 1 且由参数组y 决定。由字典的超完备特性可知，7 所代表的参数组个数远大于信号长度。 冗余字典d 中原子总数用厶表示，则有厶。采用匹配追踪算法实现的信 号稀疏分解表述过程如下【1 】： 首先，在超完备冗余字典中找出与信号厂最搭配的原子鼠，满足如下公 式： 胁g ) i - 辈l ( 厂，g ，) l ( 2 - 1 ) 其中( 厂，鼠) 是待分解信号和超完备冗余字典中原子的内积。信号厂可 以用既上面的分量和残差共同表示出来，即： 厂= ( 厂，g ) g 托+ 尺1 厂 ( 2 2 ) 其中( 厂，g 托) g 是信号厂在最佳原子鼠上的投影，r 1 厂是最匹配原子与信号 进行匹配后的信号残留。尺1 与彰。符合正交性，即： 2 = 陋鼠) | 2 + l i r l 州2 ( 2 3 ) 如果要使公式( 2 2 ) 中的( 厂，g ) 既是的最佳逼近，则残留能量月1 必须最 小。实际上就是要使投影分量 厂，鼠) 最大，即要使公式( 2 1 ) 成立。要使投影分 西南交通大学硕士研究生学位论文第7 页 量最大，实际上就是要在超完备冗余字典中找出最靠近信号厂的单位向量。寻 找最佳原子过程就是m p 算法中匹配追踪的实现。 对残留信号刷厂继续分解，分解过程与对原始信号的分解方式相同。即： r 厂= ( r 。厂，g h ) + r “1 厂 ( 2 4 ) 其中g ，满足以下公式，即： 弦厂，既) 1 2 磐弦，瓢) l ( 2 5 ) 8 r 厂1 1 2 = i ( 尺厂，g h ) 1 2 + 8 r 七+ 1 ，1 1 2 ( 2 6 ) 结合公式( 2 2 ) 、( 2 3 ) 、( 2 - 4 ) 及( 2 6 ) ，并经过日步分解可得： 厂= ( r 厂，g h ) g h + r 日厂 ( 2 - 7 ) 并且满足能量守恒，即： 2 ：兰l 1 2 + i i r 片卅2 ( 2 8 ) i l 厂8 2 = = l 1 2 + i i f ? 片厂0 2 ( 2 8 ) 公式( 2 - 7 ) 里面，r 厂为原始信号厂分解日次后的残留。由公式( 2 5 ) 可知， 随着一次次的分解，残留信号r 厂会越来越小，最后趋近于0 。 但实际上，只需要少数几个原子就可以重构出原始信号厂的主要成分，即： 厂( 尺厂，g h ) g 段 ( 2 9 ) 其中日，由式( 2 9 ) 和日体现出了信号m p 稀疏分解的思想。 2 1 2 信号质量评价标准 评价信号m p 稀疏分解的质量从两个方面入手，一个是分解速度，另一个 是重构信号的效果。重构效果的评价标准有两个，一是均方误差( m e a ns q u a r e e r r o r ，m s e ) 。二是信号与其噪声的功率之比( s i g n a lt 0n o i s er a t i o ，s n r ) 5 4 1 。 信号m s e 表达式如下： ，一l 蚝= 寺 邝) 一厕】2 ( 2 1 0 ) v f 卸 信号s n r 表达式如下： 西南交通大学硕士研究生学位论文第8 页 = 1 0 l g 专窆 ： v i = o 专瓤旷厕 2 ( 2 - 1 1 ) 在公式( 2 1 0 ) 、( 2 1 1 ) 中厂( f ) 代表原始信号f 点的值，厂( f ) 代表重构信号第f 个点的值，代表原始信号和重构信号的长度。本文主要使用信噪比来评价信 号，信噪比越大，重构信号质量越好。 、 2 1 3 超完备冗余字典 往往具有良好时频特性的冗余字典更容易抓住信号的特性，更能够稀疏的 表示出原有信号。本文使用文献 3 】中超完备冗余字典的形成方法，这种超完备 冗余字典在许多文献中被应用，具有一定的代表性，由g a b o r 原子构成。一个 高斯窗函数经过平移变换、尺度变换后调制，形成一个g a b o r 原子。即： g ，( r ) ：；g ( 竺) c o s + w )( 2 1 2 ) qs s 其中g ( f ) = p 一妒为高斯窗函数，y = ( s ，“，v ，w ) 是时频参数。其中s ，“，w 分别为尺 度因子、位移因子、频率因子和相位因子。其中时频参数的离散化方式如下： 厂= ( 口7 ，p 口7 “，勋一7 孝，f w ) ，其中参数的设置为： 口= 2 ， 善= 万， “= 1 2 ， w = 石6 ， 0 p 2 7 “一l ，0 歹1 0 9 2 ， 0 七 2 7 ”，o f 1 2 。 2 1 4 基于f f t 的信号m p 稀疏分解 文献 4 4 和文献 4 5 中提出了基于f f t 的信号m p 稀疏分解快速算法及其 改进算法。其基本思想是将信号或者信号残差与原子的内积运算转换成互相关 运算，然后将互相关运算转换成线性卷积或者循环卷积。然后对线性卷积或者 循环卷积通过快速傅里叶变换( f a s tf o u r i e rt r a n s f o 珊，f f t ) 来实现。 基于f f t 的信号m p 稀疏分解快速算法起源于冗余字典的集合划分。集合 划分的由来是因为决定一个g a b o r 原子的因素有四个：s ，”，1 ，w 。其中参数组 ( s ，v ，w ) 决定原子波形形状，在参数组( s ，v ，w ) 不变的前提下，可以获得具有相 同波形的一类原子，”决定一个g a b o r 原子的位置。通过对超完备冗余字典的 集合划分，可以用一个原子氍代表一个等价超完备冗余字典的子字典，由此 大幅度减少冗余字典中的原子个数，降低计算复杂度。文献 5 2 】中实验结果分 析得出，集合划分方法使空间复杂度降低到原有的1 1 0 。 西南交通大学硕士研究生学位论文第9 页 计算信号或信号残差与原子的内积( 尺厂，g 。) 占用了寻找最佳原子的大部 分时间。对于某类g a b o r 原子g ，参数组以( s ，v f ，) ，如果让“，选遍所有的 【o ，一l 】，实际上就重现了冗余字典子字典中所有的原子。“，在0 到一1 之间 连续取值时，内积运算( 尺。，乳) 就可以转化成一次互相关运算r 僻厂，鼠) 。运 算转换后，运算效率大大提高。 如果对g ，逆置，则互相关运算就可以使用线性卷积或者循环卷积实现。 而f f t 运算又可以实现线性卷积和循环卷积，这就是基于f f t 的信号m p 稀 疏分解思想。由文献 4 4 可知，计算速度能够获得1 2 个数量级的提升。 2 2 基于c ud a 的g p u 通用计算 2 2 1g p u 体系架构 从微观体系架构来看，c p u 和g p u 是根据不同的应用要求来设计的。c p u 的体系架构在于寻求逻辑指令执行和数据运算的平衡。g p u 则弱化控制单元， 使用了更多的晶体管来侧重大量数据的运算。因此，g p u 在处理逻辑事务上有 其先天的不足，但在加、减、乘法运算中有明显优势，往往在运算效率上可以 获得高于c p u 一个、两个甚至几个数量级的加速比。许多公司都提出了自己 的g p u 架构体系，如n v i d i a 、a m d 等。n v i d i a 公司是g p u 的提出者和先 行者，其g p u 产品为c u d a 。基于c u d a 的g p u 简略的硬件体系架构模型如 图2 1 所示【49 1 。 图2 1 基于c u d a 的g p u 体系架构 【1 】将数据从主存传送到全局存储器。主存位于c p u 端，全局存储器位 于g p u 端。 【2 借助c u d a 运行时a p i 或驱动a p i ，c p u 发出处理指令的信息。 【3 g p u 计算单元中每一个流处理器s m 开始并行的执行任务。 4 将计算结果通过全局存储器再回传到主存中，一次运算数据传输完 成。 西南交通大学硕士研究生学位论文第l o 页 2 2 2c u d a 编程平台概述 目前，主机一设备模式【4 9 】是基于g p u 的通用计算模式。c p u 作为主机端， 专注于处理逻辑性强的串行计算任务；g p u 作为协处理器端，专注于处理具有 并行特性的数据运算任务。c p u 和g p u 各司其职，分工协作。由主机端串行 代码和设备端核函数有机组合，构成了完整的c u d a 程序。命令由c p u 端通 过k e r n e l 核心函数发布，实际数据运算在g p u 端执行。如图2 。2 所示【4 9 1 。 串行代码 h o s t 端串弦代码运行 d e v i c e 端g r i do b 1 0 c k ( o 3 ) 核心函数 7 l b l o c k o ，o ) i 8 l o c 蛾埘1 l b l 。c k ( 2 ，o ) t 1 1 r e a d ( o ，o )t h r e a d ( 1 ，o )t h r e a d ( 2 o )t h r e 8 d ( 3 ，o ) 恤。c k ( o ，1 ) l b l 。c k o ，2 刈b l 。c k ( o 3 ) t h r e a d ( o 。1 )t h r e a d ( 1 ，1 )t h r e a d ( 2 ，1 ) t h r e a d ( 3 ，1 ) 串行代码 h 。s t 端串行代码运行 、 t t h r e a d ( 0 。2 )t h r e a d ( 1 ，2 )t h r e a d ( 2 ，2 )t h r e a d ( 3 ，z ) d e v i c e 端g r i d1 t h r e a d ( 0 3 )t h r e a d ( 1 。3 )丁h r e a d ( 2 ，3 )t h r e a d ( 3 ，3 ) 核心函数 网匝面习 匦巫 圆函 图2 - 2c u d a 编程模型 其中每个b l o c k 还可以细分，我们以g r i d0 中b l o c k ( 0 ，3 ) 为例。线程t h r e a d 是并行计算的最小执行单元。由图2 2 可知，一个k e r n e l 中的线程可以使用最 高为三维的索引来标示。标示的过程是通过内建变量t h r e a d i d x 和b l o c k i d x 来 实现。此方式可以简洁明了的对向量、矩阵和空间进行数据划分。索引使用的 是d i m 3 类型，即基于u i n t 3 的矢量类型。而u i n t 3 是由三个u n s i g n e di n t 型变 量所组成的结构体类型。 k e m e l 函数的完整的执行配置形式是： 。其中各参数 的含义如下。参数d g 为d i m 3 类型，定义整个块的尺寸大小和维度，用 d g ( d g j ，风y ，1 ) 来表示。参数d 6 和d g 也是d i m 3 类型，定义一个b l o c k 的尺寸 大小和维度，用d 6 ( 助工，d 6 y ，d 6 z ) 来表示。参数胍用来配置每个b l o c k 中可以 动态分配的共享存储器大小，这是个可选参数。参数s 也是一个可选参数为 c u d a s t r e a mt 类型。，也可以不填写，默认是0 号流，初始值也为o 。 作为一个完整的计算架构，c u d a 包含硬件和软件两部分。软件部分由 c u d a 库函数、驱动程序、运行时a p i 、编译工具等组成。如图2 3 所示”引。 西南交通大学硕士研究生学位论文第11 页 图2 3c u d a 软件体系 c u d ac 语言是c u d a 的核心。通过启动内核函数，来管理g p u 上的硬 件资源。而启动内核函数，必须以c u d a 的a p i 为桥梁。运行时a p i 和驱动i a p i 可以实现相同的功能，但两者不能混合调用。 g p u 中的最小执行单元t h r e a d ，可以访问自己的私有寄存器和局部存储 器。每个b l o c k 中所有t h r e a d 拥有一块共享的存储器。共享存储器的使用是 c p u 和g p u 最主要的区别之一，在g p u 体系结构中拥有重要的作用。因为 g p u 中流处理器访问共享存储器速度和访问寄存器速度相当，用户将数据首先 存入共享存储器中，可以减少访问延时。全局存储器被每个g r i d 中的全部线 程都共同拥有。全局存储器又称显存，是主机端和协处理器端实现数据交互的 纽带。g p u 计算单元中，有许多“计算核心”流多处理器( s t r e a mm u l t i p r o c e s s o r ， s m ) 。每个s m 中包含8 个标量流多处理器( s t r e a mp r o c e s s o r ，s p ) 。如图2 4 所 示【4 舛。 图2 4c u d a 计算单元简图 西南交通大学硕士研究生学位论文第1 2 页 一个s m 中有8 个s p ，其中四个为一组，实质上组成了两个4 d 的s i m d 处理器。此外，每个s p 里面还有一些寄存器、共享存储器、纹理存储器和常 数存储器。在实际执行c u d a 程序时，每个s m 对应一个b l o c k ，每个s p 对 应一个t h r e a d 。b l o c k 在微观上体现为许多更小的w a r p ，即线程束。在硬件中 程序以w a r p 为单位执行。3 2 个线程组合成一个w a r p ，其中16 个为一组以 h a l f - w a r p 为单位执行。 在s i m t 模型中，只有运用分支，才能从微观上控制某个线程的操作。而 分支的使用，又会使g p u 运算效率急剧下降。c u d a 以w a r p 为单元来执行， 一个w a r p 中线程执行指令是一样的，分支性能就可