并行压缩论文（通用5篇）
并行压缩论文 篇1
并行计算是指同时使用多种计算资源解决计算问题的过程, 用多个处理器并发执行计算。数据压缩算法需要用大量的处理器来分析编码数据, 使其转换成更小的存储形式, 这样就迫切需要并行数据压缩技术来提高压缩速度和增大压缩比, 尤其是在信息量急剧增大的今天, 重要性不言而喻。本文主要是介绍了基于bizp2的并行数据压缩技术, 分析其如何实现快速数据压缩, 提出在CUDA架构上利用GPU实现基于bzip2的并行数据压缩, 以达到更快的压缩速度和更大的压缩率。
1 bzip2数据压缩技术
bzip2采用Burrows-Wheeler块排序文本压缩算法和Huffman编码方式压缩文件, 压缩率一般比基于LZ77/LZ78的压缩软件好得多, 其性能接近PPM族统计类压缩软件, 而且速度较快。本文采用开源的bzip2压缩工具, 相比其他工具, 采用BWT算法的bzip2压缩工具已经可以达到很好的效果。BWT算法它与以往所有通用压缩算法的设计思路都迥然不同, 其核心思想是对字符串轮转后得到的字符矩阵进行排序和变换, 大致分为3个步骤:1.排序变换;2.解压变换;3.输出原字符串。
为了提高压缩速度和压缩比, 文献[3]提出在共享内存架构上实施并行BWT算法。主要有两种并行化BWT算法的方法:1.并行排序算法, 因为在BWT算法中, 排序占用时间较长, 所以在并行机上实施排序算法能大大减少排序所占时间;2.使用更多的块, 由于BWT算法需要比输入数据多10倍的存储空间, 将数据拆分成很多独立的块, 各个块在并行机上独立压缩, 最后再实现各块的汇总, 这需要很大的内存空间。并行化BWT算法由此引发了pbzip2的提出。pbzip2也是采用把数据分成多个块的方法, 一次读入整块数据, 采用FIFO队列系统的生产者/消费者模型。队列的容量取决于pbzip2采用的处理器的数目, 这样可以很好协调速度和所需内存之间的关系, 同时pbzip2采用的BWT算法减小了块间通信对压缩速度的影响。文献[3]表明在多处理器系统上使用并行bzip2可以达到很好的压缩效果, 大大提高了压缩速度。
下面来看看串行bzip2和pbizp2的流程示意图如图1, 图2所示。
2 CUDA上实现数据压缩
2.1 CUDA上LZ77数据压缩
统一设备架构 (CUDA) 是NVIDIA公司提出的一个基于GPU通用计算的开发环境, 它针对GPU多处理单元的特性, 通过并行计算提高大规模运算的速度。CUDA架构的出现, 引出了在CUDA架构上实现数据压缩的研究, 试图利用GPU的特性, 提高压缩性能。目前, 已经实现了在GPU上JPEG的压缩, 主要是充分利用了CUDA架构的优势———在共享内存上进行大批量数据密集并行操作, 而它的瓶颈是执行控制逻辑和处理存在数据依赖时速度很慢。如果不能充分利用CUDA架构的优势, 在GPU上执行反而会降低压缩性能。因为JPEG图像压缩中各图像是独立的, 很少存在数据依赖问题, 这符合CUDA架构优势, 可充分利用CUDA在处理计算密集型方面的优势, 而且JPEG在GPU上编码后, 在CPU上执行Huffman编码, 这样GPU和CPU密切配合起来, 协同工作;无损编码在GPU上执行, Huffman编码在CPU上执行, 提高了压缩速度。这是并行计算技术的又一重大突破。
那么在GPU上实现数据压缩是否能比在多处理器的CPU上用pbzip2获得更好的性能, 目前已有众多科研者在研究这一问题。斯坦福大学研究者研究实现了用LZ77算法在GPU上的数据压缩, 可以达到比在多处理器上多线程CPU上并行数据压缩高4倍的压缩比, 但由于LZ77算法含大量的内存比较和I/O操作, 不符合CUDA的架构特性, 所以在GPU上执行数据压缩的速度不如CPU上。其中通过增加CPU和GPU间的内存带宽是更好发挥GPU特性的一种方法。
由图3和表1可以看出, 在CUDA上执行的LZ77数据压缩算法性能不如在CPU上并行压缩达到的速度快, 主要原因是因为算法中涉及到的控制分支结构和数据依赖本身决定了其不符合在CUDA架构, 不适合在GPU上实现提速。没有充分利用CUDA的强大的向量处理能力, 而在并行CPU上多线程处理能获得更块的压缩速度是因为各线程独立处理分支, 不用线程间通信引起的依赖关系。
2.2 CUDA上并行bzip2数据压缩
如今海量数据压缩, 需要更快的速度, 更高的压缩比, 那么既然在多处理器CPU上利用并行bzip2能达到很好的压缩效果, 能否在GPU上实施该并行数据压缩算法, 达到比多处理器CPU上并行bzip2更快的压缩速度和更高的压缩比。bzip2工具主要采用BWT算法和Huffman编码, 文献[3]BWT算法中都是将数据分成很多独立的块, 并不存在很多的数据依赖和控制结构, 所以在GPU上执行会比在多处理器的CPU上并行执行速度要快, Huffman编码由于算法中存在数据依赖和控制结构, 故选择在CPU上执行, GPU和CPU密切配合, GPU作为CPU的协处理器, 结合算法本身特性, 达到很好的数据压缩效果是可行的。经调研, 也有研究者在付诸实施, 但是还未实现。现阶段, 人们已经提出很多方法来实现高速数据压缩, 例如增加GPU和CPU间的内存带宽, GPU植入共享内存多处理器, 都能提高数据压缩的速度。
3 结束语
本文介绍了基于bzip2的并行数据压缩技术, 提出了在GPU上基于并行bzip2的数据技术以及其存在的问题, 接下来的工作是研究并行bzip2工具以及其中的算法BWT是否能充分利用CUDA架构在GPU上来优化数据压缩效果。若不合适, 能否改进算法, 使其充分发挥CUDA架构的优势。研究如何充分发挥GPU和CPU的特性, 达到比在并行多处理器CPU上实施并行bzip2更好的数据压缩效果。寻找适合CUDA架构的压缩算法, 期待达到比并行多处理器CPU数据压缩更好的压缩效果, 将此压缩技术运用到海量数据压缩中, 比如医学图像处理, 地震数据管理等。
摘要：在信息爆炸的今天, 提高海量数据压缩比和压缩速度已成为一种迫切需求。该文主要通过介绍数据压缩的背景知识、数据压缩的现状, 详细分析了基于bzip2的并行数据压缩技术及其并行实现高速数据压缩的算法, 提出在CUDA架构上利用GPU实现并行数据压缩的方法。结果表明, 该文提出的方法相对于在CPU上并行压缩, 虽然压缩速度降低但压缩比却提高了, 这体现了CUDA的优势和局限性。
关键词：并行计算,数据压缩,pbzip2,GPU
参考文献
[1]Wu Leiwen, Storus M, Cross D.CUDA WUDA SHUDA:CUDA Compression Project[D].Stanford University, 2009.
[2]Pankratius V.Parallelizing BZip2:A Case Study in Multicore Software Engineering[D].University of Karlsruhe, 2009.
[3]Jeff Gilchrist Elytra Enterpises Inc.Parallel data compression with BZip2[J].Computer, 2007
[4]DONG Luo.Study on application of parallel computation on CUDA[J].Information Technology, 2010.
并行压缩论文 篇2
压缩感知(Compressed Sensing,CS)理论采用非自适应线性投影来保持信号的原始结构,以远低于Nyquist频率对信号进行采样,通过数值最优化算法准确重构出原始信号[1]。它已广泛应用在遥感图像处理领域中的各个方面,如图像去噪、融合、压缩等。然而,由于遥感图像具有高分辨率、多时相等特点,存在数据量大,使得利用压缩感知理论在遥感图像处理中计算量很大,传统CPU的串行处理运行时间长,无法实时/准实时恢复出原始图像。
为加快算法的处理速度,人们开始尝试多种方法,主要有CPU多线程的并行处理和基于硬件的并行加速[2,3,4,5]。这两种方法虽然都能提高一定的加速比,但也存在一些不足。如采用CPU多线程进行加速,由于操作系统的流水线作业调度方式和CPU本身在浮点运算上的限制,处理速度提升有限;在采用硬件加速方面,研究人员需要对相对复杂的硬件内部结构有十分深入的研究,故存在设计复杂、开发周期长等问题。
最近几年,新提出的图像处理器( Graphic Processing Unit,GPU) 采用相对简单的控制逻辑,大量晶体管被用于算术逻辑单元(Arithmetic Logic Unit,ALU) 参与数据处理,凭借其强大的计算能力和卓越的性价比,在并行计算性能上带来了很大的突破[6]。如“天河一号A”采用CPU + GPU的混合计算架构,其峰值速度为4700TFlops,持续速度为2566TFlops( LINPACK实测值),曾在2010 年11 月获得全球速度最快超级计算机的头衔,它的成功已经充分证明了GPU在数据计算方面的优势。因此,利用GPU的并行加速来实现数字图像处理为遥感领域提供了更为广阔的应用空间。
目前,已有相关人员将GPU引入到压缩感知领域中。如Calgary大学的Andrecut等人实现了匹配追踪(Matching Pursuit,MP)算法的GPU并行化[7]。陈帅、代媛分别采用CUDA(Compute Unified Device Architecture,统一计算架构) 编程语言对正交匹配追踪(Orthogonal Matching Pursuit,OMP)算法进行并行化设计,提高了SAR图像重构和苹果图像重构的速度[8,9]。Yong Fang等人基于GPU实现了压缩感知算法的并行化设计,速度提升了38 倍左右[10]。耿旻明基于GPU设计了阈值迭代重构算法的并行化,也提高了微波成像的速度[11]。从实验结果来看,这些并行算法都取得了较好的性能,说明GPU对提高重构算法处理速度很具有优势。而本文研究的重构算法是压缩感知匹配追踪算法(Compressive Sampling Matching Pursuit,Co Sa MP),它是在OMP算法的基础上衍化而来,其主要思想是在每次迭代的过程中不断的更新索引集,同时引用了具有回溯的顺序编码思想。Co Sa MP算法易于实现,并且原子选择机制引入了回溯思想,所有原子都可以自由添加或者移除,同时又结合了凸优化的特性,具有良好的稳定性和鲁棒性[12]。相较于文献[7 - 10]研究的贪婪重构算法,Co Sa MP算法体现出较强的抗噪干扰能力,提高了信号的重构效果。目前,对于CoSa MP重构算法在GPU上的并行研究还很少,因此,本文采用CUDA编程模型对Co Sa MP算法进行并行化研究,加快算法的处理速度。
1 CUDA简介
2007 年6 月,NVIDIA公司推出了一种专为GPGPU( General Purpose GPU,通用计算图形处理器)设计的应用开发平台CUDA,其包含C /C + + 软件开发工具并兼容传统的C /C + + 编译器、函数库和硬件抽象机制,彻底改变了GPGPU并行计算的命运[13]。在对相关算法进行并行设计时,采用CUDA编程模型只需编写相应并行代码而不必考虑GPU硬件细节,其编程得到了简化,CUDA为开发者有效利用GPU的强大并行计算能力提供了有利的条件。CUDA编程模型发展相对成熟,拥有丰富的文档资源,是目前应用最为广泛的GPU通用计算开发平台。
CUDA的体系架构主要包含三个部分:开发库、运行期环境和驱动。开发库是基于CUDA技术所提供的应用开发库,如CUFFT(离散快速傅立叶变换)和CUBLAS(离散基本线性计算) 的实现。这两个数学运算库所解决的是典型的大规模的并行计算问题,也是在密集数据计算中非常常见的计算类型。开发人员在开发库的基础上可以快速、方便的建立起自己的计算应用。运行期环境提供了应用开发接口和运行期组件,包括基本数据类型的定义和各类计算、类型转换、内存管理、设备访问和执行调度等函数。由于目前存在着多种GPU版本的NVIDIA显卡,不同版本的GPU之间都有不同的差异,因此驱动部分基本上可以理解为是CUDA - enable的GPU的设备抽象层,提供硬件设备的抽象访问接口。
2 压缩感知重构算法
压缩感知理论主要包含三个关键部分:信号稀疏表示、压缩采样和算法重构三个部分。其理论框架如图1 所示。
信号的稀疏表示是压缩感知理论应用的一个重要前提,因为它直接影响到解码端重构算法所需的时间和重构的精度。假定原始图像为a ∈ RM* N,在某种稀疏基 Ψ = [ψ1,ψ2,…,ψn]下的稀疏表示为X ∈ RM* N,其稀疏度为K,即包含非零的个数。可用公式表示为:
在压缩采样部分,并不是直接对X进行压缩采样,而是通过观测矩阵 Φ 将信号从高维到低维的投影。用公式表达如下:
信号重构是压缩感知算法的关键部分,其目的是实现从少量测量值中近似精确地重建出原始信号。但是在压缩感知理论中,由于信号X是稀疏的,所以就转化为求解最小l0范数的最优化问题,从而就能用部分测量值Y以较高的概率重构出原始信号X ,即式:
式中:0 范数指的是0 元素的个数。由于上式是欠正定的,无法直接由观测值Y来重构系数X。但当观测矩阵与稀疏系数不相关时,满足了RIP条件,理论上稀疏系数Y的精确重构就可以通过求解最优l0范数问题来解决的。
目前重构算法主要包括两类:贪婪算法和凸优化算法。贪婪算法是通过选择合适的原子并经过一系列逐步递增的方法实现信号矢量的逼近,此类算法主要包含匹配追踪算法、正交匹配追踪算法、压缩感知匹配追踪算法等。凸优化算法是将0 范数用1范数代替,通过线性规划求解的,此类算法主要包含梯度投影法( Gradient Projection,GP)、基追踪法(Basis Pursuit,BP) 等。目前应用较多的是贪婪算法,基于上述分析,本文选择的是Co Sa MP重构算法。
采用Co Sa MP算法对观测采用矩阵Y进行重构,即将矩阵Y的每一列都采用Co Sa MP算法进行重构,则可精确重构出。Co Sa MP串行算法具体描述可以分为以下几步:
初始化: r0= y ,,索引集,迭代次数n = 1。
①计算信号代理,计算余量r和高斯随机矩阵Φ 的每一列的内积gn= ΦTrn -1。
②合并支撑集,Λ = { gn中绝对值最大的2K个元素},更新索引集 Γn= Γn -1∪ Λ。
③利用最小二乘法计算信号估计量,
④剪切信号,选出xn中最大的K个元素,完成信号索引集筛选。xk{xn中最大的K个元素}。
⑤更新残差,得到rn= y - Φxk,检验迭代停止条件:判断是否满足 ‖rn‖2≥ ‖rn -1‖2,若满足则停止迭代,输出
3 并行化设计与实现
3. 1 并行化分析
在对Co Sa MP算法进行并行设计时,首先需要对串行算法进行热点分析,找出算法的性能瓶颈。本文采用time. h库提供的clock()函数在串行算法中插入时间点,统计各步骤的运行时间,并计算各步骤占总运行时间的百分比。据压缩感知算法的描述,将算法细分为以下几个步骤:①计算信号代理;②从计算结果中选出2k个较大值位置作为新添加的支撑集;③合并支撑集;④获取新的信号估计量;⑤信号索引筛选;⑥更新残差、确定迭代停止条件。采用三种不同大小的遥感图像进行测试,结果表明,算法运行时间主要集中在步骤④,其次是步骤①和步骤 ⑥,以512 × 512 图像大小为例,分别为91. 82% ,1. 92% ,3. 49% 。这三步骤运行时间占串行程序总运行时间的百分比为97. 23,可以表明这些步骤是串行算法的性能瓶颈所在。
得到算法的性能瓶颈,接下来就需要分析这些步骤的可并行性。步骤①是计算相关度,完成矩阵与向量乘法的计算。步骤④是估计新的信号,主要是计算最小二乘法。步骤⑥是更新残差,主要是矩阵向量乘法、向量的模等函数的计算。这些步骤都是矩阵、向量运算,元素相关性小,非常适合在GPU上进行实现。因此,为加速Co Sa MP算法的处理时间,需对步骤①、④、⑥在GPU平台上进行并行化设计。
3. 2 并行化实现
根据Co Sa MP算法的并行化分析和GPU硬件特性,对Co Sa MP算法并行设计流程图如图2 所示。
从上面分析可知,算法主要是对一些矩阵操作进行并行化设计,由于CUDA自身已提供了矩阵运算库———CUBLAS库,此运算库是专门针对NVIDIA显卡进行设计的,具有很好的计算性能,因此,本文中的某些矩阵运算并行化实现可直接调用CUBLAS库提供的相应函数。根据并行算法流程图,对于Co Sa MP算法并行实现主要分为以下步骤:
①首先对GPU平台进行初始化,查看平台上的NVIDIA显卡属性,调用cuda Set Device ( ) 函数确定使用的GPU显卡。由于并行处理中需要用到CUBLAS库,在使用前需调用cublas Create ( ) 函数对CUBLAS库内容进行初始化。然后在GPU上调用cuda Malloc() 函数分配内存,并采用cuda Memcpy()将所需的数据从CPU复制到GPU上,为后续的并行处理做准备,最后设置循环起始迭代步数n = 1。
②在GPU上完成相关度计算,即gn= ΦTrn -1的乘积。通过调用CUBLAS库提供的cublas Dgemv()函数实现矩阵向量乘法,该函数实现的功能是y = alpha* op( A) * x + beta* y,通过此函数并行计算得到向量gn。由于选出gn中最大的2K个元素这步计算量很小,且包含条件判断,因此将此步在CPU上计算,并将结果 Λ。和上一次循环得到的Γn -1合并为向量 Γn,将传到GPU,为后续的数据做准备。
③在GPU上完成矩阵扩充操作,得到矩阵。创建内核函数Mat Col Copy Mat Kernel( ),输入参数为矩阵A 、向量index(Γn) ,输出参数为矩阵B ,即将矩阵A中某些行( A中的某些行是指保存在向量index的行索引号对应的矩阵A的行) 复制到矩阵B中。每个工作组复制完成矩阵一行的复制,工作组中的工作项负责对应行中元素的复制。伪代码为:
④并行处理最小二乘法,获取新的估计信号xn。最小二乘求解的解为。其中调用cublas Dsyrk()和cublas Dgemv()函数分别计算。对于最小二乘法计算现在只需求解线性方程Axn= a,由于矩阵B是对称正定矩阵,一般采用Choleksy分解。对于矩阵A ∈ RN* N可表示为B =LLT,其中L为N* N的上三角矩阵。Axn= a则可转换成求解Lz = a与LTxn= z ,通过调用两次三角函数cublas Dtrsm()则可求出xn的值。
对于Cholesky分解的串行实现,目前主要有常规求解方法和分块求解方法,由于常规求解方法中存在大量的数据依赖关系,不适合在GPU上进行并行实现,因此,本文采用分块求解方法。参考Lapack库里提供的分块Cholesky分解方法,在GPU上的处理流程如图3 所示。
从图中可知,对于矩阵进行Cholesky分解是按块t的大小从左到右依次进行处理,根据上一次计算得到矩阵A1和B1来更新矩阵A2和B2的值,直到整个矩阵完全分解。对于Cholesky具体设计,首先设置合适的t,从循环1 到n /t完成步骤① - ④,具体步骤如下:
①更新A2的值,采用公式A2= A2- CCT进行计算,此步在GPU上进行处理,调用函数cublas Dsyrk()。
②对A2进行Cholesky分解,公式为A2= LLT,由于A2较小,不适合在GPU上进行处理,因此将A2传到CPU上常规的choleksy分解,将分解结果传到GPU上。
③对矩阵B2采用公式B2= B2- DC进行处理,调用cublas Dgemm()函数进行实现。
④更新矩阵B2,公式为B2= B2/ A2,此步调用三角函数cublas Dtrsm()。
根据上述步骤,实现Cholesky分解的编码,创建内核函数:void cholesky_block ( double * A,int n,double * work),其中输入参数为矩阵B、work,其中work用于存放中间变量,即子矩阵A2,输出参数为矩阵A。其函数伪代码如下:
⑤信号剪切操作是从xn中选出最大的K个元素保存为 Γn -1,向量xk为。此步在CPU上计算,将结果复制到GPU。
⑥通过公式rn=y-Φxk,完成更新残差的操作,调用cublas Dgemv()函数实现矩阵向量乘法、向量减法并行操作,得到残差值rn。并行计算二范数,即调用cublas Dnrm2()函数实现,判定是否满足迭代停止条件。若满足迭代停止条件,则重构信号,若不满足,则n = n + 1 ,继续循环。
⑦内存释放。在算法结束时,调用cublas Destory() 函数释放与CUBLAS库相关的资源,同时通过调用cuda Free()函数释放在GPU上分配的内存。
4 实验与分析
4. 1 实验环境
本实验在NVIDIA平台上( Shelob高性能计算平台) 测试。Shelob高性能计算平台采用的是CPU + GPU异构,是目前主流的异构计算平台。其硬件配置详情如表1 所示。
4. 2 性能指标
图像质量:重构后的图像与原始图像相比较,允许存在一定的误差,对于图像保真度的判断,本文采用客观数字标准来进行定量衡量,一般为峰值信噪比(Peak Signalto Noise Ratio,PSNR ),其中MSE是原图像与重构图像之间均方误差。
加速比:采用加速比(Speedup) 来评价并行压缩感知算法性能。如下公式所示。Sp表示加速比,T1表示串行算法在CPU单核上运行时间,Tp表示并行算法在GPU上运行时间。
4. 3 实验数据
本实验数据来源于Landsat - 7 卫星,将下载的遥感图像用ENVI软件裁剪成三种不同大小的遥感图像,分别是512 × 512、1024 × 1024、2048 × 2048,其数据格式为Geo Tiff。
4. 4 实验内容
在压缩感知重构算法中,其可变因素为采样率,本实验设置为常用值:0. 5。在NVIDIA平台上对串、并行算法进行测试,统计串、并行算法的运行时间,得到相应的加速比。以3 次实验的平均值作为算法最终的执行时间,时间单位为s。
从表2 中可以看出,并行算法的处理时间相对于在CPU上的串行算法处理时间大大缩短了,算法执行效率得到明显提升。同时,从PSNR值来看,其图像也表现出较好的重构效果。根据加速比公式,分别计算不同尺寸遥感图像的加速比,如图4 所示。
从图4 中可以看出,随着图像尺寸的增大,加速比也逐渐增大,从图线趋势来看,基本成线性增长。在图像较小时,由于算法并行部分的矩阵和向量的都较小,无法完全体现出GPU的众核特性,加速比较小,随着图像的增大,GPU的利用率越来越大,在图像为2048 × 2048 时,加速比达到100X。由此可见,本文设计的并行算法充分利用了GPU的优势,基于CUDA设计的压缩感知重构算法能在很短时间内完成,满足了人们对图像处理的实时性要求。
5 结束语
针对压缩感知重构算法运行时间长的问题,本研究利用GPU的强大浮点处理能力,采用CUDA编程模型实现了压缩感知重构算法的并行设计。实验结果表明本文设计的并行算法在NVIDIA平台上运行,与仅使用CPU的串行程序相比,取得了不错的加速比。因此可以说明本文设计的并行算法能提高了算法的处理速度,解决了压缩感知算法在实际应用中的问题。
同时,对于压缩感知重构算法的并行化设计还可进一步研究,如目前使用广泛的编程模型Open CL,采用此编程语言设计的并行算法具有跨平台处理的能力,因此下一步可考虑采用Open CL编程语言实现压缩感知并行算法研究。
摘要：压缩感知重构算法存在计算量大、运行时间过长的问题,无法满足人们对算法处理实时/准实时性要求。最近几年,GPU计算能力得到很大的提升,已成为提高算法处理速度最有效的方式之一。根据GPU的硬件特性,文中提出了基于CUDA的压缩感知重构算法的并行设计。实验结果表明:在NVIDIA K20Xm平台上运行,并行算法取得的加速比可达到100X。
并行压缩论文 篇3
数据记录与回放[1,2]是预警机任务电子系统[3,4,5]的重要部件之一, 在执行任务过程中, 需要对关键实时数据进行记录, 便于任务结束后的任务回放分析。随着前端传感器性能的逐步提升, 任务总线上传输数据量、记录数据量急剧增长, 严重影响数据加卸载的性能。为减少记录数据存储空间大小, 采用zlib对数据进行实时压缩, 实验表明, 能得到较好的压缩效果。同时也带来了数据记录性能的瓶颈。
为缓解性能瓶颈, 本文提出一种基于多核处理器的并行压缩算法, 实验结果表明:在SMP (单路8核) 处理机上, 该算法取得了8.7倍的加速比。
1相关工作
无损压缩是指数据经过压缩后, 信息不受损失, 还能完全恢复到压缩前的原样。现在无损压缩的方法主要包括两类:字典算法和统计算法。LZ77[6]为字典算法的代表, PPM[7]和BWT[8]为统计算法的代表。LZ77算法是第一个被广泛使用的开源压缩算, 由Jacob Ziv和Abraham Lempel在1977年提出, 该算法由此得名。现在流行的zlib压缩库采用LZ77的压缩原理。
在LZ77的压缩过程中, 若文件中存在相同内容的数据块, 则只需保存第一个数据块, 并使用这样一对信息, 来替换后面的数据块。由于这一对信息的大小, 小于被替换内容的大小, 使文件得到了压缩。LZ77算法使用滑动窗口, 寻找文件中相同内容的数据块。
随着高性能计算的发展[9,10,11], 并行压缩算法的研究逐渐成为了热点。本文在多核处理器上采用zlib压缩库对任务系统记录数据进行并行压缩处理, 在保证压缩率与串行算法相同的同时, 取得了较大的加速比。
2并行压缩算法
基于zlib的串行压缩方法对原始数据进行逐块读入, 依次进行压缩。在整个串行压缩的过程中, 只有一个进程在工作。多线程处理的核心是对多个程序代码片段或数据块进行并发执行, 这样可有效地利用系统资源, 避免处理器空闲。
本文采用一个读线程、一个写线程和多个压缩处理工作线程。多个压缩处理工作线程可以对不同数据块进行同时压缩, 只要读缓冲区里有数据块, 压缩工作线程就可一直进行处理, 从而提高效率。
2.1“生产者/消费者模型”
不同线程之间的读写交互工作机制是典型的生产者/消费者模型。读线程将数据读入缓冲区, 压缩工作线程从缓冲区中取数据进行压缩, 完成后将压缩过的数据写入缓冲区, 写线程从缓冲区中取数据并输出到指定文件。
在读线程和压缩工作线程之间, 压缩工作线程和写线程之间, 后面的线程要用到前面线程所产生的数据。为防止线程之间的冲突, 在读线程和压缩工作线程之间的缓冲区设置了信号锁, 压缩工作线程和写线程之间的缓冲区也利用了锁信号进行互斥访问。
2.2无锁缓冲区队列
队列是一种先进先出 (FIFO) 的线性表, 为缓解生产者和消费者线程之间的速度不匹配问题, 以及由于缓冲区互斥访问而带来的性能开销, 本文采用一种无锁缓冲区机制, 如图1所示。
无锁缓冲区由N组缓冲区队列构成, 每个缓冲区队列最大可缓存M条数据, 每个缓冲区队列都有一个标识位, 用于判别是否可读。算法1描述了写缓冲区的过程;算法2描述了读缓冲区的过程。
2.3输出顺序队列
写线程在对压缩后的数据块进行输出时, 需对按照数据块的先后顺序进行输出。在对数据块进行读入时, 每个数据块分配一个数据块编号, 用于识别写先后顺序。
输出顺序队列为一个循环队列, 初始化时就申请足够大的空间, 队列的插入和删除, 不需要比较和移动数据元素, 只需要修改队列头和尾标记, 并向队尾增加元素或从队头取出元素。
3实验结果与分析
衡量压缩算法性能好坏的重要指标有:压缩比、加速比和数据解压恢复效果。本算法利用zlib库对数据进行压缩处理, 所以对于数据解压恢复效果已是业界标准, 本文不对数据解压恢复效果进行实验分析。本文重点从加速比和压缩比两方面进行论证分析本算法的性能优劣。算法验证硬件参数:CPU主频为3.40 GHz;核心数量为8;内存为8 GB。
3.1压缩算法加速比分析
加速比定义是能基本反映并行算法的好处, 但是最优串行算法难以找到, 甚至不存在。因此, 通常以串行算法来替换[12]。本算法主要研究大数据文件的压缩性能, 所以选取1.6 GB的真实记录数据进行压缩处理, 串行算法运行时间选取操作系统中tar命令的运行时间作为参考值。
算法使用8核处理器进行实验, 将每个处理线程均衡绑定到多核处理器, 线程数的增加实际上是处理器核数的增加。通过图3可看出, 随核数增加时数据加速比快速增大。同时一次读取数据块的大小影响I/O操作次数和并行压缩线程一次可处理的数据量, 所以也对加速比有影响。随着从原文件中一次读取数据量的增加, 加速比也随之变大, 但一次读取数据量到达一定阈值后, 将使内存切换频率增加, 导致加速比下降。经过实验得出, 对于本实验平台从原文件中一次读取64 k B的数据块可达到最优加速比, 是使用tar命令压缩时间的8.7倍。
3.2压缩算法压缩比分析
文件压缩后占用的磁盘空间与原文件的比率称压缩比。本文主要解决大数据量数据存储问题, 所以此处依然选用大小1.6 GB的记录数据文件的压缩比率进行分析, 并以tar命令压缩同一原文件的压缩比率作为对比值。
从图4可看出, 随着从原文件中一次读取数据量的增加, 压缩比逐渐减小。在并行压缩算法中为了保证压缩后数据块的正确性、有序性和解压恢复效果, 在每块数据添加信息头。随着从原文件中一次读取数据量的增大, 数据块数量下降, 信息头总量变小, 从而降低了压缩比。经过实验得出, 对于本实验平台当一次读取数据量达到64 k B之后, 压缩比变化趋势减缓。在一次读取数据量大小为64 k B时的压缩比是tar命令压缩比率的56%。
4结束语
并行压缩论文 篇4
随着科学技术的发展和社会发展应用需求, 人们对视频图像采集处理高清化, 传输实时化和控制智能化的要求越来越高。高清视频图像在军事、科研、安防、工业生产、医疗卫生等领域得到了更为广泛的应用[1]。
特别在安防行业, 现有系统由于技术、成本和传输距离的原因, 传输带宽都不高, 直接实时传输高清视频图像难以实现, 但是某些关键时刻或者特殊场景却需要高清晰度、高分辨率的图像进行细节的分析处理, 便于智能化的应用。本文为了解决这一个矛盾的需求, 提出了在视频监控系统的前端——图像采集和处理将采集到的原始高清图像数据分成两路同时进行处理的思想:一路按照传统的处理方法压缩处理转为标清视频流传输, 实现监控的实时化;另一路数据由外部扩展SDRAM缓存, DSP实时读取缓存数据进行智能分析处理, 根据分析处理结果决定是否传输高清图像或者结果。基于不同处理芯片在图像处理各层次应用有不同的针对性, 合理分配硬件资源及算法, 能够显著提高系统整体性能。本文采用FPGA+DSP技术实现高清图像采集和处理, 并在硬件层面将数据分路处理。
1 系统结构及原理
本文设计的硬件系统, 就是利用FPGA和DSP对高分辨率CMOS数字图像传感器OV5642进行图像采集和处理。系统完成对FPGA, DSP和OV5642芯片进行初始化。FPGA对OV5642进行全分辨率的数据采集。FPGA将采集到的图像数据成两路处理, 一路直接原始高清数据传输外部SDRAM缓存, 由DSP读取缓存数据进行智能分析处理;另一路由FPGA进行硬件预处理, 将原始高清图像转换为合适的分辨率, 送到DSP片内进行格式转换、压缩等处理后传输到外部接口。DSP根据分析处理结果和设置阈值条件, 决定是否对高清图像数据进行传输。需要传输的图像帧融入数据流中传输。外部扩展的输出接口可以将经过系统处理的数据流传输到本地监控或者远程监控。系统原理框图如图1所示。
在高清实时图像采集处理中, 图像采集的速度高, 低层的预处理中要处理的数据量大, 对处理速度要求高, 但运算结构相对比较简单, 适合用兼顾速度及灵活性的FPGA进行硬件实现。高层的处理算法的特点是处理的数据量较低层算法少, 但算法的结构复杂, 适合用运算速度高、寻址方式灵活、通信机制强的DSP芯片来实现[2]。DSP+FPGA架构的最大特点是结构灵活, 有较强的通用性, 适合于模块化设计, 从而能够提高算法效率, 同时其开发周期短, 系统易于维护和升级, 适合于实时视频图像处理[3]。
在本设计中充分考虑到FPGA和DSP在图像采集处理各层次应用有着不同的优势, 采用FPGA+DSP结构, 通过合理的硬件资源分配及算法处理, 实现了高清图像采集和实时处理。在FPGA内设计采集模块和预处理模块, 充分利用FPGA时钟频率高, 内部延时小, 运行速度快, 全部控制逻辑由硬件完成的特点, 主要完成图像数据采集、数据分路和图像缩放预处理。通过FPGA内模块间协调, 在硬件层面完成数据的分路。在DSP内则是利用DSP运算速度快、寻址方式灵活、通信机制强大等特点, 主要完成系统配置、图像格式转化、压缩处理以及图像的智能分析处理、传输接口配置等。
2 系统硬件设计
2.1 图像采集模块设计
图像采集模块主要包括传感器工作模式配置、图像采集控制和数据传输。整个模块的功能示意图如图2所示。FPGA片内模拟I2C控制器, 将COMS图像传感器OV5642初始化。OV5642[4]在外部时钟VXCLK作用下, 输出Bayer RGB格式图像数据和同步时钟。FPGA内部设计的采集控制器在PCLK, HREF, VSYNC同步时钟作用下, 产生相应控制读写信号, 进行数据传输采集。
通过SCCB总线设置OV5642相关的内部控制寄存器, 实现对OV5642初始化, 从而确定输出分辨率、开窗位置、曝光时间等。SCCB总线是Omni Vision公司特有的一种三线串行摄像控制总线[5]。三线中的SCCB_E为片选信号线, 本文中只有OV5642一个从设备, 所以SCCB_E直接置低, 始终选中OV5642。在模拟I2C控制器控制下, 第一步, SIO_D线传输OV5642的器件地址加上写操作标识, 确定操作的器件和注明是写操作;第二步, 传输内部的目标寄存器的地址;第三步, 传输要设置的数据并写入到对应的寄存器中, 完成寄存器配置。
采集控制器是在FPGA设置的一个时序逻辑控制器, 主要产生OV5642需要的外部时钟XVCLK和根据OV5642输出的像素时钟PCLK, 行参考时钟HREF, 帧同步时钟VSYNC产生读写控制存储信号。通过对PCLK, HREF, VSYNC时钟的计数, 可以得到写满一行或者一帧信号, 为后继处理提供同步时钟和使能信号。
2.2 预处理模块设计
预处理模块主要是利用FPGA可编程性和内部丰富的硬件资源, 在硬件层面选择性的传输数据, 将高清图像的分辨率降低。FPGA采集到的原始图像数据格式为Bayer RGB格式, 每个像素点只有一种颜色分量, 其余颜色分量可以通过插值算法恢复[6,7]。如图3左边所示就是4×4的Bayer RGB格式。为了保持数据格式一致性, 需要每隔2行或者每隔2列选择一个像素传输。本设计采用在行方向上每隔2列选择传输一个像素点, 在列方向上每隔2行选择传输一个像素点。这样能将图像分辨率降低, 达到缩放目的, 如图3所示。
图像数据是逐个像素逐行串行传输的, 在缩放处理上, 利用PCLK, HREF和VSYNC信号时序关系产生计数脉冲和使能信号。在行方向上, 选择传输一个像素点数据后, 利用PCLK作为列计数脉冲, 每过两个脉冲 (隔两个像素点) 再选择传输一个像素点数据, 一直循环选择, 直到处理完一行图像数据。这时根据HREF信号产生列计数器清零信号, 将列计数器清零, 暂停数据选通。在列方向上, 由行计数器利用HREF信号进行计数, 每过两个计数脉冲 (隔两行图像数据) , 重复行方向上的处理方式对当前行进行选择数据传输。如此循环处理, 直到一帧图像数据处理完毕。每帧图像处理完毕信号是由VSYNC信号产生的。同时, VSYNC信号对行计数和列计数器清零, 直到新一帧图像到达, 计数器重新计数, 开始新的一帧图像缩放处理。通过这样的缩放处理, 可以将2 592×1 944的图像降为648×486的图像, 数据量得到减少。预处理模块将缩放后图像传输到DSP中处理。
2.3 SDRAM控制器 (MC) 的设计
SDRAM控制器模块是FPGA内部设计的模块, 用于将图像数据传输到外部存储器暂存。图4为FPGA设计的顶层模块示意图[8]。在MC控制器的内部, 采用状态机来实现数据读写、设置模式寄存器和刷新等操作的命令译码, 产生输出给SDRAM芯片的RAS/CAS/WE/CS/DQM等信号。已经初始化的SDRAM在得到了RAS, CAS, WE的值后开始执行相应的命令[9]。在对SDRAM进行读、写操作过程中, 要先进行页激活操作, 保证存储单元是打开的, 再通过预充电命令实现来关闭存储单元。在进行写操作时, 内部的列地址和数据都会被寄存, 而进行读操作时, 内部地址被寄存, 数据的读取则发生在CAS延迟时间 (通常为1～3个时钟周期) 后。SDRAM顺次的进行读、写操作后, 当达到突发长度或者突发终止指令出现时, SDRAM控制器将终止其操作。
通过SDRAM控制器模块的控制传输, 可以将采集到图像数据实时的传输到存储器件暂存。采用控制器模式具有一定的通用性, DSP可以通过控制器模块直接读取存储图像数据进行分析处理。
2.4 DSP子系统
DSP接收预处理模块输出的降了分辨率的Bayer RGB格式数据到数据缓存器, 再将缓存数据传到片内preview engine模块进行格式转换, 将Bayer RGB格式图像数据转换为YUV422格式数据[10]。DSP对YUV422格式数据进行压缩处理后送到输出端口输出。
DSP通过SDRAM控制器读取SDRAM中的高清原始数据, 进行一些智能化分析处理, 如识别、验证等。根据处理结果和系统设定的阈值如光强变化、动静变化等, 决定是否对当前或者前几帧图像进行传输。高清图像数据传输由DSP通过一定的相关处理结合到输出数据流中传输到后端, 由后端提取出高清原始数据, 进行各种应用。
3 结 语
采用了FPGA和DSP技术, 设计了对CMOS图像传感器进行图像采集和处理系统。该系统直接对CMOS传感器进行原始数据的采集, 为后继处理的灵活性和应用的多样性做好数据基础。在FPGA中将数据分成两路, 一路作为原始数据暂存到SDRAM, 一路按照传统的处理、输出。这样既能实现了传统图像采集处理系统的功能, 又能保存原始的数据为进一步的应用开发提供了硬件基础, 能较好地解决网络传输带宽不足与关键时刻或者关键场景需要高分辨率图像进行分析处理的矛盾要求。采用FPGA+DSP的硬件组合具有相当大的灵活性, 后期功能开发潜力大, 可以根据不同的软件配置, 实现多种功能, 具有良好的应用前景。
参考文献
[1]孙康明, 袁祥辉.PCI9052在图像采集系统中的应用[J].仪器仪表学报, 2004 (8) :554-555.
[2]王建华, 刘缠牢, 陈大川, 等.基于DSP+FPGA技术的实时视频采集系统的设计[J].研究与开发, 2007 (9) :42-44.
[3]刘晓明, 田雁, 许朝辉.基于DSP和FPGA的视频处理系统设计及其实现[J].激光与红外, 2007 (12) :1328-1330.
[4]Omni Vision.OV5642_datasheet (1.11) [M].USA:OmniVision Technologies Inc., 2009.
[5]Omni Vision.Serial camera control bus (SCCB) functionalspecification[M].USA:Omni Vision Technologies Inc., 2003.
[6]BAYER B E.Color i maging array:US, 3971065[P].1976-07-20.
[7]马涛, 汶德胜, 崔巍.Bayer格式图像压缩方法及FPGA实现[J].科学技术与工程, 2006 (6) :1505-1511.
[8]赵釜.基于CycloneⅡ系列FPGA的图像实时采集与预处理系统研究[D].重庆:重庆大学, 2009.
[9]李刚, 李智.SDRAM通用控制器的FPGA模块化设计[J].电子产品世界, 2007 (8) :84-88.
并行压缩论文 篇5
基于小波变换的小波包变换,不仅在时频域都具有良好的局部化性质,而且对信号的高频部分提供了更精细的分解,从而得到大量高频信息[1,2,3]。小波包变换在电力系统多方面的应用都有明显的优势,例如在数据压缩领域,小波包变换可以针对电力系统故障录波信号中蕴含丰富暂态特征信号的特点,将故障信号分解成各个频带的信息,选择有重要信息的频带采用各种压缩算法进行压缩。近些年,在小波包算法基础之上,又提出了与嵌入式零数编码相结合[4]、与快速傅里叶变换相结合[5]、混合小波包[6]等各种提高压缩精度的压缩算法。这些算法虽然在一定程度上使压缩性能得到提升,但却增加了算法复杂度。随着电力系统数据记录装置的飞速发展、电力系统高采样的逐步演变、滤波装置的不断更新,电力系统电能质量数据逐渐呈现海量化趋势,传输、存储等环节对实时性的要求又进一步提高,因此,电力系统数据压缩效率问题得到越来越多的关注。以上各种压缩算法所基于的小波包变换,其核心部分的卷积运算过程复杂、运算量大、实时性差,严重阻碍了其在实际工程中的应用。为了提高小波包变换的计算速度,解决目前电力系统海量数据的压缩效率问题,本文提出将小波包变换并行化处理。
目前,针对这一问题,国内外学者提出利用各种并行技术来加快小波包变换的运算速度[7,8,9,10,11,12,13],大部分文献都是利用多机网络环境进行并行化处理,该方法不可避免地受到系统维护及网络传输环节所带来的不利影响。随着计算机的发展,单机多核处理器应用越来越广泛,因此基于多核技术的并行小波包研究具有十分重要的意义。
本文利用Pthreads[14]和Open MP[15,16,17]2种并行编程环境,针对提高小波运算速度问题,提出小波包Mallat分解重构算法不同的并行策略。在Pthreads环境下,提出小波包分解过程数据级并行、重构过程任务级并行;在Open MP环境下,分别提出小波包分解重构特征嵌套和非嵌套并行策略。并利用C语言在单机双核处理器平台上进行了海量数据压缩实验研究,取得了明显的效果,为解决电力系统数据压缩效率问题提供一种新的方法。
1 小波包Mallat算法并行性分析
小波包是小波概念的推广。它是在小波变换(V0=V1⊕W1=V2⊕W2⊕W1=…)只将V(尺度)空间进行分解的基础上,进一步对Wj(小波空间)进行分解,使正交小波变换中随j的增大而变宽的频谱窗口进一步变细,达到最适合于待分析信号的时频窗口或最优基[18]。其分解过程如图1所示,图中h0与h1分别表示小波包分解后的高频系数与低频系数,a表示尺度空间数据,d表示小波空间数据。
小波包分解重构过程的核心是滤波器与待处理数据的卷积过程。从卷积计算的公式可以了解到,卷积计算结果与待处理数据序列直接相关,不同位置的待处理数据与滤波器的卷积过程得到不同的卷积结果。因此不同位置的卷积结果之间并没有相关性,可以将待处理数据进行分配并行卷积。
小波包Mallat重构原理如图2所示,图中g表示由小波空间数据与尺度空间数据重构后得到的上一层的重构数据。可以看出,小波包变换中对尺度空间和小波空间的处理也不存在关联性,该部分同样可以作为并行任务执行。
2 基于Pthreads与Open MP的并行小波包实现
2.1 Pthreads与Open MP
Pthreads是Linux操作系统的多线程接口标准,在Windows操作系统上,可以利用Pthreads-win32开放源代码版本实现并行编程。与Pthreads库不同,Open MP是通过采用指导语句、库函数调用和环境变量来给用户提供在共享存储计算机上创建和管理可移植并行程序的方法。它是一个在多处理机上用以编写可移植的多线程应用程序的API库,采用ForkJoin并行模式。
2.2 基于Pthreads的并行小波包实现
小波包对信号数据处理的流程,需要经过数据加载、延拓、分解、二抽取、二插值、重构这一过程。利用Pthreads实现分解过程数据级并行分解、重构过程任务级重构。其中,延拓、二抽取与二插值的过程与分解、重构过程融合为同一个流程。
a.数据延拓。为了执行数据延拓,将每组与后一组重复NFilter-1个数据,其中NFilter是滤波器系数个数,本文采取周期延拓,最后一组与第1组数据重复前NFilter-1个数据,假设有p个线程参与执行并行计算,则每组有N/p+NFilter-1个数,N为原始数据个数,卷积时滤波器第1位只对应每组前N/p个数进行计算。
b.数据级并行分解。由于小波包分解时各数据序列之间没有相关性,可以将各个数据分配给各个线程同时执行。为保证各个执行线程负载平衡,本文根据小波包分解层数将近似系数与细节系数的数据分别分为N/p组,每层N的大小为上一层的1/2,数据分组如图3所示。
将分解的前q组数据分给q个线程,每个线程同时执行分解过程,待线程挂起后,主线程继续向这些子线程派发新的q组数据。分解一层后,先对近似系数进行分组并行分解,再对细节系数分组执行。此时需要注意的是,由于延拓方式的影响,对应于每一层中近似与细节系数的延拓值将会不同,因此在分组完成后先要计算此次延拓后的余值项,再采用新的余值进行延拓与卷积计算。
c.二抽取。为了减少小波包变换计算时间,可以将分解中二抽取过程与分解过程相结合[20],即不再计算所有数据,而是选择奇数位数据计算,偶数位数据直接跳过。图4采用滤波器系数为4说明此过程。图中当数据延拓分组后,不同的线程针对本组数据进行卷积计算时,每个线程执行第1、3、5、…位为首的运算。
图5为小波包Pthreads并行分解流程,图中Ti为不同的线程,di为不同组的数据,主线程完成数据载入与延拓后,将数据分组,分出一组数据后创建一个线程执行该组的分解运算,完成近似系数的分解,接着继续分解第i层细节系数,直到所有系数分解完成。
由于数据回存需用到上一步线程的结果,并且是在同一堆栈中进行读写,为了保证数据回存的正确性,各线程完成卷积计算以后,需在分解数据回存之前与主线程合并,主线程完成分组后在此等待,创建的线程得到释放。
d.二插值与任务级重构。重构的过程中可以发现,每一层对应的近似系数和细节系数个数是相同的,并且不同的系数与不同的滤波器进行运算,不同类型系数之间没有相关性,读取数据实现卷积的过程就不会出现同步的问题,因此可以将近似系数和细节系数重构的过程看成是不同的任务,实现任务分解方式及任务大小相同,这也满足负载平衡要求。
小波包重构并行过程,先根据每一层循环与分解层数的关系,计算数据延拓后的系数值,二插值时不进行补零操作,而是在非补零位置计算待处理数据与滤波器奇数位的系数卷积,补零位置计算待处理数据与滤波器偶数位的系数卷积。而整个过程中尺度空间与小波空间同时进行重构运算,其任务级并行重构流程如图6所示。
2.3 基于Open MP的并行小波包实现
Open MP标准可以直接在串行程序的基础上调整程序的并行性,因此利用Open MP实现小波包并行必须首先编写小波包分解的串行程序,本文在Visual studio 2008平台上利用C语言完成串行编程。Open MP最显著的用处在于,可以将小波包for循环分配到不同处理器上同时执行,即根据处理器的个数p将循环次数分为p组,每组循环由一个线程执行,这样由p个线程同时完成不同次循环体中卷积、二抽取计算,如图7所示。
小波包分解串行程序核心部分是一个嵌套循环过程。嵌套循环的含义是把小波包分解层次与计算低频、高频系数的次数相联系。为处理边界问题,对边界进行周期延拓,共享数据作为私有副本分配给各个线程。根据图2,假设分解n层(n≥1),外层循环需要进行2n-1次。假设外层分解至第j(j=0,1,2,…,2n-2)次,内层循环则从j N/(2n-1)开始至(j+1)N/(2n-1)次结束。
a.嵌套方案。在Open MP内,嵌套是一个默认不使能的布尔属性。当并行区域嵌套出现在线程已经运行在并行区域又遇到另一个并行区域时,若嵌套使能,那么程序就会按照之前动态线程的规则生产一个新的线程组。可以通过omp_set_nested(i)来设置嵌套使能状态,i=0表示嵌套未使能,i=1表示嵌套使能。
小波包分解过程利用嵌套使能并行执行嵌套循环。当主线程遇到外层循环时,派生出一组线程,这些线程同时继续向内层循环执行下一层并行,这时派生出的线程和原来的主线程成为针对内存循环的主线程,继续按照之前的方式派生新的线程从而并行执行内层循环,当内层循环执行结束时,这些线程逐级挂起,最终回到最初的主线程上。嵌套循环并行执行线程运行过程如图8所示,m为实际计算机核数。
b.非嵌套方案。另外一种方法即类似于小波分解并行执行过程。对于嵌套循环的程序,可以选择只对一层循环作并行处理,由于小波包分解中外层循环次数不多,而内层循环复杂度较高,本文选择只对内层循环过程作并行处理,即利用多核处理器同时对不同尺度的系数做卷积和二抽取过程。非嵌套循环并行执行线程运行状态如图9所示。
3 数据压缩分析实验
3.1 实验基本过程
为了检测并行小波包在数据压缩中的性能表现,本文对数据进行并行小波包压缩解压处理,由于小波包变换可以使信号经过小波包变换后能量集中在少数的系数上,并且这些系数的能量能够远大于其他多数小波包的系数,因此可采用阈值方法,现有的文献阈值选取包括全局阈值与局部阈值,考虑到全局阈值能降低计算的复杂度,而本文分析重点在于研究算法的并行性,因此选取全局阈值压缩。
数据压缩方法采用阈值压缩算法,阈值处理后需要记录非零小波系数的位置以及系数的取值,此过程采用文献[22]所提出的位图压缩法。
小波分解的最大级数J定义[23]如下:
其中,ff是信号的基础频率,fs是信号的采样频率。
实验主要步骤如下。
a.载入信号后,对信号作并行小波包分解;分解层数根据式(1)得出,本实验分解层数为3层,分解过程采用第2节提出的小波包并行分解方案。
b.将分解后的小波系数,经过全局阈值处理,利用位图压缩算法将剩余后的小波系数依次排列,完成压缩过程。解压过程根据位图压缩法还原各系数原始位置,对其余位置进行补零操作。
c.采用第2节提出的并行小波包重构方案,对解压后系数作小波包重构,还原原始数据。
实验主要用于检验并行小波包的计算效率,在保证分解重构的结果与串行计算结果相一致的前提下进行。
实验时间记录从主线程执行并行小波包分解开始,直到小波包重构结束。由于实验针对小波包分解压缩重构的并行过程,因此不记录载入信号与写出信号的时间。
仿真信号源采用的是:
3.2 实验环境
本文采用的实验平台为:处理器为Intel(R)Core(TM)2 Duo CPU T5750,内存为3 GB。所有数据为5次计算时间平均值。
3.3 实验方案
为比较并行算法性能,采用本文所提出基于Pthreads及Open MP 2种并行编程环境下的小波包并行算法与串行小波包算法分别进行数据压缩。实验在210、215、216、220、221这5种数据量下,采用db4小波包,将信号分解为3层。实验结果见表1、2。
为了显示并行算法相对串行算法的性能改变,采用加速比描述:加速比=串行算法计算时间/并行算法计算时间。
表3中S1、S2、S3分别表示Pthreads环境下小波包并行压缩解压加速比、Open MP环境下小波包嵌套并行压缩解压加速比、Open MP环境下小波包非嵌套并行压缩解压加速比。
3.4 实验结论
a.从实验可以看出基于Pthreads与Open MP的并行小波包算法,在计算速度上有着较大的优势,这种性能的提升随着数据量的增大而增大。相对于串行算法有着接近2倍的速度提升,甚至在用Open MP进行并行处理时出现超线性加速比的情况。
b.在数据量较少时,由于并行计算不可避免的开销要比并行效果带来的节约时间要大,并行计算的性能不如串行计算,在数据量为215时,各种方法的加速比表现较为一致,且都大于1,说明在此数据量附近,并行带来的节约只略大于并行开销,一旦计算机有其他程序的任务,就会严重影响此时加速比的表现。这一问题将随着海量数据处理的发展而逐渐被忽略。
c.随着数据量的增大,基于Open MP的并行小波包加速比比基于Pthreads的并行小波包要好,这是由于Pthreads是直接控制线程调度,可以由程序员自主控制程序的底层运行,一旦代码优化效果好,就可以达到较高的加速比,反之,由于优化存在难度,在代码复杂度较高的情况下,可能达不到Open MP的并行效果。
d.嵌套循环的并行性能比非嵌套循环较弱,这是由于嵌套使能开启后,内部循环仍旧按照之前的方式派生线程,由于外层循环根据处理器个数已经产生最大可并行执行的线程,因此,在内层循环中所派生出的新线程与其主线程并没有同时执行程序而是交替进行。此外创建和退出线程的过程又带来一定的时间消耗,使得性能下降。但是在处理器个数大于2时,通过动态分配线程,改变外层和内层线程分配方式,可以使嵌套并行循环的性能更优。
4 结语