IEICE Trans - An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique

An Efficient GPU Implementation of CKY Parsing Using the Bitwise Parallel Bulk Computation Technique

Toru FUJITA  Koji NAKANO  Yasuaki ITO  Daisuke TAKAFUJI

Publication
IEICE TRANSACTIONS on Information and Systems   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
Keyword:
parallel algorithms,  bulk computation,  bitwise operations,  context-free grammar,

Full Text: PDF(569.3KB)>>

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.