GPU上编辑距离算法的自动参数优化

### GPU上编辑距离算法的自动参数优化 #### 1. 引言 近似字符串匹配是分析给定字符串与模式的相似性并找到其最佳对齐的问题，它在信息科学中是一个重要问题，不仅应用于文本检索，还广泛应用于计算生物学等多个领域。然而，近似字符串匹配的计算包含一些计算量较大的步骤。 GPU最初是为图像处理而创建的硬件，具有大量计算单元，能以相对较低的成本实现高峰值性能。通用GPU计算（GPGPU）技术应运而生，使得GPU的强大计算能力可用于图像处理之外的计算。尽管随着GPU架构的改进和一些有用开发环境（如NVIDIA的CUDA）的出现，GPGPU编程变得更加容易，但要充分发挥GPU的性能仍然具有挑战性。 为了充分利用GPU的计算单元，需要选择高度并行化的算法并创建大量线程。同时，内存访问成本也是决定整体性能的一个重要因素。为了降低这一成本，通过限制每个线程使用的资源大小并增加线程总数来增加同时执行的线程数量以隐藏延迟非常重要，此外，有效利用低容量但快速的共享内存也是常见的做法。 对于GPU上的近似字符串匹配，已有多项关于在GPU上实现Smith - Waterman算法并行版本的研究。这些研究大多强调在有大量查询时的性能，而对由于查询数量相对于GPU容量不足导致活动线程数量受限的情况考虑较少。当活动线程数量不足时，由于无法隐藏延迟或实现负载均衡，性能会下降。 本文提出了一种在GPU上计算一对字符串编辑距离的并行算法。通过分析计算时间与并行化相关参数（块大小参数和活动线程数量）之间的关系，发现设备内存的延迟及其隐藏对性能的影响最大。在此基础上，构建了执行时间的估计模型，并将其应用于系统以自动选择最佳块大小。 #### 2. 编辑距离算法与并行化 ##### 2.1 动态规划算法 编辑距离定义为将一个字符串转换为另一个字符串所需的最少编辑操作次数，编辑操作包括插入、删除和替换字符。例如，字符串“change”和“hunger”的编辑距离为3，通过删除‘c’、将‘a’替换为‘u’以及插入‘r’可以实现转换。 用 $d(str1, str2)$ 表示两个字符串 $str1$ 和 $str2$ 的编辑距离，$|str|$ 表示字符串 $str$ 的长度，$str[i]$ 表示字符串 $str$ 的第 $i$ 个字符（$0 ≤ i < |str|$），$str[i..j]$ 表示字符串 $str$ 从第 $i$ 个字符到第 $j$ 个字符的子字符串（$0 ≤ i ≤ j < |str|$）。 编辑距离 $d(str1, str2)$ 可以通过动态规划计算，具体公式为： $d(str1[0..i], str2[0..j]) = min(d(str1[0..i - 1], str2[0..j]) + 1, d(str1[0..i], str2[0..j - 1]) + 1, d(str1[0..i - 1], str2[0..j - 1]) + c(str1[i], str2[j]))$ 其中，当 $str1[i]$ 等于 $str2[j]$ 时，$c(str1[i], str2[j])$ 为0，否则为1。 通过完成一个类似于图1所示的 $str1$ 和 $str2$ 前缀编辑距离 $d(str1[0..i], str2[0..j])$ 的表格，可以计算出 $d(str1, str2)$。表格最左边和最上边的单元格值可以直接得到，而每个内部单元格的值可以通过其左侧、左上和上方单元格的值使用上述公式计算得到，计算顺序是从左上角到右下角，计算量为 $O(|str1||str2|)$。该计算具有一定的并行性，并且单元格值的计算顺序具有一定的灵活性。 ##### 2.2 GPU架构 GPU主要由多个多处理器（MP）和一个设备内存组成。一个MP是一组由八个称为标量处理器（SP）的简单处理器组成。同一MP中的SP像SIMD指令一样，同时对不同数据执行相同的指令。GPU通过使众多SP并行执行相同操作来提供强大的性能。 设备内存可从CPU和GPU中的所有MP访问。通常，GPU程序首先将数据从CPU的主机内存复制到GPU的设备内存，然后运行并行代码（CUDA内核），使每个MP从设备内存读取数据、进行计算并将结果写回内存，最后将结果传输回主机内存。 除了设备内存，每个MP都有自己的低延迟内存，称为共享内存。通过共享内存，每个SP可以非常快速地访问同一MP中其他SP的计算结果。 为了使GPU执行任务，需要给它一组称为网格（grid）的线程。一个网格由多个称为线程块（thread block）的线程组组成。网格、线程块和线程的关系对应于GPU、MP和SP的关系。每个线程块被分配到一个MP，线程块中的每个线程被分配到MP中的一个SP。每个SP（或MP）通过频繁切换要执行的线程（或线程块）来并发执行多个线程（或线程块）。 为了充分发挥GPU的性能，需要考虑以下两点： - **任务和硬件的层次结构**：同一MP中的SP只能同时执行相同的指令，因此应避免条件分支，使同一线程块中线程执行的指令序列尽可能接近。同一线程块中的线程可以通过共享内存和快速同步指令快速通信，而