Sequential pattern mining with the Micron automata processor
Sequential pattern mining with the Micron automata processor
复制标题
使用 Micron 自动机处理器进行顺序模式挖掘
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
K. Skadron
中科院分区：
文献类型：
--
作者：
Ke Wang;Elaheh Sadredini;K. Skadron
序列模式挖掘（SPM）是一种广泛应用的数据挖掘技术，用于发现大型数据库中事件的共同序列。与简单的集合挖掘问题和字符串挖掘问题相比，序列模式挖掘的分层结构（由于需要考虑每个项集中的频繁子集以及项集之间的顺序）和由此产生的巨大置换空间使得 SPM 在传统处理器架构上的成本极高。我们利用 Micron 的自动机处理器 (AP)（一种非确定性有限自动机 (NFA) 的硬件实现）提出了 SPM 的硬件加速解决方案。用于 SPM 搜索的广义序列模式 (GSP) 算法具有大规模并行性，因此非常适合 AP 加速。我们通过 AP 的快速可重构性实现了 GSP 的多通道剪枝策略。通过将顺序模式扁平化为简单字符串，我们提出了一种广义自动机结构，以缩短编译时间并最大限度地减少重新配置的开销。与优化的多核 CPU 和 GPU GSP 实现相比，AP 加速的 GSP 在六个实际数据集上分别实现了高达 90 倍和 29 倍的加速。建议的 CPU-AP 解决方案在多核 CPU 上的性能也优于最先进的 PrefixSpan 和 SPADE 算法，速度分别提高了 452 倍和 49 倍。随着数据集的增大，AP 的优势还将进一步扩大。
Sequential pattern mining (SPM) is a widely used data mining technique for discovering common sequences of events in large databases. When compared with the simple set mining problem and string mining problem, the hierarchical structure of sequential pattern mining (due to the need to consider frequent subsets within each itemset, as well as order among itemsets) and the resulting large permutation space makes SPM extremely expensive on conventional processor architectures. We propose a hardware-accelerated solution of the SPM using Micron's Automata Processor (AP), a hardware implementation of non-deterministic finite automata (NFAs). The Generalized Sequential Pattern (GSP) algorithm for SPM searching exposes massive parallelism, and is therefore well-suited for AP acceleration. We implement the multi-pass pruning strategy of the GSP via the AP's fast reconfigurability. A generalized automaton structure is proposed by flattening sequential patterns to simple strings to reduce compilation time and to minimize overhead of reconfiguration. Up to 90X and 29X speedups are achieved by the AP-accelerated GSP on six real-world datasets, when compared with the optimized multicore CPU and GPU GSP implementations, respectively. The proposed CPU-AP solution also outperforms the state-of-the-art PrefixSpan and SPADE algorithms on multicore CPU by up to 452X and 49X speedups. The AP advantage grows further with larger datasets.