Parallel CYK Membership Test on GPUs

Abstract : Nowadays general-purpose computing on graphics processing units (GPGPUs) performs computations what were formerly handled by the CPU using hundreds of cores on GPUs. It often improves the performance of sequential computation when the running program is well-structured and formulated for massive threading. The CYK algorithm is a well-known algorithm for the context-free language membership test and has been used in many applications including grammar inferences, compilers and natural language processing. We revisit the CYK algorithm and its structural properties suitable for parallelization. Based on the discovered properties, we then parallelize the algorithm using different combinations of memory types and data allocation schemes using a GPU. We evaluate the algorithm based on real-world data and herein demonstrate the performance improvement compared with CPU-based computations.
Type de document :
Communication dans un congrès
Ching-Hsien Hsu; Xuanhua Shi; Valentina Salapura. 11th IFIP International Conference on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. Springer, Lecture Notes in Computer Science, LNCS-8707, pp.157-168, 2014, Network and Parallel Computing. 〈10.1007/978-3-662-44917-2_14〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01403076
Contributeur : Hal Ifip <>
Soumis le : vendredi 25 novembre 2016 - 14:28:32
Dernière modification le : vendredi 1 décembre 2017 - 01:10:04
Document(s) archivé(s) le : lundi 20 mars 2017 - 16:34:00

Fichier

978-3-662-44917-2_14_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Kyoung-Hwan Kim, Sang-Min Choi, Hyein Lee, Ka Man, Yo-Sub Han. Parallel CYK Membership Test on GPUs. Ching-Hsien Hsu; Xuanhua Shi; Valentina Salapura. 11th IFIP International Conference on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. Springer, Lecture Notes in Computer Science, LNCS-8707, pp.157-168, 2014, Network and Parallel Computing. 〈10.1007/978-3-662-44917-2_14〉. 〈hal-01403076〉

Partager

Métriques

Consultations de la notice

48

Téléchargements de fichiers

67