一种适用于GPU图像处理算法的合并存储结构*

左宪禹，张 哲，黄祥志，葛 强，张理涛，臧文乾

(1.河南省大数据分析与处理重点实验室，河南 开封 475004; 2.河南大学计算机与信息工程学院数据与知识工程研究所，河南 开封 475004; 3.郑州航空工业管理学院数学学院，河南 郑州 450015; 4.中国科学院空天信息创新研究院，北京 100094;5.中科空间信息(廊坊)研究院，河北 廊坊 065000)

1 引言

由于硬件架构的特点，GPU (Graphics Processing Units)在大数据量、密集型计算方面具有较大优势，因此被广泛应用于图像处理领域，以提高图像处理算法的执行速度[1 - 3]。但是，由于GPU上的部分计算资源如显存(Graphics Memory)容量等与CPU相比较小，而计算核心(Cores)数量与CPU相比则较充足，因此利用GPU进行加速的图像处理算法必须依据硬件架构有针对性地设计算法流程，才能使GPU计算资源利用率最大化，取得较好的加速效果。

针对图像处理算法的GPU并行加速问题，现有文献提出了多种方法用以提高GPU资源利用率及加速效果。Luley等[4]利用CUDA(Compute Unified Device Architecture)编程模型的Hyper-Q特性和CUDA流(Stream)将数据传输与核函数执行操作进行重叠(Overlap)，以减少部分数据传输及核函数执行耗时。Pai等[5]则重点关注GPU硬件资源的更新升级对算法的影响，并提出了一种允许对GPU计算资源进行细粒度控制的弹性核函数策略，大大提高了程序的可扩展性及兼容性。沈夏炯等[2]针对遥感影像的特点，提出了对较大尺寸遥感影像进行分块、分批次处理的方法，并取得了较好的加速效果。通过对GPU硬件架构的研究以及对基于GPU加速图像处理算法类文献的总结，可以发现基于GPU优化的图像处理算法中影响加速性能提升的2个主要耗时因素是数据传输与核函数执行。为了进一步提高图像处理算法的GPU加速效果，通常采用文献[4]中提出的方法，利用CUDA流来重叠数据传输与核函数执行，以减少部分数据传输和核函数执行耗时。但是，对于数据传输与核函数执行操作之间的调用间隙问题、较小尺寸图像的批量处理问题以及算法中包含较多输入图像，并对各输入图像分别执行无依赖性[2]处理步骤(本文将这类操作称为算子)的情况，即使利用CUDA流对数据传输与核函数执行进行重叠，在执行性能方面仍存在可提升空间。

为了优化上述问题，本文以待处理图像的存储结构为切入点，对基于GPU加速的较小尺寸图像的批量处理和包含较多算子操作的图像处理算法中合并存储结构对加速效果的影响进行了探讨分析以及实验验证。本文对CUDA编程模型中CUDA流的优势及其局限性分别进行了论述，并对数据传输与核函数执行在GPU上的执行过程进行了分析。根据分析结果以及现有基于GPU加速的图像处理算法中存在的问题，本文提出了一种适用于GPU的图像合并存储结构CSS(Combined Storage Structure)，并对其有效性进行了理论分析。采用非合并存储结构SEP(SEParate structure)和CSS结构分别实现了基于GPU加速的NDVI提取(Normalized Differential Vegetation Index)提取算法，并对其进行了实验验证，对实验结果进行了归纳总结。

2 相关工作

本节首先对GPU工作队列(即CUDA流)的优势及其局限性进行分析；其次对CUDA编程模型中数据传输及核函数执行操作进行分解，并分析指出可优化部分；最后针对GPU硬件架构特性以及分析结果提出一种适用于GPU图像处理算法的数据合并存储结构，并对该结构在GPU上的有效性进行分析。

2.1 GPU工作队列

利用GPU实现并行加速的图像处理算法通常包含以下3个主要执行步骤：

(1)将输入图像从主机端(Host)内存传输至设备端(GPU)显存。

(2)核函数在设备端(GPU)执行。

(3)将计算结果从设备端(GPU)显存传输至主机端(Host)内存。

