基于异构计算的图像搜索

分享至:

异构计算背景

近年来,随着深度学习技术的突破,掀起了新一轮的人工智能浪潮。AI 技术和市场在蓬勃发展的同时,对海量数据进行计算的需求呈指数级增长。随着英特尔原定 16 年上市的 10nm 工艺芯片连续跳票三年,CPU 的计算力增长速度大幅放缓。为了满足计算力的增长需求,异构计算越来越受到业界的重视。

异构计算,是将 CPU、GPU、FPGA、ASIC 等不同体系结构的处理器放在一起,共同完成计算的方式。不同的处理器,有着不同的特性,通常会根据应用场景的需求来选择搭配处理器。目前最常见的异构计算架构是 CPU + GPU 的组合。CPU 是通用的中央处理器,会兼顾着计算和控制,擅长处理业务逻辑。GPU 是图像显示处理器,负责图像的显示和渲染,由于像素点之间通常是不相关的,因此可以并行处理。GPU 内部控制单元很少,主要由计算单元组成,通过 NVIDIA CUDA、OpenCL 等编程模型,可以充分利用 GPU 的海量算力,完成模型训练、模型推理等计算密集型任务。

基于异构计算的图像搜索

针对海量指纹图像的搜索场景,墨奇创造了一套基于异构并行计算的搜索技术。

特征表示

我们对于指纹图像,通过对视觉信号的学习提炼获得特征。特征具备不同的尺度,既有全局的指纹纹型特征,也有局部的指纹分叉点、断点等细节特征。特征也具备不同的维度,如中心的位置、分叉点的方向、纹线的走向等。通过对这些多尺度、多维度的特征进行距离计算,就可以获取指纹图像的相似度。

Image

搜索算法

以此为基础,我们设计了一套两阶段的搜索算法。第一阶段,我们进行全量数据的快速初筛比对。我们采用指纹特征中的一些简单特征向量,通过汉明距离的计算、聚合、排序,初筛过滤保留约 0.1%-1% 的数据。在该阶段,特征的距离计算需要极高的算力支持,因此我们选用 GPU,利用其大量的计算单元和充分的并行度,在很短的时间内完成海量搜索计算。第二阶段,我们对于保留的数据,进行精确的匹配搜索。我们会对多尺度、多维度特征,进行精确的距离计算、融合算分,最后聚合、排序,保留前 1/5/10 名。在该阶段的搜索过程中,不仅有大量的计算,还有很多的逻辑控制,如用哈希对特征进行分类,用深度优先、广度优先等不同的策略进行相关特征的匹配搜索。为兼顾计算和逻辑控制,该阶段的工作交由 CPU 负责。

Image

基于 GPU + CPU 的两阶段算法,我们既实现了保证了极高的精度,同时也实现了系统搜索性能的大幅提升。

Image

异构计算中的性能优化

整个系统的比对搜索性能优化,主要集中在第一阶段,即 GPU 搜索比对阶段。关于 GPU 比对这个部分,我们会从数据传输、数据访问、计算等几个方面来分别介绍。

数据传输

在程序搜索比对的过程中,指纹的特征数据是存在于 CPU 主存,通过 PCIE 传入 GPU 显存。在这个过程中,有两点需要注意。

一方面,特征数据在主存中有两种存在形式:可分页内存和页锁定内存。通常程序运行时用的都是可分页内存,这种形式的内存数据,在内存空间快满的时候,是可以被置换到磁盘上的。页锁定内存则相反,一经分配,则不能被分页换出。当 GPU DMA 进行数据传输时,总是需要先创建页锁定内存,从可分页内存拷贝数据,然后才能进行数据传输,可分页内存的数据传输性能比较差。因此,我们将指纹的特征数据直接放在页锁定内存中,相当于牺牲一部分内存空间,换取传输的时间,保证 GPU 比对过程中的传输性能最大化。

Image

另一方面,CPU 主存和 GPU 显存的数据传输链中,PCIE 是显然的瓶颈。通常 PCIE 3.0 16 路带宽实测最大约 12 GB/s,明显低于主存、显存的带宽,在机器装配时,务必要避免 GPU 插在 PCIE x4、x8 的卡槽,确保其插在 x16 的卡槽,保证带宽的最大化。同时,尽量避免两张卡插在同一个 PCIE Switch 上,否则在比对过程中,如果程序在同时往两张卡传数据,那么单张卡的传输带宽会减半。

Image

数据访问

GPU 的存储模型分两类:片上存储、板载存储。片上存储是存在于 GPU 计算芯片上的存储单元,主要由寄存器和共享内存(Shared Memory)组成,类似 CPU 的寄存器和 L1/2/3 级缓存,特点是读写性能好,但是存储空间小。板载存储是在 GPU 计算单元外的单独存储空间,称为 GPU 全局内存(Global Memory),类似 CPU 主存,特点是空间大(e.g. RTX 2080ti 11GB,T4 16G),整体的读写性能相对片上存储较差。

Image

