CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

PFAC Implementation Issues and their Solutions on GPGPU’s using OpenCL

by Chirag Agarwal, Akhtar Rasool, Nilay Khare
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 72 - Number 7
Year of Publication: 2013
Authors: Chirag Agarwal, Akhtar Rasool, Nilay Khare
10.5120/12510-9161

Chirag Agarwal, Akhtar Rasool, Nilay Khare . PFAC Implementation Issues and their Solutions on GPGPU’s using OpenCL. International Journal of Computer Applications. 72, 7 ( June 2013), 52-58. DOI=10.5120/12510-9161

@article{ 10.5120/12510-9161,
author = { Chirag Agarwal, Akhtar Rasool, Nilay Khare },
title = { PFAC Implementation Issues and their Solutions on GPGPU’s using OpenCL },
journal = { International Journal of Computer Applications },
issue_date = { June 2013 },
volume = { 72 },
number = { 7 },
month = { June },
year = { 2013 },
issn = { 0975-8887 },
pages = { 52-58 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume72/number7/12510-9161/ },
doi = { 10.5120/12510-9161 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:37:47.204591+05:30
%A Chirag Agarwal
%A Akhtar Rasool
%A Nilay Khare
%T PFAC Implementation Issues and their Solutions on GPGPU’s using OpenCL
%J International Journal of Computer Applications
%@ 0975-8887
%V 72
%N 7
%P 52-58
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Aho-Corasick is a standard string matching algorithm. It can match multiple patterns simultaneously and affirmed deterministic performance under all circumstances. Aho-Corasick feed solutions to various real world applications like intrusion detection systems, text mining, search engine, multimedia and computational biology. In order to improve performance of these applications parallelization of Aho-Corasick is crucial. PFAC (Parallel Failure Less Aho-Corasick) algorithm provides high degree of parallelization in Aho-Corasick algorithm. PFAC implementation on GPGPU's architecture may consist various implementation issues. In this paper discrete implementation issues of PFAC on GPGPU's using OpenCL, their solutions and comparative analysis are discussed.

References
  1. A. V. Aho and M. J. Corasick, "Efficient String Matching: An aid Bibliographic search". In Communication of the ACM Vol. 18, issues 6, pp. -333-340, 1975.
  2. Tumeo, O. Villa and D. G. Chavarria-Miranda," Aho-Corasick String Matching on Shared and Distributed-Memory Parallel Architectures", Vol. 23, Issue 3, pp. 436-443, march 2012.
  3. Cheng-Hung Lin and Shih-Chieh-Chang," Efficient pattern matching algorithm for memory architecture",Vol. 19, issue 1, pp. 33-41, Jaunary 2011.
  4. Chengguo Chang and Hui Wang," Comparison of Two-Dimensional String Matching Algorithms"In the proc. International Conference on Computer Science and Electronics Engineering (ICCSEE), Vol. 3, pp. 608-611,march 2012.
  5. S. Antonatos, et al. , "Generating realistic workloads for network intrusion detection systems," Proc. 4th Int'l Workshop on Software and Performance, pp. 207-215, 2004.
  6. Ziv Bar-Yossef and Haifa," Efficient Search Engine Measurements", ACM Transactions on the Web (TWEB), Vol. 5, issue 4, October 2011.
  7. Fang Xiangyan, Xiong Tinggang, Ding Yidong and Yuan Youguang," The research and improving for multi-pattern string matching algorithm",In the proc. IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS), Vol. 1, pp. 266-270,Oct. 2010.
  8. D. Lee, Yannakakis and Mihalis," Testing finite-state machines: state identification and verification", IEEE Transactions on, Vol. 43, issue 3, pp. 306-320, Mar 1994.
  9. Raphaël Clifford, Markus Jalsenius, Ely Porat and Benjamin Sach," Pattern matching in multiple stream",in the proc. 23rd Annual conference on Combinatorial Pattern Matching, pp. 97-109,2012.
  10. R. Takahashi, U. Inoue, "Parallel Text Matching Using GPGPU", in the proc. 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel & Distributed Computing (SNPD), pp. 242-246, Aug. 2012.
  11. C. Lin, et al. , "Accelerating String Matching Using Multi-Threaded Algorithm on GPU," Proc. IEEE Global Telecommunications Conf. ,pp. 1-5, 2010.
  12. J. D. Owens, et al. , "A Survey of General-Purpose Computation on Graphics Hardware," Computer Graphics forum, Vol. 26, No. 1, pp. 80-113, 2007.
  13. C. Lin, C. Liu, L. Chien, and S. Chang," Accelerating Pattern Matching Using a Novel Parallel Algorithm on GPUs", IEEE Transactions on computers, vol. pp, issue 1.
  14. Zha Xinyan and S. Sahni," Multipattern string matching on a GPU", In the proc. IEEE conference on Computers and Communications (ISCC), pp. 277-282, July 2011.
  15. Tran Nhat-Phuong, Lee Myungho, Hong Sugwon and Minho Shin," Memory Efficient Parallelization for Aho-Corasick Algorithm on a GPU", IEEE 14th International Conference on High Performance Computing and Communication, pp. 432-438, June 2012.
  16. Jungwon Kim, Honggyu Kim, Joo Hwan Lee and Jaejin Lee," Achieving a single compute device image in OpenCL for multiple GPUs", Proceedings of the 16th ACM symposium on Principles and practice of parallel programming, pp. 277-288,2011.
  17. Hyeran Jeon, Xia Yinglong and V. K. Prasanna," Parallel Exact Inference on a CPU-GPGPU Heterogenous System", In the proc. 39th International Conference on parallel Processing (ICPP), pp. 61-70,Sept. 2010.
  18. Liang Hu, Che Xilong and Xie Zhenzhen," GPGPU cloud: A paradigm for general purpose computing", Tsinghua Science and Technology, Vol. 18, issue 1, pp. 22-23, Feb. 2013.
  19. web resource-www. gpgpu. org
  20. Xinyan Zha and Sartaj Sahni," GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU", IEEE Transactions on Computers,Volume 62, Issue 6, pp. 1156-1169,2013.
  21. M. Potel," A decade of applications Computer graphics]", Computer Graphics and Applications IEEE, Vol 24, Issue 6, pp. 14-19,Dec. 2004.
  22. http://www. ece. ncsu. edu/asic/ p183-dharmapurikar. pdf
  23. http://www. ieee-icnp. org/2006/papers/s5a4. pdf.
  24. Cheng-Hung Lin, Sheng-Yu Tsai, Chen-Hsiung Liu, Shih-Chieh Chang and Shyu, J. -M. ," Accelerating String Matching Using Multi-Threaded Algorithm on GPU",In the proc. Of IEEE conference on Global Telecommunications Conference (GLOBECOM 2010), pp. 1-5, Dec. 2010.
Index Terms

Computer Science
Information Sciences

Keywords

GPGPU AC Techniques PFAC Techniques Parallel AC

Powered by PhDFocusTM