从上述步骤可知，数据传输与核函数执行操作是基于GPU的并行优化算法中必不可少的2个重要步骤。由于核函数执行操作通常在算法执行总耗时中占据较大比重，所以在现有的大部分文献中，重点关注如何对GPU核函数执行部分进行优化。即根据算法本身特性及GPU计算架构的特点来设计性能最优的核函数，从而达到较好的加速效果。此外，针对GPU数据传输耗时的优化方法比如零拷贝(Zero-Copy)[6]和Overlap[7]等的应用也取得了一定的加速效果。Zero-Copy是一种将主机端分配的锁页内存(Pinned Memory)映射到GPU显存地址空间的方法，GPU可在需要该内存中数据时自动通过PCI-E总线访问主机端内存中的数据，而不必手动将数据提前传输至GPU显存。但是，由于所需数据并没有缓存到GPU显存中，所以每次访问该数据都需要重新获取，因此只适用于数据量较小或数据访问次数较少的情况。Overlap则是利用CUDA流[3,7-9]实现不同GPU工作队列的并发执行。不同型号GPU通常拥有数量不等的可连接硬件工作队列上限，并可以进行显式设置，而逻辑工作队列(即CUDA流)则没有固定数量限制。通过将逻辑工作队列映射到不同硬件工作队列，可以重叠数据传输与核函数执行操作，在支持Hyper-Q特性的GPU上还可以达到核函数执行之间的重叠，从而减少部分程序执行耗时。如图 1所示，当批量处理6幅图像时，可以将每幅图像的处理操作分配到1个单独的CUDA流上，在计算资源充足的情况下，数据传输与核函数以及不同流上核函数的执行时间轴会出现重叠，从而获得较高的并行度与较好的加速效果。

Figure 1 Timeline of CUDA streams that executed concurrently图1 CUDA流并发执行时间轴

虽然CUDA流在逻辑上是相互独立且可并发执行的GPU工作队列，但将逻辑工作队列(即CUDA流)映射到硬件工作队列时会受到硬件计算资源方面的限制。GPU中包含较多的计算核心(Cores)，主要分为SP(Stream Processor)和SM(Stream Multi-processor)，多个SP可组成1个SM，每个GPU硬件工作队列包含至少1个SM。当多个逻辑工作队列映射到同1硬件工作队列时，这些逻辑工作队列将会采取分时复用的方式执行。因此，即使创建多个逻辑工作队列，但当硬件工作队列不足以同时执行全部逻辑工作队列时，逻辑上并行执行的工作队列在物理上仍是串行执行的。如图 2a所示，假定GPU硬件资源仅支持同时执行3个硬件工作队列，即使创建逻辑上可并行执行的6个逻辑工作队列，但未抢占到硬件工作队列所有权的逻辑工作队列不得不进行等待，图2a所示逻辑工作队列执行时间轴对应的硬件工作队列执行时间轴如图 2b所示。此外，在每个硬件工作队列上需要串行执行的操作中，数据传输与数据传输之间以及核函数执行与数据传输之间存在调用间隙。在这种情况下，算法的实际执行情况并没有达到图 1所示的理想效果。

Figure 2 Logical work queue and hardware work queue图2 逻辑工作队列与硬件工作队列

2.2 数据传输与核函数执行

由GPU硬件架构及CUDA编程模型的特性可知，每次调用数据传输及核函数执行操作都需要对GPU设备进行初始化，即存在固定代价，如DMA引擎设定、起始地址和目标地址的设定、核函数发射等，且固定代价耗时随设备端操作被调用次数的增加而增加。

CUDA编程模型中主机端与设备端之间单次数据传输操作耗时计算方法如式(1)所示。

Ttotal=Tinit+Tcopy

(1)

其中，Tinit是每次数据传输执行前的设备初始化耗时，包括前面提到的DMA引擎设定、起始地址设定等，因此为固定代价；Tcopy为数据拷贝耗时，随拷贝数据量的大小而变化，为非固定代价；Ttotal则代表单次数据传输操作的总耗时。

核函数执行操作耗时如式(2)所示：

KTtotal=KTinit+KTlaunch+KTcompute

(2)

