使用Windows平台下的VS2022集成CUDA环境进行开发，CUDA版本11.8，硬件平台为NVIDIA RTX 2060。

本项目共对6种算法进行加速并对算法性能进行比较。

暴力算法逐字符进行比较，平均时间复杂度 $O(n)$，最差时间复杂度$O(n \times m)$。 CUDA加速时我们令每个线程负责文本中某个位置的比较，同时我们会将模式串与每个block需要处理的文本加载进共享内存。同时由于需要找到所有匹配的位置，我们通过私有化原子操作将匹配结果写入共享内存，最后再将各个block的结果合并到全局内存中。

KMP通过检查模式串某个位置之前的子串的后缀是否有模式串的前缀与其对应来构造next数组。next数组中存储该位置之前的子串对应的前缀的下一个位置。 执行匹配时从前向后匹配，匹配失败时，将模式串滑动为next数组中存储的位置继续进行比较。 通过KMP方法可以避免匹配失败后回溯，最差时间复杂度为 $O(n+m)$。

BM通过构建坏字符和好后缀两个数组来进行启发式搜索，坏字符数组记录字母表中每种字符在模式串中最后出现的位置，若不存在则为-1。好后缀数组记录模式串的每个后缀在除了自己本身所在的位置之外最后一次出现的位置，若不存在则为-1。 在执行匹配时我们执行如下过程：我们匹配时由后向前进行匹配，匹配失败时检查失败位置的字符在坏字符数组中的值，与当前位置值作差作为跳转长度。同时检查已匹配的后缀，对于第一个被发现在模式串中出现过的后缀，将模式串长度减去好后缀中存储位置作为跳转长度。取两种跳转长度的最大值，跳转长度最小值限制为1。 BM算法最好时间复杂度为 $O(n/m)$，最差时间复杂度为 $O(n \times m)$。

Sunday算法中与BM算法类似，也会记录字母表中某一字符最后出现的位置。 在执行匹配时执行如下过程：从前向后进行匹配，匹配不成功时检查模式串之后的一个字符在模式串中最后一次出现的位置，二者之差作为跳转长度。 Sunday算法的平均时间复杂度为 $O(n)$, 最差时间复杂度为 $O(n \times m)$。

以上三种算法采用同一种加速思路：由每个线程负责对某一段小文本执行字符串匹配，若该大小设置的过小则相当于是暴力算法，故本项目中设置的文本大小为模式串大小的四倍。在这种情况下每个block理论上可以匹配的位置数量会超过共享内存的大小，故我们只将模式串和各个算法构建的表加载进共享内存。 KMP算法的next数组通过递推来构建，故未使用CUDA加速，但是BM算法的坏字符与好后缀数组以及Sunday算法构建的表都可以使用CUDA配合原子操作来加速构建过程。

该算法的主要**是将一段文本加载进SIMD寄存器中，将这些字符同时与模式串的某个字符进行比较，最后通过位运算来获取匹配结果。 容易看出，我们匹配的最大次数与模式串长度相等，每次匹配进行相应的右移，只有每次匹配都为1的位置才是匹配成功的位置。这本质上就是并行化的暴力比较。 由于SSE寄存器大小限制，最大模式串长度为16，显然越接近16并行度越差，例如当模式串长度等于16时每次只能检测一个位置是否匹配。 EPSM$\alpha$在模式串长度小于8时时间复杂度可以达到 $O(n)$，最差时间复杂度为 $O(n \times m)$。

由于该算法是对暴力算法并行化的尝试，故采用与暴力算法相同的方法进行CUDA加速。同时由于CUDA并行不再受SSE寄存器大小的限制，故对模式串长度不做限制。

由于SSE寄存器最多处理16个字符，我们将文本按照16这一大小分块，从0开始编号。若模式串长度大于16*2即32，则模式串所匹配的位置一定可以完整的占据其中的某一块。 对于长度为m(m$\ge$32)的模式串来说，他最多可以填满n= $\lfloor \frac{m}{16} \rfloor$ 块，可以证明它所填满的块中，有且仅有一个块的编号为n-1的倍数。 因此我们检查文本时，我们首先对模式串进行处理，对每个位置极其之后的16个字符进行编码，编码相同的存入相应的链表中，这相当于是构建哈希表。构建方法是将这16个字符的某个比特位上的0或1取出并组合成一个16位的数作为哈希编码，我们会事先对模式串各个字符每一位上的0、1比例进行统计，并选取比例最接近1的那一位。 接着我们检查文本中编号为n-1的倍数的块，将该块中的16个字符采用上述方式进行编码，并在链表中查找该编码是否在模式串中出现，若出现则执行逐字符比较过程。显然随着模式串长度的增长这种方法的效率会提高。 该算法平均时间复杂度为 $O(\frac{n \times m}{65536})$，最坏时间复杂度为 $O(n \times m)$。

CUDA加速不再受SSE寄存器大小的限制，对于长度 $\lt$ 32的模式串来说编码长度为模式串长度的 $\frac{1}{2}$，这样就可以保证模式串的匹配一定占满一个块。令文本块长度为p。 对于最佳比特位与链表的构建我们同样使用CUDA加速。由于对于16位编码来说，哈希链表初始值即为65536，这大于block中48KB的空间，故哈希表会存储在全局内存中。 匹配加速时为每个文本块分配p个线程，每个线程对对应的字符进行移位操作，最后由0号线程执行位运算并查询链表。若分配连续线程，由于warp大小为32，warp上最终只有2个线程在运行，故采用交错分块的**，将组内编号为0的线程尽量集中在一起来提高效率。

我们使用两种文本作为算法性能测试基准：英文钦定版《圣经》（4.17MB），大肠杆菌基因组序列（4.33MB），选取2,4,8,16,32,64,128,256,512,1024十种模式串序列长度，每种算法在每种模式串长度下运行10000次求平均运行时间。

六张实验图像存储在experiment data文件夹中。

通过分析数据与图像，可以看出6种算法经过CUDA加速后都可以取得良好的性能，其中暴力算法经过优化成为一种高效且稳定的算法，BM、Sunday、EPSM$\alpha$、SSEF算法都可以保持串行方法中的优异性能，KMP算法在模式串长度增长后由于本身串行匹配性能较差从而并行性能减弱。