Parallel Construction for the Graph Model of the Longest Common Non-superstring using CUDA
Hyun-Chul Yoon, Jeong Seop Sim · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2012
Given a set of strings F over a constant size alphabet, consider a string x such that x does not include any string in F as a substring. We call x a common non-superstring (CNSS for short) of F. Among the CNSSs, the longest one with finite length is called the longest common non-superstring (LCNSS for short) of F. The LCNSS problem can be solved by two graph-based models: the prefix-based model and the suffix-based model. The LCNSS problem can be applicable to intrusion detection systems and DNA analysis. Meanwhile, with the advance of the multi-core processors, parallel algorithms are being studied vigorously. Sequential algorithms perform only one operation in a single step, but parallel algorithms perform multiple operations in a single step to reduce the time to solve problems. Recently, especially GPU-based solutions are being studied actively due to the high computational power of GPUs. In this paper, we present some results for the LCNSS problem. We implemented the prefix-based graph modeling algorithm for the LCNSS problem using nVidia CUDA (the Compute Unified Device Architecture). We give some experimental results to show the effectiveness of our implementation.