指纹特征数据从 CPU 主存传入 GPU 显存时,会存放于全局内存。从全局内存进行高效的数据读取(写入),对系统的整体性能影响很大。为了优化数据读取,我们需要理解 GPU 的指令执行模式和内存访问模式:1) 单指令流多数据流(SIMD)的指令执行模式,是指 GPU 计算时,会调度多个线程(通常 32 个线程为一组 Warp)同时执行同一条指令,每个线程可以访问不同的内存地址。2) GPU 访问全局内存时,每次 cache line 会读取 32 byte 的数据。基于 GPU 的架构设计,一组 Warp 在执行数据读取时,当每个线程需要读取 1 个 byte 并且访问的是相邻地址的数据,那么该指令一共需要访问 32 byte 的数据,一次内存读取即可获取全部数据。而当每个线程隔 1 位读取时,该指令一共需要访问 64 byte 地址的数据,需要两次内存读取,整体的读取性能会下降一半以上。读取数据的地址间隔越大,整体读取的性能就越糟糕。因此在做算法设计时,我们应当尽量保证访问的数据为相邻数据,且地址的起始点为 32 的倍数,那么就可以合并访问,提升整体的数据读取性能。

Image

当 GPU 计算时,数据会从全局存储载入到片上存储。片上存储的共享内存,是片上最大的存储空间(48 KB),通常用作高速缓存。共享内存的结构如下图所示,由 32 个 bank 组成,每一格对应 4 byte 数据。地址编号为 0, 32, 64 等,对应同一个 bank 0,以此类推。基于这个结构,在从共享内存进行数据读取时,有三种情况:1) 当 Warp 的 32 个线程同时访问不同的 bank,如编号 0 – 31,可以一次访问读取所有数据,能实现最大带宽,这是最理想情况。2) 当不同线程访问同一个 bank 的不同地址时,如两个线程同时访问 0 和 32,那么这条指令会对应两次读取,会造成性能下降一半,这就是 bank conflict。3) 当所有线程读取同一个 bank 的同一个地址时,此时数据读取会存在广播的机制,只需要一次读取即可,不会造成 bank conflict。我们在做程序设计时,访问共享内存的部分,需要特别注意避免 bank conflicts。

Image

为实现整体性能的最大化,我们参考了局部性原理做程序设计。计算前,我们会将计算时多次使用的数据从全局内存载入到共享内存,计算时的读写都放在共享内存,计算完成后再将结果写回全局内存。从全局内存读取数据时,我们尽量实现合并访问。从共享存储读写数据时,我们尽量避免 bank conflicts。这样,我们就能够充分的利用 GPU 内各个存储组件的特性,实现最佳的读写性能。

并行计算

GPU 计算的整体流程,通常由三个步骤组成:将数据从主存传入 GPU 显存,GPU kernel 执行计算,将结果传回主存。整个流程的优化原则,是提高整体并行度,使得 GPU 占用率尽可能高。基于这个原则,有两个主要的优化方向:1) 并行处理数据传输和计算,提升数据传输的带宽利用率和 Kernel 计算的 GPU 占用率。2) 提升 Kernel 计算效率,使得计算尽可能快。

为了并行处理数据传输和计算,我们可以将需要处理的进行合理的拆分,用不同的线程流(Cuda Stream),异步的进行数据拷贝(cudaMemCpy)和 Kernel 计算,提升整体的并行度。为此,我们设计的 GPU 比对算法,是对指纹按照不同的手指指位(拇指、食指等)进行分类,对数据进行拆分,对每个类别的数据分别进行数据传输和计算,实现并行度的最大化。

Image

Kernel 计算效率的提升,尽可能的避免分支(Branching)是一项重要的原则。因为 GPU 是 32 个线程(Warp)并行执行同样的指令,当存在 if else 等分支情况时,会出现部分线程空闲状态,造成整体计算性能下降。如图所示,在执行 if  时,只有三个计算单元是执行状态,剩下的是空闲状态。执行 else 时,则反之。为了避免分支,我们会尽量合并不同的分支条件,对于无法合并的,我们尽量将分支相关部分放在 CPU 处理。我们会根据分支条件,拆分成不同的 Kernel,使得一个 Kernel 内尽量避免分支出现,确保 GPU 计算时的性能最大化。

Image

总结与展望

本文从特征表示、搜索算法介绍了异构计算搜索技术,并通过数据传输、数据访问、计算等方面阐述了 GPU 比对优化的实践经验。基于这套异构并行计算技术,墨奇创造了新一代指纹掌纹识别系统,在 10 亿级的指纹库上实现了秒级搜索。该技术目前应用于 2 个 10 亿级的国家级指纹中心,管理了超过 40 亿枚指掌纹数据。

未来,我们会持续积累和探索异构并行计算相关的技术,在边缘端和服务端尝试不同的硬件(NPU、GPU、FPGA 等)提升计算性能,并在更多更具挑战的业务场景中发挥价值,助力墨奇建设下一代非结构化数据搜索引擎。

分享至:
您已经发表过意见了!
Social media & sharing icons powered by UltimatelySocial