An optimized Parallel Failure-less Aho-Corasick algorithm for DNA sequence matching

Autor:	Thambawita, Vajira, Ragel, Roshan G., Elkaduwe, Dhammike
Rok vydání:	2018
Předmět:	Computer Science - Distributed Parallel and Cluster Computing Computer Science - Data Structures and Algorithms Computer Science - Performance
Druh dokumentu:	Working Paper
DOI:	10.1109/ICIAFS.2016.7946533
Popis:	The Aho-Corasick algorithm is multiple patterns searching algorithm running sequentially in various applications like network intrusion detection and bioinformatics for finding several input strings within a given large input string. The parallel version of the Aho-Corasick algorithm is called as Parallel Failure-less Aho-Corasick algorithm because it doesn't need failure links like in the original Aho-Corasick algorithm. In this research, we implemented an application specific parallel failureless Aho-Corasick algorithm to the general purpose graphics processing unit by applying several cache optimization techniques for matching DNA sequences. Our parallel Aho-Corasick algorithm shows better performance than the available parallel Aho-Corasick algorithm library due to its simplicity and optimized cache memory usage of graphics processing units for matching DNA sequences. Comment: 6 pages, 3 figures, 4 tables, 5 graphs, 2016 IEEE International Conference on Information and Automation for Sustainability (ICIAfS)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1811.10498 Zobrazit plný text záznamu View this record from Arxiv