异构计算背景
近年来，随着深度学习技术的突破，掀起了新一轮的人工智能浪潮。AI 技术和市场在蓬勃发展的同时，对海量数据进行计算的需求呈指数级增长。随着英特尔原定 16 年上市的 10nm 工艺芯片连续跳票三年，CPU 的计算力增长速度大幅放缓。为了满足计算力的增长需求，异构计算越来越受到业界的重视。
异构计算，是将 CPU、GPU、FPGA、ASIC 等不同体系结构的处理器放在一起，共同完成计算的方式。不同的处理器，有着不同的特性，通常会根据应用场景的需求来选择搭配处理器。目前最常见的异构计算架构是 CPU + GPU 的组合。CPU 是通用的中央处理器，会兼顾着计算和控制，擅长处理业务逻辑。GPU 是图像显示处理器，负责图像的显示和渲染，由于像素点之间通常是不相关的，因此可以并行处理。GPU 内部控制单元很少，主要由计算单元组成，通过 NVIDIA CUDA、OpenCL 等编程模型，可以充分利用 GPU 的海量算力，完成模型训练、模型推理等计算密集型任务。
基于异构计算的图像搜索
针对海量指纹图像的搜索场景，墨奇创造了一套基于异构并行计算的搜索技术。
特征表示
我们对于指纹图像，通过对视觉信号的学习提炼获得特征。特征具备不同的尺度，既有全局的指纹纹型特征，也有局部的指纹分叉点、断点等细节特征。特征也具备不同的维度，如中心的位置、分叉点的方向、纹线的走向等。通过对这些多尺度、多维度的特征进行距离计算，就可以获取指纹图像的相似度。
搜索算法
以此为基础，我们设计了一套两阶段的搜索算法。第一阶段，我们进行全量数据的快速初筛比对。我们采用指纹特征中的一些简单特征向量，通过汉明距离的计算、聚合、排序，初筛过滤保留约 0.1%-1% 的数据。在该阶段，特征的距离计算需要极高的算力支持，因此我们选用 GPU，利用其大量的计算单元和充分的并行度，在很短的时间内完成海量搜索计算。第二阶段，我们对于保留的数据，进行精确的匹配搜索。我们会对多尺度、多维度特征，进行精确的距离计算、融合算分，最后聚合、排序，保留前 1/5/10 名。在该阶段的搜索过程中，不仅有大量的计算，还有很多的逻辑控制，如用哈希对特征进行分类，用深度优先、广度优先等不同的策略进行相关特征的匹配搜索。为兼顾计算和逻辑控制，该阶段的工作交由 CPU 负责。
基于 GPU + CPU 的两阶段算法，我们既实现了保证了极高的精度，同时也实现了系统搜索性能的大幅提升。
异构计算中的性能优化
整个系统的比对搜索性能优化，主要集中在第一阶段，即 GPU 搜索比对阶段。关于 GPU 比对这个部分，我们会从数据传输、数据访问、计算等几个方面来分别介绍。
数据传输
在程序搜索比对的过程中，指纹的特征数据是存在于 CPU 主存，通过 PCIE 传入 GPU 显存。在这个过程中，有两点需要注意。
一方面，特征数据在主存中有两种存在形式：可分页内存和页锁定内存。通常程序运行时用的都是可分页内存，这种形式的内存数据，在内存空间快满的时候，是可以被置换到磁盘上的。页锁定内存则相反，一经分配，则不能被分页换出。当 GPU DMA 进行数据传输时，总是需要先创建页锁定内存，从可分页内存拷贝数据，然后才能进行数据传输，可分页内存的数据传输性能比较差。因此，我们将指纹的特征数据直接放在页锁定内存中，相当于牺牲一部分内存空间，换取传输的时间，保证 GPU 比对过程中的传输性能最大化。
另一方面，CPU 主存和 GPU 显存的数据传输链中，PCIE 是显然的瓶颈。通常 PCIE 3.0 16 路带宽实测最大约 12 GB/s，明显低于主存、显存的带宽，在机器装配时，务必要避免 GPU 插在 PCIE x4、x8 的卡槽，确保其插在 x16 的卡槽，保证带宽的最大化。同时，尽量避免两张卡插在同一个 PCIE Switch 上，否则在比对过程中，如果程序在同时往两张卡传数据，那么单张卡的传输带宽会减半。
数据访问
GPU 的存储模型分两类：片上存储、板载存储。片上存储是存在于 GPU 计算芯片上的存储单元，主要由寄存器和共享内存（Shared Memory）组成，类似 CPU 的寄存器和 L1/2/3 级缓存，特点是读写性能好，但是存储空间小。板载存储是在 GPU 计算单元外的单独存储空间，称为 GPU 全局内存（Global Memory），类似 CPU 主存，特点是空间大（e.g. RTX 2080ti 11GB，T4 16G），整体的读写性能相对片上存储较差。
指纹特征数据从 CPU 主存传入 GPU 显存时，会存放于全局内存。从全局内存进行高效的数据读取（写入），对系统的整体性能影响很大。为了优化数据读取，我们需要理解 GPU 的指令执行模式和内存访问模式：1) 单指令流多数据流（SIMD）的指令执行模式，是指 GPU 计算时，会调度多个线程（通常 32 个线程为一组 Warp）同时执行同一条指令，每个线程可以访问不同的内存地址。2) GPU 访问全局内存时，每次 cache line 会读取 32 byte 的数据。基于 GPU 的架构设计，一组 Warp 在执行数据读取时，当每个线程需要读取 1 个 byte 并且访问的是相邻地址的数据，那么该指令一共需要访问 32 byte 的数据，一次内存读取即可获取全部数据。而当每个线程隔 1 位读取时，该指令一共需要访问 64 byte 地址的数据，需要两次内存读取，整体的读取性能会下降一半以上。读取数据的地址间隔越大，整体读取的性能就越糟糕。因此在做算法设计时，我们应当尽量保证访问的数据为相邻数据，且地址的起始点为 32 的倍数，那么就可以合并访问，提升整体的数据读取性能。
当 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。
为实现整体性能的最大化，我们参考了局部性原理做程序设计。计算前，我们会将计算时多次使用的数据从全局内存载入到共享内存，计算时的读写都放在共享内存，计算完成后再将结果写回全局内存。从全局内存读取数据时，我们尽量实现合并访问。从共享存储读写数据时，我们尽量避免 bank conflicts。这样，我们就能够充分的利用 GPU 内各个存储组件的特性，实现最佳的读写性能。
并行计算
GPU 计算的整体流程，通常由三个步骤组成：将数据从主存传入 GPU 显存，GPU kernel 执行计算，将结果传回主存。整个流程的优化原则，是提高整体并行度，使得 GPU 占用率尽可能高。基于这个原则，有两个主要的优化方向：1) 并行处理数据传输和计算，提升数据传输的带宽利用率和 Kernel 计算的 GPU 占用率。2) 提升 Kernel 计算效率，使得计算尽可能快。
为了并行处理数据传输和计算，我们可以将需要处理的进行合理的拆分，用不同的线程流（Cuda Stream），异步的进行数据拷贝（cudaMemCpy）和 Kernel 计算，提升整体的并行度。为此，我们设计的 GPU 比对算法，是对指纹按照不同的手指指位（拇指、食指等）进行分类，对数据进行拆分，对每个类别的数据分别进行数据传输和计算，实现并行度的最大化。
Kernel 计算效率的提升，尽可能的避免分支（Branching）是一项重要的原则。因为 GPU 是 32 个线程（Warp）并行执行同样的指令，当存在 if else 等分支情况时，会出现部分线程空闲状态，造成整体计算性能下降。如图所示，在执行 if 时，只有三个计算单元是执行状态，剩下的是空闲状态。执行 else 时，则反之。为了避免分支，我们会尽量合并不同的分支条件，对于无法合并的，我们尽量将分支相关部分放在 CPU 处理。我们会根据分支条件，拆分成不同的 Kernel，使得一个 Kernel 内尽量避免分支出现，确保 GPU 计算时的性能最大化。
总结与展望
本文从特征表示、搜索算法介绍了异构计算搜索技术，并通过数据传输、数据访问、计算等方面阐述了 GPU 比对优化的实践经验。基于这套异构并行计算技术，墨奇创造了新一代指纹掌纹识别系统，在 10 亿级的指纹库上实现了秒级搜索。该技术目前应用于 2 个 10 亿级的指纹中心，处理了超过 数十 亿枚指掌纹数据。
未来，我们会持续积累和探索异构并行计算相关的技术，在边缘端和服务端尝试不同的硬件（NPU、GPU、FPGA 等）提升计算性能，并在更多更具挑战的业务场景中发挥价值，助力墨奇建设下一代非结构化数据搜索引擎。