其中，KTinit为每次核函数执行操作的初始化耗时，KTlaunch为核函数发射耗时，KTcompute为核函数访存与计算耗时，KTtotal则代表单次核函数执行操作的总耗时。

与数据传输操作的初始化耗时Tinit类似，KTinit为每次核函数执行操作的固定代价，而KTlaunch则随核函数发射次数的增加而增加，同样可看作固定代价。KTcompute与核函数取指和访存次数密切相关，因此为非固定代价。

综上可知，数据传输及核函数执行操作的耗时与其被调用次数紧密相关。当调用次数减少时，操作的固定代价、调用间隙以及执行过程中的非固定代价也会随之减少，即被调用次数的减少会带来相应的性能提升。因此，可考虑将较小尺寸的待处理图像进行合并，进而将数据传输及核函数执行操作进行合并，减少操作的调用次数。

2.3 图像合并存储结构

在图像处理领域中，通常将图像视为数字矩阵传输至GPU显存中进行处理[10,11]。因此，本文提出一种适用于GPU的图像合并存储结构(CSS)，如图 3所示。利用CSS可以将具有相同类型、相同算子、相同或不同大小的图像进行合并存储、传输及计算。

Figure 3 Combined storage structure of images图3 图像合并存储结构

如前文所述，每次GPU数据传输操作都存在固定代价。Tinit在每次数据传输操作调用前都会执行，即属于固定代价且不随传输数据量的大小而改变。而Tcopy不属于固定代价，因此随传输数据量的增加而增加。当将多次数据传输操作进行合并时，固定代价会随之减少。分别采用SEP与CSS的多次GPU数据传输操作总耗时计算方法如式(3)所示：

(3)

其中，n表示待传输数据(图像)的个数；Tinit为单次数据传输的初始化操作固定代价；i表示待传输的第i个图像数据；Tcopy(i)则代表数据i的拷贝耗时。由式(3)可以看出，采用CSS结构可以节省数据传输操作中的Tinit固定代价，且节省的固定代价大小随数据传输操作合并数量的增加而增加。

GPU核函数执行过程中通常包含较多访存操作。CUDA编程模型访存操作采用内存事务(Transaction)[12]的方式实现，而内存事务执行次数与数据在显存中的分布情况紧密相关。CUDA单次内存事务缓存粒度通常是128字节，即每次缓存连续的128字节数据进缓存区，内存事务操作示意如图 4所示。由图 4可知，当将SEP结构的数据合并为CSS结构时，2次内存事务操作也可随之进行合并。因此，在某些情况下，采用CSS结构可以减少部分内存事务的执行次数。

Figure 4 Transactions of CUDA memory access图4 CUDA内存事务访问

此外，当采用CSS结构将待处理图像进行合并后，GPU算子核函数也可随之进行合并。如式(4)所示，采用CSS结构后，KTinit固定代价减少，取指次数及内存事务执行次数也有所减少：

(4)

其中，n表示核函数调用次数，通常为待处理数据的个数；Δ为核函数及内存事务的加速比率，Δ≤1，是性能影响因子，随具体的数据分布情况及GPU硬件资源而变化；i表示待处理图像数据；KTcompute(i)则表示针对数据i的核函数执行耗时。由式(4)可知，采用CSS结构可以有效减少部分固定代价耗时，提升核函数的执行性能。

综上所述，利用CSS结构对输入图像进行合并可节省GPU数据传输及核函数执行操作部分的固定代价及非固定代价，带来执行性能的提升。且随着待处理图像合并数量的增加，带来的性能提升效果也更显著。根据上述分析结果，可对GPU算法执行情况进行模拟：假设GPU硬件资源在物理上仅支持2个硬件工作队列并行执行，当对6幅图像进行批量处理时，分别采用SEP与CSS结构的GPU算法模拟执行时间轴如图 5所示。

Figure 5 Timeline for simulation execution图5 模拟执行时间轴

由式(3)和式(4)可知，采用CSS结构能够有效减少操作调用间隙及部分固定代价。在图 5所示的模拟执行时间轴中，采用CSS结构的数据传输时间为采用SEP结构等量数据传输的时间总和，核函数执行时间为采用SEP结构核函数执行时间的总和，并未考虑固定代价的减少。即便如此，从模拟时间轴上仍可看出CSS结构在加速效果方面取得了一定的提升。

