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.
展开▼
机译：本文的主要贡献是提出了针对上下文无关文法的CKY解析的批量计算的高效GPU实现，它确定了上下文无关文法是否派生大量输入字符串中的每一个。批量计算是针对多个输入依次或同时执行相同的算法。 CKY解析将确定上下文无关语法是否派生给定字符串。我们显示，可以使用按位并行批量计算（BPBC）技术在GPU中高效地实现CKY解析的批量计算。我们还展示了规则最小化技术和动态调度方法，用于进一步加速GPU上的CKY解析。使用NVIDIA TITAN X GPU进行的实验结果表明，对于长度为32的字符串，按位并行CKY解析的实现每个字符串需要395μs的时间，并针对512个非终端符号使用131072生成规则。
展开▼
