我有一个程序必须处理大量数据并根据某种模式将其分类。我会稍微谈谈。
该数据表示为一个矩阵，其中每一列是一个不同的元素，分为“子元素”。该程序采用这个“子元素”并遍历每个模式（模式由 DFA - Deterministic Finite Automaton * 表示）以查看元素属于哪个组（该元素不属于多个组） .
- 我以这种方式使用矩阵在将其移植到 GPU 时进行内存合并。
下图以可视化的方式解释了数据组织。
- 显然数据集远大于 4 个元素
CPU-CODE - 首先我用 CPU 代码编写了这个程序。它完全序列化。该程序从一个元素中获取每个子元素，并检查该元素是否属于一个组，检查第一个模式。如果没有，请查看第二个模式。等等。当第一个元素被分类时，检查第二个元素，然后是第三个元素，依此类推。 /CPU代码
你怎么看，如果并行化，这段代码会快得多。然后程序在 CUDA 中编码。
GPU-CODE - 为了在 GPU 中以低内存传输运行代码，所有数据和自动机在“分类代码”开始之前被传输到 GPU 内存。现在的区别是我可以启动很多线程和块，每个线程将采用一个元素并对其进行分类。下图解释了它是如何在 GPU 中完成的。
GPU 代码比 CPU 代码快得多。/GPU-代码
现在的问题：就像我说的那样，模式被检查进入自动机。自动机有一些状态，每个状态都有一些转换。转换的数量几乎不大于 6。由于内存限制，自动机在默认模式下不表示，只需查看表即可获得下一个状态（表编码）。
我的编码需要不止一次查看才能获得下一个状态。为了获得下一个状态，我采用子元素并检查第一个转换是否由它触发。如果没有，我检查第二次转换，依此类推。
如果还不够清楚，上面的 CPU 和 GPU 代码都在自动机状态中以串行方式运行。换句话说，它检查第一个转换以查看我们是否与下一个状态匹配。如果没有，请检查下一个转换，依此类推。
我想在每个州内并行化这个搜索。换句话说，我希望每次转换一个线程。就像我说的，一个状态中的转换数量几乎不大于 6。我知道似乎没有必要并行化它，因为转换数量很少，但是这部分代码（匹配）重复了几次。
我试图在每个状态中并行化这个搜索，但执行时间比串行代码大。我将在下面解释我是如何完成我的幼稚实现的：
在这个测试中，我使用了一个自动机，每个状态最多有 4 个转换（但它可以少于 4 个）。所以我在线程块的 Y 维中启动了 4 个线程（X 维线程获取元素，Y 维线程获取子元素）并在共享内存中创建一个数组，如果我有一个“过渡匹配”与否。该数组具有块的大小 (blockDim.x * blockDim.Y)，因为它是针对所有元素完成的。
问题是：有时我每个状态的转换少于 4 个，这意味着线程 3 例如可以检查不是我感兴趣的状态并且匹配错误的其他状态。这个问题迫使我进行“第一次匹配”搜索，并且我以串行方式进行此搜索，这与我之前所做的相同，但现在我有一个与创建线程和数组相关的开销（我设置了数组数组的元素为 0，开销更大）。因此，我什么也没做。
只是为了让事情清楚，这张图片显示了我试图做的事情。
我之前问过如何在 stackoverflow 中进行首次匹配搜索，但我的问题是缺少一些关于我的代码和问题的重要细节，我在这里解释。
所以我的问题是，我能否有效地在每个状态中并行化此搜索（即使转换次数很少），还是不值得，我应该使用我的序列化 GPU 代码？
如果您认为我可以并行化，我应该使用我的最后一个代码来更好地实现“首次匹配”搜索，还是应该使用完全不同的方法？