3 实验对比

3.1 实验环境

本文实验环境采用的CUDA版本为9.2，GPU采用NVIDIA GeForce GTX 1060，该GPU搭载了6 GB全局显存，1 280个CUDA计算核心(Cores)，最高时钟频率可达1.67 GHz。本文测试所用图像为GF1卫星拍摄的遥感影像数据，并根据实验需求将其裁剪为4000×4000像素的规整大小。测试算法为NDVI提取算法。NDVI是被用来描述植被数量、生长情况和覆盖状况等的指标，可以大致反映出植被信息，在遥感影像信息提取中应用广泛[10,13]。其计算方法如式(5)所示：

NDVI=(NIR-RED)/(NIR+RED)

(5)

其中，NIR和RED分别代表遥感影像的近红外波段和可见光红外波段的光谱反射率。

3.2 实验结果及分析

为了验证不同图像合并数量对加速性能的影响，分别采用SEP与CSS结构对数量为8,16,32,64和128的5组单个大小均为4000×4000像素的遥感影像数据在单流和多流情况下进行实验。

基于SEP与CSS结构实现的NDVI提取算法单流实验结果如图 6所示，实验执行时间轴示意可参见图 5所示的模拟执行时间轴。由图 6可知，在单流的情况下，采用CSS结构的NDVI提取算法执行耗时皆少于采用SEP结构的NDVI提取算法的，与式(3)和式(4)的分析结果一致。

Figure 6 Test results of single stream图6 单流实验结果

当利用GPU进行批量图像处理时通常采用CUDA流进行优化，多流的优势及其局限性已在前文中进行了讨论。为了测试CSS结构在多流上的应用，本文实验将GPU硬件工作队列最大可连接数(即可并行执行硬件工作队列数)限制为4，采用同样的5组数据进行实验，将每组数据平均分配到每个硬件工作队列中，并利用CSS结构将其合并。多流情况下的实验执行时间轴可参见图 5，实验结果如图 7所示。

Figure 7 Test results of multiple streams图7 多流实验结果

由图 7可知，多流情况下采用SEP与CSS结构的算法执行耗时均少于图 6所示的单流情况下的算法执行耗时，表明多流具有更好的加速效果。与单流情况相比，多流情况下采用CSS结构的NDVI提取算法与采用SEP结构的NDVI提取算法相比取得了更好的执行性能。且随着图像合并数据的增加，采用CSS结构所取得的加速效果与采用SEP结构所取得的加速效果相比有更大的提升。

综上所述，单流和多流情况下采用CSS结构实现的NDVI提取算法执行性能均优于采用SEP结构实现的NDVI提取算法的，这证明了所提CSS结构在GPU上的有效性。在多流情况下，采用CSS结构获得的加速效果更加明显，且随着图像合并数量的增加，加速效果也随之提升，显示了CSS结构的可扩展性。

4 结束语

由于GPU显存容量的限制，部分基于GPU实现的图像处理算法通常需要对输入的较大尺寸图像进行分块、分批次处理。但是，针对利用GPU加速较小尺寸图像批量处理的研究则较少，通常采用循环复用方法进行处理，存在GPU资源利用率较低等问题。本文从基于GPU实现的图像处理算法的存储结构出发，通过对CUDA编程模型在执行过程中的2个主要耗时操作进行分析，提出了一种适用于GPU图像处理算法的合并存储结构。并以基于GPU实现的NDVI提取算法为例，对多组图像进行批量NDVI提取实验，验证了所提存储结构在GPU上的有效性及可扩展性。

从本文实验结果可知，所提的CSS结构在GPU上的适用性、有效性及可扩展性均得到了验证。由于本文实验仅考虑了存储结构对执行时间的影响，且实验中采用的算法为复杂度较低的点运算算法，因此所取得的加速效果并不十分显著，但为GPU图像处理的优化研究提供了新的思路及理论证明。下一步工作将对本文方法做进一步实验及完善，针对CSS结构在不同情况下的合并策略及其瓶颈问题进行研究，并以本文方法为基础尝试提出一个基于GPU的遥感影像动态划分(分割/合并)处理模型。