IEICE TRANSACTIONS on Information
An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique
Summary :
The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.12 pp.2857-2865
- Publication Date
- 2017/12/01
- Publicized
- 2017/08/04
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2017PAP0018
- Type of Manuscript
- Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
- Category
- GPU computing
Authors
Toru FUJITA
Hiroshima University
Koji NAKANO
Hiroshima University
Yasuaki ITO
Hiroshima University
Daisuke TAKAFUJI
Hiroshima University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Toru FUJITA, Koji NAKANO, Yasuaki ITO, Daisuke TAKAFUJI, "An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 12, pp. 2857-2865, December 2017, doi: 10.1587/transinf.2017PAP0018.
Abstract: The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2017PAP0018/_p
Copy
@ARTICLE{e100-d_12_2857,
author={Toru FUJITA, Koji NAKANO, Yasuaki ITO, Daisuke TAKAFUJI, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique},
year={2017},
volume={E100-D},
number={12},
pages={2857-2865},
abstract={The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.},
keywords={},
doi={10.1587/transinf.2017PAP0018},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique
T2 - IEICE TRANSACTIONS on Information
SP - 2857
EP - 2865
AU - Toru FUJITA
AU - Koji NAKANO
AU - Yasuaki ITO
AU - Daisuke TAKAFUJI
PY - 2017
DO - 10.1587/transinf.2017PAP0018
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2017
AB - The main contribution of this paper is to present an efficient GPU implementation of bulk computation of the CKY parsing for a context-free grammar, which determines if a context-free grammar derives each of a lot of input strings. The bulk computation is to execute the same algorithm for a lot of inputs in turn or at the same time. The CKY parsing is to determine if a context-free grammar derives a given string. We show that the bulk computation of the CKY parsing can be implemented in the GPU efficiently using Bitwise Parallel Bulk Computation (BPBC) technique. We also show the rule minimization technique and the dynamic scheduling method for further acceleration of the CKY parsing on the GPU. The experimental results using NVIDIA TITAN X GPU show that our implementation of the bitwise-parallel CKY parsing for strings of length 32 takes 395µs per string with 131072 production rules for 512 non-terminal symbols.
ER -
English
