GPU并行计算（精选6篇）
GPU并行计算 篇1
1. 引言
随着半导体工艺、功耗、大规模集成电路技术的不断进步, 单个芯片上集成了越来越多的晶体管 (可达10亿) , 但受到CMOS制造工艺特征的限制, 单个芯片的主频已无过大的提升空间 (仅有少数芯片可达5GHz以上的时钟速率) 。换句话说, 除非芯片制造工艺有所突破, 否则单个芯片的主频不会再有提高。随着晶体管集成工艺进入瓶颈, 多核、众核并行计算逐渐成为计算性能提升的主要途径;在绿色高性能计算时代, CPU/GPU异构并行计算系统可兼顾性能、效能和通用性, 是一种极具发展潜力的并行计算类型。
G P U逻辑电路简单 ( 相对于通用CPU) , 不包含乱序执行、分支预测等耗费资源的复杂控制逻辑和多媒体处理指令, GPU通过增加晶体管资源来增强自身的并行计算能力。随着GPU编程界面及指令级功能的不断改进, 其已广泛应用于非图形领域的计算, 出现了一个全新领域GPGPU (General Purpose Computation on GPUs) 。就目前来看, GPU的处理器数量远远高于CPU的处理器数量, 如英伟达 (NVIDIA) 公司较早的GPU产品G80拥有128个流处理器, 而最新的基于Maxwell架构的GTX TITAN X包含了80亿个晶体管, 拥有3072个流处理器。GPU拥有的流处理器数量较大程度上决定了其计算能力, 随着相关产业各项技术的发展, 单GPU的流处理器数量必将不断增加, 其计算能力也必将不断增强。
CPU/GPU异构并行系统充分利用CPU和GPU各自资源做自己擅长的事情, 不仅能节省资源和成本, 也可显著提高计算能力, 已成为高性能计算领域的重要发展趋势。因为GPU具有优异的图像处理能力, 其浮点并行计算能力尤为突出, 相对于CPU, GPU对浮点数据的计算可达百倍加速效果, 此外, GPU的理论带宽也要明显高于CPU。但不容忽略的是, CPU具有大容量缓存和复杂控制逻辑, 能应对各种不同情况, 尤其擅长复杂的逻辑运算, 因此使用CPU进行事务处理和复杂逻辑运算, GPU作为加速阵列负责逻辑分支简单、计算密度高的大规模数据并行任务, 可最大程度利用计算机的处理能力, 实现桌面上的超级计算。2015年世界上最快的超级计算机为中国国防科技大学研制的“天河二号” (每秒33.86千万亿次浮点运算速度) , 其运算速度是美国能源部下属橡树岭国家实验室的“泰坦”超级计算机的两倍, “天河二号”[即采用了CPU和GPU异构并行计算方式, 实现了中国高性能计算的历史性突破。
2. CPU/GPU异构系统
半导体工艺的快速发展给GPU和通用CPU带来了长足发展, 但相对于CPU, GPU在性能上的发展更加迅速, 这与GPU体系结构的设计理念有关, GPU早期主要用于加速图形处理, 重点关注细粒度数据计算, 且采用的计算模型较为固定, 因此其控制逻辑简单, 没有通用CPU上耗费资源的分支预测等复杂逻辑, 能够通过集成更多的晶体资源提升峰值计算能力。而CPU更为关注标量和通用计算能力, 其指令集更加复杂, 且通过使用大量硬件逻辑单元来提升计算性能, 因此GPU和通用CPU分别被称为“容量型”和“能力型”处理器。
如图1所示, CPU与GPU主要区别在于结构上, CPU中的晶体管主要用作逻辑控制单元 (Control) 和高速缓存 (cache) , 仅有少量晶体管用于计算 (ALU) 。而GPU的晶体管主要用作计算单元, 少量晶体管用于逻辑控制单元和高速缓存, 这使得GPU更适合用于密集计算任务。
为更好说明GPU并行计算结构, 在此引入CUDA (Compute Unified Device Architecture, 统一计算设备架构) 概念, CUDA是由NVIDIA推出的一种将GPU作为并行计算设备的软硬件体系。CUDA体系中有两个单位概念: 线程 (thread) 和线程块 (block) , CUDA程序会根据实际情况调用具体的block和thread, 实现数据的并行处理。此外, CPU调用线程需耗费较多的时钟周期, 而CUDA程序调用线程几乎不消耗时间。
如图2 所示, CUDA的强大计算能力来自于SPA (ScalableStreaming Processor Array) 中的大量计算单元T PC ( Thread Processing Cluster) 。SPA包含多个TPC, 每个TPC又包含多个SM (Streaming Multiprocessor) , 这些SM共享存储器流水线, 每个SM内部资源相当于8个SIMD处理器, 执行线程的最小单位为warp, 其指令宽度为32。SM具有完整独立的前端, 包括译码、发射、取址和执行单元等, SM通过向量机技术增强了计算性能, 减少了控制开销。
GPU和CPU通过外部PCI-E总线互连 (如图3所示) , 各自拥有自己的片外存储器, 应用程序的GPU加速流程主要包括以下三步:
☆ 将待处理数据从CPU端存储器拷贝到GPU端存储器;
☆ 调用kernel函数执行;
☆ 将数据处理结果拷贝回CPU端存储器;
由于GPU依靠并行执行大量运算单元来获取高计算性能和高吞吐率, 因此, GPU计算程序常常将可并行执行、耗时较长的循环结构映射到GPU上执行。
3. CPU/GPU异构并行计算优化方法
并行计算性能优化的最终目的是以最短的时间, 在允许的误差范围内完成既定的计算任务。由于GPU和CPU架构不同, 二者的性能衡量方法和并行优化方法也不相同, GPU的并行优化侧重于计算的密度和吞吐量, 而不是单个数据的延迟。
1) 最大并行执行原则
在CUDA架构下, 如何将算法进行划分才能使算法合理分配到GPU和CPU上, 以获得最佳的并行执行效果, 是异构并行计算优化首要考虑的问题。
首先需考虑算法的选择, 算法选择应比较不同算法间的计算复杂度和效率。值得注意的是, 并行实现的算法不一定就会比串行算法快, 当目标问题规模较小时, 计算复杂度低的算法不一定比计算复杂度高的算法耗时更短, 因此, 需根据问题规模的大小, 选择合适的算法实现, 将任务中耗时多的大规模数据并行、高计算密度的计算放到GPU上。
2) 最大内存带宽原则
内存带宽一直是计算机性能的瓶颈之一, 目前内存访问速度要低于处理器的计算能力, 因此, 想要获得高性能的计算结果, 需要对内存访问进行优化, CUDA架构提供了多种类型的内存, 下面讨论如何利用各种内存特性, 实现最大的可用带宽。
☆ 全局内存访问优化
由于流处理器并没有对全局存储器做缓存, 因此全局存储器具有较大的延时 (约400~600个时钟周期) , 经常成为并行运算的性能瓶颈。若想获得最佳的内存访问, 应尽量遵循连续合并访问的原则, 即被访问的内存地址需连续, 而且开始必须是每个线程所存取大小的16倍。如每个线程读取32bits的数据, 那么第一个线程读取的地址必须是的倍数。
☆ 共享内存访问优化
共享内存位于GPU内部, 其速度与寄存器相当, 比全局内存和本地内存要快的多 (其延迟仅为全局内存和本地内存的百分之几) , 假设每个流处理器有16KB的共享内存, 每个共享内存分为16个内存模块, 如果同时每个线程存取不同的内存模块, 就不会产生任何问题。如果同时有多个线程同时存取同一内存模块的数据, 就会发生内存模块冲突, 这些线程就必须按顺序去存取, 而无法同时存取共享内存, 此时有效内存带宽会降低几倍, 因此, 共享内存访问优化的目的就是通过优化调度访问请求减少内存模块冲突。
☆ 其他类型内存访问优化
在CUDA架构里, 还有常数内存、寄存器、纹理内存、主机内存等几种常用内存, 下面分别介绍这几种内存的访问优化。
纹理内存能通过缓存利用数据的局部性, 提高效率, 其主要用途是用于查表和存放图像, 以下两种情况可以获得很好的访问性能: ( 1 ) 数据不能进行合并访问, 采用纹理内仍能获得较高带宽; (2) 随机访问数据时, 若数据量较少, 采用纹理内存效率也很高, 当同一线程束的各个线程读取地址相近的数据, 纹理内存可达到最高效率。
常数内存用于存放程序中待使用的常数, 其访问速度比共享内存要慢, 比纹理内存要快。
寄存器内存是GPU上的高速缓存, 其基本单位是寄存器, 执行单元可以以非常高的速度访问寄存器。
3) 最大指令吞吐量原则
在CUDA架构下, 每个线程束的大小为32, 一条指令有32个操作组成, 指令吞吐量如下式:
其中, Pn为处理器个数, It为指令吞吐量, T为一个周期下执行的操作数目。
满足最大指令吞吐量的前提是要有足够大的计算量, 如果计算量小, 则使用GPU进行并行计算并不划算, GPU延迟要大于CPU, 只有足够的计算量才能忽略GPU延迟。衡量计算量有两种方式:相对方式和绝对方式。
☆ 绝对方式
若待优化的程序使用频率较低, 且每次调用需要的时间也可以接受, 那么即使进行优化也不会提升程序性能。对于一些计算量非常小的程序而言, 使用CUDA构架进行计算时无法隐藏访问内存和数据传输的延迟, 会造成程序执行时间反而比CPU的长。虽然GPU对浮点数处理能力以及带宽都远远超过CPU, 由于目前GPU大多数是通过PCI-E总线与CPU连接, 因此其输入和输出的吞吐量受到了输入输出带宽的限制。当要程序的计算密度很低时, 执行的时间大多数花费在输入输出上, 远远大于计算本身的时间上, 则整个程序的瓶颈就会出现在PCI-E带宽上。
☆ 相对方式
CUDA程序是由串行部分和并行部分组成的。如果要优化的程序中并行部分所占的比例较小, 则针对GPU进行优化获得性能的提升也比较有限, 同时也应考虑是否需要采用GPU进行并行计算。整个性能提升计算公式如下:
其中, T为程序执行总时间, Tp为并行部分执行时间, Ts为串行部分执行时间;假设程序执行总时间T为1, 其中串行部分执行时间Ts为0.9, 并行部分执行时间Tp为0.1, 若将并行执行部分进行优化后得到10倍性能的提升, 使得Tp变为0.01, 则程序执行总时间变T为0.91, 其加速比仍然很小。
4. 3D渲染优化方法
由于GPU架构的特殊性, 在编写GPU并行程序时, 需要对内存的选择、线程快大小的划分、计算量等方面进行考虑, 否则无法获得高加速比。
1) 顶点处理
在顶点处理阶段 ( Vertex Process) , GPU在处理光照和顶点变化上, 可利用顶点缓存来提高效率, 如果目标顶点已处理过, 则再次处理时可直接从缓存中读取。
在渲染网格时, 程序常常将多个顶点缓存绑定在一起, 在对顶点进行操作前, 需要为顶点进行初始化, 即分配一块内存。在初始化期间, 每个顶点数据都是从显存对应的顶点流中被提取出来的, 这些值称为顶点属性。随着顶点数量的增加, 需要提取的属性信息也随之增多, 也就是说, 当在渲染时, 一次性要处理的顶点过多, 那么顶点初始化阶段则会成为整个渲染管线的瓶颈, 检测顶点处理初始化阶段是否存在瓶颈, 主要有以下两个方法:
☆ 增加顶点数据大小:保持算法不变, 增加顶点数据, 进行性能对比, 如果顶点数量增加导致新能急剧下降, 则应考虑如何减少顶点数据, 获得性能提升。
☆ 减少顶点数据大小:与之前的方法相反, 保持算法不变, 通过减少顶点数据来提高算法性能。减少顶点数据的方法是替换顶点所对应的属性信息。
2) 纹理贴图
纹理贴图 (Texture) 是三维渲染中非常重要的一环, 就是将材质图片或纹理经过坐标变换等计算后, 映射到对应三角形的像素上, 并通过纹理来表示物体表面丰富的光照细节和几何细节, 还可通过纹理形变来描述物体的几何形状, 这样做可以显著增强三维渲染的真实感和细节度。常见的纹理贴图有很多种方法, 其中多分辨率纹理贴图技术的性能最好。
在三维渲染时, 过大或尺寸不符的贴图会占用过多的纹理带宽, 导致GPU显存不足而频繁交换, 此时, 应该尽量减小或使用多分辨率纹理贴图技术。多分辨率贴图技术的核心就是纹理LOD, 其根据不同精度要求, 使用不同材质进行贴图, 如当观察视角靠近物体时, 程序会在物体表面贴上清晰度较高的材质图案, 反之, 程序会贴上清晰度较低的材质图案, 进而提升图形处理的整体效率。现在的硬件普遍支持多分辨率纹理贴图, 硬件会为纹理自动生成各分辨率下的纹理图形, 然后根据实际情况进行贴图, 使用多分辨率纹理贴图可以实现30%~40%的性能提升和节省33%的内存使用率。
3) 光栅化
光栅化是一种将基本图元转化为二维图像的过程, 转化后的二维图像像素点均包含深度和颜色等信息。由此可见, 光栅化主要包括两方面工作, 一是决定窗口坐标中哪些栅格区域被基本图元占用, 二是分配一个深度值和一个颜色值到各个区域。处理结果会被传递到下一个片元操作, 在那里利用消息更新帧缓存中的适当区域。
在进行光栅化的过程中 (如图4所示) , Ge Force系列显卡能在仅渲染模板值或深度值得情况下, 以双倍的速度进行渲染, 要实现这种渲染模式, 必须遵循下列规则:禁用颜色写入操作、多重采样、裁剪切面、色彩替换、阿尔法测试技术。由于实际操作过程中, 模板渲染和倍速Z-Only省去了纹理取样和光照等操作, 因此速度非常快, 同时该模式清除深度缓存非常快。
另一种光栅化性能优化技术称为Z轴精简, 其通过避免渲染被遮挡的表面来提高性能, 如果被遮挡面上应用了非常复杂的着色算法, 那么Z轴精简可以节省大量处理时间。点光栅化
利用上述两个特性提升渲染速度, 最好的办法是利用“深度优先”进行绘制, 首先用倍速深度渲染来绘制场景 (不着色) , 这样建立的表面距离视点最近;然后使用完全着色渲染场景, Z轴精简则会自动剔除无法看到的表面。
4) 反锯齿
反锯齿也称为抗锯齿, 是通过某种技术将图像边缘的“锯齿”缓和, 使图形边缘更加平滑, 虽然三维渲染技术不断提高, 画面中的环境和人物也越来越真实, 但由于画面是由上千万个像素构成, 即意味着物体轮廓处最终还是锯齿状。目前, 多数GPU硬件上都集成了反锯齿功能, 我们只需进行相应简单设置即可实现抗锯齿的功能。
5. 结束语
本文介绍了CPU/GPU异构并行优化方法和3D渲染优化方法, 其中并行优化主要遵循最大并行、最大带宽和最大吞吐量三个原则;3D渲染优化包括顶点处理、纹理贴图、光栅化和反锯齿等几个方面, 经过优化后的CPU/GPU异构并行系统可以实时处理3D和4K视频。
GPU并行计算 篇2
渲染一个复杂的三维场景, 需要在一秒内处理几千万个三角形顶点和光栅化几十亿的像素。早期的3D游戏, 显卡只是为屏幕上显示像素提供一个缓存, 所有的图形处理都是由CPU单独完成。图形渲染适合并行处理, 擅长于执行串行工作的CPU实际上难以胜任这项任务。所以, 那时在PC上实时生成的三维图像都很粗糙。GPU卸载了CPU的图形处理功能, 使画面清晰流畅。
1 超长流水线技术
GPU的功能更新很迅速, 平均每一年多便有新一代的GPU诞生, 运算速度也越来越快。2004年推出的GPU Nvidia Ge Force 6800 Ultra可达到峰值40 Gigaflops (1 Giga FLOPS=1秒钟进行10亿次的浮点运算) , 2005年发布的Nvidia Ge Force7800 GTX更是将峰值提高至令人惊讶的169 Gigaflops。而Intel3GHz Pentium 4采用SSE指令集也只能达到6 Gigaflops (见图1) 。GPU的运算速度如此之快, 主要得益于GPU是对图形实时渲染量身定制的, 具有两点主要特征:超长流水线与并行计算。
1.1 流水线的工作原理
流水线技术与工厂里的装配线原理类似。如果装配一台汽车需10个时间单元, 将它分成10个流水线阶段, 每个阶段分配一个时间单元, 那么一条装配线每一个时间单元就可以生产一辆汽车。显然流水线模式的生产在理想状况下要比串行方式快了10倍。也就是说为了提高流水线的速度, 可以将任务划分成更小的单元, 这样流水线的级数就增加了。CPU的设计中就使用了流水线原理, 奔腾IV就有20级的流水线。但是流水线级数越多, 一条指令从开始进入流水线到最后被执行完毕这之间的延迟间隔会相当大。换句话说, 当流水线级数过多时, 控制台发出一条指令, 会经过很长时间才会真正生效, 这不适用于快速反应要求很高的场合。打个比方, 当用消防水龙头救火时, 正常情况下打开阀门开关几秒后水便喷射出来, 立刻可用来扑灭火灾。但是如果延迟了十几分钟, 才有水流出, 即使这时水流速度 (吞吐量) 还是很快, 不过这时火灾就会造成更大的损失了。CPU的设计目标是不仅要有很高的吞吐量, 还要求很小的延迟, 这是CPU并不采用过多流水线级数的原因之一。另外, 流水线只有在满载时, 才能发挥出最佳效率来。由于CPU执行的代码中有很多分支语句, 因此长流水线需要用有效的技术来预测分支, 尽量保持流水线在满负荷状态。但是, 一旦预测分支失败, 就会清除流水线中滞留的大量无用指令, 同时将新指令流重新注入流水线。如果流水线阶段过多的话, 充满整个流水线就需要很长的时间, 这样使流水线保持满载的机会不多, 速度反而下降了。所以权衡利弊, CPU不会选择深度流水线。
1.2 流水线技术在GPU中的实现
GPU采用了几百级的流水线, 比如Ge Force 3的流水线有800个阶段。GPU的应用为何可以忍受这么大的延迟呢?假设以每秒50帧的速率显示画面, 那么只要求每帧在20ms以内生成就行。而Ge Force 3的时钟频率是200MHz (每个时钟周期是5ns) , 5ns*800=4μs<20ms。所以, 对GPU来说这一些延迟根本不成问题, 而且GPU中执行的Shader程序中, 分支语句用的很少 (在早期的GPU中, 甚至不提供动态的分支语句) 。因此, GPU的流水线深度变大后, 利大于弊, 大大提升了整体性能。
GPU的执行速度很快, 但是当运行从内存中获取纹理数据这样的指令时 (由于内存访问是瓶颈, 此操作比较缓慢) , 整个流水线便出现长时间停顿。在CPU内部, 使用多级Cache来提高访问内存的速度。GPU中也使用Cache, 不过Cache命中率不高, 只用Cache解决不了这个问题。所以, 为了令流水线保持忙碌, GPU的设计者使用了多线程机制 (multi-threading) , 见图2。当像素着色器针对某个像素的线程A遇到存取纹理的指令时, GPU会马上切换到另外一个线程B, 对另一个像素进行处理。等到纹理从内存中取回时, 可再切换到线程A。但是使用这种方法有一个前提, 线程A与线程B没有数据依赖性, 也就是说两线程之间无需通讯。如果线程B需要线程A提供某些数据, 那么即使切换到线程B, 线程B仍是无法运行, 流水线还是处于空闲状态。不过幸运的是, 图形渲染本质上是一个并行任务。
2 并行计算
无论是CPU送给GPU的顶点数据, 还是GPU光栅生成器产生的像素数据都是互不相关的, 可以并行地独立处理。而且顶点数据 (xyzw) , 像素数据 (RGBA) 一般都用四元数表示, 适合于并行计算。在GPU中专门设置了SIMD指令来处理向量, 一次可同时处理四路数据。SIMD指令使用起来非常简捷, 可以看一个顶点矩阵变换的例子 (见下代码) 。此外, 纹理片要么只能读取, 要么只能写入, 不允许可读可写, 从而解决了存贮器访问的读写冲突。GPU这种对内存使用的约束也进一步保证了并行处理的顺利完成。
为了进一步提高并行度, 可以增加流水线的条数。在Ge Force 6800 Ultra中, 有多达16组像素着色器流水线, 6组顶点着色器流水线。多条流水线可以在单一控制部件的集中控制下运行, 也可以独立运行。在单指令多数据流 (SIMD) 的结构中, 单一控制部件向每条流水线分派指令, 同样的指令被所有处理部件同时执行。另外一种控制结构是多指令多数据流 (MIMD) , 每条流水线都能够独立于其他流水线执行不同的程序。Ge Force 6800 Ultra的顶点着色器流水线使用MIMD方式控制, 像素着色器流水线使用SIMD结构。MIMD能比较有效率地执行分支程序, 而SIMD体系结构运行条件语句时会造成很低的资源利用率。不过SIMD需要硬件少, 这是一个优势。
CPU中大部分晶体管主要用于构建控制电路 (例如分支预测等) 和Cache, 只有少部分的晶体管来完成实际的运算工作。而GPU的控制相对简单, 且对Cache的需求小, 所以大部分晶体管可以组成各类专用电路、多条流水线, 使得GPU的计算速度有了突破性的飞跃, 拥有了惊人的处理浮点运算的能力。现在CPU的技术进步正在慢于摩尔定律, 而GPU (视频卡上的图形处理器) 的运行速度已超过摩尔定律。
3 结束语
虽然GPU最初是专门为图形渲染设计的, 但是GPU还可以有效地执行多种通用计算, 从线性代数和信号处理到数值仿真等等, 有的专家甚至认为GPU将进入计算的主流。
参考文献
[1][美]费尔南多 (Randima Fernando) .GPU精粹:实时图形编程的技术、技巧和技艺[M].姚勇, 王小琴, 译.北京:人民邮电出版社, 2006.
[2][美]法尔 (Matt Pharr) .GPU精粹2:高性能图形芯片和通用计算编程技巧[M].龚敏敏, 译.北京:清华大学出版社, 2007.
[3]The Cg Tutorial:The Definitive Guide to Programmable Real-Time Graphics.
基于GPU的高性能并行算法研究 篇3
GPU并行计算属于目前并行计算领域的一个新的分支, 我们常见的并行计算有多线程, Open MP[5]等等, 它们都属于超负荷的使用CPU加快运算的速度。GPU并行计算是利用的图形处理器, 也可以说是计算机上的显卡, 充分的利用GPU的内部结构, 加快运算的效率。目前, 针对GPU并行计算, 人们已经提出了很多的模型, 甚至是开发平台, 比如CUDA、Open GL等。当前, 产业界和学术界对GPU的并行计算都产生了很大的兴趣, 甚至有人说, 以后GPU必将取代CPU的存在。但是目前, 能够被证明利用GPU达到高速计算的算法并不多, 很多算法使用GPU并不如不使用GPU的效果好。因此, 对GPU的研究更加迫切, 证明那些算法, 如何设计可以使用GPU得到最大的加速比是非常重要的。这不仅仅是学术研究的需要, 同时对于工业界产业界都将发挥不可取代的作用。一旦GPU被证明可以取代CPU的地位, 计算机界必将掀起再一次发展的高潮。本文针对GPU高性能并行算法进行研究, 主要是对稀疏矩阵向量乘算法和空间邻搜索算法进行研究, 通过一定的实验证明在GPU下的加速比, 了解GPU的加速状况。
1 并行计算简介
并行计算是指在单位时间段内, 同时执行多条数据计算和多条指令, 可以充分的利用多个处理器单元。并行计算的提出是根据现实的需要, 现实中, 很多领域的数据利用传统的计算方法数据量非常大, 计算很耗时, 人们就思考, 计算机能不能一次处理多个数据进行多次计算, 然后就提出了并行计算。
2 GPU简介
GPU的体系架构在不停的更新, 不同的体系架构必然要设计不同的模型才能进行并行加速操作。目前来说, GPU有存储器系统和可伸缩流处理器阵列两部分组成。可伸缩流处理器阵列都是有很多的线程处理器群组成, 然后线程处理器群又有多个流处理器组成。流处理器都具有指令指针和寄存器, 流多处理器有发射、取值、译码、执行单元等。目前多数GPU的体系结构如图1所示。
对于一般的计算机来说, GPU就是图形处理的一个硬件, 计算机显示界面的效果, 或者三维图片, 视频播放效果的好坏都与GPU有关。GPU的主要工作其实是渲染图像和绘制图像。但是图像形态的生成、运动等图形处理操作还是由CPU所完成的。这就导致了CPU的工作量巨大, GPU长期处于空闲状态, 没有被合理的利用。随着计算机行业的发展, GPU的体系结构也得到了进一步的改变, GPU开始适合于标准处理模式, 大大简化了通用算法进行GPU并行计算的复杂程度。
下面本文将介绍基于GPU的高性能并行算法, 通过对三种不同类型的算法的GPU并行计算, 来展示GPU针对某些具体计算的并行计算效率。
3 基于GPU的稀疏矩阵向量乘算法研究
稀疏矩阵 (矩阵中非零元素的个数远远小于矩阵元素的总数, 并且非零元素的分布没有规律) 与稠密矩阵 (非0元素占所有元素比例较大的矩阵) 不同, 稠密矩阵可以采用m行n列的数组来存放数据即可, 稀疏矩阵来说就不可以采用m行n列的数组来存放数据, 因为这样就会浪费很多的存储单元和存储空间, 增加计算的时间。对于稀疏矩阵来说, 还有没一种统一的最好的存储结构来存储稀疏矩阵, 通常都是根据稀疏矩阵不同的特征来确定具体的存储形式。
CSR (Corporate-Social-Responsibility) 是一种存储没有规律的稀疏矩阵数据的形式, 对于拥有q个元素的稀疏矩阵, 采用CSR存储的话, 要使用三个数组, 一个是数组长度为q的数组Data, 按行分为m段, 一个是数组长度为q的列下标数组Indices, 一个是数组长度为m+1的数组ptr, 稀疏矩阵数组中的顺序号由该数组元素指向。CSR与其他稀疏矩阵的存储来比较, CSR具有相当好的空间效率, 我们将采用该形式完成SPMV (Sparse MatrixVector Multiplication中文名稀疏矩阵向量乘) 。
根据线程同步特性, 一个线程块对应一行数据是比较适合GPU的内部结构的, 但是每个线程块通常都有多个线程, 当非零元素的个数不能与线程数匹配时, 也会导致一些现成无事可做。结合GPU访问时, 全局存储器合并的需要, 我们采用Half-warp作为最小的单位, 作为输入向量和稀疏矩阵一行相乘的计算。这样就可以减少一定程度上线程空转的比例。
利用CUDA平台尽量测试, 经过实验, GPU下进行并行计算的平均加速比为30左右。
4 基于GPU的空间最近邻搜索算法研究
最近相邻问题是对每个点找到距离它最近的数据点, 最近相邻问题再目标识别、模式识别、数据聚类、密度估计、函数逼近、文本分类、矢量量化等科学工程中应用非常广泛。通常求解最近相邻问题的方法是暴力搜索法。具体步骤如下:
(1) 计算所有点到指定点的距离。
(2) 对所有的距离进行排序。
(3) 找出离指定点最近的那个点
(4) 所有点都使用上面三种步骤找到最近点。
显然上面的最近相邻问题解法复杂度非常的高, 超过一定的数据量的话, 就会产生很大的计算量, 因此我们可以对空间最近邻搜索算法采用GPU并行化的方法。针对传统的最近邻搜索算法使用GPU高性能并行计算, 研究此算法在GPU上的运行效率。我们可以将传统的最近邻搜索算法进行一些改进, 视同CPU进行空间的划分, 划分方法使用KD-Tree算法, 然后求出剪枝阈值, ABT剪枝和空间点距离的计算采用GPU上并行计算。这种方法经过大量的实验证明比普通的CPU暴力方法效率要高几十倍, 也比GPU上并行采用暴力的方法要高上一倍的效率。证明这种解法, 效率是非常不错的。
基于KD-Tree空间划分介绍:
此种方法属于一种高维空间搜索树法, 它的每个节点代表n维空间的一维。它的作用是进行空间剪枝, 通过此种算法将空间合理的进行划分, 避免将大量的数据同时计算距离问题, 利用此种算法将空间划分为若干部分, 每部分的任务量基本一致。
通过将此算法利用CUDA平台上进行基于GPU的高性能并行计算测试, 大量的测试结果证明与串行的效果相比, 加速比在20左右。
5 基于GPU的NDVI算法研究
NDVI的计算:NDVI计算是通过一定的数学公式得到的, 但是数学公式的参数却是我们利用遥感卫星拍摄的遥感图像, 通过计算机分析得到的。归一化植被指数即NDVI是通过NIR (近红外波段反射率) 和RED (红光波段反射率) 来计算出来的。即NDVI= (NIR-RED) / (NIR+RED) 。
5.1 NDVI的并行化实现
利用GPU的并行特性及Open CL的异构计算特性, 可以分别对:直方图的计算、直方图的拉伸、直方图的均衡化、NDVI的计算等四个过程进行并行实现。
5.2 NDVI算法并行和串行运行比较
CPU程序运行的串行算法, 选用的是Open VC库, 对遥感图像进行读取, Open CV库, 会对CPU的代码进行优化, 因此使用Open CV库, 可以对实验的结果进行客观的比较。Open CL并行程序的测试时间不包括CPU程序部分的时间, 但是包括数据从内存中读出来的时间。
串行与并行运行结果表1所示。
通过表1, 我们可以看到直方图的加速比为9.7;直方图拉伸的加速比为7.2;直方图均衡化的加速比为5.9;NDVI计算的加速比为5.8。整体的加速比为8.1。根据我们得到的加速比, 我们可以看出我们的实现结果是非常可观的。我们的最低加速比也在5以上, 而通过多核来进行并行操作时, 在我们测试的4核的机器上, 最理想的加速比应该是4。因此我们的实现结果还是非常良好的。
从上面我们对加速比的计算结果, 我们也可以得出另外一个结论, 不仅仅加速效果比较好, 而且当数据量比较大, 比如直方图的计算, 在CPU串行情况下, 需要76ms, 在GPU并行的情况下, 需要7.83376ms, 加速比为9.7, 在所有的段中属于最高的加速比。也说明了, 在数据量越大的情况下加速的效果越明显。但是此结论仅仅是在本实验结果中, 数据量太大的情况下, 也可能会出现相反的结果。
6 总结
本文研究的目标是基于GPU的高性能并行算法研究, 首先本文对并行计算和GPU进行了简单的说明, 通过对稀疏矩阵向量乘算法、空间最近邻搜索算法和基于GPU的NDVI算法的研究, 说明了GPU高性能并行计算在某些算法上应用起来效率是非常可观的, 比普通的CPU计算要高几十倍的效率。本文提到的稀疏矩阵向量乘算法的加速比为30左右, 空间最近邻搜索算法的加速比为20左右, NDVI算法的加速比为8左右。
参考文献
[1]张舒, 褚艳利.GPU高性能计算之CUDA[M].中国水利水电出版社, 2011.
[2]吴恩华.柳有权.基于图形处理器 (GPU) 的通用计算[J].计算机辅助设计与图形学学报, 2010, 16 (5) :601-612.
[3]白洪涛, 欧阳丹彤, 何丽莉, 姜珊珊.一种基于图形处理器的压缩单纯形方法[J].电子学报, 2012.
[4]朱鉴, 吴恩华, 基于GPU的球面深度图实时绘制[J].计算机学报, 2011, 32 (2) :231-240.
[5]陈永健.OpenMP编译与优化技术研究[D].北京:清华大学, 2011.
GPU并行计算 篇4
随着大数据时代的来临,生物信息学、地址勘探、数据挖掘、 电影特效渲染、金融计算等科学和工程领域对数据处理能力都不断提出更高的要求。图形处理器GPU本来是用于图形处理的专用处理硬件,为了适应图形应用的需求逐渐发展形成超越现有CPU的计算能力。伴随其编程能力的提升,现在GPU也被广泛应用于通用计算［1，2］。然而,较高的程序设计复杂度已经成为限制GPU通用计算的瓶颈,传统的数据结构很难直接应用于GPU并且获得较高的性能,因此当前一个重要趋势是为GPU计算提供通用数据结构和算法库( Thrust［3］,CUSP［4］) 。队列是程序设计最常使用的数据结构之一［5］,但是目前GPU上并行队列数据结构还远远不能充分利用GPU的计算能力。因此, 本文研究适合于GPU程序设计的高性能队列数据结构。
根据并行访问时保持数据一致性的方式,并行数据结构可以分为阻塞和非阻塞两种类型。阻塞并行数据结构通过对数据结构加锁来进行实现,即所有线程对锁进行竞争,竞争到锁的线程可以对数据结构进行操作,其他线程则进入等待。非阻塞并行数据结构摒弃了加锁的方式,通过原子操作原语来实现并行,这种实现方式可以保证至少一个线程向前执行,不会产生死锁、 活锁和优先级反转等问题。同时,非阻塞数据结构可以获得更高的性能。由于GPU并没有提供明确的锁的机制,也为了获得更高的效率,本文采用非阻塞方式实现并行队列。
实现高效并行队列的关键在于减少线程间的冲突和保证并行操作中数据一致性。随着并行度的增加,线程间的冲突不可避免,在大数据量的计算背景下,通过近似手段来提升性能成为一种趋势,其中一种有效的思想是对传统数据结构的语义约束进行松弛［6］,即松弛FIFO队列的约束条件,实现非严格意义的FIFO队列,以此来达到提升性能的目的。
针对以上问题,本文主要贡献如下: 提出一种基于GPU的非阻塞并行队列数据结构,并通过引入语义松弛机制提高并行性; 同时针对GPU的单指令多线程SIMT的执行模式进行优化, 构造任务收集策略降低线程冲突提升性能。实验表明,基于单位时间对队列操作数量的评估,本文提出的数据结构在GPU上实现后,比现有多核CPU和GPU结果,分别达到20倍和200倍以上的性能提升。本文采用线性化准则对算法实现进行正确性验证。
1相关工作
在多核CPU平台,Michael等［7］首次提出完整可实现的非阻塞并行队列,引入基于CAS( Compare and swap) 原子操作来保证非阻塞机制。此后涌现出大量针对该算法的改进算法,通过原子操作在不同的底层数据结构上进行实现,Edya等［8］通过双向链表提高执行性能,Hoffman等［9］引入basket的概念,允许在basket链表节点中存储多个元素,以此提高并行度,Gidenstam等［10］使用数组链表作为底层实现,更进一步对缓存和内存一致性进行调优。Morrison等［11］则摒弃传统的CAS原子操作,使用x86架构特有的fetch and add( F&A) 原子操作来保证非阻塞,进一步提高执行效率,但是该方法只能运用于x86架构。但是随着应用对并行效率需求的进一步提高,上述方法依然不能满足现在的需要。
在GPU方面,虽然其并行性能日益突出,但是在并行数据结构方面研究还比较初步,Misara等［12］首次对GPU上的并行数据结构进行了全面对比和分析,Cederman等［13］针对并行队列进行深入研究,并与CPU并行队列作对比,其实验结果与CPU上性能相比还有差距。以上研究工作实现了基于GPU的并行数据结构,但是其对GPU的体系架构和并行数据结构结合性方面的研究还不够。
针对高性能计算效率不能满足需求的问题,Kirsch等［6］提出了非精确系统和非精确计算的概念,即在可测量范围内可以容忍程序一定量的非精确性,通过降低精度来达到提升效率的目的,在并行队列方面即对其语义进行松弛,实现非精确FIFO队列。Haas等［14］基于以上概念在多核CPU上实现了基于共享内存的分布式队列,即将单独队列拆分为多个FIFO队列,通过松弛FIFO语义,线程出队获得的元素可以是第一到第k个元素中的一个,而不是严格意义上的先入先出,同时对该机制在大规模计算中的实用性进行分析,实验表明,其性能有明显提升。
2语义松弛分析
本节对语义松弛机制进行介绍。
语义松弛即对数据结构原本的语义进行一定范围内的松弛,使得新数据结构在规定范围内实现原数据结构的功能。目前基于并行化程序的需要,针对串行数据结构的语义松弛往往是为了在可接受范围内进行语义松弛从而获得并行性能的提升。
以并行队列为例,典型的先入先出( FIFO) 队列,其标准语义即元素A和元素B,假如元素A比元素B先入队,则元素A必定比元素B先出队。为了适应并行程序的需要,对其标准语义进行松弛如下: 限定范围k ,在其中的元素可以无序出队,即会出现元素A比元素B晚出队的情况,虽然是部分无序出队, 但是在限定内,出队元素不会比最早入队元素晚入队k以上,即在第一个入队元素未出队的情况下,第k + 1个元素受到约束不会出队。
3并行队列实现与分析
在本节中,将详细介绍基于语义松弛概念实现的并行队列。 首先介绍并行队列底层实现结构,其次介绍任务收集机制和松弛机制的实现方法,最后介绍具体入队出队流程。
在GPU中,所有线程在不同数据上执行相同指令操作,这就造成CAS操作的大量冲突,这也是之前研究中忽视的问题。 本算法创新性地结合多任务收集机制和通用计算GPU的单指令多线程( SIMT) 模式,提出一种用于任务收集的共享数据结构,并采用CAS原子操作保证非阻塞实现。
基于语义松弛的并行队列SRQ( Semantic-relaxed non-bloc- king queue) 底层由分布式的多个子队列构成,每一个子队列均严格遵守FIFO语义。为了提高效率,每一个子队列中存储的元素为共享数据结构SDS( Shared Data Structure) 的索引,SDS本身存储队列的详细信息,每一个子队列均有单独的head和tail,同时SRQ有全局的global_head_max和global_tail_max作为语义松弛约束,保证松弛机制的正确性,其结构如图1所示。
基于block的任务收集机制基于GPU中block来对所有线程进行分组,一个block内部所有线程采用共享数据结构存储队列详细信息,由task_list[]、first_pos和last_pos组成。为了更加符合GPU的内存访问模型,将结构体分解为多个数组分别存储结构体中不同变量,task_list[]用于实现多线程任务收集机制,各个线程通过prefix-sum机制［15］并行计算其任务所在task_ list[]中的位置。如图2所示,假如一个block内部有8线程( 实际情况远远多于8) 并行地执行prefix-sum,1表示有任务,0则表示没有。最终所有线程并行地将任务插入到task_list[]中, first_pos和last_pos表示task_list地[]中第一个和最后一个元素的位置。
与基于warp的任务收集相比,基于block的机制能够在更多的线程中执行prefix-sum,局部组合更多任务请求,进一步减少CAS原子操作彼此冲突的数量。因为block内部的warp调度是随机的,所以block内部的线程没有先后顺序之分,在执行prefix-sum时不会产生顺序方面问题。
语义松弛机制本算法的语义松弛依赖于负载均衡器实现,算法伪代码如下所示。入队和出队操作进行前会调用负载均衡器来获得执行操作的子队列序号。以入队为例,global_tail _max表示当前各个子队列中最大入队个数,新入队操作进行时会选择某一个子队列进行入队。首先随机产生一个队列序号seed_id,查看入队个数是否等于最大入队个数,如果等于则查看下一个直到小于最大入队个数,则返回当前序号; 如果查找一遍均等于则增加当前最大入队个数,并返回当前序号,算法执行结束。出队同理,负载均衡器可以保证出队元素为入队顺序第一到第k个元素中的一个,即k无序出队。
负载均衡器伪代码:
本算法分为入队操作和出队操作,基于以上描述,算法具体实现如下。
入队操作伪代码如下所示。以GPU中block为整体执行prefix-sum,计算各线程任务的对应位置,并行插入到task_list[] 中( 行13、14) ; 由一个线程代表block内所有线程执行操作,调用负载均衡器获得对应的操作子队列序号( 行18) ; 循环执行CAS原子操作与其他block竞争入队tail,将结构体插入到队列中,直到CAS原子操作成功,则退出循环,执行完成( 行17 - 24) 。
入队操作伪代码:
出队操作伪代码如下所示。出队操作较入队操作更加复杂,需要的CAS原子操作更多。一个block内所有线程基于共享数据结构完成prefix-sum,计算各线程的任务对应位置,初始化共享数据结构( 行27,28) ; 由一个线程代表block内所有线程执行操作,调用负载均衡器获取对应的操作子队列序号( 行32) ; 获取每一个节点内元素个数,并通过CAS原子操作出队, 循环执行直到出队元素达到需求数量num_task( 行31 - 55) ; 各线程通过对应位置获得出队元素。
出队操作伪代码:
4正确性验证
本节对入队和出队操作的正确性进行验证。
采用线性化准则进行验证［16］,线性化是针对对共享数据结构进行并行化操作的一种正确性验证方法。如果一个并行数据结构符合线性化,则其并行操作正确,因为对该数据结构进行的并行化操作会映射到线性化的串行时间点上,从而使对该数据结构的并行操作线性地起作用。
线性化时刻即针对该数据结构的操作起作用的时刻,在该时刻数据结构的更改生效,同时被其他线程所发现。基于以上, 针对入队操作我们做如下证明。
观察1入队操作的线性化时刻是22行CAS操作成功,在这一时刻,该线程将数据入队,因为CAS是原子操作,其执行过程不会被打断。
定理1根据观察1,在入队和出队操作并行执行过程中, 入队操作符合线性化准则。
证明: 假设两个线程分别执行入队操作A和B。如果A和B同时得到相同的next,且同时执行22行CAS操作,则必有一个成功一个失败再循环。如果A成功,则A成功入队,B循环后获得新的next,从而入队成功。如果B成功,A失败,结果相反,同样保证两者入队的线性化; 出队操作和入队操作不会相互影响,因为入队操作在执行CAS操作后出队操作才会看到入队效果,从而不会进行错误的出队。
出队操作证明与入队操作类似,这里不再赘述。
基于以上分析,可以得知本文中实现的并行队列符合线性化准则,正确性得到验证。
5实验分析与性能评估
本节对实验过程和实验结果进行分析和说明。为了更加全面说明问题,实验过程中与多核CPU和GPU上已有的实现进行对比。为了与SRQ作比较,在本文以上优化方法的基础上, 我们去掉语义松弛条件,实现了严格语义的FIFO并行队列Se- mantic-Strict FIFO Queue( SFFQ) 。多核CPU采用文献[11]实现Fast Concurrent Queue( FCQ) ,GPU上采用文献[13]非阻塞并行队列中性能最好的Michael and Scott Queue( MSQ) 。据笔者所知,两者分别为对应平台上的最高效实现。
实验平台如表1所以,其中GPU上采用NVIDIA的两种不同架构Fermi和Kepler。
采用多种测试用例对四种并行队列进行测试,按照入队和出队操作不同的百分比安排测试用例如下:
( 1) 100 /0: 所有线程执行入队操作,每个线程执行100次操作。
( 2) 70 /30: 每个线程随机执行入队和出队操作100次,入队和出队操作比例为70∶ 30( 队列中已有元素215) 。
( 3) 50 /50: 每个线程随机执行入队和出队操作100次,入队和出队操作比例为50∶ 50( 队列中已有元素215) 。
( 4) 30 /70: 每个线程随机执行入队和出队操作100次,入队和出队操作比例为30∶ 70( 队列中已有元素215) 。
( 5) 0 /100: 每个线程随机执行入队和出队操作100次,入队和出队操作比例为100∶ 0( 队列中已有元素225) 。
所有测试用例均执行100次,采用最终平均值作为结果,测试结果采用每秒钟执行百万次操作( MOPS) 的方式呈现。结果如图3所示,其中GPU程序在两种架构的GPU上分别执行, FCQ则采用文献[11]中结果根据使用的CPU主频换算得到。 根据图3中数据可知,SRQ的性能相比CPU和GPU上以前的结果有了较大提升,与FCQ相比有20倍的提高,而与MSQ相比有200倍的提高,由文献[13]可知,这是首次GPU上并行队列性能超越多核CPU; 而我们实现的严格意义上FIFO并行队列SFFQ与以前结果相比同样有相同幅度提升,在所有测试用例中,SRQ的性能与SFFQ相比有50% 到290% 的提升,这也说明通过对队列进行松弛语义,我们可以在性能上获得较大提升。
由以上分析可知,我们的实现在所有测试中对已有实现均有较大提升,包括严格FIFO队列和语义松弛并行队列,这将为未来进行基于GPU的大规模数据并行应用的开发提供高效支持。
为了更进一步测试并行队列的性能和其扩展性,本文针对GPU上的并行队列进行更深入测试,选取典型测试用例2和测试用例4为例,我们针对不同block数量对三种队列实现进行测试,测试结果如图4和图5所示。
通过分析可知,SRQ和SFFQ的性能总体上是随着block数增加而呈上升趋势,在block数量较少时其为线性上升,当block达到一定数量后MOPS开始保持稳定或者略有下降。同时,测试用例4和测试用例2相比整体性能有所下降,这是因为测试用例4加大了出队操作比例,而出队操作与入队操作相比需要更多CAS原子操作,因此出队操作性能会比入队操作低。
6结语
GPU并行计算 篇5
半定规划SDP(Semi Definite Programming)是线性规划的一种推广,它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化的问题。目前为止,已有学者对SDP在电力系统优化调度中的应用作了初步研究,文献[1]使用SDP算法来求解中期水火电力系统调度问题,得到了较好的结果。文献[2-3]针对机组组合模型中存在0/1整数变量的特点,引入一种整数约束条件,同时将目标函数和各种约束条件转换成变量的二次形式,最后采用对偶变尺度算法对得到的SDP模型进行求解。SDP算法与拉格朗日松弛法[4]和传统分支定界法[5]将机组给合(UC)模型分割成上下层循环迭代求解不同,它属于一种直接求解算法,尤其是在考虑网络安全约束情况下,可将所有约束化成相应的半定矩阵形式后使用内点法求解。
内点SDP存在以下2个问题:所需内存较大,由于每个约束条件均对应一个半定矩阵,随着机组组合模型变量和规模的增加,所需的内存空间急剧增加;内点法每次迭代中求解大规模、稀疏、半正定线性方程组需要消耗大量时间。针对第1个问题,可利用半定矩阵对称、稀疏的特点,采用稀疏存储技术减少所需内存。第2个问题归纳为解Ax=b所示的大型稀疏线性方程组,解法可分为直接法和迭代法2类。直接法主要是通过对系数矩阵进行变换,如Gauss消元、Cholesky分解、QR分解等,将原方程组化为三角或三对角等容易求解的形式,然后通过回代或追赶等方法得到方程组的解。该方法一般能得到准确解,但由于固有的前推回代的特点,使得很难实现并行化,因而所需的内存与计算量均很大。迭代法可分为古典迭代法和Krylov迭代法两大类,其中,古典迭代法有Jacobi迭代法、Gauss-Seidel迭代法、SOR等。目前很少用古典迭代法直接求解大规模稀疏线性方程组,常结合Krylov迭代法来使用。Krylov子空间方法的主要思想是为各迭代步递归构造残差向量,即第n步的残差向量rn通过系数矩阵A的某个多项式与第1个残差向量r1相乘得到。迭代多项式的选取应使所构造的残差向量在某种内积意义下相互正交,从而保证某种极小性,达到快速收敛的目的。由于迭代法的存储开销极大减少,同时每步迭代中只包括向量与矩阵的乘法和加法或者向量内积运算,便于并行加速,因此成为稀疏线性方程组并行算法研究的热点。
作为显卡上计算核心的图形处理器GPU(Graphic Processing Unit),是一种用于密集数据计算的多核并行处理器,计算单元数量要远超过CPU。已有部分学者对GPU在电力系统中的应用进行了研究,并取得了一定的成果。文献[6]把GPU应用到潮流计算中,取得了一定的加速比。文献[7-9]利用GPU实现了电力系统暂态仿真并行计算,相比传统的串行算法取得了良好的加速比。
为提高内点SDP算法中大型稀疏线性方程组的计算效率,本文提出了一种基于GPU的Krylov子空间并行算法。该并行算法针对系数矩阵稀疏、半正定的特点,采用预条件处理的拟最小残差法(QMR法),并以矩阵分块技术为基础,在CSR(Compressed Sparse Row)存储格式下由GPU实现了稀疏矩阵的Incomplete Cholesky预处理方法和所有迭代计算。实验分析表明,它是一种求解稀疏、对称、半正定线性方程组的有效方法。对10~100机24时段6个不同的算例进行仿真,结果表明:本文算法是一种十分有效的求解机组组合问题的算法,所达到的加速效果随着算例规模的增加而更加明显。
1 机组组合问题的SDP模型
1.1 SDP原理
SDP是线性规划的推广,是一种非光滑凸优化问题。将现代内点法应用于SDP后,可保证求解诸多凸优化问题时在多项式时间内收敛于最优解[10]。
SDP模型的标准形式如下。
其中,Ai、C、Z为n×n实对称矩阵,A=[A1A2…Am]T;y为m维向量;b=[b1b2…bm]T;“垠”表示左侧矩阵为半正定矩阵,即该矩阵的特征根均大于等于0;
比较成熟的SDP内点法有原始对偶内点法及对偶变尺度法等,本文所采用的不可行内点法属于前一类,可把一个不在可行域内的解作为初始解进行迭代运算,简化了初始化计算。
1.2 不可行内点法
求解式(1)所示的SDP原问题等价于求解其对偶问题的对数障碍问题,其一阶KKT最优条件为:
其中,X、Z垠0,用XZ=μI代替式(2)中第3式(μ为障碍因子,随着μ0,X、Z的值为相应的最优值),并利用泰勒级数进行展开,得到以下线性系统:
对式(3)进行求解便可得到X、y和Z的搜索方向(ΔX,Δy,ΔZ)。但是直接求解得到的ΔX不是对称矩阵,需引入对称化算子对式(3)中的第3式进行处理,算子如下[11]:
其中,V为需进行对称化处理的矩阵;P表示不同的搜索方向,本文取P=Z-1/2。
得到:
其中,E=P-TZ塥sP,F=PX塥sP-T,塥s为对称克劳内特积运算;svec表示将对称矩阵转化为向量的运算,smat为逆运算svec运算的逆运算,表示将向量转化为对称矩阵。消去式(5)中的ΔX和ΔZ可得:
其中,G=AE-1FAT,h=rp-AE-1(Rc-FRd)。求解线性方程组式(6)得到Δy后,便可代入式(5)求出ΔX和ΔZ,然后通过线性搜索得到迭代步长,当对偶间隙C·X-bTy满足指定精度时中止迭代。
1.3 机组组合问题的SDP模型
本文采用文献[6]所示的机组组合模型,机组的启动费用采用传统的冷热启动三段式模型,约束条件包括机组出力约束、最小启停时间约束、机组爬坡约束、功率平衡约束和旋转备用约束等。该模型本身并非凸优化问题,原因是机组启停变量为0/1整数变量,为此引入辅助变量Q2=1,同时将0/1整数变量约束用凸二次约束ui2,t-ui,tQ=0代替,ui,t表示机组i在时段t的启停状态,这样UC问题就可描述为一个凸优化问题,进而用内点SDP法求解。关于机组组合SDP模型的具体介绍可见文献[6]。
2.1 GPU结构
近年来,随着人们对计算机图像显示效果的要求越来越高,显卡上核心处理器GPU的计算量和吞吐量也越来越大。与CPU注重逻辑控制不同,GPU主要负责大规模的密集型数据并行计算。
如图1所示,CPU采用复杂的控制逻辑,用指令来控制单线程可执行程序的执行,还采用大型缓存,既可以减少访问复杂应用程序的指令和数据时产生的延时,又能够节约带宽。而GPU包含了大量的计算单元,通过多线程技术来提升运算速度与吞吐量。硬件充分利用因为等待访问内存而产生较长延时的大量线程,减少了控制逻辑中需要执行的线程,因此简化了逻辑控制和缓存单元。图中Control表示逻辑控制单元,ALU表示运算单元,Cache表示缓冲单元,DRAM表示内存单元。
2.2 统一计算设备架构编程
统一计算设备架构CUDA(Compute Unified Device Architecture)是NVIDIA在2007年推出的一种用于GPU的编程模型。该编程模型不需要借助于图形学应用程序编程接口(API),采用比较容易掌握的类C语言进行开发。
CUDA模型中的线程采用线程网格(grid)和线程块(block)2级结构。线程块网络和线程块中可以分别有多个线程块和线程(thread),且都有唯一的ID标志。线程是最基本的计算单元,可以分配到单个数据的计算中。以向量A[n]和B[n]相加为例,如果该程序在CPU上执行需要循环n次;当采用CUDA编程时,可以分配n个线程,单个线程根据自身ID来执行向量对应位置上元素的和运算,如A[i]+B[i],由此实现了并行化计算。
3 基于GPU的预条件处理QMR法
原-对偶内点法求解机组组合SDP模型时,求解式(6)所示的大型线性方程组为主要步骤,矩阵G的维数等于模型的约束条件数,例如10机24时段算例的约束条件数为1 488,20机算例为2 928,100机算例达到14448,且呈现高维数、稀疏、对称、半正定的特点,使用直接法(如Cholesky分解)求解需要大量的存储空间以及消耗很长的时间,而Krylov子空间法作为20世纪90年代才完整提出的一类迭代法,具有存储量少、计算量少且易于并行等优点,非常适合于并行求解大型稀疏线性方程组,且结合预条件处理技术可获得良好的收敛特性和较高的数值稳定性,目前已是求解大型稀疏线性方程组的最主要方法。关于Krylov子空间法的基本原理详见文献[12],这里不再赘述。
矩阵G具有部分特征根接近于0的特点,常用于求解对称矩阵的CG(Conjugate Gradient)法可能会导致数值的不稳定性,因此,本文采用预条件处理QMR法来求解大型稀疏线性方程组。
3.1 预条件处理的QMR法
设有n阶线性方程组:
其中,J为n×n维的实对称矩阵,k为n维向量,w为方程的解。
设w0为该方程组迭代计算的初值,算法流程如下。
d.若ρn-1<ε,结束计算;否则ρn=rnTun,βn=ρn/ρn-1,qn=un+βnqn-1,n=n+1,返回步骤b。
由此可知,除去步骤c中un=M-1rn的计算,n次循环迭代的计算量主要包括n次矩阵向量乘法、3n次向量内积运算和3n次向量加减法。上述运算可通过并行稀疏矩阵向量乘法和并行向量运算在GPU上实现并行运算,故并行算法实现的难点在于使用GPU计算预处理矩阵M和实现un=M-1rn运算。
3.2 基于矩阵分块的Incomplete Cholesky预处理矩阵计算
预处理技术通过改变系数矩阵的条件数来达到加快迭代法收敛速度的目的[12]。目前为止,尚没有一种适用于所有线性方程组的预处理技术,实际计算中应根据系数矩阵的特点来设计相应的预处理矩阵。文献[14-15]根据Chebyshev多项式求出矩阵A的近似逆矩阵作为M-1,加快了收敛速度,但仅适用于强正则矩阵。文献[16]基于最小化Frobenius范数‖I-AM‖的方法来设计预处理矩阵,取得了一定的效果。文献[17]提出了一种对称超松弛(SSOR)法预处理技术,通过矩阵相乘和相加运算便可得到矩阵M。Incomplete Cholesky[18]对于正定型系数矩阵是一种有效的预处理方法,但在分解过程中前后行(列)元素之间是顺序进行的,不利于并行化计算。
基于矩阵分块技术,本文提出一种Incomplete Cholesky并行预处理方法,在CSR稀疏矩阵存储格式下使用GPU实现了预处理矩阵的并行计算,提高了计算效率。
在求解UC问题的半定规模过程中,矩阵G的结构如图2所示,考虑到对称性,只对下三角矩阵部分进行分析,阴影部分表示非0元素,对角线的元素可分为各个独立的2×2矩阵,如Fi、Bi所示。可以看出矩阵Fi之间完全独立,可进行并行Cholesky分解;分解完成后,剩余矩阵部分B中非0元素利用Fi的分解结果进行Incomplete Cholesky分解,由于B中各行元素互相独立,因此可实现并行化;计算完成后,可在矩阵B对角线上继续寻找互相独立的2×2矩阵进行并行Cholesky分解,如此循环直至得到Incomplete Cholesky预处理矩阵M。
矩阵G的分块流程具体如下。
a.存放分块信息的向量Pos,flag=1,Pos[flag]=1,矩阵维数为N,i取2,j取1。
c.如果G[i,j]为非0元且i-j>2,flag=flag+1,Pos[flag]=i,转步骤e;否则转步骤d。
d.如果j
e.如果i
实际计算中,矩阵G以CSR格式存储,分块计算中只需遍历非0元,有效减少了计算时间;此外,采用原-对偶内点法计算时,经过少数几次迭代后,矩阵G的非0元的位置便恒定下来,因此,矩阵分块信息不需每次都进行更新。以10机系统为例,Incomplete Cholesky预处理矩阵计算的循环次数从分块前的1 488次降至分块后的96次,具体的计算消耗时间及加速比将在4.2中给出。
3.3 基于GPU的预处理QMR并行算法
CUDA并行计算kernel以线程网格(grid)的形式组织,每个线程网格由若干个线程块(block)组成,而每个线程块又由若干个线程(thread)组成,实质上,kernel是以block为单位执行的。
使用GPU实现基于矩阵分块的Incomplete Cholesky预处理矩阵计算如图3所示,给每个相互独立对角线上的2×2矩阵(F1、F2、F3、F4)分配相应线程块(block0、block1、block2、block3)进行Cholesky分解;分解完成后,给矩阵B分配线程块(block4、block5、block6)对相应行的非0元素进行Incomplete Cholesky分解。其中,由于矩阵F1、F2、F3、F4中计算量较小,线程块block0、block1、block2、block3中线程数取32;block4、block5、block6线程设计为二维形式,每一行线程对应于矩阵B中某一行的计算。
图4所示为QMR并行算法在CPU和GPU中的任务划分,将可以实现并行化的计算放在GPU中,而逻辑控制功能和简单的代数运算由CPU实现,既充分利用了GPU适合密集型并行运算的优点,又发挥了CPU具有逻辑控制功能的优势。值得注意的是,GPU任务中线性方程组求解是指QMR算法中的un=M-1rn运算,求解时存在前推和回代2个过程,前推过程可以利用已得到的矩阵G的正向分块信息实现并行化,而回代过程需要对矩阵G进行一次反向的分块计算并根据得到的信息并行计算即可。
4 算例分析
4.1 开发环境及算例介绍
本文以Microsoft Visual Studio 2008和CUDA平台为开发环境,采用C语言编写了基于GPU的Incomplete Cholesky预处理QMR并行算法,并在同一平台上编写了基于CPU的Incomplete Cholesky串行分解和Cholesky直接法求解线性方程组的程序。硬件平台:CPU为Intel Core 2,主频为2.4 GHz,内存为10 GB;GPU为NVIDIA Tesla C2050,显存频率为1147 MHz。
4.2 Incomplete Cholesky并行预处理矩阵的计算
衡量并行算法优劣的指标为所需存储量和加速比。对文中所述的Incomplete Cholesky预处理QMR而言,GPU并行算法所需的存储量明显小于CPU串行算法,因此只对算法的加速比进行分析。表1列出了对不同规模的矩阵进行Incomplete Cholesky分解时,CPU串行算法和GPU并行算法消耗的时间。可以看出,矩阵维数为1488和2928时,Incomplete Cholesky分解的串行算法消耗的时间要小于并行算法,这是由于计算量不是太大且数据在GPU内存和CPU内存间的通信需要消耗一定的时间造成的,随着矩阵维数从2 928增加到14 448,系数矩阵的分块信息没有发生改变,而每次循环计算时增加的计算量可以通过增加线程块的方式实现并行化,因此GPU并行算法消耗的时间逐渐小于CPU算法,维数为14448时可取得1.420的并行加速比。
4.3 基于GPU的QMR预处理并行算法
QMR算法中的参数ε设为10-10,表2所示为Cholesky直接法和基于GPU的QMR预处理并行算法对不同规模线性方程组求解所需的时间。
与Incomplete Cholesky并行算法类似,当维数为1 488时,直接法的运行时间要小于并行算法,随着维数的增加,并行算法的速度优势逐渐体现出来,最终可取得7.45的并行加速比。在不同规模算例情况下,本文并行算法在经过几次迭代后可取得满足计算精度的结果,表明了算法的正确性。表3为N=8 688时,QMR并行算法运行时间的分布。表中解线性方程表示使用前推和回代求解方程组;向量运算包括向量间、向量与常数以及向量内积等计算;其他部分包括CPU和GPU之间的数据传递、CPU的逻辑判断程序和CPU上代数计算等。虽然经过矩阵分块技术可以减少Incomplete Cholesky分解和使用前推回代法求解un=M-1rn的循环计算次数,然而其本身所具有的串行性质,使得其求解时间占总运行时间的绝大部分,而稀疏矩阵与向量乘法和向量相关运行运算在GPU可实现良好的并行化。
4.4 基于GPU的内点法求解机组组合问题的SDP模型
为了验证并行算法的有效性,采用10、20、40、60、80和100机24时段6个测试系统,20~100机算例通过对10机算例的扩展得到,其发电机参数及各时段负荷数据见文献[19],所有机组均考虑爬坡约束,旋转备用取系统总负荷的10%。
用SDP求解机组组合问题是一种直接求解法,不需要多重循环,也不同求解一系列子问题,可同时考虑所有的约束条件,由表4可见,通过30次左右循环计算,便可得到解结果。当算例为10机系统时,GPU并行内点算法的运行时间要略大于直接法,随着算例规模的增大,求解线性方程组式(6)的计算量逐渐增加,GPU并行算法的并行效率得到了体现,加速比从10机系统的0.95变大到100机系统的2.61。但是,由于SDP内点法除求解线性方程组外的其他计算也需要消耗一定的时间,因此取得的加速比要小于表2中的加速比。
建立机组组合模型时,机组启动费用采用时间的指数函数或者冷热启动三段式费用更加符合实际情况,然而却难以转换成SDP所要求的凸优化形式,因此,在建立UC问题的SDP模型时启动费用采用固定值方式,在通过内点法求解得到机组的最优启停状态并进行经济调度时,目标函数中再加入指数或者三段式的启动费用,这样可以保证计算结果的准确性。表5所示为采用本文算法对6个算例求解得到的运行成本。表6为不考虑爬坡约束时本文算法与其他算法计算结果的对比,表中,LR、GA、EP、LRGA、GAUC分别指拉格朗日松弛法、遗传算法、进化算法、拉格朗日-遗传混合算法、基于分类的遗传算法。
可以看出,本文算法可以很好地处理爬坡约束,得到的运行费用略大于不考虑爬坡约束的情况。从表6可以看出,SDP的并行内点法每次计算只需固定的迭代次数,随机性较小,可获得稳定的计算结果,得到的费用优于部分算法,并可得到较好的近似最优解。
通过上面的分析,可得到以下结论。
a.基于矩阵分块技术的Incomplete Cholesky并行预处理矩阵计算,可获得一定的加速比。由于分解本身具有串行的性质,可取得的加速比有限,同时,在矩阵维数较小且计算量不大情况下,计算时间反而略大于串行算法。
b.基于GPU的QMR预处理并行算法是一种有效的大型稀疏线性方程组求解方法,可通过少数几次迭代获得解结果。Incomplete Cholesky预处理矩阵和前推回代的并行计算时间占解方程总时间的绝大部分,但该预处理法很好地处理系数矩阵半正定的特点,且在维数较大时可获得良好的加速比。
c.SDP的并行内点法可提高算法的计算效率,但如1.1节所示,除式(6)所示的大型稀疏线性方程组求解外,包括其他大量的数据处理以及矩阵和向量间的基本运算,仍需要消耗一定的时间,故算法整体的加速比小于QMR预处理并行算法求解线性方程组。在建立机组组合的SDP模型时,文中所采用的启动费用的处理方式可以很好地解决启动费用难以化成凸规划形式的问题,提高了结果的准确性。
5 结论
移动平台GPU通用计算研究综述 篇6
GPU英文全称为Graphic Processing Unit, 中文翻译为图形处理器。近年来, GPU正在以远超摩尔定律的速度高速发展。GPU在高性能计算方面具有3大优势:高效的并行性、高密集的运算和超长的图形流水线。正是由于GPU的这些特点, 使越来越多的研究人员和商业组织开始利用GPU完成一些非图形绘制方面的计算, 开创了一个新的研究领域, 即基于GPU的通用计算, 其应用范围包括计算医学、计算化学、计算物理学、计算金融等。随着科技的发展, 硬件设备性能的不断加强, 可编程GPU已经从桌面平台搬移到手持设备上, 例如智能手机和游戏操作平台, 使移动平台具备了科学计算能力。
1 移动平台GPU通用计算的软硬件支持
在2013年3月之前, 移动平台上唯一可用做GPU通用计算的API只有OpenGL ES, 所以目前国内外移动平台GPU通用计算的研究还多数采用OpenGL ES语言[1,2,3,4,5]。通常在桌面上使用的更加高端的API, 如CUDA等, 在移动平台上是不支持的。
如今, OpenCL是一个广受欢迎的通用计算标准, 它是第一个面向异构系统通用目的并行编程的开放式、免费标准, 也是一个统一的编程环境, 便于软件开发人员为高性能计算服务器、桌面计算系统、手机设备编写高效轻便的代码。在移动端上, ARM、Imagination、高通、三星、德州仪器均保证支持OpenCL, 在其各自的平台上提供OpenCL SDK, 并进行过一些实例演示。索尼也选择在其Xperia系列设备上支持OpenCL。
2 国内外研究进展
2.1 移动GPGPU速度和功耗表现
利用移动平台做并行计算有两个目的: (1) 为了提高应用或程序运行速度, 满足实时性要求, 例如面部识别; (2) 为了降低应用或程序运行功耗, 有效缓解移动电源电量有限的问题。下面分别进行说明。
首先分析移动GPGPU的速度表现。由于GPU支持大规模的并行运算, 较CPU有更多运算单元, 因而在GPU上做通用计算可以有极佳的速度表现。韩国汉阳大学的Jungsik Park[6]等在文章中介绍其用移动平台GPU开展立体图像校正的研究。他们选用的通用计算平台为OpenGL ES 2.0, 研究结果发现GPU执行立体图像校正的时间比单独CPU执行时间快两到三倍。还有很多研究者同样有效利用了移动平台GPU超强的通用计算速度优势[2,3,4,5]。
接着分析移动GPGPU的功耗表现。根据A P Chandrakasan[7]等在文章中的描述, CPU中门切换消耗的能量为电容 (C) 乘以电压 (V) 的平方。这些门在1秒内切换的次数等于频率。因此一个微处理器的功耗计算为P=CV2 f。如果将一个频率为f、电压为V的单核处理器与一个类似的双核处理器 (每个核芯的频率为f/2) 进行比较, 芯片中的回路数会提高。理论上这会将电容提高2.2倍, 不过电压会显著减少到0.6V。所以在这两种情况下, 每秒执行的指令数一样, 但双核处理器中的功耗是单核处理器的0.396倍。因此低频率运行的多核在功耗上会有显著提高, GPU通用计算在功耗上的表现也是我们关注的。美国莱斯大学的Blaine Rister等[1]使用移动平台GPU运行当前流行的SIFT算法, 相比CPU执行有4~7倍的提速, 同时每张图片处理节省能耗87%。
2.2 移动设备嵌入式OpenCL性能功耗表现
2009年NOKIA公司用虚拟的嵌入式编程环境模拟OpenCL在移动设备上的表现, 研究结果表明嵌入式GPU能为算法在速度和功耗方面提供极佳表现[8]。
随着OpenCL在移动设备上得到广泛支持, 基于移动设备的GPU通用计算将会成为一个潮流。来自美国莱斯大学的Guohui Wang[9]等在第一时间使用移动GPU中的OpenCL做通用计算, 并发表了相关研究。OpenCL是专为异构计算设计的程序框架, 其可以跨多个不同的计算平台。研究成果表明, 通过异构加速, 物品移除算法从CPU单独执行所需的393.8秒缩短到只需1~5秒, 完全符合移动应用的实时性、可用性。2013年9月, Guohui Wang等[10]又发表了在智能手机上基于OpenCL的SIFT算法研究。结果显示GPGPU运算相对于单独CPU运算有1.69倍的加速和41%的能量节省。
3 移动平台GPU通用计算中需要注意的问题
3.1 移动内存限制问题
嵌入式GPU没有自己的图形内存, 而需要与其它计算部件共享系统总线以获得外部内存。GPU的执行受限于内存, 当移动计算涉及较大数据计算时, 选择合理的算法是必要的。NOKIA在题为OpenCL in Handheld Devices的报告中将相同图形处理算法在移动平台上做了3次测试, 即单独CPU运行、单独GPU运行、CPU与GPU联合运行。结果发现单独用GPU运行在速度与功耗的表现上均优于单独用CPU运行, 更重要的发现是CPU与GPU联合采用OpenCL并行运行的表现虽优于单独CPU运行, 但劣于单独GPU运行。经分析得知, CPU与GPU之间的数据传输是并行表现不佳的重要原因。CPU与GPU有其各自的内存, 即便是如今的APU也仅仅是物理上将CPU和GPU集成在一个芯片上, 从软件角度上来说它们是完全分离的。
解决方法是当CPU不用为GPU传输数据时才让CPU做框架计算, 如此优化时序安排可以让数据传输全速运行。而AMD公司推出的Kaveri处理器创新采用hUMA方法, 即实现了异构系统同一内存寻址, 从根本上解决了CPU和GPU之间数据传输的不经济问题。
3.2 移动设备功耗测量问题
目前国内外测量移动设备或开发板的功率消耗只能做到大致测量。困难点在于测量消耗功率需要测量开发板的供电电流, 这要求测量仪器有很好的精度;另外, CPU和GPU整合在一个芯片上, 因而要想单独测得各个部件的消耗功率很难。大多数研究者选择测量整机功耗来粗略代替CPU和GPU的消耗功率[10]。为得到有效的SoC系统级功耗估算值, 需要单独计算出显示屏和SoC外部其它耗电部件的功耗, 才能排除它们的影响。另外高通公司为开发者提供了Trepn插件, 用来测量程序运行功耗, 也成为解决功耗测量问题的一种方案。
4 移动平台OpenCL并行程序开发案例
下面介绍移动平台上OpenCL的实现, 目的是说明如何在移动平台上编写OpenCL并行程序。使用的移动平台为小米2S, 搭载的操作系统为基于Android OS v4.1的双MIUI V5, GPU型号为高通Adreno320, 支持OpenCL编程。具体开发步骤如下:
(1) 首先需要安装好JDK、eclipse、ADT、Android sdk等基本的Android应用程序开发环境, 在此基础上由于需要在Android平台上使用Java调用OpenCL写好的N-ative C, 因此需要搭建好NDK开发环境。
(2) NDK开发环境配置好后, 开始编写OpenCL代码, 本案例使用的是简单的矩阵相乘。在Eclipse中新建一个工程FirstTest, 对布局文件进行修改。
(3) 在src包下新建一个Java类, 命名为nativeSimpleMultiply, 再在nativeSimpleMultiply类中声明一个函数, 命名为simpleMultiplyMain。具体如下:
package com.firsttest;
public class nativeSimpleMultiply{public native int simpleMultiplyMain () ;}
(4) 生成com_firsttest_nativeSimpleMultiply.h的头文件。具体是使用Cygwin进入workspace中工程所在目录, 输入$javah–classpath bin/class–d jni com.ndk.HelloJni。结果在工程FirstTest下出现jni包, 包内是生成的com_firsttest_nativeSimpleMultiply.h。
(5) 将之前写好的矩阵相乘的C代码移植过来, 以完成本地实现, 并将之命名为com_firsttest_nativeSimpleMultiply.c。
(6) 编写Android.mk文件, 用其向编译系统描述源代码, 具体代码如下:
LOCAL_PATH:=$ (call my-dir)
include$ (CLEAR_VARS)
LOCAL_MODULE:=NSM
LOCAL_SRC_FILES:=com_firsttest_nativeSimpleMultiply.cpp aopencl.c
LOCAL_LDLIBS+=-L$ (SYSROOT) /usr/lib-llogldl
include$ (BUILD_SHARED_LIBRARY)
(7) 编写Application.mk文件, 用其描述在应用系统中所需的模块 (即静态库或动态库) , 代码如下:
APP_CPPFLAGS:=-frtti-fexceptions
APP_ABI:=armeabi-v7a
APP_PLATFORM:=android-8
STLPORT_FORCE_REBUILD:=true
APP_STL:=gnustl_static
(8) 将aopencl.c和aopencl.h加入到jni包中, aopencl.h头文件中有各种OpenCL函数的声明。
(9) 编译生成libNSM.so动态链接库, 使其能够被Java调用。
(10) 编写MainActivity.java, 实现整个应用功能, 代码如下:
需要特别说明的是这里的static{System.loadLibrary ("NSM") ;}用于装载动态库libNSM.so。
至此在移动平台上编写OpenCL并行程序的整个过程已介绍完毕。该程序开发框架如图1所示, 应用程序的Java部分通过JNI完成对应用程序Native C部分的调用。其中Native C中写有OpenCL并行程序, 该并行程序通过libOpenCL.so与设备的GPU和CPU交互完成并行计算。
5 结语
移动平台GPU在速度和功耗方面具有非凡表现, 随着移动设备供应商对OpenCL标准的支持, 移动平台在通用计算上展现出无穷的潜力, 相信将会有越来越多基于OpenCL的应用涌现。但是, 由于移动GPU与CPU计算单元和内存带宽的限制, 使移动平台GPU存在一定的瓶颈, 如果下一代移动GPU可以拥有更好的内存科技与更高速的内存带宽, 移动设备更加高速的异构计算技术将是可以预见的。国内利用移动平台GPU做通用计算的深入研究基本为零, 因此该研究前景广阔且具有重要意义。
参考文献
[1]B RISTER, G WANG, M WU, et al.A fast and efficient SIFT detector using the mobile GPU[C].In ICASSP 2013-IEEE International Conference on Acoustics Speech and Signal Processing, Piscataway, NJ:IEEE Press, 2013:2674-2678.
[2]N SINGHAL, W Y JIN, H Y CHOI, et al.Implementation and optimization of image processing algorithms on embedded GPU[C].IEICE Transactions on Information and Systems, Japan:IEICE Press, 2012:1475-1484.
[3]Y C WANG, S PANG, K T CHENG.A GPU-accelerated face annotation system for smartphones[C].In 18th ACM International Conference on Multimedia ACM Multimedia 2010, New York:Association for Computing Machinery Press, 2010:1667-1668.
[4]N SINGHAL, I K PARK, S CHO.Implementation and optimization of image processing algorithms on handheld GPU[C].In IEEE International Conference on Image Processing, Piscataway, NJ:IEEE Computer Society Press, 2010:4481-4484.
[5]R HOFMANN, H SEICHTER, G REITMAY.A GPGPU accelerated descriptor for mobile devices[C].In 2012IEEE International Symposium on Mixed and Augmented Reality[C].Washington, DC:IEEE Computer Society Press, 2012:289-290.
[6]J PARK, J CHOI, B K.SEO, et al.Fast stereo image rectification using mobile GPU[C].In The Third International Conference on Digital Information Processing and Communications, USA:SDIWC, 2013:485-488.
[7]CHANDRAKASAN A P, POTKONJAK M, MEHRA R, et al.Optimizing power using transformations[J].Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 1995, 14 (1) :12-31.
[8]J LESKELA, J NIKULA, M SALMELA.OpenCL embedded profile prototype in mobile device[C].In 2009IEEE Workshop on Signal Processing Systems, Piscataway, NJ:IEEE Press, 2009:279-284.
[9]G WANG, Y XIONG, J YUN, et al.Accelerating computer vision algorithms using OpenCL framework on the mobile GPU-A case study[C].In ICASSP 2013-IEEE International Conference on Acoustics Speech and Signal Processing, Piscataway, NJ:IEEE Press, 2013:2629-2633.